在 LinkedHashMap 中使用双向链表而不是单链表

Question

我知道我的问题与 posted previously.I 已经经历了多次 post 的问题非常相似，但仍然不太清楚 answer.That 这就是我 post 再次使用它的原因。

Why Linked HashMap uses doubly LinkedList over Single LinkedList while order can also be maintained through Single LinkedList.

在之前post的一些回答中提到LinkedHashMap提供了O(1)的删除复杂度，因为它有前一个和下一个元素指针，但我认为HashMap也提供了O(1)删除。

谢谢，

Answer 1

i think HashMap also provides O(1) for deletion

没错，但是 HashMap 不必保持键的顺序。因此，当删除条目时，只需修改删除条目的桶的小链表（在Java 8 之前的实现中。Java 8 实现使用树），这应该需要 O(1) 时间。

另一方面，

LinkedHashMap 必须保持将键添加到 Map 的顺序，它使用包含 Map 所有条目的附加链表来实现。因此，当你删除一个条目时，如果你无法访问这个大链表中的前一个条目，你将不得不从头开始遍历链表直到找到它，这将需要线性时间。

您可以在此处查看删除条目后 LinkedHashMap 的作用：

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

单向链表无法在恒定时间内完成此操作。

在 LinkedHashMap 中使用双向链表而不是单链表

Use of doubly Linked List in LinkedHashMap over Single LinkedList

java

linkedhashmap