JDK collection source code LinkedHashMap parsing

Introduction of LinkedHashMap

• LinkedHashMap maintains a bidirectional linked list that ensures that elements are accessed either in the order they were inserted or in the order they were accessed.
• LinkedHashMap can be thought of as LinkedList + HashMap.
• LinkedHashMapinheritanceHashMapwithHashMap(Reference link:JDK collection source HashMap parsing), and added additional featuresAccess in a certain orderThe characteristics ofLinkedHashMapThe default storage order is insertion order, or elements can be stored in access order.

@Test
public void test01(a){
    HashMap hashMap = new HashMap();
    hashMap.put("name"."csp");
    hashMap.put("name"."csp1999");
    hashMap.put("age"."22");
    hashMap.put("sex"."man");
    hashMap.put("school"."haust");
    hashMap.put("class"."1801");
    System.out.println(hashMap);{school=haust, sex=man, name=csp1999, class=1801, age=22}
    
    LinkedHashMap linkedHashMap = new LinkedHashMap();
    linkedHashMap.put("name"."csp");
    linkedHashMap.put("name"."csp1999");
    linkedHashMap.put("age"."22");
    linkedHashMap.put("sex"."man");
    linkedHashMap.put("school"."haust");
    linkedHashMap.put("class"."1801");
    System.out.println(linkedHashMap);{name=csp1999, age=22, sex=man, school=haust, class=1801}
    // LinkedHashMap is stored in insert order by default, but elements can also be stored in access order
}
Copy the code

LinkedHashMap Inheritance system

LinkedHashMap uses a storage structure (array + single linked list + red-black tree). LinkedHashMap inherits from HashMap, so it has all three structures inside, but it also adds a “two-way 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.

LinkedHashMap source code analysis

1. The attribute

/** * Serialized version */
private static final long serialVersionUID = 3801124242820219131L;

/** * the head node of the bidirectional linked list. * Objects decorated with transient keywords cannot be serialized */
transient LinkedHashMap.Entry<K,V> head;

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

/** * Whether to sort by access order * true: sort by access order * false: sort by insert order *@serial* /
final boolean accessOrder;
Copy the code

• Head: The head node of a bidirectional list where old data is stored.
• Tail: Indicates the tail node of a bidirectional list. New data is stored in the tail node.
• AccessOrder: whether elements need to be sorted in accessOrder, if false, in insertion order, or if true, in accessOrder.

2. The inner class

/** * subclass of HashMap 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); }}/** ** is in the HashMap. */
static class Node<K.V> implements Map.Entry<K.V> {
    final int hash;// hash Stores the hash value calculated by the key
    final K key;/ / key
    V value;/ / value
    Node<K,V> next;// Next node
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next; }... }Copy the code

3. Construction method

    // The default is false, so the output of the iteration is the order in which the nodes are inserted. If true, the output is in the order in which the nodes are accessed.
    // When true, a LruCach can be constructed on this basis
    final boolean accessOrder;

    public LinkedHashMap(a) {
        super(a); accessOrder =false;
    }
    // Specify the capacity at initialization,
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    // Specify the capacity for initialization and the load factor for expansion
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
    // Specify the capacity at initialization, the loading factor for expansion, and the order in which the output nodes are iterated
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    // Build with another Map,
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(a); accessOrder =false;
        // This method is used to batch insert all the data in a map into this collection.
        putMapEntries(m, false);
    }
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.

4. Membership method

4.1 to add

LinkedHashMap does not override any put methods. But it overrides the newNode() method that builds new nodes. NewNode () is called in the putVal() method of the HashMap, which inserts putMapEntries in bulk (Map
m, Boolean evict) or when inserting a single data public V PUT (K key, V value).

LinkedHashMap overrides newNode() by linkNodeLast(p) each time a newNode is built; Link the new node to the end of the internal bidirectional list.

    // When you build a new Node, you build 'linkedhashmap. Entry' instead of 'Node'.
    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;
    }
    // Add the new node to the end of the list
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        // The set is empty before
        if (last == null)
            head = p;
        else {// Join the new node at the end of the listp.before = last; last.after = p; }}Copy the code

AfterNodeAccess () afterNodeInsertion() visting emoval()

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) {}void afterNodeInsertion(boolean evict) {}void afterNodeRemoval(Node<K,V> p) {}Copy the code

    // A callback function that calls back after a new node is inserted to determine whether the oldest node needs to be removed based on evICT. This method will be used if you implement LruCache.
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        //LinkedHashMap returns false by default to not delete the node
        if(evict && (first = head) ! =null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null.false.true); }}//LinkedHashMap returns false by default to not delete the node. Returning true indicates that the earliest node is to be deleted. Normally building a LruCache returns true when the Cache reaches its upper limit
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
Copy the code

Void afterNodeInsertion(Boolean evict); Boolean removeEldestEntry(map. Entry

eldest); You can ignore them in LinkedHashMap.
,v>

4.2 delete

    // Delete node E from the bidirectional list
    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // The front and rear nodes of node P to be deleted are empty
        p.before = p.after = null;
        // If the front node is null, the current head should be the back node A
        if (b == null)
            head = a;
        else// Otherwise, the rear node of the front node B points to a
            b.after = a;
        // If the trailing node is null, then the trailing node should be b
        if (a == null)
            tail = b;
        else// Otherwise, the front node of node A is b
            a.before = b;
    }
Copy the code

4.3 check

LinkedHashMap overrides the get() and getOrDefault() methods:

    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;
    }
    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }
Copy the code

In contrast to the implementation in HashMap,LinkedHashMap simply adds a callback to the void afterNodeAccess(Node

e) function if the member variable (assigned at constructor time)accessOrder is true.
,v>

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

The afterNodeAccess() function moves the currently accessed node E to the end of the internal bidirectional list.

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;// The original tail node
        // If accessOrder is true and the original tail node is not equal to e
        if(accessOrder && (last = tail) ! = e) {// node e is strongly converted to bidirectional list node P
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //p is now the last node, and the trailing node must be null
            p.after = null;
            // If the front node of p is null, then p used to be the head node, so update the current head node is a after P
            if (b == null)
                head = a;
            else// If p is not updated, the node after b is a
                b.after = a;
            // If the postnode of p is not null, the pre-node of postnode A is changed to b
            if(a ! =null)
                a.before = b;
            else// if the trailing node of p is null, p is the last node. At this point, the reference to last is updated as the leading node B of P
                last = b;
            if (last == null) If the last node is null, there is only one node in the list
                head = p;
            else {// Otherwise, update the last node before the current node p and p after the last node
                p.before = last;
                last.after = p;
            }
            // The reference to the last node is assigned to p
            tail = p;
            // Modify modCount.++modCount; }}Copy the code

Note that afterNodeAccess() modiates modCount, so iterating over LinkedHashMap in accessOrder=true will also cause fail-fast if you query access data at the same time. Because the order of iteration has changed.

4.4 traversal

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        / / return LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K.V>> {
        public final Iterator<Map.Entry<K,V>> iterator() {
            return newLinkedEntryIterator(); }}Copy the code

    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K.V>> {
        public final Map.Entry<K,V> next(a) { returnnextNode(); }}abstract class LinkedHashIterator {
        // Next node
        LinkedHashMap.Entry<K,V> next;
        // The current node
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;

        LinkedHashIterator() {
            // When initialized, next is the flat head of the bidirectional list maintained internally by LinkedHashMap
            next = head;
            // Record the current modCount to satisfy fail-fast
            expectedModCount = modCount;
            // The current node is null
            current = null;
        }
        // Determine if there is still next
        public final boolean hasNext(a) {
            // check whether next is null, default next is head
            returnnext ! =null;
        }
        NextNode () is the next() method in the iterator.
        // The implementation of this method shows that iterating over the LinkedHashMap loops from the header of the internally maintained double-linked list.
        final LinkedHashMap.Entry<K,V> nextNode(a) {
            // Record the e to return.
            LinkedHashMap.Entry<K,V> e = next;
            / / fail - fast
            if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
            // If the node to be returned is null, exception
            if (e == null)
                throw new NoSuchElementException();
            // Update the current node to e
            current = e;
            // The next node to update is the post-node of e
            next = e.after;
            / / return e
            return e;
        }
        // The delete method ends up calling the removeNode method of HashMap
        public final void remove(a) {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null.false.false); expectedModCount = modCount; }}Copy the code

4.5 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.

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

Evict means to expel.

(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.

4.6 afterNodeAccess(Node E)

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

4.7 Visting deremoval (Node 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;
    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.

4.8 Get (Object Key) method

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

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;

LinkedHashMap is relatively simple compared to the source code for HashMap. For great trees are good for nothing but shade. It inherits HashMap and just overrides a few methods to change the order in which it iterates through. This is the biggest difference from HashMap. Each time data is inserted, accessed, or modified, nodes are added, or the order of nodes in the linked list is adjusted. To determine the order of output during iteration.

• accessOrder, the default is false, then the output order during iteration isSequence of nodes to be inserted. If true, the output is in the order in which the nodes are accessed. When true, one can be built on top of thisLruCache.
• LinkedHashMapI didn’t override any put methods. But it overrides how to build new nodesnewNode()Each time a new node is built, theThe new node is linked at the end of the internal bidirectional list
• accessOrder=trueIn the mode ofafterNodeAccess()Function, will be the currentTo be accessedTo node E,mobileTo an internal bidirectional linked listThe tail of the. It’s worth noting that,afterNodeAccess()Function, will be modifiedmodCountSo when you areaccessOrder=trueIn the mode of iterationLinkedHashMapIf the access data is queried at the same time, thefail-fastBecause the order of iteration has changed.
• nextNode()That’s what’s in the iteratornext()Methods.
  
  The implementation of the method can be seen as iterativeLinkedHashMap, it is fromInternally maintained double-linked list headers start looping output.
  
  The order of doubly linked list nodes isLinkedHashMaptheAdd, delete, change, check will be updated. Whether to output in insert order or access order.
• It has to do withHashMapThere’s also a little optimization, rewrittencontainsValue()Method, directly through the internal linked list to check whether the values are equal.

extension

/ * * *@author: csp1999
 * @date: 2020/11/10 * /
public class LRUTest {
    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));
    
        lru.put(6.Awesome!);
    
        {3=3, 5=5, 7=7, 4=4, 6=666}
        // 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