java - 为什么 HashMap 会重新哈希键对象提供的哈希码？

Question

我正在阅读 Java 1.6 API 提供的 HashMap 类的代码，无法完全理解以下操作的需要(在 put 和 get 方法的主体中找到):

int hash = hash(key.hashCode());

hash() 方法的主体如下:

 private static int hash(int h) {
         h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

这通过对提供的哈希码执行位操作有效地重新计算哈希。我无法理解这样做的必要性，即使 API 声明如下:

This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits.

我确实理解键值解析存储在数据结构数组中，并且该数组中项目的索引位置由其哈希确定。 我不明白的是这个函数如何为散列分布添加任何值。

Answer 1

正如 Helper 所写，它的存在只是为了防止现有的关键对象哈希函数出现故障，并且不能很好地混合低位。根据the source由 pgras 引用，

 /**
  * Returns index for hash code h.
  */
 static int indexFor(int h, int length) {
     return h & (length-1);
 }

散列以 2 的幂长度进行 AND 运算(因此，length-1 保证是 1 的序列)。由于这个 ANDing，只有 h 的低位被使用。 h 的其余部分将被忽略。想象一下，无论出于何种原因，原始哈希仅返回可被 2 整除的数字。如果直接使用它，则永远不会使用 hashmap 的奇数位置，从而导致冲突次数增加 x2。在真正病态的情况下，糟糕的哈希函数会使 HashMap 表现得更像一个列表，而不是一个 O(1) 容器。

Sun 工程师必须进行测试，证明太多的散列函数在其低位不够随机，而且许多散列映射不够大，无法使用高位。在这些情况下，HashMap 的 hash(int h) 中的位操作可以提供对大多数预期用例的净改进(由于较低的冲突率)，即使需要额外的计算也是如此。