为什么链接哈希映射维护双链表进行迭代

performance java

2022-09-03 14:03:35

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

对于插入顺序，使用单链表进行维护就足够了，但为什么不呢？
在这种情况下，双重链表如何提高性能？
所有的方法都是从哈希映射xpt 4方法继承的，那么哈希映射的迭代器不维护顺序，而linkedhashmap保持顺序？

答案 1

您是对的，您只需要维护一个单链表来跟踪广告订单。但是，为了有效地维护单个链表，您实际上需要一个双链表。

按顺序考虑三个条目

A ---> B ---> C

假设您删除了 .显然，现在应该指向。但是，除非您之前知道该条目，否则您无法有效地说出哪个条目现在应该指向。要解决此问题，您需要将条目指向两个方向。BACBC

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

这样，当您删除时，您只需查看（和）之前和之后的条目，然后进行更新，以便相互指向。BBACAC

尽管除了4种方法之外，其他所有方法都继承了，但保持广告顺序而没有的原因在于它写得非常巧妙。大多数特定于实现的操作都是的成员，而不是。有一个类，该类扩展了类。例如，当您调用或时，的代码可以与的代码相同，因为正是条目本身跟踪了之前和之后的信息。例如，这是我上面解释的完整代码LinkedHashMapHashMapHashMap.EntryHashMapLinkedHashMapprivate staticLinkedHashMap.EntrystaticHashMap.EntryHashMapputremoveLinkedHashMapHashMapLinkedHashMap.Entry.remove()

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

答案 2

LinkedHashMap基本上为每个条目维护两个指针，即-：之前，之后

顾名思义，这两个指针都用于排序目的，并用于在插入或删除的情况下调整指针。