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

hashcode collections hashmap java hash

2022-09-03 05:09:06

我正在阅读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 使用两个长度的幂哈希表，否则会遇到哈希代码的冲突，而哈希代码在较低位上没有差异。

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

答案 1

正如Helper所写的那样，它的存在只是为了以防万一关键对象的现有哈希函数有问题，并且在混合较低位方面做得不够好。根据pgras引用的消息来源，

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

哈希值以 2 的幂长度进行 ANDed（因此，保证为 1 的序列）。由于这种 ANDing，仅使用的较低位。其余的将被忽略。想象一下，无论出于何种原因，原始哈希只返回可被2整除的数字。如果直接使用它，则永远不会使用哈希图的奇数位置，从而导致冲突次数增加 x2。在真正病态的情况下，一个糟糕的哈希函数可以使哈希映射的行为更像一个列表，而不是一个O（1）容器。length-1hh

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

答案 2

我在某处读到这是为了确保一个好的分布，即使你的hashCode实现，嗯，错误，很糟糕。