由于任何一个线程中都没有内部和合理的解释,请给我提供确切的原因。
对于插入顺序,使用单向链表足以维护,但为什么不采用呢?
双向链表在这种情况下如何提高性能?
所有的方法都是从哈希映射继承而来的,即使哈希映射只有4个方法,然后仅有一个迭代器,而LinkedHashMap却维护了顺序,为什么?
由于任何一个线程中都没有内部和合理的解释,请给我提供确切的原因。
对于插入顺序,使用单向链表足以维护,但为什么不采用呢?
双向链表在这种情况下如何提高性能?
所有的方法都是从哈希映射继承而来的,即使哈希映射只有4个方法,然后仅有一个迭代器,而LinkedHashMap却维护了顺序,为什么?
你说得对,只需要维护一个单向链表就可以跟踪插入顺序。但是为了有效地维护单向链表,你实际上需要一个双向链表。
考虑按顺序排列的三个条目
A ---> B ---> C
假设你移除了B
。显然,A
现在应该指向C
。但是,除非你知道B
之前的条目,否则你无法高效地说出现在应该将哪个条目指向C
。为了解决这个问题,你需要让条目双向指向。
---> --->
A B C
<--- <---
这样,当你移除B
时,你只需要查看B
之前和之后的条目(A
和C
),并更新A
和C
指向彼此。
LinkedHashMap
保持插入顺序而 HashMap
不保持的原因是它写得非常巧妙。大多数特定于实现的操作都是 HashMap.Entry
的成员,而不是 HashMap
的成员。 LinkedHashMap
有一个私有静态类 LinkedHashMap.Entry
,它扩展了 HashMap
的静态类 HashMap.Entry
。例如,当你调用 put
或 remove
时,LinkedHashMap
的代码可以与 HashMap
的代码相同,因为是条目本身跟踪前面和后面的信息。以下是我上面解释的LinkedHashMap.Entry.remove()
的完整代码示例:
private void remove() {
before.after = after;
after.before = before;
}
LinkedHashMap基本上为每个条目维护两个指针 -:
Before , After
顾名思义,这两个指针都用于排序目的,并在插入或删除时用于调整指针。
LinkedHashMap.keySet().iterator()
返回的是一个普通的 Iterator
而不是一个 ListIterator
。无论是否使用双向链表,都不能以相反的插入顺序迭代键。API 不允许这样做。 - Stephen C我想补充的一件事是,LinkedHashMap也可以通过设置它的构造函数中的accessOrder布尔值为true来作为LRU缓存使用。
现在,LinkedHashMap维护两个指针head(LinkedHashMap中最老的)和tails(LinkedHashMap中最年轻的)。所以请记住,当您将accessOrder设置为true时,它停止维护插入顺序,并开始像一个合适的LRU缓存一样运行。
现在当LRU缓存超过其限制并且我们想要删除最老的条目时,由于它内部维护了DoublyLinkedList,所以删除最老的条目相对较快,因为它维护了两个指针(head和tails),这些指针可以向两个方向移动,或者我们可以说如果它是一个Singly LinkedList,为了删除最古老的条目,我们需要遍历所有节点,然后再删除它。由于有指针head和tails的帮助,我们只需到达那里并通过将最后一个节点(最古老的节点)删除来使最后一个节点的前面指针成为LinkedHashMap中的第二个尾巴节点,从而轻松完成操作。
reversed
方法,该方法提供了地图的反向视图。为了有效地反向迭代列表以提供这个视图,需要使用后向链接。LinkedHashMap 可以用于维护插入顺序和访问顺序。 LinkedHashMap 继承了 HashMap 的相同功能,用于在 bucket 中维护列表,所以使用 next 引用。
为了维护插入顺序,它们使用双向链表 (使用 before 和 after 引用),但这也可以通过使用单向链表来完成。同时,他们还需要实现访问顺序功能,并且需要将元素频繁移动到末尾,这需要频繁删除,因此他们使用了双向链表。