68

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。它可能取自Java String 的 hashCode 实现，它是出于性能原因而使用的，在引入硬件乘法器之后早已不复存在。在这里，对于 i 和 j 的小值，您有许多哈希码冲突：例如 (0,0) 和 (-1,31) 具有相同的值。我认为这是一件坏事(TM)，因为小值经常出现。对于 String.hashCode，您还会发现许多具有相同哈希码的短字符串，例如“Ca”和“DB”。如果你取一个大素数，如果你选择素数，这个问题就会消失。

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

这是一个一般性问题——所以我不想给出 i 和 j 的范围。但我想在大多数应用程序中，相对较小的值比较大的值更频繁地出现。（如果你有很大的值，那么选择素数可能并不重要。）它可能没有太大的区别，但更好的选择是改进这一点的简单而明显的方法 - 那么为什么不这样做呢？Commons lang HashCodeBuilder还提出了奇怪的小值。

（澄清：这不是Why does Java's hashCode() in String use 31 as a multiplier?的重复？因为我的问题不关心JDK中31的历史，而是关于新代码中什么是更好的价值使用相同的基本模板。那里没有一个答案试图回答这个问题。）

4

6 回答 6

80

我建议使用92821。这就是为什么。

要对此给出有意义的答案，您必须了解i和的可能值j。一般来说，我唯一能想到的是，在许多情况下，小值会比大值更常见。（15 作为一个值出现在您的程序中的几率比 438281923 好得多。）因此，通过选择适当的素数来使最小的哈希码冲突尽可能大似乎是个好主意。对于 31 这相当糟糕 - 已经 fori=-1和j=31你有相同的哈希值 for i=0and 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 更有意义，除非你有充分的理由不这样做。

于 2010-05-12T07:26:44.150 回答
6

实际上，如果你取一个大到接近 的素数，INT_MAX由于模运算，你会遇到同样的问题。如果您希望主要散列长度为 2 的字符串，那么可能最好使用接近平方根的素数INT_MAX，如果您散列的字符串更长，则无关紧要，无论如何冲突都是不可避免的......

于 2009-12-02T21:54:16.047 回答
5

碰撞可能不是什么大问题......哈希的主要目标是避免使用等于进行 1:1 比较。如果您有一个实现，其中对于具有冲突哈希的对象，equals“通常”非常便宜，那么这不是问题（根本）。

最后，什么是最好的散列方式取决于你在比较什么。对于 int 对（如您的示例），使用基本的按位运算符就足够了（如使用 & 或 ^）。

于 2009-12-02T23:20:52.810 回答
4

您需要定义 i 和 j 的范围。您可以对两者都使用质数。

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}
于 2009-12-02T21:52:51.627 回答
4

我会选择 7243。足够大以避免与小数字发生冲突。不会很快溢出到小数字。

于 2009-12-02T22:11:23.703 回答
1

我只想指出哈希码与素数无关。在JDK实现中

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

我发现如果将31替换为27，结果非常相似。

于 2016-10-15T05:25:26.180 回答