2

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

我的目标是尽可能减少碰撞，但我不知道如何。

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

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

4

1 回答 1

2

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

快速浏览一下您的代码，我会说您的哈希函数过于复杂。
首先，我想指出您当前算法的一个问题：这一行 '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 以便结果适合诠释。只是一个想法:)

于 2013-01-26T13:13:43.583 回答