2

I review the source code of Arrays.hashCode(char[] c)
I am not very confirm that the algorithm it applies well work well in all cases.

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

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

    return result;
}

Does the hash function implement here really uniformly distributes the all the input arrays.And Why we use prime 31 here .

4

3 回答 3

6

为什么使用质数 31？

这可以分成两部分吗？

  1. 为什么是素数？

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

这里的关键词，是唯一的。

素数

素数是唯一的数字。它们的独特之处在于，素数与任何其他数字的乘积最有可能是唯一的（当然，不像素数本身那么独特），因为使用了素数来构成它。此属性用于散列函数。

.

为什么是 31 号？

从有效的Java

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

  • 它也比二的幂小一，这允许按位优化

    这是完整的报价，

来自第 9 条：覆盖等于时始终覆盖 hashCode：

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

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

31 * i == (i << 5) - i 现代虚拟机自动进行这种优化。

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

也许该平台的后续版本将为其类和实用方法提供最先进的散列函数，以允许普通程序员构建这样的散列函数。同时，本项目中描述的技术应该足以满足大多数应用程序的需要。

这是一个非常好的来源。

于 2013-09-13T14:04:26.610 回答
1

选择值 31 是因为它是一个奇数素数。如果它是偶数并且乘法溢出，则信息将丢失，因为乘以 2 相当于移位。使用素数的优势不太明显，但它是传统的。31 的一个很好的特性是乘法可以用移位和减法代替以获得更好的性能：31 * i == (i << 5) - i。现代虚拟机自动进行这种优化。

于 2013-09-13T14:03:07.647 回答
1

见这篇文章：为什么 Java 的 String 中的 hashCode() 使用 31 作为乘数？

这就是 TheEwook 的答案。

通常，您使用素数是因为它们没有任何因素，并且会更好地分配模 N，其中 N 是您要分箱的范围的大小。31 是一个小的奇数素数，所以它工作得很好。但是，正如您在 Internet 上找到的各种来源所表明的那样，像 31 这样的小素数可能会比较大的素数导致更多的冲突（特别是如果被散列的值一开始就没有很好地分布），所以您可以选择一个如果您发现性能不如您想要的那么好，请使用更大的素数。

于 2013-09-13T14:13:48.137 回答