An overview of the
In this article, we will analyze LinkedHashMap.
Take a look at the class inheritance structure of LinkedHashMap:
You can see that LinkedHashMap inherits from HashMap.
We know that the HashMap is unordered, meaning that the order of the iterators has nothing to do with the insertion order. LinkedHashMap adds order to HashMap: insert order and access order, respectively. That is, traversing the LinkedHashMap keeps the same order as the insertion order; Or the order consistent with the order of access.
How are these two orders implemented internally in LinkedHashMap? It is maintained by a double-linked list. Therefore, you can think of a LinkedHashMap as “double linked list + hash” or “ordered hash”.
The code analysis
Node class Entry
LinkedHashMap has a nested class Entry that inherits from the Node class in HashMap as follows:
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); }}
static class Node
implements Map.Entry
{ final int hash; final K key; V value; Node
next; Node(int hash, K key, V value, Node
next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } / /… }
This Entry class is the node class in the LinkedHashMap.As you can see, it adds before and after variables to the Node class, which hold the Node’s precursor and successor (It can also be inferred from the literal meaning) to maintainLinkedHashMapThe order.
Member variables
/** * The head (eldest) of the doubly linked list. */transient LinkedHashMap.Entry
head; /** * The tail (youngest) of the doubly linked list. */transient LinkedHashMap.Entry
tail; /** * The iteration ordering method for this linked hash map: True * for access-order, false for insertion-order. False indicates the insertion order. */final boolean accessOrder;
The constructor
Constructor 1:
/ * * * Constructs an empty insertion-ordered LinkedHashMap instance * with the default initial capacity (16) and load factor (0.75).* /public LinkedHashMap(a) { super(); accessOrder = false;}
The super() method here calls the no-parameter constructor of the HashMap. The constructor method constructs an empty LinkedHashMap with a capacity of 16 (the default initial capacity) and a load factor of 0.75 (the default load factor), in insert order.
Constructors 2, 3, 4, 5:
public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false;}public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false;}
public LinkedHashMap(Map<? extends K, ? extends V> m) { super(a); accessOrder = false; putMapEntries(m, false);}public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;}
You can see that all of the above constructors were initialized by calling the constructor method of the parent class (HashMap), which is no longer analyzed. The default value of the accessOrder variable for the first four constructors is false; The last one is slightly different in that its accessOrder can be specified at initialization, which specifies the order (insert or accessOrder) of the LinkedHashMap.
Put method
LinkedHashMap itself does not implement the PUT methodIt reads and writes by calling the methods of its parent class (HashMap). Here is the put method for HashMap:
public V put(K key, V value) { return putVal(hash(key), key, value.false.true);}final V putVal(int hash, K key, V value, boolean> boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)// New bin node tab[i] = newNode(hash, key, value.null); else { Node<K,V> e; K k;// Key already exists if (p.hash == hash &&((k = p.key) == key || (key ! =null && key.equals(k)))) e = p;// hash conflict else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {// Iterate over the list for (int binCount = 0; ; ++binCount) {// Insert the new node to the end of the list if ((e = p.next) == null) { p.next = newNode(hash, key, value.null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash &&((k = e.key) == key || (key ! =null && key.equals(k)))) break; p = e; } } if(e ! =null) { // existing mapping for key V oldValue = e.value; if(! onlyIfAbsent || oldValue ==null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null;}
Where is this method associated with LinkedHashMap? How do I preserve the order of the LinkedHashMap? Look at the newNode() method, which has the following code in the HashMap:
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next);}
However, LinkedHashMap overrides this method:
// Create a new linkedhashmap.entry nodeNode<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);// Connect the new node to the end of the list linkNodeLast(p); return p;}
// link at the end of listprivate void linkNodeLast(LinkedHashMap.Entry
p) { LinkedHashMap.Entry
last = tail; tail = p; If (last == null) head = p; Else {// Insert the new node at the end of the list p.before = last; last.after = p; }}
As you can see, each time a new node is inserted, it is saved to the end of the list. This is where the insertion order of the LinkedHashMap is implemented.
AfterNodeAccess and afterNodeInsertion are two callback methods. theyEmpty in HashMap:
// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node<K,V> p) {}void afterNodeInsertion(boolean evict) {}
Again, LinkedHashMap overwrites them. AfterNodeAccess:
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last;// accessOrder is true to indicate the accessOrder if(accessOrder && (last = tail) ! = e) {// p is the node to be accessed, b is its precursor, and a is its successor LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null;// p is the head node 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; }}
To facilitate analysis and understanding, two operation diagrams are drawn here:
Two situations before and after this operation are described here. As you can see, the node P is moved to the end of the list after this method is executed.
The get method
LinkedHashMap rewrites the get method of HashMap, mainly to maintain access order, as follows:
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null;// Move the accessed nodes to the end of the list if (accessOrder) afterNodeAccess(e); return e.value;}
The getNode method here is the parent (HashMap). If accessOrder is true (that is, the accessOrder is specified), the accessed nodes are moved to the end of the list.
AfterNodeInsertion method rewritten in LinkedHashMap
The removeNode method is in the parent class HashMap.
final Node<K,V> removeNode(int hash, Object key, Object value. boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index;// Table is not empty and the hash value given is not empty if((tab = table) ! =null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) ! =null) { Node<K,V> node = null, e; K k; V v;// The node corresponding to the given key is the first position in the array if (p.hash == hash &&((k = p.key) == key || (key ! =null && key.equals(k)))) node = p;// The location of the given key is a red-black tree or linked list else if((e = p.next) ! =null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key ||(key ! =null && key.equals(k)))) { node = e; break; } p = e; } while((e = e.next) ! =null); } }// Delete a node if(node ! =null&& (! matchValue || (v = node.value) = =value || (value! =null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size;// The operation after the node is deleted afterNodeRemoval(node); return node; } } return null;}
In the HashMap, the vide-emoval method is also empty:
void afterNodeRemoval(Node<K,V> p){}Copy the codeLinkedHashMap overrides this method:
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;}
This method is the operation of deleting a node from a doubly linked list.
Code to rehearse
Use LinkedHashMap
We know that HashMap is unordered, for example:
Map<String, String> map = new HashMap<>();map.put("bush"."a");map.put("obama"."b");map.put("trump"."c");map.put("lincoln"."d");System.out.println(map);// Output result (out of order) :// {obama=b, trump=c, lincoln=d, bush=a}
Instead of LinkedHashMap, you can keep the insertion order:
Map<String, String> map = new LinkedHashMap<>();map.put("bush"."a");map.put("obama"."b");map.put("trump"."c");map.put("lincoln"."d");System.out.println(map);// Output result (insert order) :// {bush=a, obama=b, trump=c, lincoln=d}
Specify the order of LinkedHashMap as access order:
Map<String, String> map = new LinkedHashMap<>(2.0.75 f.true);map.put("bush"."a");map.put("obama"."b");map.put("trump"."c");map.put("lincoln"."d");System.out.println(map);map.get("obama");System.out.println(map);// Output result (insert order) :// {bush=a, obama=b, trump=c, lincoln=d}// After visiting Obama, Obama moves to the end// {bush=a, trump=c, lincoln=d, obama=b}
Implement LRU cache
private static class LRUCache<K.V> extends LinkedHashMap<K.V> { private int capacity; public LRUCache(int capacity) { super(16.0.75 f.true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }}
Examples:
LRUCache<String.String> lruCache = new LRUCache<>(2);lruCache.put("bush"."a");lruCache.put("obama"."b");lruCache.put("trump"."c");System.out.println(lruCache);// Output result:// {obama=b, trump=c}
In the LRUCache class defined here, the removeEldestEntry method is overridden to remove the earliest inserted element “bush” when the cache capacity is greater than 2. So there are only two values left.
summary
1. LinkedHashMap inherits from HashMap, and its structure can be understood as “double linked list + hash table”;
2. Two kinds of sequences can be maintained: insert sequence or access sequence;
3. LRU cache can be conveniently implemented;
4. Threads are unsafe.
Stay hungry, stay foolish.
