LinkedHashMap data structure

This article requires an understanding of HashMap, which you can see in this article

Since LinkedHashMap is implemented by integrating HashMap, it uses the HashMap data structure itself, i.e., an array + a linked list (or a red-black tree, java8).

The black part is the HashMap data structure (array + unidirectional linked list), and the green arrow links a bidirectional linked list, which is the data structure maintained by LinkedHashMap.

As you can see, it’s basically a HashMap Node with two additional variables (Pointers), before and after, for bidirectional linked lists. The nodes in the HashMap are connected in a different order (accessOrder or insertion order) depending on the accessOrder parameter of the constructor.

By adding a small amount of memory (before and after Pointers), the reuse of nodes can achieve order. As we iterate over the elements in the LinkedHashMap, we can read the elements sequentially from the HEAD of the list, achieving a kind of ordered traversal.

Source code analysis

Here are a few important ways to show how LinkedHashMap maintains the order of linked lists: Get (Object), afterNodeInsertion(Node), Vitization (Node), and afterNodeAccess(Node).

To get into these methods, we need to understand the LinkedhashMap.entry class, which is the key to storing node data:

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); }}Copy the code

This is the picture above:

As you can see from this class, LinkedhashMap.entry

is inherited from HashMap.node

, And there are two more variables before and after than hashMap.node

to refer to the Node’s previous and next nodes.
,v>
,v>
,v>

Create a LinkedhashMap.entry

node by overwriting the hashMap.newNode () method:
,v>

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); // Add linkNodeLast(p) to the end of the list.return p;
}
Copy the code
  1. Get (Object) method and afterNodeAccess(Node) method.
public V get(Object key) { Node<K,V> e; // Use the getNode() method of HashMap to get the node corresponding to the keyif ((e = getNode(hash(key), key)) == null)
        returnnull; // Add nodes to the end if you are sorting by access orderif (accessOrder)
        afterNodeAccess(e);
    returne.value; } afterNodeAccess (afterNodeAccess) {afterNodeAccess (afterNodeAccess)} 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

Only when accessOrder is true when the LinkedHashMap is constructed will the elements be placed at the end of the bidirectional list in order of access.

  1. AfterNodeInsertion (Node) method

This method is a hook in hashMap.putVal () that determines whether the earliest (in order of insertion, or in order of access) elements need to be removed after new elements have been added. This method will be covered later in the LRU algorithm.

void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; // Check whether the node needs to be deleted. // Where removeEldestEntry is displayedif(evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false.true); }}Copy the code
  1. AfterNodeRemoval (Node) method

This is a hook method in hashMap.removenode ().

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

So what we’re doing here is we’re deleting a node from a bidirectional linked list.

Tips: In case you are wondering, what to do when a linked list is transformed into a tree? That is, a HashMap is converted to a red-black tree when the list length is 8 or greater.

Entry

: TreeNode
,v>
,v>

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; . }Copy the code

We can also use the TreeNode

TreeNode as a bidirectional linked list node.
,v>

Why use two-way linked lists

Because we can easily delete and add elements, the time complexity is basically O(1).

We can use HashMap to find the node (getNode method) in O(1) time, and then easily delete the node through the front and back Pointers of the node, rather than having to traverse the list to find the previous node and then delete it, as in a unidirectional linked list.

LRU algorithm implementation

The Least Recently Used (LRU) algorithm is primarily applied to the memory cache, where the Least Recently Used elements need to be eliminated when the memory Used reaches the limit. This algorithm is conveniently implemented here using LinkedHashMap.

import java.util.LinkedHashMap; import java.util.Map; public class LRUCache<K, V> extends LinkedHashMap<K, V> { private int capacity; Public LRUCache(int capacity) {super(capacity, 0.75f,true); this.capacity = capacity; } // Return when the element capacity exceeds the limittrue/ / then afterNodeInsertion method will remove head of two-way linked list node @ Override protected Boolean removeEldestEntry (Map) Entry > < K, V eldest) {returnsize() > capacity; }}Copy the code