我知道我的问题与之前发布的问题非常相似.我已经通过了多个帖子,但仍然不太清楚答案.这就是为什么我再次发布它.

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

在上一篇文章的回答中,提到LinkedHashMap为删除提供了O(1)复杂性,因为它有前一个和下一个元素指针,但我认为HashMap也提供O(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;
}

使用单链表不能在恒定时间内完成.