如何减少哈希冲突？

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;
}  

这是我的compress方法(对于大小为100的数组)：

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

我是否应该改变我的压缩方法，或者有一些方法可以帮助我？

Answer 1

您似乎正在寻找的是一个完美的散列函数，不幸的是，据我所知，这样的散列并不存在:)

要指出的另一件事是，哈希函数的性能也因您想要实现的结果类型而有所不同；我的意思是，哈希函数在“存储”电话号码方面可能表现出色，但在存储联系人姓名方面却表现不佳。

快速浏览一下你的代码，我会说你的散列函数太复杂了。

首先，我想指出您当前算法的一个问题：'sum+=(charsi)*Math.pow(z，i);‘这一行将返回的值远远超出了长度超过4-5个字符的单词的整数范围(只是猜测)。您可能会说这没问题，因为它会溢出等等，但事实并非如此，因为sum+=语法实际上隐藏了一个类型转换(试着把它写成sum=sum+)，在这种情况下，sum的值将是Integer.MAX_VALUE。这可能就是你的算法现在很慢的原因。

如果我是您，出于字典的目的(这似乎就是您正在尝试做的事情)，并假设Entry#getKey()是String类型，我可能只会使用：

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

如果你仍然想要想出你自己的散列函数，为什么不用一些更简单的东西，比如:单词长度+前X个字母的字符代码+最后一个字母的字符代码，这样结果就可以放入一个int中。这只是一个想法:)