当不同的键具有相同的哈希码时，为什么 HashMap 中不会发生冲突

Question

我试图故意制造碰撞。

 fun main(args: Array<String>) {
   val india = Country("India1", 1000)
   val india2 = Country("India2", 1000)

   val countryCapitalMap: HashMap<Country, String> = hashMapOf()
   countryCapitalMap.put(india, "Delhi1")
   countryCapitalMap.put(india2, "Delhi2")
 }


class Country(var name: String, var population: Long) {

  override fun hashCode(): Int {
      return if (name.length % 2 == 0) 31 else 95
  }

  override fun equals(obj: Any?): Boolean {
      val other = obj as Country?
      return if (name.equals(other!!.name, ignoreCase = true)) true else false
  }
}

所以，我有india反对india2意见。我已经重写了Country 的equals()和hashCode()方法，以便：

• india.hashCode() == india2.hashCode()--> 正确
• india.equals(india2)--> 假

根据Java HashMap 中的冲突解决方案和文章“让我们将这个 Country 对象放入 hashmap”的一部分，如果 key1 的结果hash(key.hashCode())等于 key2 上的相同操作的结果，则应该存在冲突。

因此，我设置断点来查看内容countryCapitalMap，发现它size是 2。即它包含两个不同的条目，并且没有 linkedList。因此，不存在碰撞。

我的问题是：

为什么countryCapitalMap尺寸为2？为什么没有碰撞呢？

为什么不HashMap创建一个LinkedList具有两个键不相等但具有相同 hashCode 的条目？

Answer 1

您混淆了冲突- 当键的哈希值相同时（或者准确地说，当哈希值在与同一存储桶相对应的范围内时 HashMap），与重复的键 （即根据 equals() 方法相同的键）。这是两种完全不同的情况。

在引擎盖下，HashMap维护着一系列的水桶。每个桶对应一个哈希值范围。

如果键的哈希值发生冲突（但键不相等），则条目（Node准确地说是）将被映射到同一个桶并形成一个链表，在达到一定阈值后将变成一棵树。

相反，尝试添加具有映射中已存在的键（即根据该方法的重复键）的新条目将导致更新现有条目的值。 equals()

因为正如您已经观察到的，india.equals(india2)will return false，HashMapwill 包含两个条目。

由于india和的哈希值india2是相同的，因此您已经成功地实现了创建冲突的意图。两个条目都将被添加，两者最终将位于同一个存储桶中（即它们的节点将形成一个链表）。

如果您想知道这个链表究竟是什么样子，请查看该类的源代码HashMap。你会发现有一个字段- 一个桶Node<K,V>[] table数组，还有一个内部类：Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

每个节点都保存一个指向next映射到同一桶（如果有）的下一个节点的引用。

旁注：

• 您在示例中提供的哈希函数是一个糟糕的函数。当然，很明显您是故意这样做的（以确保两个键会发生碰撞）。但需要指出的是，契约的正确实现equals/hashCode对于每个要与集合框架一起使用的对象都至关重要。HashMap对于像和这样的基于散列的集合来说，实现良好的HashSet性能hashCode()非常重要。如果散列函数产生大量冲突，则许多条目可能出现在同一个桶中，同时大量桶可能未被占用。并且根据负载系数（已占用的存储桶数与存储桶总数之间的比率），您的集合可能永远不会调整大小，这将导致性能下降。
• 与哈希相关的另一件值得一提的事情是，在创建新节点hashCode()时，密钥只会被调用一次。看一下上面的代码，您会注意到该字段被标记为。这是故意这样做的，因为计算某些对象的哈希值可能会很昂贵。这意味着，如果该密钥的状态发生变化，a将不知道该更改，并且无法识别相同的密钥，即，如果先前的哈希值和新的哈希值不同，则不会调用该方法，并且将允许相同的密钥出现两次。 。这就引出了另一个经验法则：用作键的对象应该是不可变的。hashfinalHashMapequals()HashMap