散列函数冲突太多
散列函数冲突太多
提问于 2018-10-21 02:49:58
我试图使用多项式累加法创建一个散列函数(假设每55k个单词有5个冲突)，但当我运行它时，有1000个单词，我得到了大约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);
}回答 3
Stack Overflow用户
发布于 2018-10-21 03:07:34
通常，素数是用于生成散列代码的首选。我建议您试一下109或251。33是3的倍数，这意味着根据您的输入更有可能出现问题。
此外，您还应该使用int进行计算，并对结果调用Math.abs。
Stack Overflow用户
发布于 2018-10-21 02:56:54
要么你的数据集非常“不幸”，要么(更有可能的) array_size太小(通常引用散列函数参数而不考虑有限的桶数组大小)。
Stack Overflow用户
发布于 2018-10-21 07:31:38
您正在生成一个较大的数字，该数字对于输入中的不同单词是不同的。但是仍然存在碰撞的可能性，例如
"bA" = 98+(33x65)=2243
"AB" = 65+(33x66)=2243如果你选择一个大于57的大数字，那么碰撞的机会就会减少。109或251将是一个不错的选择。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52909017
复制相关文章
相似问题
腾讯云开发者
