HashMap中的Hash方法

Question

  /**
    * 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在较小程度上），则对于低于X的值（someBinaryRoundNumber我们可以预期是最常见的），此哈希有效return Y。

我们所有的辛苦工作被浪费了！

所使用的重新哈希方法是使用这种逻辑进行哈希方法，效果略好。

值得一提的是，过于批评这种(X << 16 | X >> 16) ^ Y方法是不公平的，因为对哈希的另一种使用可能具有优于给定替代方法的形式。