为什么linkedhashmap维护迭代的双向链表

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?

双重链表如何在这种情况下提高性能？
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?

所有方法都继承自hashmap xpt 4方法，然后hashmap的迭代器不维护顺序，而linkedhashmap维护顺序？

5 个解决方案

#1

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.

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

Consider three entries in order

按顺序考虑三个条目

A ---> 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.

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

  --->   ---> 
A      B      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.

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

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

LinkedHashMap维护插入顺序的原因，而HashMap没有，尽管除了4个方法之外的所有方法都是继承的，因为它写得非常巧妙。大多数特定于实现的操作都是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;
}

#2

The LinkedHashMap basically maintains two pointers for each entry namely -: Before , After

LinkedHashMap基本上为每个条目维护两个指针，即：Before，After

as the name suggest both the pointers are used for the ordering purpose and are used to adjust the pointers in case of insertions or deletions.

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

#3

To maintain Insertion Order there is doubly LinkedList. AT any point of time you can move ahead node or backward Node. But if you are having single LinkedList if your Pointer moved to last element you again need to start from initial point and you can not moved on previous node.

为了维持插入顺序，有双重LinkedList。在任何时候你都可以向前移动节点或向后节点。但是如果你的指针移动到最后一个元素，你有单个LinkedList，你再次需要从初始点开始，你不能移动到前一个节点。

#4

One thing I would also like to add is that LinkedHashMap can also be used as an LRU Cache by setting it's accessOrder boolean to true via its constructor.

我还想补充的一点是LinkedHashMap也可以通过其构造函数将accessOrder boolean设置为true来用作LRU Cache。

Now LinkedHashMap maintains two pointers head(eldest of the LinkedHashMap) and tails(youngest of the LinkedHashMap). So keep in mind when you set accessOrder to true it stops maintaining the insertion-order and starts behaving like a proper LRU cache.

现在LinkedHashMap维护两个指针head（最长的LinkedHashMap）和tails（最小的LinkedHashMap）。因此，当您将accessOrder设置为true时请记住它停止维护插入顺序并开始表现得像正确的LRU缓存。

Now when LRU cache exceeds its limit and we want to remove the eldest entry, as it maintains DoublyLinkedList internally the removal of eldest entry is comparatively fast, as it maintains two pointers(head and tails) which can move in both directions or we can say if it was a Singly LinkedList for removing eldest entry we need to traverse all the nodes and then remove it. Thanks to pointers head and tails it can easily be done by just removing the last node(eldest one) by reaching there with help of tails pointer and taking that last node's previous pointer to make second last node tail of the DoublyLinkedList in LinkedHashMap.

现在当LRU缓存超过其限制并且我们想要删除最老的条目时，因为它在内部维护DoublyLinkedList，删除最老的条目相对较快，因为它保持两个指针（头部和尾部）可以向两个方向移动或者我们可以说如果它是用于删除最旧条目的Singly LinkedList，我们需要遍历所有节点然后将其删除。感谢指针的头部和尾部，只需删除最后一个节点（最旧的节点），然后在tails指针的帮助下到达那里，并将最后一个节点的前一个指针作为LinkedHashMap中DoublyLinkedList的第二个最后一个节点尾部。

#5

-1

LinkedHashMap can be used for maintaining the insertion order and for maintaining the access order. LinkedHashMap inherited the same functionality of hashmap for maintain list in bucket,so used next reference.

LinkedHashMap可用于维护插入顺序和维护访问顺序。 LinkedHashMap继承了hashmap中用于维护列表的hashmap的相同功能，因此使用了下一个引用。

For maintaining the insertion order they used doubly linked list(used before and after reference),but that can be done by using singly linked list. At the same time they have to achieve the access order functionality and in that they need frequent movement of the element to the end and that require frequent deletion for frequent deletion they used doubly linked list .

为了维护插入顺序，他们使用了双向链表（在引用之前和之后使用），但这可以通过使用单链表来完成。同时，他们必须实现访问顺序功能，并且他们需要频繁地将元素移动到最后并且需要频繁删除频繁删除它们使用双向链表。

#1