When I saw LinkedList today, I suddenly thought about LinkedHashMap!

​

Then searched the source code, WC, really have!! Oh! Today is another day of learning.

Well, since we didn’t know that before, let’s find out what it is.

Open the LinkedHashMap class, it can be seen from the structure of the class that LinkedHashMap inherits from HashMap and implements the Map interface.

​

LinkedHashMap has a static inner class Entry

that inherits from Hashmap. Node

and extends two pointer attributes, before and after.
,v>
,v>

These two Pointers point to the first and last elements in the list: “The after pointer to the previous element points to itself, and its before pointer points to the previous element; The same goes for the after pointer.

​

There are also two attributes inside the LinkedHashMap: head and tail, which are the head and tail nodes of the bidirectional list.

​

If you look at the comments, you’ll see that there’s also a word for the concept of time on both properties. This…… And sort?

​

Further down, you see a Boolean type attribute accessOrder.

This value indicates how the LinkedHashMap is sorted iteratively, true by access and false by insertion (which it is).

A HashMap traverses the output after insertion in a different order than the order in which it was inserted, but a LinkedHashMap by default with accessOrder ensures that the insertion and output are in the same order.

AccessOrder defaults to false if not specified during LinkedHashMap initialization.

​

Next, several constructors of LinkedHashMap are basically similar to that of HashMap. In addition to the no-parameter constructor, parameters include: initial capacity, load factor, incoming Map type, etc. The only constructor that can specify accessOrder, passing in the initial capacity, load factor, and accessOrder values.

​

After looking at the basic structure of LinkedHashMap, let’s take a look at how it works.

Put method

The fact that the put method is not overridden in LinkedHashMap shows that it is fully using the insert logic of HashMap (we will not expand the put method of HashMap here). When is the list maintained, since it uses HashMap insert logic entirely?

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ... If ((p = TAB [I = (n-1) &hash]) == null) TAB [I] = newNode(hash, key, value, null); else { ... If (e! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the code

First, LinkedHashMap overrides the **newNode()** method of HashMap.

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

The newNode method calls a **linkNodeLast()** method, which links the inserted element to the end of the list. Now, it’s clear when we put the element in the list.

// link at the end of list
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

Second, there are two methods in the HashMap PUT method that are implemented in LinkedHashMap.

afterNodeInsertion(boolean evict)

This method takes a Boolean parameter, which means whether to remove the oldest or least accessed element after inserting the new element. The argument passed in the put method is always true (evict = true), but **removeEldestEntry()** always returns false in LinkedHashMap, so there is no removal element.

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

afterNodeAccess()

This method is called when the inserted key exists. One variable used in this method is the accessOrder specified when the LinkedHashMap is initialized. This method is valid only if this variable is true. Places the accessed element at the end of the list.

void afterNodeAccess(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

As you can see from the put() method, the LinkedHashMap links the elements to the end of the list each time a new element is inserted. When accessOrder is true, place existing elements that are not trailing back at the end of the list.

The get method

LinkedHashMap overwrites the HashMap get method, but still uses the HashMap getNode() method, but appends the **afterNodeAccess()** method to getNode() when accessOrder is true.

The remove method

In addition, the remove() method of LinkedHashMap was also used to clean HashMap, and the remove() method was called in the LinkedHashMap to clean deremoval ()**. The vivienemoval method simply unlinked the data from the linked list.

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
Copy the code

traverse

LinkedHashMap is a sort Map. When accessOrder is false, the list is traversed from the head node in the order in which it was inserted, because new elements are inserted at the end of the list. When accessOrder is true, the list is traversed from the head node in the order of access, with the least number of accesses going forward and the most accesses at the end.

conclusion

Most of the LinkedHashMap methods are directly inherited from HashMap, and some of the HashMap methods are overridden to maintain the linked list data. For example, **newNode(), newTreeNode(), afterNodeInsertion(), visting moval(), afterNodeAccess(), etc.

When accessOrder is true, one might think of LRU (Least Recently Used). However, we said that the removeEldestEntry() method returns false by default when inserting data, so to implement the LRU algorithm you need to override the removeEldestEntry() method.

Finally, take a look at the LinkedHashMap’s list structure

The data structure of LinkedHashMap is inherited from the HashMap, with the orange lines representing the before and After Pointers to the bidirectional list.

I am not just, can only shallow way, if there is anything wrong and inadequate, but also ask you great god to teach ah.

Try to be a daily blogger as soon as possible