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 回答