HashMap中的哈希方法[重复]

Question

可能重复：
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);
   }

有人能详细解释一下这个方法吗，谢谢。

Answer 1

很好，不涉及细节，但：

>

由于hascode（）和equals（）契约，hashcode函数的糟糕实现可能会导致不同实例具有相同的hashcode。这意味着您可能有一个具有蹩脚hashcode（）方法实现的类，这样该类的equals（）方法将为a和B实例返回false（这意味着它们不同于业务逻辑的观点），但hashcode（）方法为实例a和B返回相同的值。同样，根据hashcode（）和equals（）约定，这在技术上是有效的，但不太合适

在类似哈希表的结构（如HashMap）中，“bucket”用于根据其哈希代码将实例放置在映射内。如果两个实例具有相同的hashcode（）（但根据equals（）方法不同），则它们都将放在同一个bucket中。从性能的角度来看，这是不好的，因为当您有很多这样的情况时，您会失去一些类似哈希表的结构固有的检索速度。这些被称为碰撞。所发生的是，如果稍后有人使用“搜索”实例从hashmap中检索某些内容，并且相应的哈希桶有多个占用者，则必须使用equals（）方法检查该桶中的每个元素，以找出需要检索的元素。在极端情况下，可以将HashMap转换为这样的链表。

该hash（int n）方法向现有hashcode（）值添加了一些额外的东西，以防止出现此类情况。

Answer 2

设计通用哈希代码的一个问题是，您将所有这些努力都放在确保良好的位分布上，然后有人出现并以完全撤销的方式使用它。

让我们举一个典型的例子，一个坐标类有一个X和一个Y，都是整数。

这是一个经典的例子，因为人们会用它来证明X^Y不是一个好的哈希码，因为通常有几个对象X==Y（所有哈希为0）或一个其X和Y是另一个的Y和X（将哈希相同）以及我们最终得到相同哈希码的其他情况。

归根结底，尽管整数有一个覆盖40亿值的可能范围，但在99%的使用中，它们往往小于几百或几万。我们永远无法摆脱在可能的结果中传播1.8京可能的值40亿，但我们可以努力使那些我们可能实际看到的值不太可能发生冲突。

现在，<代码>（X

不幸的是，如果使用此哈希是为了索引到表中（或者甚至在较小的程度上索引到其他数字），那么对于X以下的值，我们可以认为是最常见的X，此哈希将有效地返回Y。

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

所使用的重新哈希是用这样的逻辑生成一个哈希，稍微好一点。

值得注意的是，对（X）过于挑剔是不公平的