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 序列)。由于这种 AND 运算，仅使用 h 的低位。 h 的其余部分将被忽略。想象一下，无论出于何种原因，原始哈希仅返回能被2整除的数字。如果直接使用它，则 HashMap 的奇数位置将永远不会被使用，导致冲突次数增加2倍。在真正病态的情况下，错误的哈希函数可能会使 HashMap 的行为更像是列表，而不是 O(1) 容器。

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