为什么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声明如下,我也无法理解这样做的必要性:

这很关键,因为HashMap使用两个幂的长度哈希表,否则会遇到低位不同的hashCodes的冲突.

我确实理解键值是存储在数据结构数组中的,并且该数组中项的索引位置由其哈希确定.我无法理解的是这个函数如何为哈希分布添加任何值.

Answer 1

正如Helper写的那样,只是在关键对象的现有哈希函数出错并且没有做好混合低位的足够好的工作的情况下.根据pgras引用的消息来源,

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

哈希与两个幂的长度进行AND运算(因此,length-1保证是1的序列).由于此ANDing,仅使用较低位h.其余的h被忽略了.想象一下,无论出于何种原因,原始哈希仅返回可被2整除的数字.如果直接使用它,则不会使用哈希图的奇数位置,从而导致冲突数量增加x2.在真正的病态情况下,错误的散列函数可以使散列图的行为更像列表,而不是像O(1)容器.

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