为什么在 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屋！