为什么在hashCode中使用素数？ [英] Why use a prime number in hashCode?

问题描述

我只是想知道为什么在类的 hashCode（）方法中使用素数？例如，当使用Eclipse生成我的 hashCode（）方法时，总是使用素数 31 ：

I was just wondering why is that primes are used in a class's hashCode() method? For example, when using Eclipse to generate my hashCode() method there is always the prime number 31 used:

public int hashCode() {
     final int prime = 31;
     //...
}

参考文献：

这是关于Hashcode的一篇很好的入门文章和关于我如何找到散列的文章（C＃，但概念是可转移的）：
Eric Lippert的GetHashCode指南和规则（）

Here is a good primer on Hashcode and article on how hashing works that I found (C# but the concepts are transferrable): Eric Lippert's Guidelines and rules for GetHashCode()

推荐答案

因为你想要你所乘的数字和你要插入的桶数有正交的素数分解。

Because you want the number you are multiplying by and the number of buckets you are inserting into to have orthogonal prime factorizations.

假设有8个桶要插入。如果您用来乘以的数字是8的某个倍数，那么插入的数据桶将仅由最不重要的条目（根本没有相乘的条目）确定。类似的条目将发生冲突。对哈希函数不好。

Suppose there are 8 buckets to insert into. If the number you are using to multiply by is some multiple of 8, then the bucket inserted into will only be determined by the least significant entry (the one not multiplied at all). Similar entries will collide. Not good for a hash function.

31是一个足够大的素数，桶的数量不太可能被它整除（实际上，现代java HashMap实现保持不变桶的数量为2）。

31 is a large enough prime that the number of buckets is unlikely to be divisible by it (and in fact, modern java HashMap implementations keep the number of buckets to a power of 2).

这篇关于为什么在hashCode中使用素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！