csp*_*eth 8 hash hash-collision n-gram
我有一个代码,使用循环多项式滚动哈希(Buzhash)来计算n-gram源代码的哈希值.如果我使用小哈希值(7-8位),则存在一些冲突,即不同的n-gram映射到相同的哈希值.如果我将哈希值中的位增加到31,则有0次冲突 - 所有ngrams都映射到不同的哈希值.
我想知道为什么会这样？碰撞是否取决于文本中的n-gram数量或n-gram可以具有的不同字符数量,还是n-gram的大小？
如何在散列n-gram时使用滚动哈希值选择哈希值的位数？
长度如何影响碰撞
这只是一个排列问题.
如果我使用小的哈希值(7-8位),那么就会发生一些冲突
好吧,让我们分析一下.对于8位,2^8可以为任何给定输入生成二进制序列.这是可以生成的256个可能的哈希值,这意味着理论上,256生成的每个消息摘要值都可以保证冲突.这被称为生日问题.
如果我将哈希值中的位增加到31,则有0次冲突 - 所有ngrams都映射到不同的哈希值.
好吧,让我们应用相同的逻辑.凭借31位精度,我们有2^31可能的组合.这是2147483648可能的组合.我们可以概括为:
Let N denote the amount of bits we use.
Amount of different hash values we can generate (X) = 2^N
Assuming repetition of values is allowed (which it is in this case!)
这是一个指数增长,这就是为什么8位,你发现很多碰撞和31位,你发现很少的碰撞.
这种影响如何碰撞？
好吧,使用非常少量的值,并且每个值映射到输入的机会相等,您可以:
Let A denote the number of different values already generated.
Chance of a collision is: A / X
Where X is the possible number of outputs the hashing algorithm can generate.
当X等于256,你有一个1/256碰撞的机会,第一次围绕.然后2/256,当生成不同的值时,您有可能发生冲突.直到最终,您已生成255个不同的值,并且您有255/256可能发生碰撞.下一次,显然它成为一个256/256机会,或者1,这是一个概率确定性.显然它通常不会达到这一点.碰撞可能比每个256循环发生的次数多得多.事实上,生日悖论告诉我们,2^N/2在生成消息摘要值之后,我们可以开始期待碰撞.所以按照我们的例子,在我们创建了16独特的哈希之后.但是,我们确实知道,至少每个256周期都必须发生这种情况.哪个不好!
在数学层面上,这意味着碰撞的可能性与可能的输出数量成反比,这就是为什么我们需要将消息摘要的大小增加到合理的长度.
关于散列算法的注释
碰撞是完全不可避免的.这是因为,存在极大数量的可能输入(2 ^所有可能的字符代码)和有限数量的可能输出(如上所示).