idea生成的hashCode方法里为什么选择数字31作为生成hashCode值的乘数

秒速五厘米 2024-02-21 09:30 21阅读 0赞

### 个人理解 ###

原因一：更少的乘积结果冲突

31是质子数中一个“不大不小”的存在，如果你使用的是一个如2的较小质数，那么得出的乘积会在一个很小的范围，很容易造成哈希值的冲突。而如果选择一个100以上的质数，得出的哈希值会超出int的最大范围，这两种都不合适。而如果对超过 50,000 个英文单词（由两个不同版本的 Unix 字典合并而成）进行 hash code 运算，并使用常数 31, 33, 37, 39 和 41 作为乘子，每个常数算出的哈希值冲突数都小于7个（国外大神做的测试），那么这几个数就被作为生成hashCode值得备选乘数了。

原因二：31可以被JVM优化

JVM里最有效的计算方式就是进行位运算了：

\* 左移 << : 左边的最高位丢弃，右边补全0（把 << 左边的数据\*2的移动次幂）。  
\* 右移 >> : 把>>左边的数据/2的移动次幂。  
\* 无符号右移 >>> : 无论最高位是0还是1，左边补齐0。

所以 ： 31 \* i = (i << 5) - i（左边 31\*2=62,右边 2\*2^5-2=62） - 两边相等，JVM就可以高效的进行计算啦。

## ChatGPT ##

在生成`hashCode()`方法的代码中，选择数字31作为生成哈希码的乘数是一种常见的做法。这种选择是基于一些理论和实践的经验，并且在大多数情况下都能产生较好的结果。

选择数字31作为乘数的原因如下：

1.  质数：31是一个质数（素数），这使得它在哈希计算中具有良好的特性。使用质数作为乘数可以减少哈希冲突的可能性，因为质数在乘法运算中产生的结果更分散，减少了相同值产生相同哈希码的概率。
2.  效率：31可具体而言，以通过移位和减法操作来优化计算过程。将乘法操作替换为移位和减法操作可以提高计算的效率，因为这些操作在大多数计算机体系结构中是较为高效的。
3.  好的乘法乘数：31是一个较大的质数，它与2的幂次方之间的乘法相当于一个较大的位移和减法操作，可以更好地散列对象的位。这样做可以增加乘法的乘数空间，提高了哈希码的分布性。

需要注意的是，选择乘数31并不是绝对适用于所有情况。在某些特定的应用场景中，可能需要根据具体的需求和数据特征选择其他乘数来生成更好的哈希码。在实际使用中，可以根据性能测试和实验评估来选择最适合的乘数。

总之，选择数字31作为生成哈希码的乘数是一种常见的做法，它基于质数的特性、效率考虑以及良好的分布性。然而，最佳的乘数选择可能因应用场景和数据特征而异，需要根据具体情况进行评估和调整。

## Assistant ##

在Java中，常见的实现hashCode方法的方式是使用31作为乘数。这个选择是有原因的，涉及到一些计算和性能方面的考虑。

1.  **质数选择**：31是一个质数（素数），在哈希计算中选择质数作为乘数可以减少哈希冲突的可能性。使用质数作为乘数可以更好地分散数据在哈希表中的位置，减少散列冲突的概率。
2.  **位操作优化**：在计算机的底层，乘法操作可以通过位移和减法来实现，而位移和减法的性能通常比乘法操作更高效。使用31作为乘数，可以进行一些位移和减法的优化操作，提高hashCode方法的执行效率。
3.  **乘法效果**：乘法操作可以将一个数扩大或缩小，而乘以31相当于将原始值左移5位，再减去原始值，这样可以在一定程度上保留原始值的特征，同时增加了一些变化，使得最终的哈希值更具唯一性。

需要注意的是，虽然选择31作为乘数是一种通用的做法，但并不是适用于所有情况的绝对最佳选择。对于特定的数据集合和哈希函数需求，可能需要根据实际情况进行调整乘数的选择。

在IDEA生成的hashCode方法中，选择31作为乘数是一个经过实践验证的常见选择，它提供了一个相对较好的平衡，既能获得较好的哈希性能，又能保持简洁和高效的实现。