java - 如何减少哈希冲突？

Question

我编写的代码从文件中读取一些单词及其含义，并将它们映射到一个数组(制作哈希表)。它使用多项式哈希码和压缩方法。

我的目标是尽可能减少碰撞，但我不知道该怎么做。

public int hashcode(Entry my){ 
    Object key=my.getKey(); 
    int sum=0 ,z=33; 
    char[] chars = new char[key.toString().length()]; 
    chars=key.toString().toCharArray(); 
    for(int i=0; i < chars.length; i++){ 
         sum += (chars[i])*Math.pow(z,i);
    } 
    return sum;
}  

这是我的压缩方法(对于大小为 100 的数组):

public int compress(int hashcode){ 
    return hashcode%100; 
}

我应该改变我的压缩方法还是有一些方法可以帮助我？

Answer 1

你似乎在寻找一个完美的散列函数，不幸的是，据我所知，这样的散列不存在:)
另一件需要指出的事情是，哈希函数的性能也因您想要获得的结果类型而异；我的意思是哈希函数在“存储”电话号码方面可能表现出色，但在存储联系人姓名方面效果不佳。

通过快速查看您的代码，我会说您的哈希函数过于复杂。
首先，我想指出您当前算法的一个问题:这一行 'sum+=(chars[i])*Math.pow(z,i);'对于长度超过 4-5 个字符的单词，将返回超出整数范围的值(只是猜测)。你可能会说没关系，因为它会溢出等等，但事实是它不会，因为 sum+= 语法实际上隐藏了一个类型转换(尝试将其写为 sum=sum+)，在这种情况下，总和将具有Integer.MAX_VALUE 的值。这可能就是您的算法现在很慢的原因。

如果我是你，为了字典的目的(这似乎是你想要做的)并假设 Entry#getKey() 是字符串类型，我可能会选择:

public int hashcode(Entry my) {
    return my.getKey().hashCode();
}

如果您仍想提出自己的哈希函数，为什么不采用更简单的方法，例如:[字长 + 前 X 个字母的字符代码 + 最后一个字母的字符代码] 在其中调整 X，以便结果将适合一个整数。只是一个想法:)