Java HashMap中的冲突解决

Question

JavaHashMap使用put方法在HashMap中插入K/V对。假设我使用了put方法，现在HashMap

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

如果密钥冲突，HashMap将用新的K/V对替换旧的K/V对。

所以我的问题是，HashMap何时使用链式冲突解决技术？

为什么它没有形成键为10，值为17,20的链接列表？




Answer 1

匿名用户

事实上，它本可以形成一个链接列表。只是Mapcontract要求它替换条目：

V put（K键，V值）

将指定值与此映射中的指定键关联（可选操作）。如果映射之前包含键的映射，则旧值将替换为指定值。（map m被称为包含密钥k的映射，当且仅当m.containsKey（k）返回true。）

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

对于存储值列表的映射，它需要是一个多映射。以下是谷歌的：http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

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

编辑：冲突解决

这有点不同。当两个不同的键恰好具有相同的哈希代码，或者两个具有不同哈希代码的键恰好映射到基础数组中的同一个bucket时，就会发生冲突。

考虑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。条目。通过查看源代码，您可以自己查看：

HashMap的GrepCode

Answer 2

在HashMap中，键是一个对象，它包含hashCode（）和equals（object）方法。

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

通常，谈到映射，当两个对象具有相同的hashCode但它们不同时，您会使用碰撞。它们内部存储在列表中。

Answer 3

当您插入对（10,17）然后（10,20）时，从技术上讲不涉及冲突。您只是用给定键的新值替换旧值10（因为在这两种情况下，10都等于10，并且10的哈希码始终为10）。

当多个键散列到同一个存储桶时，会发生冲突。在这种情况下，您需要确保能够区分这些键。链式冲突解决是用于此目的的技术之一。

例如，假设两个字符串“abra ka dabra”和“wave my wand”分别产生哈希码100和200。假设总数组大小为10，则它们最终都位于同一个存储桶中（100%10和200%10）。链接确保无论何时进行映射。获取（“abra ka dabra”） ，则最终得到与键关联的正确值。对于Java中的哈希映射，这是通过使用equals方法实现的。