Java Arrays.hashcode() 的 hashcode 实现是否均匀分布

我查看了源代码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 。

为什么使用素数 31？

这可以分成两部分吗？

1. 为什么是质数？

在这里我们需要明白，我们的目标是获得unique对象的 HashCode 将帮助我们在 O(1) 时间内找到该对象。

这里的关键词是unique.

Primes

素数是唯一的数字。它们的独特之处在于， 质数与任何其他数字最有可能是唯一的（不是 当然，与素数本身一样独特），因为素数 用于组成它。该属性用于散列函数。

.

为什么是31号？

From 有效的Java

• 因为它是一个奇素数，并且使用素数是“传统”的。

• 它也比 2 的幂小 1，这允许按位 优化

  这是完整的报价，

来自第 9 条：始终覆盖 当您覆盖 equals 时的 hashCode：

选择值 31 是因为它是奇素数。如果是偶数且 乘法溢出，信息将会丢失，因为 乘以 2 相当于移位。使用的优点 素数不太清楚，但它是传统的。

31 的一个很好的特性是乘法可以用 移位（§15.19）和减法以获得更好的性能：

31 * i == (i

虽然本项中的配方产生了相当好的哈希函数， 它不会产生最先进的哈希函数，Java 也不会 自版本 1.6 起，平台库提供了此类哈希函数。 编写这样的哈希函数是一个研究课题，最好留给 数学家和理论计算机科学家。

也许该平台的后续版本将提供最先进的 其类的哈希函数和允许平均的实用方法 程序员构造这样的哈希函数。与此同时， 本项中描述的技术对于大多数人来说应该足够了 应用程序。

这是一个非常很好的来源。