logo标签列表

什么是用于哈希码计算的合适质数？

javahashcodeprimes
70

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）具有相同的值。我认为这是一件坏事(TM)，因为小值经常出现。对于String.hashCode，您还会发现许多哈希码相同的短字符串，例如"Ca"和"DB"。如果选择一个大质数，则此问题将消失，如果正确选择质数，则问题将消失。

所以我的问题是：选择哪个好的质数？您如何应用标准来找到它？

这是一个通用问题 - 所以我不想给出i和j的范围。但我认为在大多数应用程序中，相对较小的值比大值更常见。（如果有大值，则质数的选择可能无关紧要。）这可能没有太大的区别，但更好的选择是改善此问题的简单明显方法 - 那么为什么不这样做呢？Commons lang的HashCodeBuilder也建议使用奇怪的小值。

（澄清：这不是为什么Java中的String使用31作为乘数的hashCode()是重复的？，因为我的问题与JDK中31的历史无关，而是关于在使用相同基本模板的新代码中应该选择更好的值。那里的答案都没有试图回答这个问题。）

4
31 仍然是一个好的选择，因为它不一定涉及加载一个常数。在 ARM 处理器上（至少是 99.9997% 的手机所使用的处理器），*31 可以在一条指令中完成。实际上，任何奇数，无论是否为质数，都足够好。 - Tom Hawtin - tackline
8
形如 p = (2^n-1) 的质数有助于优化 x * p = (p << n) - p ，这通常由编译器完成。引自 Joshua Bloch 的《Effective Java》第3章第9条。关于此问题的 Stack Overflow 帖子：https://dev59.com/gnVC5IYBdhLWcg3wbQfA#299748 - corsiKa
在JVM中，与整数<128相乘会有额外的提升。2^n-1、质数、较小的值会给出31。 - J-16 SDiZ
@Dr.Hans-PeterStörr 在i86上，有一个单字节立即操作数模式的区别。您可以获得更短的指令，在我多年前编写的基准测试中，速度略有提升。 - maaartinus
2
@MarkRotteveel 请注意，这与为什么Java中String的hashCode()使用31作为乘数？非常不同，因为这不是关于31的历史，而是关于在不使用其他库或完全不同的计算哈希方法的情况下，使用什么才是更好的选择。那里的任何答案都没有解决这个问题。 - Hans-Peter Störr
显示剩余2条评论
6个回答
87

我建议使用92821。以下是原因：

为了对此进行有意义的回答，您必须了解i和j的可能值。总的来说，我想到的唯一一件事是，在许多情况下，小值比大值更常见。（在您的程序中出现值15的机会比438281923好得多。）因此，选择适当的质数使最小的哈希码冲突尽可能大似乎是个好主意。对于31而言，这相当糟糕，因为即使i=-1和j=31，您得到的哈希值与i=0和j=0相同。

由于这很有趣，我编写了一个小程序，在整个int范围内搜索了最佳质数。也就是说，对于每个质数，我搜索了所有具有与0,0相同哈希码的i,j的值上Math.abs(i) + Math.abs(j)的最小值，然后选取了该最小值尽可能大的质数。

鼓掌：在这个意义下，最好的质数是486187739（最小碰撞是i=-25486，j=67194）。几乎同样好但易记得多的是最小碰撞为i=-46272，j=46016的92821。

如果您给“小”一个不同的含义，并希望使Math.sqrt(i*i+j*j)尽可能小以实现最大的碰撞，则结果会略有不同：最好的质数是1322837333，最小碰撞为i=-6815，j=70091，但是我最喜欢的92821（最小碰撞为-46272,46016）再次接近最佳值。

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

1
你正在寻找一个完美的哈希魔数，或者至少是几乎完美的。但我更感兴趣的是看到一种针对哈希大小的任意输入的解决方案（例如，在8字节哈希码中有4个2字节值），而不是这种简单换位的特殊情况。 - Jason
2
8字节的哈希码？至少在Java中，这是4字节。无论如何：你可以继续使用Eclipse hashCode生成中使用的方案：result = prime * result + i; result = prime * result + j;等等。对于此，92821可能是一个很好的质数选择-至少比Eclipse默认值31要好得多。 - Hans-Peter Störr
1
不仅使用一个小常数是错误的，重复使用它也是错误的，因为你会得到类似 newArrayList("a", "bc").hashCode() == newArrayList("ab", "c").hashCode() 的冲突（我的例子可能不起作用，但类似的情况确实存在）。 - maaartinus
@maaartinus，你说得对，确实有很多更好的哈希算法。我只是想指出一个简单但值得改进的常用算法。如果你想要真正好的性能，有一些库可以提供更好的选择，但这通常是过度设计了。 - Hans-Peter Störr
1
@ToolmakerSteve 我也怀疑10%是可行的。对于一个应用程序来说，这样做可能不值得努力。如果我们可以重新设计整个Java哈希，那么10%可能是可实现的（避免像hashCode为零的任何新Map.Entry与相等的键和值发生愚蠢的冲突等），而即使0.1%也可能是值得改进的。 - maaartinus
显示剩余5条评论
6

实际上，如果您选择一个接近INT_MAX的大质数，由于模算术的原因，您将遇到相同的问题。如果您预计主要哈希长度为2的字符串，则可能最好选择接近INT_MAX平方根的质数。如果您要哈希的字符串较长，则问题不太重要，碰撞是无法避免的...

没错，模数算术使问题变得困难而有趣。我想我会写一个小程序来寻找一个好的解决方案。 :-) - Hans-Peter Störr
5

碰撞可能不是一个很大的问题......哈希的主要目标是避免使用equals进行1:1比较。

如果您有一种实现方式，其中对于已发生哈希碰撞的对象而言，equals通常非常便宜，则这不是问题（根本不是问题）。

最终，哈希的最佳方法取决于您要比较什么。在整数配对的情况下（如您的示例），使用基本位运算符可能足够（例如使用&或^）。

5
当然，这并不太重要，但更改主元素是明显且简单的方式来改善事物。那么为什么不这样做呢？ - Hans-Peter Störr
1
同意。我主要是想强调使用质数并不是做事情的唯一方法，因为问题最终具有非常“通用”的范围。 - Romain
顺便说一句：使用 && 是非常糟糕的，因为它往往会在每个步骤之后减少比特数。使用 ^ 更好，但正如有人指出的那样，如果 i 和 j 相等，则使用 i ^ j 的结果为 0，这也是一个相当常见的情况。 - Hans-Peter Störr
4

您需要定义i和j的范围。您可以使用质数来定义两个变量。

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

我会选择7243。这个数字足够大，避免与小数字产生冲突，并且不会很快溢出到小数字。

2
我使用前1000个质数作为小质数的方便来源。http://primes.utm.edu/lists/small/1000.txt - Steve Kuo
我认为溢出并不重要 - 如果质数足够大，即使发生溢出，结果仍然会很大。我在考虑类似于1327144003这样的东西。 - Hans-Peter Störr
1

我想指出的是，哈希码与质数无关。在JDK实现中

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

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

3
质数是确保每个哈希码都出现的简单方法，以便在分布它们时不浪费任何位于整数空间中的位。我不确定是否还有其他优点。但你说27大概也能做到这一点。因此，这与最初选择的31一样糟糕——你也会遇到非常小的哈希码冲突。;-) - Hans-Peter Störr
@Dr.Hans-PeterStörr 对于大小为2的幂次方的哈希表，你只需要一个奇数乘数，无论是否为质数。对于质数大小的哈希表，质数乘数非常重要，因为它们没有任何共同因素（除非你不幸地使用相同的质数:D）。据我所知，在JDK中仅在String#intern中使用了大小为质数的哈希表。 - maaartinus
@maaartinus 一个奇数乘数到底是为了什么？正如我所讨论的，哈希码冲突对性能不利，而小的乘数会产生更多的哈希码冲突，因为属性的小值比大值更有可能出现。 - Hans-Peter Störr
@Dr.Hans-PeterStörr 为了不丢失信息，奇数乘数是必要的（最糟糕的乘数是以许多二进制零结尾的乘数）。显然，丢失信息是不好的，而且很容易避免。 +++ 我们同意小乘数也不好。 +++ 我的观点是质数性。像m = 101 * 103 * 107 * 109这样的乘数对于大小为103的哈希表来说是一场灾难（但没有人使用这样的大小）。对于2的幂大小的表格，它很可能比31好得多。因此，对于与m互质的大小的表格，它很可能也是如此。 - maaartinus
1
@maaartinus 是的，那是乘数应满足的明显属性。我试图指出，如果你再深入思考一下，就可以轻松地使它变得更好，并通过稍微多想一点来减少哈希码冲突。而这些无论表格大小如何都会影响性能。 - Hans-Peter Störr
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接