Shulou(Shulou.com)06/03 Report--

This article mainly shows you the "sample analysis of LinkedHashMap in java", which is easy to understand and clear. I hope it can help you solve your doubts. Let the editor lead you to study and study the "sample analysis of LinkedHashMap in java".

LinkedHashMap maintains the order of inserts.

Element storage relationship

Red and yellow arrows: element addition order

Blue arrow: storage order of elements in a single linked list

Head: linked list header

Tail: tail of linked list

Inheritance system

It inherits from HashMap, so it has all the glory HashMap has.

Attribute

Head of two-way linked list (oldest)

End of double linked list (minimum)

Subclass of HashMap.Node: regular LinkedHashMap node, adding before and after attributes to maintain the structure of two-way linked lists

The iterative sorting method for this LinkedHashMap:

True: access order

False (default): insert order

Construction method

Constructors always execute the constructor of the parent class HashMap first.

No parameter

Construct an empty LinkedHashMap instance that maintains the insertion order, with default initial capacity (16) and load factor (0.75).

Have a reference

To construct an empty LinkedHashMap instance, you can specify the initial capacity, load factor and sorting mode.

Construct a LinkedHashMap instance that maintains the insertion order, which has the same mapping relationship as the specified map, and the created LinkedHashMap instance has a default load factor of 0.75 and is sufficient to accommodate the initial capacity of the mapping in the specified map.

Let's start to look at how the main features of this class are implemented in code.

Access in insertion order

The default accessOrder of LinkedHashMap is false, which provides access in insertion order, and does not override the put method of the parent class HashMap. But in HashMap, put is the Node type node of HashMap, and the Entry of LinkedHashMap is different from its structure, so how to establish a two-way linked list? Let's take a look at the code related to LinkedHashMap insertion.

Ignoring the unrewritten put= > putValue code, let's look directly at the rewritten

NewNode

HashMap

LinkedHashMap rewriting

Control the addition of new nodes to the tail of the linked list, so that each new node is appended to the tail, which ensures the insertion order.

Continue to study linkNodeLast

LinkNodeLast

Add a new node and append it to the end of the linked list.

`/ / link at the end of list``private``void`` linkNodeLast (LinkedHashMap.Entry p) {``LinkedHashMap.Entry last = tail;`` / added to the tail node ``if`` / / last is null, indicating that the linked list is empty ``if`` (last = = `null``) ``head = p; ``/ / the linked list is not empty, and the relationship between the new node and the previous tail node ``else` {`` / / connects the new node p directly to the tail ```p.before = last; ``last.after = p; `} ``}``

From this, we know that through the new header and tail node on the basis of HashMap, the before and after attributes of the node, we can directly append the node to the tail node each time we add it, and then we can achieve the purpose of maintaining the linked list structure according to the insertion order.

Steps to create a graphical linked list

The blue part is HashMap's method.

The orange part is unique to LinkedHashMap.

Note that although LinkedHashMap is also a two-way linked list, it only provides one-way access from beginning to end in the order of insertion, which is not as good as LinkedList.

LinkedHashMap is accessed through an iterator and is accessed from the beginning node by default

During the iteration, the traversal can be completed by constantly visiting the after node.

Check at 1 place

2 find the successor node through the after attribute of the node

Deletion of linked list nodes

Callbacks saved in HashMap that allow LinkedHashMap post-processing

Like the insert operation, the code related to the LinkedHashMap delete operation is implemented directly with the parent class. When you delete a node, the parent class does not fix the bi-directional linked list of LinkedHashMap. So after deleting the node, how can the deleted node be safely removed from the double-linked list? In fact, after the node is deleted, the callback method afterNodeRemoval will be called. LinkedHashMap overrides this method.

`/ e is the deleted node ``void`` afterNodeRemoval (Node e) {``/ unlink`LinkedHashMap.entry p =`` (LinkedHashMap.Entry) e, b = p.before, a = p.head; ``/ sets the predecessor and successor reference of p node to null, auxiliary GC``p.before = p.after = ``null``;` / / LinkedHashMap.entry p is the head node `if`` (b = = `null``)`` head = a ``else ``/ otherwise connect the precursor node of p to the successor node of p`` b.after = a; ``/ / an is null, indicating that p is the tail node ``if`` (a = = `null``) ``tail = b; otherwise connect the precursor node of a to b``a.before = b;``} `

The main process for deleting an element:

Locate the bucket position according to hash

Traverse the linked list or call the deletion method related to the red-black tree

Remove the node to be deleted from the double-linked list maintained by LinkedHashMap

Rollover failed and re-upload canceled

LRU (Least recently used, least recently used) Chestnut

Frequently accessed elements are appended to the end of the queue so that infrequently accessed data is naturally close to the head of the line, and then you can delete the header node by setting a deletion policy, such as when the number of Map elements is greater than

The element is moved to the end of the line

When get, the element is moved to the end of the line:

`public``V get (Object key) {``Node e;`` / / call the HashMap get method ``if`` (e = getNode (hash (key), key)) = = ``null``; ``/ / if the LRU policy ``if`` (accessOrder) `` / / this method moves the current key to the end of the line ``afterNodeAccess (e); ``valun`e.value`; `} `

From the above source code, you can see that the current visiting node is moved to the end of the queue through the afterNodeAccess method, not only the get method, but also when executing the getOrDefault, compute, computeIfAbsent, computeIfPresent, and merge methods. By constantly moving the frequently visited node to the end of the queue, then the node close to the head of the queue is naturally an element that is rarely visited.

The above is all the content of the article "sample Analysis of LinkedHashMap in java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.