当不同的键具有相同的哈希代码时，为什么哈希映射中没有冲突

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.hash代码（）==india2.hash代码（）

根据JavaHashMap中的冲突解决方案和文章“让这个国家对象在hashmap中”的一部分，如果key1的结果hash（key.hashCode（））等于key2上的相同操作，那么应该会有冲突。

所以，我放置断点来查看countryCapitalMap的内容，并查看它的size是2。也就是说，它包含两个不同的条目，并且没有linkedList。因此，没有碰撞。

我的问题是：

为什么Country Capital alMap的大小为2？为什么没有碰撞？

为什么HashMap不创建一个LinkedList，其中包含两个键相等但哈希代码相同的条目？

Answer 1

当键的哈希相同时，您将冲突情况与重复键（即根据equals（）方法相同的键）混淆。这是两种完全不同的情况。

在引擎盖下，HashMap维护一组桶。每个bucket对应一系列散列值。

如果键的散列冲突（但键不相等），条目（Nodes）将映射到同一个bucket并形成一个链表，在达到某个阈值后，链表将变成一棵树。

相反，如果试图添加一个新条目，而该条目的密钥已经存在于映射中（即重复密钥），则会导致更新现有条目的值。

因为正如您已经观察到的，india.equals（India2）将返回false，HashMap将包含两个条目。

由于india和india2的散列是相同的，因此您成功地实现了创建冲突的意图。两个条目都将被添加，都将在同一个bucket中结束（即，它们的节点将形成一个链表）。