java - HashMap中的哈希方法

Question

这个问题已经有答案了:

已关闭 10 年前。

Possible Duplicate:
Explanation of HashMap#hash(int) method

   /**
    * Applies a supplemental hash function to a given hashCode, which
    * defends against poor quality hash functions.  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. Note: Null keys always map to hash 0, thus index 0.
    */
   static int hash(int h) {
       // This function ensures that hashCodes that differ only by
       // constant multiples at each bit position have a bounded
       // number of collisions (approximately 8 at default load factor).
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }

谁能详细解释一下这个方法，谢谢。

Answer 1

设计通用哈希码的问题之一是，您投入所有精力来确保良好的位分布，然后有人出现并以完全撤销这一点的方式使用它。

让我们举一个坐标类的经典示例，其中 X 和 Y 均为整数。

这是一个经典的例子，因为人们会用它来证明 X ^ Y不是一个好的哈希码，因为通常存在多个对象，其中 X == Y(全部哈希为 0)，或者一个对象的 X 和 Y 是另一个对象的 Y 和 X(将哈希相同)，以及我们最终得到相同哈希码的其他情况。

归根结底，虽然整数的可能范围涵盖 40 亿个值，但在 99% 的使用中，它们往往少于几百或最多几万。我们永远无法摆脱在 40 亿个可能结果中分散 18万亿个可能值的尝试，但我们可以努力使那些我们可能实际看到的值不太可能发生冲突。

现在，(X << 16 | X >> 16) ^ Y在这种情况下做得更好，将 X 中的位分散得更多。

不幸的是，如果使用这个哈希来做% someBinaryRoundNumer索引到表中(甚至是 % someOtherNumber ，程度稍小)，然后对于低于 someBinaryRoundNumber 的 X 值- 我们可以预期这是最常见的 - 这个哈希变得有效 return Y .

我们所有的努力都白费了!

使用的rehash就是用这样的逻辑做一个hash，稍微好一些。

值得注意的是，对 (X << 16 | X >> 16) ^ Y 过于挑剔是不公平的。方法作为哈希的另一种使用可能具有优于给定替代方案的形式。