Java HashMap中的冲突解决方案
Java HashMap使用put方法在HashMap插入K / V对。 比方说，我已经使用put方法，现在HashMap<Integer, Integer>有一个条目，其中key为10， value 17。
如果我在这个HashMap插入10,20，由于相同的密钥10，它会由于碰撞而简单地用此条目替换以前的条目。
如果密钥发生冲突， HashMap新的K / V对替换为新的K / V对。
所以我的问题是什么时候HashMap使用Chaining碰撞解析技术？
为什么它没有形成一个linkedlist其中键为10，值为17,20？
当插入一对(10, 17) ，然后(10, 20) ，技术上不存在碰撞。 你只是用给定键10的新值替换旧值（因为在这两种情况下，10等于10并且10的散列码总是10）。
当多个键散列到同一个存储桶时发生碰撞。 在这种情况下，您需要确保您可以区分这些键。 链接冲突解决方案是用于此的那些技术之一。
举例来说，让我们假设两个字符串"abra ka dabra"和"wave my wand"产生散列码100和200 。 假设总阵列大小为10，它们都会在同一个桶中（ 100 % 10和200 % 10 ）结束。 Chaining确保每当你做map.get( "abra ka dabra" ); ，你最终会得到与该键相关的正确值。 对于Java中的哈希映射，这是通过使用equals方法完成的。
在HashMap ，键是一个包含hashCode()和equals(Object)方法的equals(Object) 。
当你在Map上插入一个新条目时，它会检查hashCode是否已知。 然后，它将遍历所有具有该散列码的对象，并使用.equals()测试它们的相等性。 如果找到相同的对象，则新值替换旧值。 如果不是，它会在地图上创建一个新条目。
通常，在谈论地图时，如果两个对象具有相同的hashCode但它们不同，则使用碰撞 。 它们在内部存储在一个列表中。
它确实可能形成了一个链表。 只是Map合同要求它替换条目：
V put(K key, V value)
将指定的值与此映射中指定的键关联（可选操作）。 如果映射先前包含该键的映射，则旧值由指定值替换。 （当且仅当m.containsKey（k）将返回true时，映射m才被认为包含关键k的映射。）
http://docs.oracle.com/javase/6/docs/api/java/util/Map.html
对于存储值列表的地图，它需要是一个Multimap 。 以下是Google的：http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
类似于Map的集合，但可以将多个值与单个关键字相关联。 如果使用相同的键但不同的值调用put（K，V）两次，则multimap包含键与两个值的映射。
编辑：碰撞解决
这有点不同。 当两个不同的密钥恰好具有相同的哈希码时发生冲突，或者具有不同哈希码的两个密钥碰巧映射到底层数组中的同一个存储桶。
考虑HashMap的源代码（删除了一些部分）：
public V put(K key, V value) {
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
// i is the index where we want to insert the new element
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// take the entry that's already in that bucket
Entry<K,V> e = table[bucketIndex];
// and create a new one that points to the old one = linked list
table[bucketIndex] = new Entry<>(hash, key, value, e);
}
对于那些很好奇HashMap的Entry类如何像列表一样行事的人来说， HashMap定义了自己的实现Map.Entry的静态Entry类。 您可以通过查看源代码自行查看：
GrepCode为HashMap
链接地址: http://www.djcxy.com/p/92195.html