Java Arrays.hashcode（）的哈希码实现是否均匀分布

Question

我查看了源代码，但Arrays.hashCode(char[] c)
我不太确定它适用的算法在所有情况下都能正常工作。

    public static int hashCode(int a[]) {
    if (a == null)
        return 0;

    int result = 1;
    for (int element : a)
        result = 31 * result + element;

    return result;
}

哈希函数是否在这里实现了真正均匀地分布所有输入数组的原因。为什么在这里使用质数31。

Answer 1

为什么使用质数31？

这可以分为两部分吗？

1. 为什么是素数？
   
   

在这里，我们需要了解我们的目标是为对象获取 唯一的 HashCode，这将有助于我们在O（1）时间内找到该对象。

这里的关键词是 唯一的 。

素数

质数是唯一数字。它们的独特之处在于，由于使用了素数来构成素数，因此素数与任何其他数字的乘积具有唯一性的最大可能性（不像素数本身那样唯一）。此属性在哈希函数中使用。

。

为什么是31号？

从 有效的Java

• 因为这是一个奇怪的素数，并且使用素数是“传统的”。
• 它也小于2的幂，这允许按位优化

这是完整的报价，

从项目9：重写等于时，始终重写hashCode：

选择值31是因为它是奇数质数。如果是偶数且乘法溢出，则信息将丢失，因为乘以2等于移位。使用质数的优势尚不清楚，但这是传统的。

31的一个不错的特性是乘法可以用移位（第15.19节）和减法代替，以获得更好的性能：

31 * i ==（i << 5）-i现代VM自动执行这种优化。

尽管此项目中的配方产生了相当不错的哈希函数，但它没有产生最新的哈希函数，Java平台库也没有提供1.6版以上的哈希函数。编写这样的哈希函数是一个研究主题，数学家和理论计算机科学家最好去做。

也许该平台的更高版本将为其类和实用程序方法提供最新的哈希函数，以允许普通程序员构造此类哈希函数。同时，此项中描述的技术应适合大多数应用。

这是一个很好的来源。