Java HashMap
使用put
方法将 K/V 对插入HashMap
。假设我使用了put
方法,现在HashMap<Integer, Integer>
有一个条目,key
为 10,value
为 17。
如果我在此HashMap
中插入 10,20,它只是由于相同的键 10 而发生冲突而用此条目替换上一个条目。
如果密钥发生冲突HashMap
则用新的 K/V 对替换旧的 K/V 对。
所以我的问题是HashMap
什么时候使用链接冲突解决技术?
为什么它没有形成键为 10 且值为 17,20 的linkedlist
?
当您插入对(10, 17)
然后(10, 20)
时,技术上不涉及碰撞。您只需将旧值替换为给定键10
的新值(因为在这两种情况下,10 等于 10,而且 10 的哈希代码始终为 10)。
当多个密钥哈希到同一存储桶时,会发生冲突。在这种情况下,您需要确保可以区分这些键。链接冲突解决是用于此目的的技术之一。
例如,假设两个字符串分别"abra ka dabra"
和"wave my wand"
生成哈希代码100
和200
。假设总数组大小为 10,则它们最终都在同一个存储桶中(100 % 10
和 200 % 10
)。链接可确保无论何时执行map.get( "abra ka dabra" );
,最终都会得到与键关联的正确值。在 Java 中的哈希映射的情况下,这是通过使用 equals
方法完成的。
在HashMap
中,键是一个对象,其中包含hashCode()
和equals(Object)
方法。
当您在 Map 中插入新条目时,它会检查hashCode
是否已知。然后,它将使用此哈希码遍历所有对象,并测试它们与.equals()
的相等性。如果找到相等的对象,则新值将替换旧值。如果没有,它将在地图中创建一个新条目。
通常,在谈论地图时,当两个对象具有相同的hashCode
但它们不同时,您会使用碰撞。它们在内部存储在列表中。
它确实可以形成一个链表。只是Map
合约要求它替换条目:
V put(K key, V value)
将指定值与此映射中的指定键相关联 (可选操作)。如果地图以前包含 键,旧值将替换为指定的值。(地图 m 是 据说包含键 k 的映射当且仅当 m.containsKey(k) 将返回 true。
http://docs.oracle.com/javase/6/docs/api/java/util/Map.html
对于存储值列表的映射,它需要是一个Multimap
。这是谷歌的: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html
类似于 Map 的集合,但可能关联多个值 用一个键。如果您调用 put(K, V) 两次,使用相同的键,但 不同的值,多重映射包含从键到两者的映射 值。
编辑:冲突解决方案
这有点不同。当两个不同的键碰巧具有相同的哈希代码,或者具有不同哈希代码的两个键碰巧映射到底层数组中的同一存储桶时,就会发生冲突。
考虑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
定义了自己的静态Entry
类来实现Map.Entry
。 您可以通过查看源代码亲自查看:
GrepCode for HashMap
首先,你对散列的概念有点错误,并且已被@Sanjay纠正。
是的,Java确实实现了冲突解决技术。当两个键被哈希为相同的值时(因为使用的内部数组大小是有限的,并且在某些时候 hashcode() 方法将为两个不同的键返回相同的哈希值),此时会在存储桶位置形成一个链表,所有信息都作为包含键值对的 Map.Entry 对象输入。如果此类列表中存在条目,则通过键访问对象最坏的情况是需要 O(n)。您传递的密钥与此类列表中的每个密钥之间的比较将通过 equals() 方法完成。
虽然,从Java 8开始,链表被树(O(log n))取代
您的情况不是在谈论冲突解决,它只是用同一键的新值替换旧值,因为 Java 的HashMap
不能包含同一键的重复项(即多个值)。
在您的示例中,对于 HashMap 中的相同键 10,值 17 将简单地替换为 20。
如果您尝试为同一键放置不同的/新值,则不是冲突解决的概念,而是简单地将旧值替换为同一键的新值。这就是HashMap
的设计方式,您可以从这里查看下面的API(重点是我的)。
公共 V 放(K 键,V 值)
将指定的值与 在此映射中指定键。如果地图以前包含映射 对于键,将替换旧值。
另一方面,只有当多个键最终具有相同的哈希码(即,它们落在已经存储条目的同一存储桶位置)时,冲突解决技术才会发挥作用。 HashMap
通过使用链接的概念来处理冲突解决,即它将值存储在链表中(或自Java8以来的平衡树,取决于条目的数量)。
当多个键最终出现在同一个存储桶中的相同哈希代码中时。当相同的键具有不同的值时,旧值将替换为新值。
在最坏的情况下,喜欢的列表从java 8版本转换为平衡的二叉树。
当 2 个不同的键生成相同的 hashcode() 值时,会发生冲突。当有更多的冲突时,它会导致哈希图的性能最差。
根据 equals 方法相等的对象必须返回相同的哈希代码值。当两个对象返回相同的 has 代码时,它们将被移动到同一个存储桶中。
冲突和重复之间是有区别的。冲突意味着哈希码和桶是相同的,但在一式两份中,它将是相同的哈希码,相同的桶,但这里等于方法出现在图片中。
检测到冲突,您可以在现有键上添加元素。 但在重复的情况下,它将替换新值。
它没有被定义为这样做。为了实现此功能,您需要创建一个将键映射到值列表的映射:
Map<Foo, List<Bar>> myMap;
或者,您可以使用谷歌收藏/番石榴库中的Multimap。
您的示例中没有冲突。您使用相同的键,因此旧值将替换为新值。现在,如果您使用映射到相同哈希代码的两个键,那么您将发生冲突。但即使在这种情况下,哈希图也会取代你的价值!如果您希望在发生冲突时链接值,则必须自己完成,例如使用列表作为值。