什么是hashCode计算的明智素数？

Question

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();则为每个其他属性重复此操作。对于ints，可以省略.hashCode（）。）

这似乎很好，但是对于首选的31。它可能取自JavaString的hashCode实现，出于性能原因而使用该特性，在引入硬件乘法器之后就已经不复存在了。在这里，对于i和j的较小值，您会有很多哈希码冲突：例如（0,0）和（-1,31）具有相同的值。我认为这是Bad
Thing（TM），因为经常会出现小的值。对于String.hashCode，您还会发现许多具有相同哈希码的短字符串，例如“ Ca”和“
DB”。如果您要大的质数，那么选择质数权会消除此问题。

所以我的问题是：选择什么是最佳素数？您应用什么标准找到它？

这是一个一般性问题-
因此，我不想为i和j给出范围。但是我想在大多数应用程序中，相对较小的值比较大的值更经常出现。（如果值较大，则选择质数可能并不重要。）这可能并没有多大区别，但是更好的选择是改善此问题的简便而显而易见的方法-
那么为什么不这样做呢？Commons langHashCodeBuilder也建议使用很小的值。

（ 澄清 ：这 _不是_为什么Java中String的hashCode（）使用31作为乘数)因为我的问题与JDK中31的历史无关，而是在新代码中什么更好的价值）使用相同的基本模板。那里的答案都无法尝试回答。）

Answer 1

我建议使用 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=-6815and j=70091，但我最喜欢的92821（最小碰撞-46272,46016）仍然几乎一样好作为最佳价值。

我确实承认，这些计算在实践中是否有意义尚有争议。但我确实认为，除非有充分的理由，否则将92821作为质数比31更有意义。