The paper

LinkedHashMap descends from HashMap and operates like HashMap and has a similar structure. The main difference from HashMap is that before and after attributes are added to maintain order through node Entry. Examples sort by insertion order:

public static void main(String[] args) { System.out.println("**********HashMap***********"); Map hashMap = new HashMap(); Hashmap. put("Marvel", "Marvel"); Hashmap. put("Deadpool", "Deadpool"); Hashmap. put("Hulk", "Hulk"); Hashmap. put("Thor", "Thor"); Hashmap. put("Wolverine", "Wolverine"); for (Iterator it = hashMap.entrySet().iterator(); it.hasNext(); ) { Map.Entry obj = (Map.Entry)it.next(); System.out.println(obj.getKey() + "-" +obj.getValue()); } System.out.println("**********LinkedHashMap***********"); Map linkedHashMap = new LinkedHashMap(); LinkedHashMap. Put ("Marvel", "Marvel"); LinkedHashMap. Put ("Deadpool", "Deadpool"); LinkedHashMap. Put ("Hulk", "Hulk"); LinkedHashMap. Put ("Thor", "Thor"); LinkedHashMap. Put ("Wolverine", "Wolverine"); for (Iterator it = linkedHashMap.entrySet().iterator(); it.hasNext(); ) { Map.Entry obj = (Map.Entry)it.next(); System.out.println(obj.getKey() + "-" +obj.getValue()); }}Copy the code

Output:

* * * * * * * * * * a HashMap * * * * * * * * * * * Thor - Thor Deadpool - die shi Wolverine - Wolverine Marvel - diffuse wei Hulk - Hulk * * * * * * * * * * LinkedHashMap * * * * * * * * * * * He was Deadpool, Hulk, Thor, WolverineCopy the code

Source code analysis

LinkedHashMap field

final boolean accessOrder; True: access order, false: insert order TRANSIENT linkedhashmap.Entry head; // TRANSIENT linkedhashmap. Entry tail; /** * next: insert before, after, insert before, insert before, insert after */ static class Entry extends Hashmap. Node {Entry before, after; }Copy the code

A constructor

The first four are default insert sorts, and the last one can be specified, with accessOrder being true and insert order being false

public LinkedHashMap() { super(); accessOrder = false; } public LinkedHashMap(int initialCapacity) {super(initialCapacity); accessOrder = false; } public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor); accessOrder = false; } // Build public LinkedHashMap(map m) {super(); accessOrder = false; putMapEntries(m, false); } public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }Copy the code

Put method

LinkedHashMap follows the HashMap PUT method but overwrites the newNode(), afterNodeAccess(), afterNodeInsertion() methods

Node newNode(int hash, K key, V value, Node e) {// Call the entry constructor of linkedhashMap. entry p = new LinkedhashMap. entry (hash, key, value, e); linkNodeLast(p); return p; Private void linkNodeLast(linkedhashmap.entry p) {// Get the linkedhashmap.entry last = tail; // set p to tail = p; If (last == null) head = p; else { p.before = last; last.after = p; }}Copy the code

As you can see from the source code above, linkedHashMap maintains an additional two-way linked list. AfterNodeAccess () is called when the put method replaces a value with a key object in the current collection:

Void afterNodeAccess(Node e) {// Move Node to last linkedhashmap.entry last; E if (accessOrder && (last = tail)! P = (linkedhashmap. Entry)e, b = P.before, a = P.after; // After = null p.after = null; If (b == null) head = a; if (b == null) head = a; Else // Otherwise set the successor of p as the successor of P b.after = a; // If the successor of p is not null, set the precursor of the successor of P to the precursor of P. = null) a.before = b; Else // Set last = b; If (last == null) head = p; if (last == null) head = p; Else {// otherwise change the precursor node of p to the original tail node, and the successor node of the original tail node to p p.before = last; last.after = p; P tail = p; ++modCount; }}Copy the code

AfterNodeInsertion () method afterNodeInsertion()

Void afterNodeInsertion(Boolean evict) {// Possibly remove Eldest linkedhashmap.entry first; if (evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); }} // Return false protected Boolean removeEldestEntry(map.entry younger) {return false; }Copy the code

Void afterNodeInsertion(Boolean evict); Boolean removeEldestEntry(map. Entry<K,V> eldest); You can ignore them in LinkedHashMap

The get method

LinkedHashMap overwrites its get() method


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

LinkedHashMap has one more operation than HashMap get, and afterNodeAccess() is called if accessOrder is true. The afterNodeAccess() method has been mentioned above, and it is important to note that modCount is modified in this method when iterating over LinkedHashMap, which causes fail-fast when querying access data at the same time, because the iteration order is changed

The remove method

LinkedHashMap inherited the remove() method of HashMap, but overwrote its visting method, which washed deremoval ()

/** * unlink linkedhashmap.entry P = (linkedhashmap.entry)e, b = p.before, a = p.after; // The front and rear nodes of node P to be deleted are null. If (b == null) head = a; // If (b == null) head = a; Else b.after = a; If (a == null) tail = b; // If (a == null) tail = b; // Else a.before = b; }Copy the code

Implement the caching mechanism with LinkedHashMap

FIFO

FIFO(First In First Out): First In, First Out, the same as queues. FIFO implementation :LinkedHashMap by default (accessOrder is false) sort data by stored data, as shown in the following example:

public class FIFOCache extends LinkedHashMap { private final int maxSize; Public FIFOCache(int maxSize) {super(); // Call the parent class default constructor, accessOrder is false this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } public static void main(String[] args) { Map fifoCache = new FIFOCache(10); For (int I = 0; i < 10; i++) { fifoCache.put(i, i); } system.out.println (" initial case :" + fifocache.tostring ()); fifoCache.put(6, 6); // Access existing data system.out.println (" after existing data is accessed :" + fifocache.tostring ()); fifoCache.put(10, 10); System.out.println(" + fifocache.toString ()); }}Copy the code

Output:

Initial situation: {0 = 0, 1 = 1, 2 = 2, 3 = 3 and 4 = 4, 5 = 5, 6 = 6, 7 = 7, 8 = 8, 9 = 9} after the existing data is accessed: {0 = 0, 1 = 1, 2 = 2, 3 = 3 and 4 = 4, 5 = 5, 6 = 6, 7 = 7, 8 = 8, 9 = 9} after a new data: {1 = 1, 2 = 2 and 3 = 3 and 4 = 4, 5 = 5, 6 = 6, 7 = 7, 8 = 8, 9 = 9, 10 = 10}Copy the code

According to the output result, it satisfies the FIFO rule and sorts according to insertion order. If any data in the cache is hit, the first-in, first-out rule will not be broken. If a new data is added outside the cache, the first inserted data is removed

LRU

public class LRUCache extends LinkedHashMap { private final int maxSize; Public LRUCache(int maxSize){super(maxSize, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } public static void main(String[] args) { Map fifoCache = new LRUCache(10); For (int I = 0; i < 10; i++) { fifoCache.put(i, i); } system.out.println (" initial case :" + fifocache.tostring ()); fifoCache.put(6, 6); // Access existing data fifocache.get (3); System.out.println(" After existing data is accessed :" + fifocache.tostring ()); fifoCache.put(10, 10); System.out.println(" + fifocache.toString ()); }}Copy the code

Output:

Initial situation: {0 = 0, 1 = 1, 2 = 2, 3 = 3 and 4 = 4, 5 = 5, 6 = 6, 7 = 7, 8 = 8, 9 = 9} after the existing data is accessed: {0 = 0, 1 = 1, 2 = 2, 4 = 4, 5 = 5, 7 = 7, 8 = 8, 9 = 9, 6 = 6, 3 = 3} after a new data: {1 = 1, 2 = 2, and 4 = 4, 5 = 5, 7 = 7, 8 = 8, 9 = 9, 6 = 6, 3 = 3 and 10 = 10}Copy the code

It can be seen from the output result that it conforms to LRU rule

conclusion

LinkedHashMap is almost identical to HashMap, except that the node class has before and after attributes and maintains a bidirectional list for insertion order (default) or access order sorting

reference

https://blog.csdn.net/u012403290/article/details/68926201