LinkedHashMap source code analysis

Art is long, life is long

Introduction to the

• LinkedHashMap internally maintains a bidirectional linked list that ensures that elements are accessed either in insertion order or in access order, which can be used to implement the LRU cache strategy.

• LinkedHashMap can be thought of as LinkedList + HashMap.

Inheritance system

LinkedHashMap inherits from HashMap and has all the features of HashMap, plus additional features that are accessed in a certain order.

Storage structure

We know that HashMap uses a storage structure (array + single linked list + red-black tree), but how does LinkedHashMap store?

From the inheritance system above, we know that it inherits Map, so it also has these three structures inside, but it also adds a “bidirectional linked list” structure to store the order of all elements.

Adding and removing elements requires maintaining storage in the HashMap as well as in the LinkedList, so performance is slightly slower than in the HashMap.

The source code parsing

attribute

/** * two-way list head node */
transient LinkedHashMap.Entry<K,V> head;

/** * the end of the bidirectional list */
transient LinkedHashMap.Entry<K,V> tail;

/** * Whether to sort by access order */
final boolean accessOrder;
Copy the code

(1) Head: the head node of the bidirectional linked list. Old data is stored in the head node.

(2) tail: the tail node of the bidirectional linked list. The new data is stored in the tail node.

(3) accessOrder: whether the elements need to be sorted by accessOrder. If false, the elements need to be stored in insertion order; if true, the elements need to be stored in accessOrder.

The inner class

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

Storage nodes, derived from the Node class of HashMap, next for single linked list storage in buckets, before and after for bidirectional linked list storage of all elements.

A constructor

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap(a) {
    super(a); accessOrder =false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(a); accessOrder =false;
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
Copy the code

The first four constructors, accessOrder, are all equal to false, indicating that the bidirectional list stores elements in insertion order.

The last constructor, accessOrder, is passed in from the constructor argument, and if true is passed in, then the elements are stored in accessOrder, which is key to implementing the LRU cache strategy.

AfterNodeInsertion (Boolean evict) method

To do something after node insertion is called in the putVal() method in the HashMap, and you can see that the implementation of this method in the HashMap is empty.

// evict means evict
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); }}protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
Copy the code

(1) If evict is true and the head node is not empty, and the oldest element is determined to be removed, call hashmap.removenode () to remove the head node (where the head node is the head node of the bidirectlist, not the first element in a bucket);

(2) After removing the object from the HashMap, the hashmap.removenode () method is called to vide-deremoval ();

(3) The method was also implemented in LinkedHashMap, which was used to modify the two-way linked list after removing the element, see below;

(4) The default removeEldestEntry() method returns false, that is, the element is not deleted.

AfterNodeAccess (Node < K, V > e) method

Called after a node has been accessed, mainly when putting () an existing element or getting (). If accessOrder is true, this method is called to move the visited node to the end of the bidirectional list.

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // If accessOrder is true and the node accessed is not the last node
    if(accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;// Remove p from the bidirectional list
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;

        if(a ! =null)
            a.before = b;
        else
            last = b;

        // Put the p node at the end of the bidirectional list
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        // The tail node is ptail = p; ++modCount; }}Copy the code

(1) If accessOrder is true and the node accessed is not the last node;

(2) Remove the visited node from the bidirectional list;

(3) Add the visited node to the end of the bidirectional linked list; (Last accessed element at the end)

AfterNodeRemoval (Node < K, V > e) method

Method called after the node has been deleted.

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // Delete node p from the bidirectional list.
    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

The classic method of removing a node from a bidirectional list.

Get (Object key) method

Gets the element.

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
Copy the code

If an element is found and accessOrder is true, the afterNodeAccess() method is called to move the accessed node to the end of the bidirectional list.

conclusion

(1) LinkedHashMap inherits from HashMap and has all the features of HashMap;

(2) LinkedHashMap internally maintains a bidirectional linked list to store all elements;

(3) If accessOrder is false, the elements can be traversed in the order they were inserted;

(4) If accessOrder is true, the elements can be traversed in the order they were accessed;

(5) The implementation of LinkedHashMap is very subtle, many methods are left in the HashMap Hook (Hook), directly implement these hooks can achieve the corresponding function, there is no need to rewrite put() and other methods;

(6) The default LinkedHashMap does not remove old elements. If you want to remove old elements, you need to rewrite the removeEldestEntry() method to set the removal strategy.

(7) LinkedHashMap can be used to implement LRU cache elimination strategy;

eggs

How does LinkedHashMap implement the LRU cache elimination policy?

First, let’s take a look at what the LRU is. LRU, Least Recently Used, that is, the Least Recently Used elements are preferred.

If we use LinkedHashMap, is accessOrder set to True enough to achieve this policy? The answer is yes. Take a look at the following code:

package com.cn.test;

import java.util.LinkedHashMap;
import java.util.Map;


public class Test {

    public static void main(String[] args) {
        // Create a cache of only 5 elements
        LRU<Integer, Integer> lru = new LRU<>(5.0.75 f);
        lru.put(1.1);
        lru.put(2.2);
        lru.put(3.3);
        lru.put(4.4);
        lru.put(5.5);
        lru.put(6.6);
        lru.put(7.7);

        System.out.println(lru.get(4));

        {3=3, 5=5, 6=6, 7=7, 4=4}
        // You can see that the oldest element is removed
        // And the most recently accessed 4 is moved to the backSystem.out.println(lru); }}class LRU<K.V> extends LinkedHashMap<K.V> {

    // The capacity to save the cache
    private int capacity;

    public LRU(int capacity, float loadFactor) {
        super(capacity, loadFactor, true);
        this.capacity = capacity;
    }

    /** * Override the removeEldestEntry() method to set when to remove old elements *@param eldest
     * @return* /
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // When the number of elements exceeds the cache capacity, the element is removed
        return size() > this.capacity; }}Copy the code

The last

Author: Tong Brother

Reference: www.cnblogs.com/tong-yuan/