I heard that you do not understand Java LinkedHashMap, ridiculous

First look and then like, give yourself a bit of time to think, wechat search [Silent King 2] pay attention to this has the appearance level but pretend to rely on talent mediocre programmer. This article has been included in GitHub github.com/itwanger, which also contains the interview questions I carefully prepared for you.

Hi, class. Remember the HashMap article? I feel very good writing ah, both easy to understand, and in-depth source code, really is a thorough analysis, clear, clearly. (Accidentally and three idioms?) A HashMap is good anywhere, really, and should be the first thing you want to use key-value pairs.

But as the saying goes, “no man is perfect without gold,” and HashMap is no exception. One requirement it doesn’t meet is that if we need a set of key-value pairs in insertion order, HashMap won’t be able to do it. Because the HashMap hashes the keys once at insert time to improve lookup efficiency, the inserted elements are unordered.

For those of you who aren’t quite sure about this, go back to the HashMap article and watch me explain the put() method.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
    // if table is null, call resize to create array with default size
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Calculate the subscript, if there is no value, then fill
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
}
Copy the code

The formula I = (n-1) &hash values are not inserted into an array with ordered subscripts of 0, 1, 2, 3, 4, and 5, but are somewhat random.

LinkedHashMap was created for this need. LinkedHashMap inherits from HashMap, so it has all the key-value pair functionality that HashMap has.

public class LinkedHashMap<K.V>
    extends HashMap<K.V>
    implements Map<K.V>{}
Copy the code

In addition, the LinkedHashMap is supplemented with a two-way list to maintain the insertion order of elements. Notice before and after in the code below, which are used to maintain the order of the preceding and following elements of the current element.

static class Entry<K.V> extends HashMap.Node<K.V> {
    LinkedHashMap.Entry<K,V> before, after;
    Entry(int hash, K key, V value, HashMap.Node<K,V> next) {
        super(hash, key, value, next); }}Copy the code

For bidirectional linked lists, you can go back to my LinkedList article to help you understand this LinkedHashMap.

Before I move on, LET me post a picture to add a bit of fun — look what I’m doing. UUID used the words “ridiculous” and “you” in the title of the article and got this hilarious comment below.

(Yes or no, I don’t know…) That LinkedHashMap also uses “you” and “ridiculous”, I don’t know if anyone will continue to be the same, think about it, I feel very happy.

01. Insertion sequence

In the HashMap article, I mentioned that null is inserted into the first part of a HashMap.

Map<String, String> hashMap = new HashMap<>();
hashMap.put("Heavy"."Silent King II.");
hashMap.put("Silent"."Silent King II.");
hashMap.put("The king"."Silent King II.");
hashMap.put("二"."Silent King II.");
hashMap.put(null.null);

for (String key : hashMap.keySet()) {
    System.out.println(key + ":" + hashMap.get(key));
}
Copy the code

The output is:

Null: Null: Silent King two sink: Silent King two two Silence King twoCopy the code

Even though null is the last bit put in, when iterating through the output, it goes first.

Take a look at LinkedHashMap.

Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("Heavy"."Silent King II.");
linkedHashMap.put("Silent"."Silent King II.");
linkedHashMap.put("The king"."Silent King II.");
linkedHashMap.put("二"."Silent King II.");
linkedHashMap.put(null.null);

for (String key : linkedHashMap.keySet()) {
    System.out.println(key + ":" + linkedHashMap.get(key));
}
Copy the code

The output is:

Sink: Silent King 2 Silent King 2 silent King 2 null: NullCopy the code

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

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

So how does LinkedHashMap do this? I am sure that you, like me, are eager to know why.

To find out, take a deep dive into the source code of LinkedHashMap. LinkedHashMap does not override the Put () method of HashMap, but rather the internal method newNode() that the put() method calls.

HashMap.Node<K,V> newNode(int hash, K key, V value, HashMap.Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
Copy the code

As mentioned earlier, linkedhashmap. Entry inherits hashmap. Node and appends two fields before and after.

Then, let’s look at the linkNodeLast() method:

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else{ p.before = last; last.after = p; }}Copy the code

As you can see, LinkedHashMap assigns head to the first element when the first element is added, before to the second element when the second element is added, and afer to the first element.

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

Note: THE JDK version I’m using is 14.

02. Order of access

LinkedHashMap maintains not only the insertion order, but also the access order. Access involves calling the get(), remove(), and PUT () methods.

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

LinkedHashMap<String, String> map = new LinkedHashMap<>(16..75f.true);
Copy the code

The first and second parameters, familiar to those who have seen a HashMap, refer to the initial capacity and load factor.

The third parameter, if true, indicates that the LinkedHashMap maintains the access order; Otherwise, maintain the insertion order. The default is false.

Map<String, String> linkedHashMap = new LinkedHashMap<>(16..75f.true);
linkedHashMap.put("Heavy"."Silent King II.");
linkedHashMap.put("Silent"."Silent King II.");
linkedHashMap.put("The king"."Silent King II.");
linkedHashMap.put("二"."Silent King II.");

System.out.println(linkedHashMap);

linkedHashMap.get("Silent");
System.out.println(linkedHashMap);

linkedHashMap.get("The king");
System.out.println(linkedHashMap);
Copy the code

The output is as follows:

{sink = King of Silence ii, Silent = King of Silence II, Silent = King of Silence II, silent = King of Silence II} {sink = King of Silence II, silent = King of Silence II, silent = King of Silence II}Copy the code

When we use the get() method to access the element with the key “silent”, in the output, silent = silent king 2 is last; When we access the element of the key “King”, in the output, king = Silent King 2 is last, and silent = Silent King 2 is second from last.

In other words, the least frequently visited ones go to the head, which is interesting. What’s interesting about it?

We can use LinkedHashMap to implement LRU caching, which is short for Least Recently Used. LRU is a common page replacement algorithm that selects pages that have not been Used for the most recent time.

public class MyLinkedHashMap<K.V> extends LinkedHashMap<K.V> {

    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) {
        returnsize() > MAX_ENTRIES; }}Copy the code

MyLinkedHashMap is a custom class that inherits LinkedHashMap and overrides the removeEldestEntry() method to make the Map hold up to five elements, which are obsolete.

So let’s test that out.

MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16.0.75 f.true);
map.put("Heavy"."Silent King II.");
map.put("Silent"."Silent King II.");
map.put("The king"."Silent King II.");
map.put("二"."Silent King II.");
map.put("An interesting programmer."."An interesting programmer.");

System.out.println(map);

map.put("A programmer with good looks."."A programmer with good looks.");
System.out.println(map);

map.put("A talented programmer."."A talented programmer.");
System.out.println(map);
Copy the code

The following output is displayed:

{sink = Silence king 2, Silent = Silence King 2, King = Silence King 2, 2 = Silence King 2, 1 interesting Programmer = 1 interesting programmer} {silence = Silence King 2, King = Silence King 2, 2 = Silence King 2, 1 interesting programmer = 1 interesting programmer, A have appearance level programmers = a appearance level programmer} {= silence reigned two wang, 2 = silence reigned two, an interesting programmers = a interesting programmers, there a appearance programmers = a have level programmers in appearance, a talented programmer = a talented programmer}Copy the code

Sink = Silent king 2 and silent King 2 were eliminated in turn.

If you get the element with the key “silent” before putting “a talented programmer” :

MyLinkedHashMap<String,String> map = new MyLinkedHashMap<>(16.0.75 f.true);
map.put("Heavy"."Silent King II.");
map.put("Silent"."Silent King II.");
map.put("The king"."Silent King II.");
map.put("二"."Silent King II.");
map.put("An interesting programmer."."An interesting programmer.");

System.out.println(map);

map.put("A programmer with good looks."."A programmer with good looks.");
System.out.println(map);

map.get("Silent");
map.put("A talented programmer."."A talented programmer.");
System.out.println(map);
Copy the code

So the output is different, right?

{sink = Silence king 2, Silent = Silence King 2, King = Silence King 2, 2 = Silence King 2, 1 interesting Programmer = 1 interesting programmer} {silence = Silence King 2, King = Silence King 2, 2 = Silence King 2, 1 interesting programmer = 1 interesting programmer, A have appearance level programmers = a appearance level programmer} {2 = silence reigned two, an interesting programmers = a interesting programmers, there a appearance programmers = a have level programmers in appearance, merlin = silence reigned two, a talented programmer = a talented programmer}Copy the code

Sink = Silence King 2 and King = Silence King 2 are out of the tournament.

How does LinkedHashMap maintain access order? If you are interested, you can explore the following three methods.

void afterNodeAccess(Node<K,V> p) {}void afterNodeInsertion(boolean evict) {}void afterNodeRemoval(Node<K,V> p) {}Copy the code

AfterNodeAccess () is called at get(), afterNodeInsertion() is called at PUT (), Visting () is called when the remove() method is called.

I’ll use afterNodeAccess() as an example.

void afterNodeAccess(HashMap.Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if(accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)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; }}Copy the code

Whichever element gets is put last. See?

Students may also be wondering why LinkedHashMap implements LRU caching to weed out the least frequently accessed element.

To insert an element, you call the PUT () method, which ends up calling afterNodeInsertion(), overridden by LinkedHashMap.

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if(evict && (first = head) ! =null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null.false.true); }}Copy the code

The removeEldestEntry() method determines whether the first element exceeds the maximum size that can be accommodated, and if so, the removeNode() method is called to remove the least frequently accessed element.

03, finally

Because LinkedHashMap maintains a bidirectional linked list, LinkedHashMap takes longer to insert and delete than HashMap.

Well, you can’t help it, can you? You gotta wear a crown. Since you want to maintain the order of elements, there is always a price to pay.

So this article has come to an abrupt end. If you want to know more, please feel free to leave a message and tell me. (Accidentally dumping three idioms at the end of the article, a bit cultural, right?)

I am the Silent King 2, a programmer with good looks who pretends to be inferior to his talent. Attention can improve learning efficiency, don’t forget three even ah, like, collect, message, I don’t pick, Ollie to 🌹.

Note: If there are any problems with the article, please kindly correct them.

If you feel that the article is helpful to you, welcome to wechat search “Silent King two” for the first time to read, reply to the keyword “xiaobai” can be free to get my liver 40,000 + words “Java Xiaobai from the entry to wunky” 2.0 version; This article has been included at GitHub github.com/itwanger.