我指的是Rabin Karp Wikipedia article on Hash use.
在本例中,字符串"hi"
使用素数101
作为基数进行散列。
hash("hi")= ASCII("h")*101^1+ASCII("i")*101^0 = 10609
这样的算法能在Java或C语言中实际使用吗?天真地说,在我看来,散列值呈指数增长,如果n足够大(即字符串长度),将导致
9,223,372,036,854,775,807
类型溢出。例如,假设我的散列字符串输入中有65个字符?这是正确的吗,还是有一些实现方法永远不需要溢出(我可以想象可能有一些懒惰的计算,它仅仅将ascii和unit位存储在prime base中)?
最佳答案
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
并利用无符号整数溢出在大多数编程语言中定义良好这一事实事实上,爪哇、C++和C 64位整数的乘法和加法等价于乘法和加法模2^64
。使用
2^64
作为模量并不一定是明智的选择事实上,您可以很容易地构造一个带有大量冲突的字符串,从而引发rabin karp最坏的情况,即Ω(n * m)
匹配而不是O(n + m)
。最好使用大质数作为模量,获得更好的抗碰撞性能。通常不这样做的原因是性能:我们需要在每次加法和乘法中明确地使用模约化(add a
% M
)更糟糕的是,我们甚至不能再使用内置乘法了,因为如果M > 2^32
,它可能会溢出所以我们需要一个定制的MultiplyMod
函数,它肯定比机器级乘法慢得多。这是正确的吗,还是有一些实现方法永远不需要溢出(我可以想象可能有一些懒惰的计算,它仅仅将ascii和unit位存储在prime base中)?
如前所述,如果不使用模来减少,散列值将与字符串本身一样大,因此首先使用散列函数是无用的所以是的,如果我们不手动减少,使用控制溢出模
2^64
是正确的,甚至是必要的。