86

JavaHashMap使用put方法将 K/V 对插入HashMap. 假设我使用put了方法,现在HashMap<Integer, Integer>有一个条目,分别key为 10 和value17。

如果我在其中插入 10,20,HashMap则由于相同的键 10 发生冲突,它只是将先前的条目替换为此条目。

如果密钥发生冲突HashMap,则用新的 K/V 对替换旧的 K/V 对。

所以我的问题是什么时候HashMap使用链式冲突解决技术?

为什么它没有形成一个linkedlist键为10,值为17,20的?

4

9 回答 9

125

当您插入一对(10, 17)然后(10, 20)时,从技术上讲不涉及碰撞。您只是用给定键的新值替换旧值10(因为在这两种情况下,10 等于 10,而且 10 的哈希码始终为 10)。

当多个键散列到同一个桶时,就会发生冲突。在这种情况下,您需要确保可以区分这些键。链接冲突解决方案是用于此的那些技术之一。

例如,假设两个字符串"abra ka dabra"分别"wave my wand"产生哈希码100200。假设总数组大小为 10,它们最终都在同一个存储桶中 (100 % 10200 % 10)。链接确保无论何时执行map.get( "abra ka dabra" );,您最终都会得到与键关联的正确值。在 Java 中的哈希映射的情况下,这是通过使用equals方法来完成的。

于 2013-10-30T19:20:45.260 回答
32

在一个HashMap键是一个对象,它包含hashCode()equals(Object)方法。

当您将新条目插入 Map 时,它会检查是否hashCode已知。然后,它将使用此哈希码遍历所有对象,并使用.equals(). 如果找到相等的对象,则新值替换旧值。如果没有,它将在地图中创建一个新条目。

通常,在谈论地图时,当两个对象具有相同但不同时,您会使用碰撞。hashCode它们在内部存储在列表中。

于 2013-10-30T19:22:26.050 回答
9

事实上,它本可以形成一个链表。只是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. 这是谷歌的:http: //google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

类似于 Map 的集合,但可以将多个值与单个键相关联。如果您使用相同的键但值不同的两次调用 put(K, V),则多重映射包含从键到两个值的映射。

编辑:碰撞解决

这有点不同。当两个不同的键碰巧具有相同的哈希码,或者具有不同哈希码的两个键碰巧映射到底层数组中的同一个桶时,就会发生冲突。

考虑HashMap's source (点点滴滴):

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);
}

对于那些好奇这个Entry类如何HashMap表现得像一个列表的人,事实证明它HashMap定义了自己的静态Entry类,它实现了Map.Entry. 您可以通过查看源代码自己了解:

HashMap 的 GrepCode

于 2013-10-30T19:21:41.963 回答
5

首先,你对散列的概念有一点错误,@Sanjay 已经纠正了它

是的,Java 确实实现了冲突解决技术。当两个键被哈希到相同的值时(因为使用的内部数组的大小是有限的,并且在某些时候 hashcode() 方法将为两个不同的键返回相同的哈希值),此时在桶中形成一个链表将所有信息作为包含键值对的 Map.Entry 对象输入的位置。如果条目存在于此类列表中,则通过键访问对象最多需要 O(n)。您传递的键与此类列表中的每个键之间的比较将由 equals() 方法完成。

虽然,从 Java 8 开始,链表被替换为树 (O(log n))

于 2015-09-26T13:48:30.837 回答
3

当多个密钥以相同的哈希码结束时,该哈希码存在于同一个桶中。当同一个键有不同的值时,旧值将被新值替换。

在最坏的情况下,喜欢的列表从病房的 java 8 版本转换为平衡的二叉树。

当 2 个不同的键生成相同的 hashcode() 值时,就会发生冲突。当有更多的冲突时,它会导致 hashmap 的性能最差。

根据 equals 方法相等的对象必须返回相同的 hashCode 值。当两个对象返回相同的代码时,它们将被移动到同一个桶中。

于 2018-11-28T05:44:39.017 回答
3

您的案例不是在讨论冲突解决方案,它只是用相同键的新值替换旧值,因为 JavaHashMap不能包含相同键的重复项(即多个)。

在您的示例中,对于 HashMap 中的相同键 10,值 17 将简单地替换为 20。

如果您尝试为同一个键设置不同/新值,这不是冲突解决的概念,而是简单地将旧值替换为同一个键的新值。这就是HashMap设计的方式,您可以查看从此处获取的以下 API(重点是我的) 。

public V put(K key, V value)

将指定的值与此映射中的指定键相关联。如果映射先前包含键的映射,则替换旧值


另一方面,冲突解决技术只有在多个键最终具有相同的哈希码(即它们落在同一个桶位置)时才起作用,其中已经存储了一个条目。HashMap通过使用链接的概念来处理冲突解决,即,它将值存储在链表中(或从 Java8 开始的平衡树,取决于条目的数量)。

于 2018-10-25T06:37:05.083 回答
2

碰撞和重复是有区别的。碰撞意味着哈希码和桶是相同的,但是在重复时,它将是相同的哈希码,相同的桶,但是这里的equals方法出现在图片中。

检测到碰撞,您可以在现有键上添加元素。但在重复的情况下,它将替换新值。

于 2017-01-04T21:54:28.410 回答
1

您的示例中没有碰撞。您使用相同的密钥,因此旧值将被新值替换。现在,如果您使用映射到相同哈希码的两个键,那么您就会发生冲突。但即使在那种情况下,HashMap 也会取代你的价值!如果您希望在发生冲突时将值链接起来,您必须自己完成,例如使用列表作为值。

于 2013-10-30T19:20:53.930 回答
1

它没有被定义为这样做。为了实现此功能,您需要创建一个将键映射到值列表的映射:

Map<Foo, List<Bar>> myMap;

或者,您可以使用谷歌收藏/番石榴库中的 Multimap

于 2013-10-30T19:20:57.367 回答