1

可能重复：
HashMap#hash(int) 方法的解释 

   /**
    * 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);
   }

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

4

2 回答 2

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。

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

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

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

于 2012-08-29T10:53:27.307 回答
0

好吧，不要进入细节，但是：

  • 由于 hascode() 和 equals() 合约，hashcode 函数的糟糕实现可能导致不同的实例具有相同的 hashcode。这意味着您可能有一个具有蹩脚的 hashcode() 方法实现的类，这样该类的 equals() 方法将为 A 和 B 实例返回 false （这意味着它们从业务逻辑的角度来看是不同的）但是 hashcode() 方法为实例 A 和 B 返回相同的值。同样，根据 hashcode() 和 equals() 合约，这在技术上是有效的，但不是很合适

  • 在类似 Hashtable 的结构（如 HashMap）中，“桶”用于根据其哈希码将实例放置在地图内。如果两个实例具有相同的 hashcode() （但根据 equas() 方法不同），它们将被放置在同一个桶中。从性能的角度来看，这很糟糕，因为当您遇到很多此类情况时，您会失去一些类似于 Hashtable 的结构固有的检索速度。被称为碰撞。发生的情况是，如果稍后有人使用“搜索”实例从哈希映射中检索某些内容，并且相应的哈希存储桶有多个占用者，则必须使用 equals() 方法检查该存储桶中的每个元素以找出哪个是需要检索的。

  • 该 hash(int n) 方法为现有的 hashcode() 值添加了一些额外的东西，以防御这种情况。

于 2012-08-29T10:54:08.937 回答