logo标签列表

为什么LinkedHashMap维护双向链表来进行迭代

javaperformance
15

由于任何一个线程中都没有内部和合理的解释，请给我提供确切的原因。

  1. 对于插入顺序，使用单向链表足以维护，但为什么不采用呢？

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

  3. 所有的方法都是从哈希映射继承而来的，即使哈希映射只有4个方法，然后仅有一个迭代器，而LinkedHashMap却维护了顺序，为什么？

我认为双向链表并不能帮助排序，它只是使遍历链表更容易。 - Kick Buttowski
2
它并不会使遍历更容易，只是使地图条目的删除更有效率。 - Stephen C
这样你就可以倒退了。 - user207421
6个回答
17

你说得对，只需要维护一个单向链表就可以跟踪插入顺序。但是为了有效地维护单向链表，你实际上需要一个双向链表。

考虑按顺序排列的三个条目

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;
}
简洁明了，易于理解。 - Basixp
非常感谢！现在我明白为什么单向链表不够用了。 - aatif
3

LinkedHashMap基本上为每个条目维护两个指针 -:

Before , After

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

1
为了维护插入顺序，需要使用双向链表。在任何时候都可以向前或向后移动节点。但是如果只有单向链表，当指针移动到最后一个元素时，您需要从初始点重新开始，并且无法移动到上一个节点。
2
我认为双向链表并不能帮助排序，它只是使遍历链表更容易。 - Kick Buttowski
如果你从内部看HashMap，它是基于LinkedList的。因此，如果您拥有诸如哪个节点在之前或之后插入的信息，那就是简单的排序。 - Prashant
单向链表足以维护顺序。这不是为什么在这种情况下使用双向链表的正确解释。 - Stephen C
2
需要注意的是，LinkedHashMap.keySet().iterator() 返回的是一个普通的 Iterator 而不是一个 ListIterator。无论是否使用双向链表，都不能以相反的插入顺序迭代键。API 不允许这样做。 - Stephen C
0

我想补充的一件事是，LinkedHashMap也可以通过设置它的构造函数中的accessOrder布尔值为true来作为LRU缓存使用。

现在，LinkedHashMap维护两个指针head(LinkedHashMap中最老的)和tails(LinkedHashMap中最年轻的)。所以请记住，当您将accessOrder设置为true时，它停止维护插入顺序，并开始像一个合适的LRU缓存一样运行。

现在当LRU缓存超过其限制并且我们想要删除最老的条目时，由于它内部维护了DoublyLinkedList，所以删除最老的条目相对较快，因为它维护了两个指针(head和tails)，这些指针可以向两个方向移动，或者我们可以说如果它是一个Singly LinkedList，为了删除最古老的条目，我们需要遍历所有节点，然后再删除它。由于有指针head和tails的帮助，我们只需到达那里并通过将最后一个节点(最古老的节点)删除来使最后一个节点的前面指针成为LinkedHashMap中的第二个尾巴节点，从而轻松完成操作。

0
其他答案已经解释了为什么目前需要双向链表。Java 21还增加了一个额外的原因：在LinkedHashMap中添加了一个reversed方法，该方法提供了地图的反向视图。为了有效地反向迭代列表以提供这个视图，需要使用后向链接。
-1

LinkedHashMap 可以用于维护插入顺序和访问顺序。 LinkedHashMap 继承了 HashMap 的相同功能，用于在 bucket 中维护列表，所以使用 next 引用。

为了维护插入顺序，它们使用双向链表 (使用 before 和 after 引用)，但这也可以通过使用单向链表来完成。同时，他们还需要实现访问顺序功能，并且需要将元素频繁移动到末尾，这需要频繁删除，因此他们使用了双向链表。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接