java - Java Arrays.hashcode() 的 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. Why a prime number?

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

这里的关键词是独特。

Primes

Primes are unique numbers. They are unique in that, the product of a prime with any other number has the best chance of being unique (not as unique as the prime itself of-course) due to the fact that a prime is used to compose it. This property is used in hashing functions.

.

Why number 31?

来自 Effective Java

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

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

  这是完整的引述，

from Item 9: Always override hashCode when you override equals:

The value 31 was chosen because it's an odd prime. If it were even and multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional.

A nice property of 31 is that the multiplication can be replaced by a shift (§15.19) and subtraction for better performance:

31 * i == (i << 5) - i Modern VMs do this sort of optimization automatically.

While the recipe in this item yields reasonably good hash functions, it does not yield state-of-the-art hash functions, nor do Java platform libraries provide such hash functions as of release 1.6. Writing such hash functions is a research topic, best left to mathematicians and theoretical computer scientists.

Perhaps a later release of the platform will provide state-of-the-art hash functions for its classes and utility methods to allow average programmers to construct such hash functions. In the meantime, the techniques described in this item should be adequate for most applications.

这是一个很Good source.