Java – why does LinkedHashMap maintain iterations of two-way linked lists

Because there is no internal and reasonable explanation in any thread

>For insertion order, it's enough to maintain a single link list, but why not? > How can a double linked list increase performance in this case? > All methods are inherited from HashMap XPT 4 method, so HashMap iterator will not maintain order, but LinkedHashMap will maintain order?

Solution

You are right. You only need to maintain a single linked list to track the insertion order But in order to maintain a single linked list effectively, you actually need a two - way linked list

Consider the order of three items

A ---> B ---> C

Suppose you delete B. obviously, a should now point to C. but unless you know the entry before B, you can't effectively explain which entry should point to C. to solve this problem, you need to enter two directions

--->   ---> 
A      B      C
  <---   <---

In this way, when you delete B, you only need to view the entries before and after B (A and C) and update them so that a and C point to each other

LinkedHashMap maintains the reason for the insertion order, while HashMap does not, although it is very smart except for four methods Most implementation specific operations are HashMap Entry, not HashMap LinkedHashMap has a private static class LinkedHashMap Entry, which extends HashMap's static class HashMap Entry. When you call put or remove, for example, the code of LinkedHashMap can be the same as that of HashMap, because it is before and after the tracking information of the item itself As an example, here is the LinkedHashMap I explained above Entry. Complete code for remove()

private void remove() {
    before.after = after;
    after.before = before;
}