理解循环多项式哈希碰撞

Question

理解循环多项式哈希碰撞

8

我有一个代码，使用循环多项式滚动哈希（Buzhash）计算源代码的n-gram哈希值。如果我使用小的哈希值（7-8位），那么会出现一些碰撞，即不同的n-gram映射到相同的哈希值。如果我将哈希值中的位数增加到31，那么就没有碰撞了——所有的n-gram都映射到不同的哈希值。

我想知道为什么会这样？碰撞是否取决于文本中n-gram的数量、一个n-gram可以具有的不同字符的数量或者是n-gram的大小？

当使用滚动哈希对n-gram进行哈希时，如何选择哈希值的位数？

- csprajeeth

7

冒着暴露自己的无知风险，我想问一下... 不同的哈希值越小，发生碰撞的可能性不是就越大吗？（其他条件相同的情况下，也就是说，使用相同的算法。） - harpo

2个回答

1

如果您有8位哈希值，总可能的值的数量为256 - 这意味着如果您哈希257个不同的n-gram，则肯定会发生至少一次冲突（...即使使用小于257个n-gram，很可能会发生更多的冲突） - 无论哈希算法或被哈希的数据如何。

如果您使用32位，则总可能的值的数量约为40亿 - 因此发生冲突的可能性要小得多。

'如何选择比特数'：我想这取决于哈希的用途。如果它用于将n-gram存储在某种哈希数据结构（字典）中，则应与数据结构的可能“桶”数相关联 - 例如，如果字典具有少于256个桶，则8位哈希是可以接受的。

有关背景，请参见this。

- MiMo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- christopher · Accepted Answer

长度如何影响碰撞

这只是一个排列组合的问题。

如果我使用小的哈希值（7-8位），那么就会有一些碰撞。

好的，让我们来分析一下。使用8位，对于任何给定的输入，可以生成2^8个可能的二进制序列。也就是说，可以生成256个可能的哈希值，这意味着理论上每256个生成的消息摘要值都保证会发生碰撞。这被称为生日问题。

如果我将哈希值中的位数增加到31位，那么就不会有碰撞-所有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^所有可能字符代码），而只有有限数量的可能输出（如上所示）。