哈希函数冲突过多

Question

我正在尝试使用多项式累积方法(应该每 55k 个单词或其他东西给你 5 次碰撞(创建一个哈希函数，但是当我用 1,000 个单词运行它时，我得到了 ~190 次碰撞。我做错了什么吗？

public int hashCode(String str) {
double hash_value = 0; // used for float
for (int i = 0; i < str.length(); i++){
hash_value = 33*hash_value + str.charAt(i);
}
return (int) (hash_value % array_size);
}

Answer 1

通常，素数有利于哈希代码生成。我建议尝试 109 或 251。33 是 3 的倍数，这意味着您更有可能根据您的输入遇到问题。

此外，您应该使用 int 进行计算，并对结果调用 Math.abs。

Answer 2

要么你的数据集非常"不走运"，要么(更有可能(array_size太小(哈希函数参数通常在不考虑有限桶数组大小的情况下引用(。

Answer 3

您正在生成一个大数字，该数字对于输入中的不同单词是不同的。但是仍然有碰撞的机会，例如

"bA" = 98+(33x65)=2243
"AB" = 65+(33x66)=2243

如果你选择大于 57 的大数，碰撞的可能性就会减少。 109 或 251 将是一个不错的选择。