c# - 对大 N 应用 Rabin-Karp Hash

Question

我指的是 Rabin Karp Wikipedia article on Hash use.

在示例中，字符串 "hi" 使用质数 101 作为基数进行哈希处理。

hash("hi")= ASCII("h")*101^1+ASCII("i")*101^0 = 10609 

这样的算法是否可以在 long 的最大值为 9,223,372,036,854,775,807 的 Java 或 C# 中实际使用？天真地，在我看来，哈希值似乎呈指数增长，并且具有足够大的 N(字符串长度)将导致 long 类型的溢出。例如，假设我的哈希字符串输入中有 65 个字符？

这是正确的，还是有永远不需要溢出的实现方法(我可以想象可能有一些懒惰的评估，它只将 ascii 和单位位置存储在素数基中)？

Answer 1

hash("hi")= ASCII("h")*101^1+ASCII("i")*101^0 = 10609

这只说对了一半。实际上，如果您实际计算值 s_0 * p^0 + s_1 * p^1 + ... + s_n * p^n，结果将是一个数字，其表示形式约为只要字符串本身，所以你没有得到任何东西。所以你实际上做的是计算

(s_0 * p^0 + s_1 * p^1 + ... + s_n * p^n) mod M

其中 M 相当小。因此，您的哈希值将始终小于 M。

因此，您在实践中所做的是选择 M = 2^64 并利用无符号整数溢出在大多数编程语言中都有明确定义的事实。实际上，Java、C++、C#中的64位整数的乘法和加法等价于乘法和加法取模2^64。

使用 2^64 作为模数不一定是明智的选择。事实上，您可以轻松构造一个包含大量冲突的字符串，从而引发 Rabin-Karp 的最坏情况行为，即 Ω(n * m) 匹配而不是 O(n + m )。

最好使用大质数作为模数，并获得更好的抗碰撞性。通常不这样做的原因是性能:我们需要明确地对每个加法和乘法使用模块化归约(添加 % M)。更糟糕的是，我们甚至不能再使用内置乘法，因为如果 M > 2^32 它可能会溢出。所以我们需要一个自定义的 MultiplyMod 函数，它必然比机器级乘法慢很多。

Is this correct, or are there methods of implementation which will never need to overflow (I can imagine possibly some lazy evaluation which merely stores the ascii and unit place in the prime base)?

正如我已经提到的，如果您不使用模数进行缩减，您的哈希值将增长到与字符串本身一样大，从而使它一开始就无法使用哈希函数。所以是的，如果我们不手动减少，使用受控溢出模 2^64 是正确的，甚至是必要的。