One, foreword

LinkedHashMap descends from HashMap, so it is recommended that you learn the HashMap series before this article to make it easier to understand.

A HashMap series

(1) HashMap series: load factor 0.75

(2) HashMap series: Tree threshold 8, degradation threshold 6

(3) HashMap series: 2 power expansion

(4) HashMap series: Put elements (you will regret it forever!)

2. Use LinkedHashMap

A lot of people might say, LinkedHashMap, who doesn’t use LinkedHashMap? Are you sure you can use it?

Before the example above, let’s write a few tool methods to make it easier to understand later:

Public class Main {// String left aligned (regardless of Chinese and English length, Private static String spaceFill(Object Object) {return string. format("%-20s", Object); } // reflection gets array objects in HashMap // what? You don't know the array object name? // Check the source code. Private static map. Entry<Integer, String>[] getArray(Object Object, Field field) throws Exception { return (Map.Entry<Integer, String>[]) field.get(object); } // Reflection get map. Entry // Because hashmap. Node is a private static class private static map. Entry<Integer, String> getObject(Object Object, String name) throws Exception { Field field = getField(object.getClass(), name); return (Map.Entry<Integer, String>) field.get(object); } private static Field getField(Class<? > clazz, String name) { if (clazz == null) { return null; } Field field = null; try { field = clazz.getDeclaredField(name); field.setAccessible(true); } catch (NoSuchFieldException e) { field = getField(clazz.getSuperclass(), name); } return field; }}Copy the code

Ok, the above tool method is complete and will be used in all the following examples.

Let’s look at two examples:

2.1. Example 1

Public class Main {public static void Main (String[] args) {// We use the default constructor LinkedHashMap<Integer, String> map = new LinkedHashMap<>(); map.put(1, "chris"); map.put(2, "qingye"); map.put(3, "[email protected]"); Field Field = getField(map.getclass (), "table"); if (field ! = null && field.getType().isarray ()) {try {// Map.Entry<Integer, String>[] table = getArray(Map, field); for (int i = 0; i < table.length; i ++) { if (table[i] ! Map.Entry<Integer, String> before = getObject(table[I], "before"); Map.Entry<Integer, String> after = getObject(table[i], "after"); if (before == null) { System.out.print("This is Head "); } else if (after == null) { System.out.print("This is Tail "); } else { System.out.print("\t\t\t "); } System.out.println("[" + i + "] => " + spaceFill(table[i]) + ", before => " + spaceFill(before) + ", after => " + spaceFill(after)); } } } catch (Exception e) { } } } }Copy the code

Output result:

This is Head [1] => 1=chris             , before => null                , after => 2=qingye            
    		 [2] => 2=qingye            , before => 1=chris             , after => [email protected]   
This is Tail [3] => [email protected]   , before => 2=qingye            , after => null   
Copy the code

2.2. Example 2

Public class Main {public static void Main (String[] args) {// Specify constructor to initialize LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true); map.put(1, "chris"); map.put(2, "qingye"); map.put(3, "[email protected]"); map.get(1); Field = getField(map.getclass (), "table"); if (field ! = null && field.getType().isArray()) { try { Map.Entry<Integer, String>[] table = getArray(map, field); for (int i = 0; i < table.length; i ++) { if (table[i] ! = null) { Map.Entry<Integer, String> before = getObject(table[i], "before"); Map.Entry<Integer, String> after = getObject(table[i], "after"); if (before == null) { System.out.print("This is Head "); } else if (after == null) { System.out.print("This is Tail "); } else { System.out.print("\t\t\t "); } System.out.println("[" + i + "] => " + spaceFill(table[i]) + ", before => " + spaceFill(before) + ", after => " + spaceFill(after)); } } } catch (Exception e) { } } } }Copy the code

Output result:

This is Tail [1] => 1=chris             , before => [email protected]   , after => null                
This is Head [2] => 2=qingye            , before => null                , after => [email protected]   
    		 [3] => [email protected]   , before => 2=qingye            , after => 1=chris   
Copy the code

WTF? ! What happened? How did the [1] element change from “Head” to “Tail”? That’s the beauty of LinkedHashMap!

Three, in-depth understanding of LinkedHashMap mystery

3.1 Relationship between LinkedHashMap and HashMap

PutXXX and getXXX of LinkedHashMap inherit from HashMap without overloading. PutXXX and getXXX of LinkedHashMap inherit from HashMap without overloading. PutXXX and getXXX of LinkedHashMap inherit from HashMap without overloading. What is the logic of put & Get for HashMap? If you’ve forgotten, check out my (4) HashMap series: Put elements. . As inheritance, their array structures are almost identical (99% identical) :

Data structure: array + linked list <– > red-black tree

Where is the 1% discrepancy?

3.2, the Map Entry

A HashMap node implements map.entry:

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable { static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; 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

What about the LinkedHashMap node?

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { 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

Ugh, it’s so damn simple! There are only two more index (pointer) nodes: before & After!

3.3, a HashMap. TreeNode

The TreeNode type was not mentioned in the previous section of HashMap. As it relates to LinkedHashMap, the TreeNode type is modified.

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable { 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; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); }}Copy the code

Perfect inheritance:

3.4, before & after

From the names of the two fields, it’s easy to guess which one points to the previous node and which one to the next (in fact, our first two examples proved this relationship). So how does this relationship manifest itself in data structures, or node objects?

Drawing is very hard…… The main purpose of LinkedHashMap is to add before and after indexes:

  • Bidirectionally linked lists (that is, bidirectionally accessible) allow the start node to be traversed all the way to the last node without having to navigate to the bucket halfway;
  • Can be accessed in insert order (default).

4. Special features of LinkedHashMap

/**
 * The iteration ordering method for this linked hash map: true for access-order, false for insertion-order.
 */
final boolean accessOrder;
Copy the code

The meaning of this field:

  • When true, elements in a bidirectional list are traversed in access order (LRU);
  • When false, elements in a bidirectional list are traversed in insertion order (default);

The implementation of LRU in Android system is actually based on LinkedHashMap and uses the way of [Example 2] to initialize the object instance.

Five, LinkedHashMap index source code implementation

We also analyzed the source from the put element. Remember when we analyzed putVal of HashMap, there were two empty functions?

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { ...... else { ...... if (e ! = null) {// The element already exists...... afterNodeAccess(e); Return oldValue; }}... afterNodeInsertion(evict); Return null; }}Copy the code

5.1, LinkedHashMap. AfterNodeAccess

This method is triggered by several other methods, such as put an existing node object, get object, replace object, and so on. This method is the traversal access order that determines whether it needs to be adjusted.

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; If (accessOrder && (last = tail)! // p points to e itself, b points to the one before e, Entry<K,V> p = (linkedhashmap. Entry<K,V>)e, b = p.before, a = P.after; p.after = null; If (b == null) head = a; // If (b == null) head = a; else b.after = a; // If a is null, e is the last node of e. // If a is null, e is the last node of e. = null) a.before = b; else last = b; If (last == null) head = p; if (last == null) head = p; Else {// otherwise, move p to the last (i.e. the last logical position) p.before = last; last.after = p; } tail = p; // Finally, tail to the last element ++modCount; }}}Copy the code

5.2, LinkedHashMap. AfterNodeInsertion

Public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> Call this method to determine if we need to remove the oldest node // since accessOrder = true, the most visited node must be at the end of the chain, Void afterNodeInsertion(Boolean evict) {// Possibly remove eldest linkedhashmap. Entry<K,V> first; if (evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; RemoveNode (hashmap.removenode); removeNode (hashmap.removenode); Adjust removeNode(hash(key), key, NULL, false, true); }}}Copy the code

5.3, LinkedHashMap. RemoveEldestEntry

Public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { Protected Boolean removeEldestEntry(map. Entry<K,V> younger) {return false; }}Copy the code

Then why do I keep mentioning LRU? Because if we implement LRU ourselves based on LinkedHashMap, we can override this method and return true, thus achieving the effect of LRU.

Well, enough for LinkedHashMap!