为什么linkedhashmap维护迭代的双向链表

Question

因为在任何线程中都没有内部和合理的解释.请给我确切的理由.

1. 对于插入顺序,它足以维持单链表,但为什么不呢？

2. 双重链表如何在这种情况下提高性能？

3. 所有方法都是从hashmap xpt 4方法继承的,然后hashmap的迭代器不维护顺序,而linkedhashmap维护顺序？

Answer 1

你是对的,你只需要维护一个单独的链表来跟踪插入顺序.但是为了有效地维护单链表,你实际上需要一个双向链表.

按顺序考虑三个条目

A ---> B ---> C

假设你删除B.显然A现在应该指出C.但除非你知道这个条目,否则你B无法有效地说出现在应该指向哪个条目C.要解决此问题,您需要指向两个方向的条目.

  --->   ---> 
A      B      C
  <---   <---

这样,当你删除B你可以看看之前和之后的条目B(A和C)和更新,以便A与C指向对方.

LinkedHashMap维持插入顺序的原因HashMap是,尽管除了4种方法之外的所有方法都是继承的,但它是非常巧妙地编写的.大多数特定于实现的操作都是成员HashMap.Entry,而不是HashMap.LinkedHashMap具有private static类LinkedHashMap.Entry扩展了static类HashMap.Entry的HashMap.当你打电话put或者remove,例如,代码LinkedHashMap可以与代码相同,HashMap因为它是条目本身跟踪信息之前和之后.作为一个例子,这里是LinkedHashMap.Entry.remove()我正在解释的完整代码

private void remove() {
    before.after = after;
    after.before = before;
}

Answer 2

为了维护插入顺序，有双重链表。在任何时间点，您都可以向前移动节点或向后移动节点。但是，如果您有单个 LinkedList，如果您的指针移动到最后一个元素，您再次需要从初始点开始，并且不能移动到上一个节点。