题
Eclipse 3.5 有一个非常好的功能来生成 Java hashCode() 函数。例如,它会生成(稍微缩短:)
class HashTest {
int i;
int j;
public int hashCode() {
final int prime = 31;
int result = prime + i;
result = prime * result + j;
return result;
}
}
(如果类中有更多属性, result = prime * result + attribute.hashCode();
对每个附加属性重复。对于整数,.hashCode() 可以省略。)
这看起来不错,但对于素数选择 31 来说。它可能取自 Java String的hashCode实现, ,它的使用是出于性能原因,而在引入硬件乘法器后,这些原因早已不复存在。这里,对于 i 和 j 的小值,存在许多哈希码冲突:例如 (0,0) 和 (-1,31) 具有相同的值。我认为这是一件坏事(TM),因为小值经常出现。对于 String.hashCode,您还会发现许多具有相同哈希码的短字符串,例如“Ca”和“DB”。如果你取一个大素数,如果你选择正确的素数,这个问题就会消失。
所以我的问题是:什么是好的素数选择?您采用什么标准来查找它?
这是一个一般性问题 - 所以我不想给出 i 和 j 的范围。但我认为在大多数应用中,相对较小的值比较大的值更频繁地出现。(如果你有很大的值,素数的选择可能并不重要。)这可能不会产生太大的影响,但更好的选择是改进这一点的简单而明显的方法 - 那么为什么不这样做呢?公共语言 哈希码生成器 还暗示了奇怪的小值。
(澄清: :这是 不是 的副本 为什么Java的String中的hashCode()使用31作为乘数? 因为我的问题不涉及 JDK 中 31 的历史,而是涉及使用相同基本模板的新代码中什么会具有更好的价值。那里的答案都没有试图回答这个问题。)
解决方案
我建议使用的 92821 即可。这里的原因。
要给出一个有意义的答案,这个你必须知道一些关于i
和j
的可能值。我一般可以想到的唯一的事情是,在许多情况下,较小的值会比大的值更常见。 (15出现在你的程序中值的几率比好多了,说,438281923.)所以这似乎是一个好主意,通过选择合适的黄金,使最小的哈希码碰撞尽可能的大。对于31这个很坏的 - 已经为i=-1
和j=31
你有相同的哈希值作为i=0
和j=0
由于这是有趣的,我写了一个小程序,搜索整个INT范围,在这个意义上最好的总理。也就是说,对于每一个主要我搜索了Math.abs(i) + Math.abs(j)
过具有相同的哈希码为i,j
0,0
的所有值的最小值,然后拿着黄金,其中该最小值为尽可能大。
击鼓声:在这个意义上的最好是素486187739(具有最小碰撞是i=-25486, j=67194
)。几乎一样好,更容易记住的是92821用最小的碰撞是i=-46272 and j=46016
。
如果你给“小”的另一种意义,并希望成为Math.sqrt(i*i+j*j)
的碰撞尽可能大的最小的,结果有一点不同:最好是1322837333与i=-6815 and j=70091
,但我最喜欢的92821(最小的碰撞-46272,46016
)是再次几乎为最佳值良好。
我承认,这是很值得商榷的,这些计算是否没什么意义的做法。但我认为,以92821作为首要更有道理比31,除非你有很好的理由不这样做。
其他提示
其实,如果你采取如此之大,接近INT_MAX
的黄金,你有因为模运算的同样的问题。如果您希望在哈希大多长度为2的字符串,也许INT_MAX
的平方根附近的主要将是最好的,如果你哈希字符串长也没关系这么多,冲突是不可避免的反正...
碰撞可能不是一个大问题...散列的主要目标是避免使用equals为1:1个的比较。 如果您拥有的是等于“一般”为万分发生了冲突hashs对象便宜的实现,那么这是不是一个问题(所有)。
在最后,是什么散列的最佳方式取决于你是什么样的比较。在一个int对的情况下(如在你的例子),采用基本位运算符可以是足够的(如使用&或^)。
您需要定义范围i和j。你可以使用一个素数两个。
public int hashCode() {
http://primes.utm.edu/curios/ ;)
return 97654321 * i ^ 12356789 * j;
}
我会选择7243大到足以避免与小数字冲突。不会溢出到小数目迅速。
我只是想指出的是,哈希码无关总理。 在JDK实现
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
我发现如果更换的 31 强>使用的 27 下,结果非常相似。