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

In this issue, the editor will bring you about the role of LinkedHashMap in Java. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

The explanation of put () method.

Final V putVal (int hash, K key, V value, boolean onlyIfAbsent

Boolean evict) {

HashMap.Node [] tab; HashMap.Node p; int n, i

/ / ①, when the array table is null, call the resize method to create an array of the default size

If ((tab = table) = = null | | (n = tab.length) = = 0)

N = (tab = resize ()) .length

/ / ②, calculate the subscript, and fill in if there is no value in this position

If ((p = tab [I = (n-1) & hash]) = = null)

Tab [I] = newNode (hash, key, value, null)

}

The formula I = (n-1) & the calculated value of hash does not insert the key-value pair into the array according to the ordered subscript 0, 1, 2, 3, 4, 5, but has a certain degree of randomness.

Then LinkedHashMap arises at the historic moment for this demand. LinkedHashMap inherits HashMap, so HashMap also has the function of key-value pairs.

Public class LinkedHashMap

Extends HashMap

Implements Map {}

In addition, a bi-directional linked list is appended inside LinkedHashMap to maintain the insertion order of elements. Notice the before and after in the following code, which are used to maintain the order of the previous element and the next element of the current element.

Static class Entry extends HashMap.Node {

LinkedHashMap.Entry before, after

Entry (int hash, K key, V value, HashMap.Node next) {

Super (hash, key, value, next)

}

}

With regard to the two-way linked list, students can look back at the LinkedList article I wrote, which will be of great help to understand the LinkedHashMap of this article.

Before continuing with the following content, I would like to post a picture to add a little fun to everyone-look at my mind. UUID used "funny" and "you" in the title of the article, only to see such a happy message below.

I don't know whether I know or not. (then LinkedHashMap also uses "you" and "funny". I don't know if anyone will continue to sit in the seat. I feel very happy when I think about it.

01. Insertion order

In the HashMap article, I explained one thing, I don't know if the students remember, that is, null will be inserted into the first place of HashMap.

Map hashMap = new HashMap ()

HashMap.put ("Shen", "Silence II")

HashMap.put (Silence, Silence II)

HashMap.put ("King", "Silent King II")

HashMap.put ("two", "Silence two")

HashMap.put (null, null)

For (String key: hashMap.keySet ()) {

System.out.println (key + ":" + hashMap.get (key))

}

The result of the output is:

Null: null

Silent: silent King II

Shen: silent King II

Wang: silent King II

Two: silent King II

Although null's last put went in, he ran to the first place when traversing the output.

Let's take a look at LinkedHashMap again.

Map linkedHashMap = new LinkedHashMap ()

LinkedHashMap.put ("Shen", "Silence II")

LinkedHashMap.put (Silence, Silence II)

LinkedHashMap.put ("King", "Silent King II")

LinkedHashMap.put ("two", "Silence two")

LinkedHashMap.put (null, null)

For (String key: linkedHashMap.keySet ()) {

System.out.println (key + ":" + linkedHashMap.get (key))

}

The output is as follows:

Shen: silent King II

Silent: silent King II

Wang: silent King II

Two: silent King II

Null: null

Null is inserted in the last bit and output in the last bit.

The output proves once again that HashMap is unordered and LinkedHashMap can maintain the insertion order.

So how does LinkedHashMap do this? I believe that the students, like me, would very much like to know why.

To figure it out, you need to take a deep look at the source code of LinkedHashMap. Instead of overriding the put () method of HashMap, LinkedHashMap overrides the internal method newNode () that the put () method needs to call.

HashMap.Node newNode (int hash, K key, V value, HashMap.Node e) {

LinkedHashMap.Entry p =

New LinkedHashMap.Entry (hash, key, value, e)

LinkNodeLast (p)

Return p

}

As mentioned earlier, LinkedHashMap.Entry inherits HashMap.Node and appends two fields, before and after.

Then let's take a look at the linkNodeLast () method:

Private void linkNodeLast (LinkedHashMap.Entry p) {

LinkedHashMap.Entry last = tail

Tail = p

If (last = = null)

Head = p

Else {

P.before = last

Last.after = p

}

}

See, when LinkedHashMap adds the first element, it assigns the head to the first element, and when the second element is added, the before of the second element is assigned to the first element, and the afer of the first element is assigned to the second element.

This ensures that the key-value pairs are arranged in the order of insertion, okay?

Note: the version of JDK I am using is 14.

02. Access order

LinkedHashMap can maintain not only the insertion order, but also the access order. Access includes calling the get () method, the remove () method, and the put () method.

To maintain the access order, we need to specify three parameters when declaring the LinkedHashMap.

LinkedHashMap map = new LinkedHashMap (16, .75f, true)

The first parameter and the second parameter, which should be familiar to students who have seen HashMap, refer to the initial capacity and load factor.

If the third parameter is true, it means that LinkedHashMap maintains the access order; otherwise, it maintains the insertion order. The default is false.

Map linkedHashMap = new LinkedHashMap (16, .75f, true)

LinkedHashMap.put ("Shen", "Silence II")

LinkedHashMap.put (Silence, Silence II)

LinkedHashMap.put ("King", "Silent King II")

LinkedHashMap.put ("two", "Silence two")

System.out.println (linkedHashMap)

LinkedHashMap.get ("default")

System.out.println (linkedHashMap)

LinkedHashMap.get ("King")

System.out.println (linkedHashMap)

The result of the output is as follows:

{Shen = Silent King 2, Silent King 2}

{Shen = Silence King two, King = Silence King two, Silence King two, Silence King two}

{Shen = Silent King 2, Silent King 2}

When we use the get () method to access the element of the key "silent", in the output result, the silent king two is at the end; when we visit the element of the key "king", the output result is the king = silent king second at the end, and the silent king two is in the penultimate place.

In other words, the least frequently visited is on the head, which is interesting. What's so interesting?

We can use LinkedHashMap to implement LRU caching. LRU, an acronym for Least Recently Used, which is the least recently used, is a commonly used page replacement algorithm that chooses the most recently unused pages to be eliminated.

Public class MyLinkedHashMap extends LinkedHashMap {

Private static final int MAX_ENTRIES = 5

Public MyLinkedHashMap (

Int initialCapacity, float loadFactor, boolean accessOrder) {

Super (initialCapacity, loadFactor, accessOrder)

}

@ Override

Protected boolean removeEldestEntry (Map.Entry eldest) {

Return size () > MAX_ENTRIES

}

}

MyLinkedHashMap is a custom class that inherits LinkedHashMap and overrides the removeEldestEntry () method-- so that Map can hold up to five elements, which will be eliminated.

Let's test it.

MyLinkedHashMap map = new MyLinkedHashMap (16pr. 0.75fjre true)

Map.put ("Shen", "Silence II")

Map.put (Silence, Silence II)

Map.put ("King", "Silent King II")

Map.put ("two", "Silence two")

Map.put ("an interesting programmer", "an interesting programmer")

System.out.println (map)

Map.put ("an attractive programmer", "a good-looking programmer")

System.out.println (map)

Map.put (a talented programmer, a talented programmer)

System.out.println (map)

The output is as follows:

{Shen = Silent King two, an interesting programmer = an interesting programmer}

{Silence = Silence King two, King = Silence King two, Silence King two, an interesting programmer = an interesting programmer, a good-looking programmer = a good-looking programmer}

{Wang = Silent Wang 2, 2 = Silent Wang 2, an interesting programmer = an interesting programmer, a good-looking programmer = a good-looking programmer, a talented programmer = a talented programmer}

Shen = Silence Wang II and Silence King II were eliminated in turn.

If you get the element with the key "default" before put "A talented programmer":

MyLinkedHashMap map = new MyLinkedHashMap (16pr. 0.75fjre true)

Map.put ("Shen", "Silence II")

Map.put (Silence, Silence II)

Map.put ("King", "Silent King II")

Map.put ("two", "Silence two")

Map.put ("an interesting programmer", "an interesting programmer")

System.out.println (map)

Map.put ("an attractive programmer", "a good-looking programmer")

System.out.println (map)

Map.get ("default")

Map.put (a talented programmer, a talented programmer)

System.out.println (map)

Then the output changes, right?

{Shen = Silent King two, an interesting programmer = an interesting programmer}

{Silence = Silence King two, King = Silence King two, Silence King two, an interesting programmer = an interesting programmer, a good-looking programmer = a good-looking programmer}

{2 = Silent King 2, an interesting programmer = an interesting programmer, a good-looking programmer = a good-looking programmer, silent = Silent Wang 2, a talented programmer = a talented programmer}

Shen = silent king two and king = silent king two is out.

So how does LinkedHashMap maintain the access order? If the students are interested, you can study the following three methods.

Void afterNodeAccess (Node p) {}

Void afterNodeInsertion (boolean evict) {}

Void afterNodeRemoval (Node p) {}

AfterNodeAccess () is called when the get () method is called, afterNodeInsertion () is called when the put () method is called, and afterNodeRemoval () is called when the remove () method is called.

Let me take afterNodeAccess () as an example to explain.

Void afterNodeAccess (HashMap.Node e) {/ / move node to last

LinkedHashMap.Entry last

If (accessOrder & & (last = tail)! = e) {

LinkedHashMap.Entry p =

(LinkedHashMap.Entry) e, b = p.before, a = p.after

P.after = null

If (b = = null)

Head = a

Else

B.after = a

If (a! = null)

A.before = b

Else

Last = b

If (last = = null)

Head = p

Else {

P.before = last

Last.after = p

}

Tail = p

+ + modCount

}

}

The element that is get will be placed last. Do you understand?

Then students may also want to know why LinkedHashMap can implement LRU caching to eliminate the element that is accessed least frequently.

When you insert an element, you need to call the put () method, which ends up calling the afterNodeInsertion () method, which is overridden by LinkedHashMap.

Void afterNodeInsertion (boolean evict) {/ / possibly remove eldest

LinkedHashMap.Entry first

If (evict & & (first = head)! = null & & removeEldestEntry (first)) {

K key = first.key

RemoveNode (hash (key), key, null, false, true)

}

}

The removeEldestEntry () method determines whether the first element exceeds the maximum range it can hold, and if it does, it calls the removeNode () method to delete the element that is accessed least frequently.

The above is what the role of LinkedHashMap in Java is shared by the editor. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are 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.