LinkedHashMap和HashMap中的删除操作有什么不同？

Question

LinkedHashMap 中的删除操作需要线性时间，这是正确的吗？因为我们需要从维护插入顺序的链表中删除键，这需要 O(n) 的时间。在普通的 HashMap 中，删除操作只需要常数时间。

- user1745356

---

参考特定链表节点的引用已存储在条目内部，因此删除时间复杂度也为O(1)。 - Alex Salauyou

@SashaSalauyou，没错，这很有道理。如果你发布你的答案，我会接受它，因为你明确指出了它为什么是常数。 - user1745356

谢谢，但我认为这不是一个答案，只是一条评论 =) - Alex Salauyou

Answer 1

根据 Javadocs，它并不是这样的：

该类提供了所有可选的 Map 操作，并允许 null 元素。像 HashMap 一样，它对于基本操作（add、contains 和 remove）提供了常量级别的性能，假设哈希函数在桶之间正确地分散元素。由于额外维护链表的开销，性能可能略低于 HashMap，唯一的例外是 LinkedHashMap 的 collection-views 迭代需要与 map 的大小成比例的时间。对 HashMap 的迭代可能会更加昂贵，需要花费与其容量成比例的时间。 LinkedHashMap 不覆盖 HashMap#remove(Object key) 方法。后者从表中删除与键对应的条目，并在删除的条目上调用 recordRemoval() 方法，该方法调整前一个和后一个链接到被删除的条目。没有迭代列表以按索引删除节点。

- M A

Answer 2

LinkedHashMap使用一个继承自HashMap.Entry的Entry，因此成本更高但仍然是恒定的。

每次在HashMap中删除一个条目时，都会调用recordRemoval(HashMap m)方法。HashMap.Entry中的实现为空，但LinkedHasMap.Entry会从列表中删除该条目。

/**
 * Removes this entry from the linked list.
 */
private void remove() {
    before.after = after;
    after.before = before;

以下是操作顺序：

该段代码如下：

• remove implementation in HashMap calls removeEntryForKey (HashMap:line551)

  public V remove(Object key) {
      Entry<K,V> e = removeEntryForKey(key);
      return (e == null ? null : e.value);
  }
  

• removeEntryForKey in HashMap calls entry.recordRemoval(this) (HashMap:line560)

  final Entry<K,V> removeEntryForKey(Object key) {
      [...]
      while (e != null) {
          Entry<K,V> next = e.next;
          Object k;
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k)))) {
              [...]
              e.recordRemoval(this);
              return e;
          }
          prev = e;
          e = next;
      }
      return e;
  }
  

• recordRemoval implementation in LinkedHasMap.Entry calls remove method above, which is O(1) (LinkedHashMap:line357)

  void recordRemoval(HashMap<K,V> m) {
      remove();
  }
  

HashMap的源代码可以在以下链接中找到: http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/HashMap.java 而LinkedHashMap的源代码则可以在以下链接中找到: http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/LinkedHashMap.java

- juanotto