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; } 

这里实现的散列函数是否真正均匀地分配了所有输入数组。为什么我们在这里使用prime 31。

Answer 1

为什么要使用素数31？

这可以分为两部分？

1. 为什么是素数？

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

这里的关键词是独一无二的 。

素数

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

。

为什么31号？

来自Effective Java

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

• 它也是一个小于2的幂，它允许按位优化

  这是完整的报价，

来自第9项：覆盖equals时始终覆盖hashCode：

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

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

31 * i ==（i << 5） - i Modern VM自动进行这种优化。

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

也许平台的后续版本将为其类和实用程序方法提供最先进的哈希函数，以允许普通程序员构造这样的哈希函数。 与此同时，本项目中描述的技术应该适用于大多数应用程序。

这是一个非常好的来源。

Answer 2

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

Answer 3

看到这篇文章： 为什么String中的Java的hashCode（）使用31作为乘数？

这就是TheEwook的答案来自。

一般来说，你使用素数是因为它们没有任何因子，并且会分配更好的模N，其中N是你正在分组的范围的大小。 31是一个小的奇数素数，所以效果很好。 但是，正如您将在互联网上找到的各种来源所表明的那样，像31这样的小素数可能会导致更多的素数而不是更大的素数（特别是如果被散列的值不是很好地分配开始），那么你可以选择一个如果你发现表现不如你想的那么好，那就更大。