对于哈希码计算来说，什么是合理的素数？

StackOverflow https://stackoverflow.com/questions/1835976

  •  11-09-2019
  •  | 
  •  

题

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 下，结果非常相似。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top