问了解循环多项式哈希冲突
EN

Stack Overflow用户

提问于 2013-05-04 02:38:30

回答 1查看 1.2K关注 0票数 8

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

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

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

发布于 2013-05-07 02:16:40

如果你有8位的散列值，那么值的总可能数量是256 -这意味着如果你散列257个不同的n-gram，肯定会有至少一个冲突(...and很可能你会得到更多的冲突，即使少于257个n-gram)-这将发生，无论散列算法或被散列的数据。

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

“如何选择位数”：我想这取决于散列的使用。如果它被用来在某种散列数据结构(字典)中存储n-gram，那么它应该与数据结构的“桶”的可能数量相关-例如，如果字典具有少于256个桶，则8位散列是可以的。

有关背景信息，请参阅this

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/16365540

复制

相似问题

问了解循环多项式哈希冲突EN