首页 文章

Java HashMap中的冲突解决方案

提问于
浏览 次
46

Java HashMap 使用 put 方法在 HashMap 中插入K / V对 . 假设我使用了 put 方法，现在 HashMap<Integer, Integer> 有一个条目 key 为10， value 为17 .

如果我在此 HashMap 中插入10,20，由于相同的密钥10，它会因碰撞而将此条目替换为前一个条目 .

如果密钥碰撞 HashMap 用新的K / V对替换旧的K / V对 .

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

为什么它没有形成 linkedlist ，键为10，值为17,20？

java hashmap

9 回答

  • 71

    没有定义这样做 . 为了实现此功能，您需要创建一个将键映射到值列表的映射：

    Map<Foo, List<Bar>> myMap;

    或者，你可以使用the Multimap from google collections / guava libraries

    回复于
  • 14

    您的示例中没有冲突 . 您使用相同的密钥，因此旧值将替换为新值 . 现在，如果你使用两个映射到相同哈希码的键，那么你就会发生冲突 . 但即使在那种情况下，HashMap会取代你的 Value ！如果您希望在发生碰撞时将值链接起来，则必须自己进行，例如：通过使用列表作为值 .

    回复于
  • 8

    插入对 (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 方法完成的 .

    回复于
  • 2

    在 HashMap 中，键是一个对象，包含 hashCode() 和 equals(Object) 方法 .

    在Map中插入新条目时，它会检查 hashCode 是否已知 . 然后，它将使用此哈希码迭代所有对象，并使用 .equals() 测试它们的相等性 . 如果找到相等的对象，则新值将替换旧值 . 如果没有，它将在 Map 中创建一个新条目 .

    通常，在谈论 Map 时，当两个对象具有相同的 hashCode 但它们不同时，您使用 collision . 它们在内部存储在列表中 .

    回复于
  • 1

    事实上，它可能形成一个链表 . 只是 Map Contract 要求它替换条目：

    V put（K键，V值）将指定值与此映射中的指定键关联（可选操作） . 如果映射先前包含键的映射，则旧值将替换为指定的值 . （当且仅当m.containsKey（k）返回true时， Map m才包含密钥k的映射 . ）

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

    对于存储值列表的 Map ，它必须是 Multimap . 这里's Google' s：http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

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

    Edit: Collision resolution

    那有点不同 . 当两个不同的密钥碰巧具有相同的哈希码时发生冲突，或者具有不同哈希码的两个密钥碰巧映射到底层阵列中的同一个桶中 .

    考虑 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

    回复于
  • 0

    首先，你有一个哈希的概念有点错误，桑杰先生已经纠正了这个概念 .

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

    尽管从Java 8开始，链表被树替换（O（log n））

    回复于
  • 2

    碰撞和重复之间存在差异 . 碰撞意味着hashcode和bucket是相同的，但是一式两份，它将是相同的hashcode，同一个桶，但这里等于方法进入图片 .

    检测到碰撞，您可以在现有密钥上添加元素 . 但如果重复，它将取代新的 Value .

    回复于
  • 0

    你的情况不是在讨论冲突解决方案，它只是用相同密钥的新值替换旧值，因为Java的 HashMap 不能包含相同 key 的重复项（即多个 values ） .

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

    如果您尝试为同一个键设置不同的/新值，则它不是冲突解决的概念，而只是将旧值替换为相同键的新值 . 这是 HashMap 的设计方式，你可以看看下面的API（重点是我的）取自here .

    public V put（K key，V value）将指定值与此映射中的指定键关联 . 如果映射先前包含键的映射，则替换旧值 .

    另一方面，只有当已经存储了条目的 multiple keys end up with the same hashcode （即，它们落在相同的桶位置）时，冲突解决技术才起作用 . HashMap 使用链接的概念处理冲突解决方案，即它将值存储在链表中（或者自Java8以来的 balancer 树，取决于条目的数量） .

    回复于
  • 1

    当多个键最终存在于同一个存储桶中的相同哈希码中时 . 当相同的键具有不同的值时，旧值将替换为新值 .

    在最坏的情况下，喜欢的列表从病房的java 8版本转换为 balancer 的二进制树 .

    当2个不同的密钥生成相同的hashcode（）值时发生冲突 . 当存在更多冲突时，它将导致hashmap的最差性能 .

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

    回复于

相关问题