Hashmaps are unordered and TreeMap can sort by key. Are there any maps that can maintain insert order? Let’s take a look at LinkedHashMap.

LinkedHashMap itself descends from HashMap, so it has all the features of HashMap, and on top of that, it provides two main features:

  • Access in insert order;
  • The least access first delete function is implemented to automatically delete keys that have not been accessed for a long time.

Structure of 1.

LinkedHashMap inheritance, core member variables, main constructors:

// LinkedHashMap descends from HashMap
public class LinkedHashMap<K.V> extends HashMap<K.V> implements Map<K.V>{

	/ / head
    transient LinkedHashMap.Entry<K,V> head;

    / / list the tail
    // If head=tail=null, the linked list is empty
    transient LinkedHashMap.Entry<K,V> tail;
	
    //--------------------------------Node-----------------------------------------
    // The Node in LinkedHashMap is called Entry, which inherits the Node of HashMap
    static class Entry<K.V> extends HashMap.Node<K.V> {
        // Add before and after attributes to each element of the array
        Entry<K,V> before, after;
        // The constructor does not change, adding before and after to the list
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next); }}// One of the elements that controls whether LRU is enabled, indicating whether the current node is allowed to move to the end of the list after access (get). The default is false
    // The other enabled element is whether the first node is allowed to be removed when put is enabled. The default return is false
    final boolean accessOrder;
    
    / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the constructor -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false; // Set accessOrder to false
    }	
    
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    
    public LinkedHashMap(a) {
        super(a); accessOrder =false;
    } 
    
    AccessOrder can be set through this constructor, which is required to enable the LRU policy
     public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder; }}Copy the code

As you can see from the attributes added to the Map above, the data structure of the LinkedHashMap is similar to that of the Node of the HashMap by replacing each element of the LinkedList with a HashMap. It is because of the addition of these structures that the Map elements can be connected together. Make a linked list, and then the linked list can be ordered, so you can maintain the order in which elements are inserted.

LinkedHashMap is achieved by combining two data structures, bidirectional Linked lists and hash tables. “Linked” actually refers to bidirectional Linked lists, not to resolving hash conflicts using Linked lists.

2. Method parsing & API

2.1 Implement LRU when adding elements

LinkedHashMap itself does not have a put method implemented. Since it inherits HashMap, HashMap’s PUT and putVal methods are called. But that’s not enough to consider two features of LinkedHashMap

  1. The LinkedHashMap needs to have list features, so the newly added nodes are also inserted into the list
  2. LinkedHashMap can implement LRU because linked lists are already implemented, but there are two issues to consider:
    1. What is the implementation strategy? Get and put
      • Get: After each node is accessed (get), the current node is placed at the end of the list
        • The reason for resetting to tail: New nodes are inserted at the end of the list, which means the tail is new anyway
        • This is also equivalent to the earlier nodes being longer and not accessed
      • Put: When a node (PUT) is inserted and all deletion conditions are met, the head node is deleted
        • In this case, a certain condition is actually the deletion policy, which generally needs to be customized, such as size>3
    2. How to enable LRU execution? You also start with get and put, which are turned off by default
      • Get: accessOrder is set to true to allow the node to be moved to the end of the list. The default is false and enabled when construction is required
      • Evict =true (default for put); evict=true (default for put);

put()

public V put(K key, V value) {
        return putVal(hash(key), key, value, false.true);
}
Copy the code

putVal()

// EVict: Determines whether to remove the least accessed element. The default is true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {...// Call newNode to add a node, but in LInkedHashMap, the newNode method is overridden because the node
        tab[i] = newNode(hash, key, value, null); .// Empty implementation in HashMap, but concrete implementation in linkedListMap
       afterNodeInsertion(evict);
 }
Copy the code

This is essentially a design principle of dependency inversion, where the top defines the interface and the bottom implements it

newNode()

Rewrite the newNode method of the HashMap to add node Entry and call linkNodeLast to append to the end of the list

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // Add a new node. Here is new Linkedhash.entry
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    // Append to the end of the list
    linkNodeLast(p);
    return p;
}
Copy the code

linkNodeLast()

Because LinkedHashMap also has a linked list feature, it can’t just be added to a hash table like a HashMap, but to a linked list as well

// The input parameter is the newly created node
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail; / / temporary tail
    tail = p; // set tail to the new node p
    
    if (last == null) // If last is empty, the list is empty, so head should also be set to the new node p
        head = p;    
    else { // The list is not empty, and the relationship between the new node and the last last node can be directly establishedp.before = last; last.after = p; }}Copy the code

afterNodeInsertion()

AfterNodeInsertion method is implemented empty in HashMap and LRU in LinkedHashMap.

void afterNodeInsertion(boolean evict) { 
    LinkedHashMap.Entry<K,V> first;
    // To remove a header node, three conditions must be met
    // 1. Evict =true, which is the default in the put method
    // 2. The queue is not empty, but this is not a problem because the method is executed after the node joins
    // 3. Delete policies Policies can be deleted. The default value is false
    if(evict && (first = head) ! =null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null.false.true); // removeNode removes the header node}}Copy the code

removeEldestEntry()

RemoveEldestEntry is usually used to define a deletion policy. If the value is true, the header is deleted; if the value is false, the header is not deleted

  • This method usually needs to be overwritten by the user. For example, delete it when return size>3
  • The default implementation is provided in LinkedHashMap, which simply returns false.
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}
Copy the code

2.2 Implement LRU when fetching elements

get()

LinkedHashMap overrides the get method of HashMap:

  1. To get the specific node, call the getNode method of the HashMap
  2. After the node is acquired, the move node is added to the end of the queue to implement the LRU operation
public V get(Object key) {
        Node<K,V> e;
        // Call hashmap.getNode () to get the specific node
        if ((e = getNode(hash(key), key)) == null)
            return null;
        // If the LRU policy is set
        if (accessOrder)
        // This moves the current key to the end of the queue
            afterNodeAccess(e);
        return e.value;
    }
Copy the code

The getOrDefault, compute, computeIfAbsent, computeIfPresent, and merge methods are used to continuously move the most frequently accessed nodes to the end of the queue. Nature is an element that is rarely accessed.

afterNodeAccess()

Move the visited node to the end of the queue

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        // accessOrder is true and e is not the end of the queue
        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

LRU sample

public void testAccessOrder(a) {
  // Build LinkedHashMap, which must use a unique constructor that can set accessOrder
  LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4.0.75 f.true) {
  New A() {{initialize} / override method}; // New A() {{initialize} / override method};
    { 
      put(10.10); // Call container specific function initialization, must add {}
      put(9.9);
      put(20.20);
      put(1.1);
    }

    @Override
    // Overwrites the delete policy method, allowing it to return true; When more than three slots are already in use, start removing the list header
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
      return size() > 3; }}; log.info("Initialize: {}",JSON.toJSONString(map));
  Assert.assertNotNull(map.get(9));
  log.info("Map. Get (9) : {}",JSON.toJSONString(map));
  Assert.assertNotNull(map.get(20));
  log.info("The map. The get (20) : {}",JSON.toJSONString(map));
}
Copy the code

The printed result is as follows

Initialization: {9:9 shall lie, 1:1} map. Get (9) : {shall lie, 1:1, 9:9} map. Get (20) : {1:1, 9:9} shall lieCopy the code

As you can see, when we initialized the map, we put four elements in, but we ended up with only three, and 10 is missing. This is mainly because we overwrote the removeEldestEntry method. We implemented that if the map has more than three elements, we remove the header element. When put(1, 1) is executed, the header 10 is deleted. This shows that the header node will be deleted automatically when the deletion policy is reached.

When we call the map.get(9) method, element 9 is moved to the end of the queue, and when we call the map.get(20) method, element 20 is moved to the end of the queue, indicating that frequently accessed nodes are moved to the end of the queue.

2.3 Iterators: Based on linked lists

Map provides iterators for keys, values, and Entities. These iterators are called from map.~Set().iterator()

  • Iteration key: LinkedHashMap –keySet()–> LinkedKeySet –iterator()–> LinkedKeyIterator
  • Iterating value: LinkedHashMap –values()–> LInkedValues–iterator()–> LinkedValueIterator
  • Iteration key: LinkedHashMap –entrySet()–> LinkedEntrySet–iterator()–> LinkedEntryIterator

Linked~~Iterator

These are different iterators, but they are essentially the same:

  1. Both inherit LinkedHashIterator
  2. All is only one way: next (), and it calls are LinkedHashIterator. NextNode (), but in the last node values are different
final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next(a) { return nextNode().getKey(); } // Call the nextNode method of the parent class to return the Key in node
}

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    public final V next(a) { return nextNode().value; } // Call the nextNode method of the parent class to return value in node
}

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K.V>> {
    public final Map.Entry<K,V> next(a) { return nextNode(); } // Call the nextNode method of the parent class to return node directly
}
Copy the code

LinkedHashIterator

LinkedHashIterator versus HashIterator

  1. Difference: nextNode approach, also known as iterative strategy
    • A HashIterator iterates bucket by bucket. The outer layer of the HashIterator iterates bucket by bucket, and the inner layer iterates the list.
    • LinkedHashIterator: Simply follow the list through all nodes
  2. Similarities: The hasNext and remove methods are identical, so the following code does not list them

But in the case of LinkedHashMap, it inherits HashMap, so both iterators can be used

abstract class LinkedHashIterator {
     
        LinkedHashMap.Entry<K,V> next; // Next node
        LinkedHashMap.Entry<K,V> current; // The current node
        int expectedModCount;  // Target operand (that is, operand before iteration begins)

        // When initialized, access starts from the beginning node by default
        LinkedHashIterator() {
            next = head;
            expectedModCount = modCount;
            current = null;
        }
     	
     	// Core method nextNode(), based on the list of iterations!!
     	final LinkedHashMap.Entry<K,V> nextNode(a) {
            LinkedHashMap.Entry<K,V> e = next;
            // verify If Map operations are performed during iteration, an error is reported
            if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            // Find the node for the next iteration through the after structure of the list
            next = e.after; 
            returne; }}Copy the code