8

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

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

在散列 n-gram（使用滚动散列）时如何选择散列值的位数？

4

2 回答 2

7

长度如何影响碰撞

这只是一个排列的问题。

如果我使用小的哈希值（7-8 位），那么会有一些冲突

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

如果我将哈希值中的位增加到 31，那么就有 0 次冲突 - 所有 ngram 都映射到不同的哈希值。

好吧，让我们应用相同的逻辑。有了 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.

当Xequals时256，您有1/256可能第一次发生碰撞。然后2/256，当生成不同的值时，您就有可能发生碰撞。直到最终，您已经生成了 255 个不同的值，并且您有255/256可能发生碰撞。下一次，显然它变成了一个256/256机会，或者1，这是一个概率确定性。显然它通常不会达到这一点。碰撞发生的次数可能比每个256周期都要多得多。事实上，生日悖论告诉我们，2^N/2在生成消息摘要值之后，我们可以开始期待冲突。因此，按照我们的示例，那是在我们创建16唯一哈希之后。然而，我们确实知道，它至少必须发生, 每个256周期。哪个不好！

这意味着，在数学层面上，冲突的可能性与可能的输出数量成反比，这就是为什么我们需要将消息摘要的大小增加到合理长度的原因。

关于散列算法的说明

碰撞是完全无法避免的。这是因为，有大量可能的输入（2^所有可能的字符代码）和有限数量的可能输出（如上所示）。

于 2013-05-06T18:16:29.263 回答
1

如果您有 8 位的哈希值，则可能的值总数为 256 - 这意味着如果您对 257 个不同的 n-gram 进行哈希处理，肯定会至少发生一次冲突（......而且很可能您会遇到更多的冲突，即使少于 257 个 n-gram） - 无论散列算法或被散列的数据如何，都会发生这种情况。

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

'如何选择位数'：我想取决于哈希的使用。如果它用于将 n-gram 存储在某种散列数据结构（字典）中，那么它应该与数据结构的“桶”的可能数量相关 - 例如，如果字典的桶少于 256 个8位哈希是可以的。

看这个了解一些背景

于 2013-05-06T18:16:39.880 回答