什么是哈希码计算的合理素数？

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();则对每个附加属性重复.对于int.可以省略.hashCode().)

这似乎很好,但选择31为素数.它可能来自Java String的hashCode实现,它被用于性能原因,这些原因在引入硬件乘法器之后很久就消失了.对于i和j的小值,这里有许多哈希码冲突:例如(0,0)和(-1,31)具有相同的值.我认为这是一个Bad Thing(TM),因为经常出现小值.对于String.hashCode,您还会发现许多具有相同哈希码的短字符串,例如"Ca"和"DB".如果选择大素数,如果选择素数,此问题就会消失.

所以我的问题是:选择什么是好的素数？你用什么标准来找到它？

这是一个普遍的问题 - 所以我不想给i和j一个范围.但我认为在大多数应用中,相对较小的值比较大的值更常出现.(如果你有大的值,素数的选择可能不重要.)它可能没有多大区别,但更好的选择是一种简单明了的方法来改善这一点 - 那么为什么不这样做呢？Commons lang HashCodeBuilder也提出了奇怪的小值.

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

1> Hans-Peter S..：

---

我推荐使用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,然后取最小值尽可能大的素数.

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更有意义,除非你有充分的理由不这样做.

---

8字节哈希码？至少在Java中这是4个字节.无论如何:你可以继续使用eclipse hashCode生成中使用的方案:result = prime*result + i; result = prime*result + j; 等等.对于这个92821可能是一个很好的选择作为素数 - 至少比日食默认31更好.

2> Pascal Cuoq..：

---

实际上,如果你把一个如此大的素数接近INT_MAX,你就会因为模运算而遇到同样的问题.如果你希望主要散列长度为2的字符串,也许最接近平方根的素数INT_MAX是最好的,如果你散列的字符串更长,那么无关紧要,碰撞也是不可避免的......

3> Romain..：

---

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

最后,散列的最佳方法取决于您所比较的内容.对于int对(如示例中所示),使用基本的按位运算符就足够了(使用&或^).

---

当然它并不重要,但改变素数是改善事物的一种明显而简单的方法.那么为什么不这样做呢？