为什么linkedhashmap维护迭代的双向链表
因为在任何线程中都没有内部和合理的解释。 请给我确切的理由。
-
对于插入顺序,它足以维持单链表,但为什么不呢?
-
双重链表如何在这种情况下提高性能?
-
所有方法都inheritance自hashmap xpt 4方法,然后hashmap的迭代器不维护顺序,而linkedhashmap维护顺序?
你是对的,你只需要维护一个单独的链表来跟踪插入顺序。 但是为了有效地维护单链表,你实际上需要一个双向链表。
按顺序考虑三个条目
A ---> B ---> C
假设你删除B
显然A
应该指向C
但除非你知道B
之前的条目,否则你无法有效地说出哪个条目现在指向C
要解决此问题,您需要输入指向两个方向。
---> ---> ABC <--- <---
这样,当您删除B
您只需查看B
( A
和C
)之前和之后的条目并进行更新,以便A
和C
指向。
LinkedHashMap
维护插入顺序的原因,而HashMap
没有,尽管除了4个方法之外的所有方法都是inheritance的,因为它写得非常巧妙。 大多数特定于实现的操作都是HashMap.Entry
成员,而不是HashMap
。 LinkedHashMap
有一个private static
类LinkedHashMap.Entry
,它扩展了HashMap
的static
类HashMap.Entry
。 例如,当您调用put
或remove
, LinkedHashMap
的代码可以与HashMap
的代码相同,因为它是跟踪信息之前和之后的条目本身 。 作为一个例子,这里是我在上面解释的LinkedHashMap.Entry.remove()
完整代码
private void remove() { before.after = after; after.before = before; }
LinkedHashMap基本上为每个条目维护两个指针,即: Before,After
顾名思义,这两个指针都用于排序目的,用于在插入或删除时调整指针。
为了维持插入顺序,有双重LinkedList。 在任何时候你都可以向前移动节点或向后节点。 但是如果你的指针移动到最后一个元素,你有单个LinkedList,你再次需要从初始点开始,你不能移动到前一个节点。
我还想补充的一点是LinkedHashMap也可以通过其构造函数将accessOrder boolean设置为true来用作LRU Cache。
现在LinkedHashMap维护两个指针head
(最长的LinkedHashMap)和tails
(最小的LinkedHashMap)。 因此,当您将accessOrder设置为true时请记住它停止维护插入顺序并开始表现得像正确的LRU缓存。
现在当LRU缓存超过其限制并且我们想要删除最老的条目时,因为它在内部维护DoublyLinkedList,删除最老的条目相对较快,因为它保持两个指针(头部和尾部)可以向两个方向移动或者我们可以说如果它是用于删除最旧条目的Singly LinkedList,我们需要遍历所有节点然后将其删除。 感谢指针的head
和tails
,只需删除最后一个节点(最旧的节点),然后在tails
指针的帮助下到达那里,并将最后一个节点的前一个指针作为LinkedHashMap中DoublyLinkedList的第二个最后一个节点tail
。
LinkedHashMap可用于维护插入顺序和维护访问顺序。 LinkedHashMapinheritance了hashmap中用于维护列表的hashmap的相同function,因此使用了下一个引用。
为了维护插入顺序,他们使用了双向链表( 在引用之前和之后使用),但这可以通过使用单链表来完成。 同时,他们必须实现访问顺序function,并且他们需要频繁地将元素移动到最后并且需要频繁删除频繁删除它们使用双向链表。