哈希码计算的明智之处是什么?

Eclipse 3.5有一个很好的function来生成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();对每个附加属性重复。对于ints,可以省略.hashCode()。

这看起来很好,但对于素数的select31。 它可能是从Java String的hashCode实现中获得的 ,这是由于硬件乘法器引入后长期以来的性能原因。 在这里,对于i和j的较小值,有很多哈希码碰撞:例如(0,0)和(-1,31)具有相同的值。 我认为这是一个坏事(TM),因为小的值经常出现。 对于String.hashCode,你还会发现许多具有相同散列码的短string,例如“Ca”和“DB”。 如果你select一个较大的素数,那么如果你select了这个素数,这个问题就会消失。

所以我的问题是:什么是最好的select? 你有什么标准来find它?

这是一个普遍的问题 – 所以我不想给我和j的范围。 但是我认为在大多数应用中,相对较小的值比较大的值更经常出现。 (如果你有很大的价值,那么素数的select可能不重要)。它可能没有多大区别,但更好的select是一个简单而明显的方法来改善这一点 – 为什么不这样做呢? Commons lang HashCodeBuilder也build议奇怪的小值。

澄清 :这不是重复的为什么Java中的String的hashCode()使用31作为乘数?因为我的问题不关心JDK中的31的历史,而是关于新代码中更好的值使用相同的基本模板,没有任何答案试图回答这个问题。)

我build议使用92821 。 这是为什么。

为了给出一个有意义的答案,你必须知道一些关于ij的可能值。 我能想到的唯一的事情就是,在很多情况下,小的价值观比大的价值观更普遍。 (在程序中出现15的几率比438281923要好得多。)因此,通过select一个合适的素数来尽可能地使尽可能大的hashcode碰撞成为一个好主意。 对于31而言,这相当糟糕 – 已经对于i=-1j=31您拥有与i=0j=0相同的散列值。

由于这很有趣,我写了一个小程序,在这个意义上search整个int范围以获得最好的素数。 也就是说,对于每个素数,我searchMath.abs(i) + Math.abs(j)的最小值,对所有具有相同哈希码的i,j值作为0,0 ,然后取这个素数最小值越大越好。

Drumroll :在这个意义上最好的素数是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更有意义,除非你有充分的理由不这样做。

碰撞可能不是一个大问题…哈希的主要目标是避免使用等于1:1的比较。 如果你有一个实现,其中equals对于碰撞散列的对象来说“通常”是非常便宜的,那么这根本就不是问题。

最后,散列的最好方法是什么取决于你在比较什么。 在int对(如你的例子)的情况下,使用基本的按位运算符可能就足够了(如使用&或^)。

实际上,如果你的素数太大以至于接近INT_MAX ,则由于模算术,你INT_MAX遇到同样的问题。 如果你希望散列大部分长度为2的string,那么INT_MAX平方根附近的一个素数可能是最好的,如果你散列的string较长,那么它并不重要,碰撞也是不可避免的。

你需要为我和j定义你的范围。 你可以使用两个素数。

 public int hashCode() { http://primes.utm.edu/curios/ ;) return 97654321 * i ^ 12356789 * j; } 

我会select7243.大到足以避免与小数目的collission。 不会很快溢出到小数字。

我只想指出hashcode与prime没有任何关系。 在JDK实现中

 for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } 

我发现如果你用27代替31 ,结果是非常相似的。