HashMap中的Hash方法


问题内容
  /**
    * 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);
   }

谁能详细解释这种方法,谢谢。


问题答案:

设计通用哈希码的问题之一是,您将所有这些工作都放在了确保良好的位扩展上,然后有人来使用并以完全撤消的方式使用它。

让我们以一个带有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方法是不公平的,因为对哈希的另一种使用可能具有优于给定替代方法的形式。