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

在代码中

Answer 1

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

Answer 2

准确地说，循环没有计算ℎ=-1，但ℎ=(−1) 模。这是一个重要的细节，因为这意味着无论 or 的值是多少，结果都不会超过 。

此外，您提供的代码块需要在前面加上才有h=1意义。

使用循环，我们可以避免较大的中间结果，这可能会跨越所使用的整数类型支持的范围。通常字符串字母 () 的大小设置为 256。现在如果要搜索的模式的长度 () 像 20，那么= 256 ²⁰ = 2 ¹⁶⁰，一个不适合典型 32 位或 64 位整数存储的数字。所以计算-1 就像那样有导致数字溢出的风险。

这就是使用循环的原因。在每次迭代中，都会应用模运算符，它具有正常值并消除了溢出的风险。在每次迭代中应用模运算符也是正确的。