hash - 理解循环多项式哈希冲突

Question

我有一个代码，它使用循环多项式滚动散列(Buzhash)来计算源代码的 n-gram 的散列值。如果我使用小的散列值(7-8 位)，那么会有一些冲突，即不同的 n-gram 映射到相同的散列值。如果我将散列值中的位增加到 31，则有 0 次冲突 - 所有 ngram 都映射到不同的散列值。

我想知道为什么会这样？冲突是否取决于文本中 n-gram 的数量或 n-gram 可以具有的不同字符的数量，还是 n-gram 的大小？

在对 n-gram 进行散列(使用滚动散列)时，如何选择散列值的位数？

Answer 1

长度如何影响碰撞

这只是一个排列问题。

If i use small hash values (7-8 bits) then there are some collisions

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

If i increase the bits in the hash value to say 31, then there are 0 collisions - all ngrams map to different hash values.

好吧，让我们应用相同的逻辑。使用 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^所有可能的字符代码)和有限数量的可能输出(如上所示)。