我正在尝试创建一个碰撞。
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两个对象。我已经覆盖了国家的equals()和hashCode()方法，以便:
india.hashCode() == india2.hashCode()—>真正的india.equals(india2)—>假
根据Java HashMap中的冲突解析和文章"let ' t put this Country objects in HashMap"中的部分内容，如果key1的hash(key.hashCode())结果等于对key2的相同操作，则应该发生冲突。
因此，我放置断点以查看countryCapitalMap的内容，并查看其size为2。也就是说，它包含两个不同的条目，并且没有linkedList。因此，没有碰撞。
我的问题是
为什么countryCapitalMap的大小为2?为什么没有碰撞?
为什么HashMap不创建一个LinkedList与两个条目的键是不相等的，但有相同的hashCode?
你混淆了碰撞-当键的哈希值相同时(或者更准确地说，当哈希值在HashMap的同一桶对应的范围内时)，重复键的情况(即。根据equals()方法相同的键。这是两种完全不同的情况。
在底层，HashMap维护一个bucket数组。每个桶对应一个哈希值范围。
如果键的哈希值冲突(但键不等于)，则条目(准确地说是Nodes)将被映射到相同的桶并形成链表，该链表在一定阈值后将变成树。
equals()方法()复制的密钥将导致更新现有条目的值。
因为正如您已经观察到的，india.equals(india2)将返回false,HashMap将包含两个条目。
由于india和india2的哈希值是相同的，您已经成功地创建了碰撞。两个条目都将被添加，它们都将在同一个bucket中结束(即。它们的节点将形成一个链表)。
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()将只调用一次，而创建一个新的节点。看一下上面的代码，您会注意到字段hash被标记为final。这样做是有目的的，因为计算哈希值对于一些对象来说是非常昂贵的。这意味着，如果键的状态发生变化，HashMap将不知道该变化，并且将无法识别相同的键，即，如果前一个和新的哈希值不同，equals()方法将不会被调用，HashMap将允许相同的键出现两次。这就引出了另一条经验法则:用作键的对象应该是不可变的。