java - Rabin-Karp 算法：为什么 h=(h*d)%q

Question

我在 Rabin-Karp 算法中了解以下内容

h=d^m-1 但我不明白我们为什么要写

for(i=0;i<M-1;i++)
    h=(h*d)%q

在代码中

标签： javastringalgorithmsearchrabin-karp

Answer 1

基本上，这些行正在为您的哈希映射初始化默认值，稍后您将对其进行更改，并且它也可以用作哈希函数，当您将插入值时，请阅读下面的段落，并投票并关注我的个人资料。当你试图理解 hashmaps 的概念时，每个人都会通过串联一些块来教你。后来，这些块被初始化了一些键值，但在您插入键值之前，这些块未初始化。所以可能有一些块没有被赋予任何关键值。它们将包含垃圾值，以及如何遍历它们，因为当您需要搜索某些内容时，您需要遍历，因此该函数正在为所有块初始化默认值。现在，如果您尝试在没有这些行的情况下运行您的代码，您的代码将只检查第一次。我所知 ，