为什么linkedhashmap 维护双向链表迭代 [英] why linkedhashmap maintains doubly linked list for iteration
问题描述
因为在任何线程中都没有内部合理的解释.请给我确切的理由.
As there is no internal and reasonable explanation in any thread. Please give me exact reason.
对于插入顺序，用单向链表维护就足够了，但为什么不呢?
for the insertion order it is enough to maintain with singly linked list but why not?
在这种情况下，双向链表如何提高性能?
how doubly linked list increases performance in this scenario?
所有方法都继承自 hashmap xpt 4 方法，然后 hashmap 的迭代器不维护顺序，而 linkshashmap 维护顺序?
all the methods are inherited from the hashmap xpt 4 methods then an iterator for hashmap not maintains the order whereas the linkedhashmap maintains the order?
推荐答案
你说得对，你只需要维护一个单向链表来跟踪插入顺序.但是为了有效地维护一个单向链表，你实际上需要一个双向链表.
You are right that you only need to maintain a singly linked list to keep track of insertion order. But in order to efficiently maintain a singly linked list, you actually need a doubly linked list.
按顺序考虑三个条目
A ---> B ---> C
假设您删除了 B.显然A 现在应该指向C.但是除非您知道 B 之前的条目，否则您无法有效地确定哪个条目现在应该指向 C.要解决此问题，您需要指向两个方向的条目.
Suppose you remove B. Obviously A should now point to C. But unless you know the entry before B you cannot efficiently say which entry should now point to C. To fix this, you need entries to point in both directions.
---> --->
A B C
<--- <---
这样，当您删除 B 时，您只需查看 B 前后的条目(A 和 C) 并更新，以便 A 和 C 相互指向.
This way, when you remove B you can just look at the entries before and after B (A and C) and update so that A and C point to each other.
LinkedHashMap 维护插入顺序而 HashMap 不维护插入顺序的原因，尽管事实上除了 4 个方法之外的所有方法都被继承了，是因为它的编写非常巧妙.大多数特定于实现的操作都是 HashMap.Entry 的成员，而不是 HashMap 的成员.LinkedHashMap 有一个 private static 类 LinkedHashMap.Entry，它扩展了 static 类 HashMap.EntryHashMap 的代码>.例如，调用put或remove时，LinkedHashMap的代码可以与HashMap的代码相同> 因为是条目本身跟踪前后信息.例如，这里是我在上面解释的 LinkedHashMap.Entry.remove() 的完整代码
The reason LinkedHashMap maintains insertion order while HashMap doesn't, despite the fact that all but 4 methods are inherited, is that it's very cleverly written. Most implementation-specific operations are members of HashMap.Entry, not HashMap. LinkedHashMap has a private static class LinkedHashMap.Entry which extends the static class HashMap.Entry of HashMap. When you call put or remove, for example, the code for LinkedHashMap can be the same as the code for HashMap because it is the entries themselves that keep track of before and after information. As an example, here is the code in full for LinkedHashMap.Entry.remove() that I was explaining above
private void remove() {
before.after = after;
after.before = before;
}
这篇关于为什么linkedhashmap 维护双向链表迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
