Shulou(Shulou.com)05/31 Report--

How to deeply interpret the LinkedHashMap principle and source code, I believe that many inexperienced people do not know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

LinkedHashMap, as its name implies, is a collection of two-way linked lists based on HashMap. HashMap is the structure of array plus one-way linked list, and LinkedList is realized by two-way linked list. And LinkedHashMap is the combination of the two.

First of all, in terms of source code, LinkedHashMap inherits from HashMap, so LinkedHashMap has most of the features of HashMap. For example: thread safety issues. About HashMap recommended reading "do not understand HashMap?" Just because you lack a flow chart of HashMap's principle and mechanism! ".

Looking down the source code of LinkedHashMap, you will find that LinkedHashMap provides five constructors. Basically, it extends the constructor of HashMap, adding an important parameter, accessOrder, which represents an access order, which will be discussed in detail later.

Note that another change in LinkedHashMap is the addition of two properties: header and accessOrder. Header is the header element of a two-way linked list. When accessOrder is true, it means to iterate in the order of access, and false means to iterate in the order of insertion. This picture is from the Internet, is based on JDK1.6, and now JDK8 has changed a lot.

LinkedHashMap inherits most of the methods in HashMap, but with two-way linked lists.

LinkedHashMap's Entry adds before and after variables for maintaining order, which are used to determine the front and back nodes of the linked list. The originally unordered array + linked list structure is related to it by before and after, and becomes ordered. When the bi-directional linked list is maintained in put and get, the traversal will be in order.

LinkedHashMap's node Entry inherits from HashMap.Node and then changes the one-way linked list to a two-way linked list.

LinkedHashMap does not override any put methods. But it overrides the newNode () method that builds the new node.

NewNode () is called in the putVal () method of HashMap, and the putVal () method is called when bulk inserting data putMapEntries (Map m, boolean evict) or inserting a single data public V put (K key, V value).

LinkedHashMap overrides newNode (), linking the new node to the end of the internal bi-directional linked list through linkNodeLast (p) each time a new node is built.

The linkNodeLast method will add the new node. If the collection is empty before, specify the head node; otherwise, connect the new node to the end of the linked list.

In addition, LinkedHashMap's afterNodeInsertion method is also very important, which will be called back after the new node is inserted to determine whether the oldest inserted node needs to be deleted based on evict and first.

LinkedHashMap also overrides the afterNodeRemoval method. When deleting node e, synchronization removes e from the two-way linked list.

In addition, the get () and getOrDefault () methods are also overridden. Because we have to adjust the specific acquisition method according to the accessOrder rules. If accessOrder is true, call back the void afterNodeAccess (Node e) function.

In the afterNodeAccess () function, the node e that is currently accessed is moved to the end of the internal two-way linked list.

Through the explanation of the above picture, you will find. The afterNodeAccess method buries the hidden trouble and modifies the modCount, so when you are iterating LinkedHashMap in accessOrder=true mode, if you query the access data at the same time, it will also lead to fail-fast, because the order of iteration has changed.

Finally, let's sum up. The source code ratio of LinkedHashMap to HashMap is very simple. Because it is easy to enjoy the cool under the big tree. It inherits HashMap and overrides only a few methods to change the order in which it iterates through time. This is also the biggest difference between it and HashMap. Each time data is inserted or accessed or modified, nodes are added or the node order of the linked list is adjusted. To determine the order of output during iteration.

AccessOrder, default is false, the order of output during iteration is the order in which the nodes are inserted.

If true, the output order is in the order in which the nodes are accessed.

When true, you can build a LruCache on top of this.

Refer to "hand-in-hand teaching you to build FIFO and LRU caching systems with LinkedHashMap"

LinkedHashMap does not override any put methods.

But it overrides the newNode () method to build new nodes. Each time you build a new node, link the new node at the end of the internal two-way linked list

In accessOrder=true mode, in the afterNodeAccess () function, the node e that is currently accessed is moved to the tail of the internal two-way linked list.

It is worth noting that the modCount is modified in the afterNodeAccess () function, so when you are iterating LinkedHashMap in accessOrder=true mode, if you query access data at the same time, it will also result in fail-fast, because the order of iterations has changed.

NextNode () is the next () method in the iterator.

As can be seen from the implementation of this method, iterative LinkedHashMap is the circular output starting from the header of the internally maintained double-linked list.

The order of double-linked list nodes will be updated when LinkedHashMap is added, deleted, changed, and checked.

To satisfy whether to output in insertion order or access order.

Compared to HashMap, it also has a small optimization that overrides the containsValue () method to traverse the internal linked list directly to compare whether the value values are equal.

After reading the above, have you mastered how to deeply interpret the principle of LinkedHashMap and the source code? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.