LinkedHashMap source code analysis
Last week I learned the source code of HashMap and felt a lot. Although I have not filled in the hole of red and black tree, I have looked at the source code of LinkedHashMap without shame. Because LinkedHashMap does have a lot to do with HashMap, I’m sure you’ll feel the same way after reading this article. In this article, we will analyze the source code of LinkedHashMap from the following aspects:
- Relationship between LinkedHashMap and HashMap
- LinkedHashMap Bidirectional linked list construction process
- LinkedHashMap Process of deleting a node
- How does LinkedHashMap maintain access order
- LinkedHashMap – The simplest way to build LRU (Least Recently Used)
Relationship between LinkedHashMap and HashMap
Let’s take a look at the LinkedHashMap architecture:
LinkedHashMap is directly derived from HashMap, which shows that all the important concepts of HashMap are owned by LinkedHashMap, including, Hash algorithms locate hash buckets, hash tables are made up of arrays and single-linked lists, and when the single-linked list is longer than 8, it turns into red-black trees and expands the system, just like a HashMap. So despite these key similarities, LinkedHashMap is more powerful than HashMap in the following ways:
LinkedHashMapInternal maintenance of a bidirectional linked list, solvedHashMapThe problem of not always keeping the traversal order and insertion order the sameLinkedHashMapThe order in which elements are accessed also provides support, known as the LRU (least recently used) principle.
There is also a source code analysis of these two differences and how to apply them.
LinkedHashMap Bidirectional linked list construction process
To make things easier to understand, before looking at the source code, let’s take a look at a diagram that nicely illustrates the relationships between LinkedHashMap elements:
Assume that the red and yellow arrows represent the order in which elements are added and the blue arrows represent the order in which elements are stored in a single linked list. Head represents the head of the bidirectional list, and tail represents the tail of the bidirectional list
When analyzing the source code of HashMap in the last article, we have a diagram showing the storage structure of HashMap as array + single linked list + red-black tree. From the above picture, we can also see that the underlying storage structure of LinkedHashMap has not changed.
The only change is the use of a bidirectional list (red and yellow arrows) to record the order in which elements are added. We know that the nodes in the HashMap only have a next pointer, which is not enough for a bidirectional list. So LinkedHashMap extends the Node:
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 codeThe LinkedHashMap basic storage unit Entry
inherits from Hashmap. Node
and adds before and after pointer variables to it. The before variable will link to the last added element each time an element is added, and the after variable of the last added element will point to the last added element, forming a two-way link. Note that LinkedHashMap does not overwrite anything about the HashMap PUT method. So the put method that calls LinkedHashMap actually calls the method of the parent class HashMap. Let’s put the putVal method of HashMap to make it easier to understand.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
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)
tab[i] = newNode(hash, key, value, null);
else{/ /hashCollision Node<K,V> e; K k;if (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p;else if(p instanceof TreeNode){.... }else {
//hashValue evaluates to the same array index, but with different keysfor (int binCount = 0; ; ++binCount) {
if((e = p.ext) == null) {// iterate to the end of the list // create a newNode, join to the end of the list p.ext = newNode(hash, key, value, null); .break; } // If the key of a node in the list is the same as the key of the current element to be inserted, the node indicated by e is the node whose Value needs to be replaced, and the loop is terminatedif (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))break; P = e; }} // If the loop is complete, e! =null indicates that the Value of the node referred to by E needs to be replacedif(e ! = null) {oldValue = e.value// Save the original Value as the returned Value // onlyIfAbsent is generally set tofalseSo replace the Valueif(! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // The implementation of this method in LinkedHashMap is explained laterreturnoldValue; }} // operand increment ++modCount; // If size is greater than the capacity expansion threshold, capacity expansion is requiredif (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeIt can be seen that each time a newNode is added, the newNode method is actually called to generate a newNode and put into the specified hash bucket. However, it is obvious that the newNode method in the HashMap cannot complete the relationship between the bidirectional linked list nodes mentioned above. So LinkedHashMap duplicates this method:
// implement Node<K,V> newNode(inthash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next); } // LinkedHashMap implementation of newNode Node<K,V> newNode(inthash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e); // attach the Entry to the end of the bidirectional list linkNodeLast(p);return p;
}
Copy the codeLinkNodeLast (); linkNodeLast (); linkNodeLast ();
/** * This reference always points to the head of the bidirectional list */ TRANSIENT linkedhashmap. Entry<K,V> head; /** * This reference always points to the end of the bidirectlist */ TRANSIENT linkedhashmap. Entry<K,V> tail;Copy the code// newNode newNode, Private void linkNodeLast(linkedhashmap.entry <K,V> p) {// Before adding elements linkedhashmap.entry <K,V> last = tail; // tail points to the newly added node tail = p; Head = tail = pif (last == null)
head = p;
else{// Otherwise, the new node's before reference points to the end of the previous list. Last. After = p; }}Copy the code
The steps for creating a LinkedHashMap list can be described in the figure above. The blue part is the method of HashMap, and the orange part is the unique method of LinkedHashMap.
When we create a new node, through linkNodeLast method, the new node and two-way chain table before the last node (tail), we still don’t know this node in this operation is stored in a hash table, but no matter what he was in place, the relationship between the node will join the two-way linked list. Nodes 3 and 4 have references to each other, as in the figure above, ensuring that the relationship between the elements of the bidirectional list is the order in which they are added.
LinkedHashMap Operation of deleting a node
Like the insert operation, LinkedHashMap does not override the remove method. It still uses code from HashMap. Let’s recall the remove method from HashMap:
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false.true)) == null ? null : e.value; } // Final Node<K,V> removeNode(inthash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; // Check whether the hash table is empty and whether the length is greater than 0if((tab = table) ! = null && (n = tab.length) > 0 && (p = tab[index = (n - 1) &hash])! // node < k, v > node = null, e; // node < k, v > node = null, e; K k; V v; // If the first node is the one we are looking for, assign it directly to nodeif (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) node = p;else if((e = p.next) ! = null) {// Walk through the red-black tree to find the corresponding nodeif (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else{// Walk through the corresponding list to find the corresponding nodedo {
if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k)))) { node = e;break;
}
p = e;
} while((e = e.next) ! = null); }} // If the node is found //! MatchValue whether not to delete the node / / (v = node. The value) = = value | | (value! = null && value.equals(v)));if(node ! = null && (! matchValue || (v = node.value) == value || (value ! = null && value.equals(v)))) {// delete the nodeif (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
elsep.next = node.next; ++modCount; --size; afterNodeRemoval(node); // Note that this method is called after the Hash table is deletedreturnnode; }}return null;
}
Copy the codeLinkedHashMap removes nodes in the Hash table by calling the remove method of HashMap of the parent class, that is:
- Obtain the hash(key) of the corresponding key and locate the corresponding hash bucket
- Traverse the single-linked list or red-black tree in the corresponding hash bucket to find the node with the same key, delete it at the end, and return the original node.
In this way, LinkedHashMap can delete the relation of the corresponding node in the two-way linked list:
Void void empderemoval (Node<K,V> e) {linkedhashmap. Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; P.before = p.after = null; // p.before is null, indicating that p is the head nodeif (b == null)
head = a;
else// otherwise connect the front drive node of p to the rear drive node of P. // IF a is null, p is the tail nodeif (a == null)
tail = b;
else// otherwise connect a to b a.before = b; }Copy the codeTherefore, the procedure for deleting the LinkedHashMap node is as follows:
LinkedHashMap Maintains the access sequence of nodes
Above, we analyzed the differences between LinkedHashMap and HashMap in adding and removing elements. We can see that in addition to maintaining the relationship of elements in the Hash table, LinkedHashMap also maintains a two-way linked list when adding and removing elements. So what does this bidirectional list do? Let’s look at the following example, where we can compare the result of traversing the Map with the same element addition order:
//Map<String, Integer> map = new HashMap<>(); Map<String, Integer> map = new LinkedHashMap<>(); //Map<String, Integer> Map = new LinkedHashMap<>(10,0.75f,true);
map.put("The boss", 1);
map.put("The second", 2);
map.put("Old", 3);
map.put("Old four", 4);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
Iterator iter1 = entrySet.iterator();
while (iter1.hasNext()) {
Map.Entry entry = (Map.Entry) iter1.next();
System.out.print("key: " + entry.getKey() + "");
System.out.println("value: " + entry.getValue());
}
System.out.println("The value of the third is:" + map.get("Old"));
System.out.println("The value of eldest is:" + map.put("The boss", 1000)); Iterator iter2 = entrySet.iterator();while(iter2.hasNext()) {// Obtain the key and value map.Entry entry = (map.entry) iter2.next(); System.out.print("key: " + entry.getKey() + "");
System.out.println("value: " + entry.getValue());
}
Copy the code/*** HashMap result */ key: second value: 2 key: fourth value: 4 key: third value: 3 key: first value: 1 Key: second value: 2 key: old four value: 4 key: old three value: 3 key: old number value: 1000 /*** LinkedHashMap Traversal result */ key: old number value: 1 key: old number value: 2 Key: the third value: 3 Key: the fourth value: 4 The value of the third value: 3 The value of the oldest value: 1 Key: the oldest value: 1000 Key: the second value: 2 Key: the third value: 3 key: Old four value: 4Copy the codeIt can be seen from the results of the above methods:
HashMapThe result of traversal is independent of the order of additionLinkedHashMapThe result of traversal is the add order
That’s what bidirectional lists do. Bidirectional lists can do more than that. Before introducing bidirectional lists to maintain access order, let’s take a look at one important parameter:
final boolean accessOrder; // Whether to maintain the element access order in the bidirectional listCopy the codeThis method is initialized with the LinkedHashMap constructor parameter. AccessOrder defaults to false. We can specify the value of this parameter through three parameter constructors.
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false); } public LinkedHashMap(int initialCapacity, int initialCapacity, int initialCapacity);float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
Copy the codeWe try to create the Map in the example above using the three-parameter constructor and see the results below
Value: 1 Key: second value: 2 key: third value: 3 key: fourth value: 4 The value of the third is: 3 The value of the first value is: 1 // The second traversal key: second value: second value: second value: 2 Key: old four value: 4 Key: old three value: 3 Key: old value: 1000Copy the codeYou can see that when we use access to true, the order in which we access the elements will be reflected in the next iteration, and the last element will be retrieved last. Void afterNodeAccess(Node
e) {putVal/get/repalce; However, in LinkedHasMap, this postfix method will be an important method to maintain the order of node access. Let’s take a look at its implementation:
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; // Access node afterdrive is null p.after = null; // If the node access precursor is NULL, p = headif (b == null)
head = a;
elseb.after = a; // If p is not the tail node, set the precursor of A to Bif(a ! = null) a.before = b;else
last = b;
if (last == null)
head = p;
else{ p.before = last; last.after = p; } tail = p; // add p to the end of the bidirectional list ++modCount; }}Copy the codeHere’s an example of what the afterNodeAccess process might look like. Let’s say we’re accessing node 13, 14 is the last driver, 11 is the first driver, and tail = 14. After accessing the 13 node through get, 13 becomes the tail node, 14 becomes its precursor, the corresponding precursor of 14 becomes 11, the trailing of 11 becomes 14, and the trailing of 14 becomes 13.
AfterNodeAccess allows the bidirectional LinkedHashMap to maintain the access order of elements in the hash table with accessOrde = true.
In the above test example, the LinkedHashMap iterator is used. Due to the existence of bidirectional linked lists, it is more efficient than HashMap to traverse nodes. Let’s compare the nextNode method in the two iterators:
Final Node<K,V>nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if(modCount ! = expectedModCount) throw new ConcurrentModificationException();if(e == null) throw new NoSuchElementException(); // Walk through the table to find the next one that holds the elementhashbarrelif((next = (current = e).next) == null && (t = table) ! = null) {do {} while (index < t.length && (next = t[index++]) == null);
}
returne; } // LinkedHashIterator nextNode method final linkedhashmap.entry <K,V>nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if(modCount ! = expectedModCount) throw new ConcurrentModificationException();if(e == null) throw new NoSuchElementException(); current = e; Next = e.footer; // Next = e.footer;return e;
}
Copy the codeMore notably, we can look at both containsValue methods:
Public Boolean containsValue(Object value) {// Go through the list directly to find the corresponding nodefor(LinkedHashMap.Entry<K,V> e = head; e ! = null; e = e.after) { V v = e.value;if(v == value || (value ! = null && value.equals(v)))return true;
}
return false; Public Boolean containsValue(Object value) {Node<K,V>[] TAB; V v;if((tab = table) ! = null && size > 0) {// iterate over the hash bucket indexfor(int i = 0; i < tab.length; ++ I) // Traverses the list or red-black tree in the hash bucketfor(Node<K,V> e = tab[i]; e ! = null; e = e.next) {if((v = e.value) == value || (value ! = null && value.equals(v)))return true; }}}return false;
}
Copy the codeThe simplest LRU build in Java
LRU class LruCache class LruCache class LruCache class LruCache class LruCache class LruCache class LruCache class Interested students can go to see the Glide cache source code analysis.
The key to the implementation of the LRU algorithm is as its name suggests. When a predetermined threshold is reached, which may be low memory or maximum capacity, the least recently used storage element is found and removed to ensure that the newly added element can be saved into the collection.
Let’s take a look at the simplest implementation of the LRU algorithm in Java. Void afterNodeInsertion(Boolean evict) {} Void afterNodeInsertion(Boolean evict) {} LinkedHashMap overrides this method:
PutVal in HashMap implements evICT passingtrue, indicating that the table is in create mode. 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 onlyIfAbsent, boolean evict) { .... } // EVICT is passed in most cases as described abovetrueVoid afterNodeInsertion(Boolean evict) {// Possibly remove Eldest linkedhashmap. Entry<K,V> first; // Because evict =trueRemoveEldestEntry (first) returns when the list is not emptytrueWhen enteringifinternalif(evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false.true); }} //LinkedHashMap returns by defaultfalseThe node is not deleted. returntrueProtected Boolean removeEldestEntry(map. Entry<K,V> Younger) {return false;
}
Copy the codeRemoveEldestEntry (map.Entry
eldest) returns true, afterNodeInsertion insertion after adding a new element The original node of the bidirectional list, the head node, will be removed. So we can start with the removeEldestEntry method to build our LruCache.
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_NODE_NUM = 2<<4;
private int limit;
public LruCache() {
this(MAX_NODE_NUM);
}
public LruCache(int limit) {
super(limitAnd 0.75 f,true);
this.limit = limit;
}
public V putValue(K key, V val) {
return put(key, val);
}
public V getValue(K key) {
returnget(key); } /** * Check whether the number of stored elements is a predetermined threshold * @returnTransfinite returntrueOtherwise returnfalse
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > limit; }}Copy the codeWe build a LruCache class that inherits from LinkedHashMap. When we build, we call the constructor of the three parameters of LinkedHashMap with accessOrder passing true. The removeEldestEntry method is overwritten. When the number of nodes in the Map exceeds the preset threshold, afterNodeInsertion will be performed at putValue to delete the elements that have not been accessed recently. Let’s test it out:
LruCache<String,Integer> LruCache = new LruCache<>(3); lruCache.putValue("The boss", 1);
lruCache.putValue("The second", 2);
lruCache.putValue("Old", 3);
lruCache.getValue("The boss"); LruCache. PutValue (lruCache. PutValue (lruCache. PutValue))"Old four", 4);
System.out.println("lruCache = " + lruCache);
Copy the codeSelect * from node where key = ‘2’;
LruCache = {lruCache =3, lruCache =1, lruCache =4}Copy the codeconclusion
This paper does not analyze the source code of LinkedHashMap from the previous four operations, but through several characteristics of LinkedHashMap that are different from HashMap.
-
LinkedHashMap has the same underlying hash table structure as HashMap, that is, array + single-linked list + red-black tree, and has the same scaling mechanism.
-
LinkedHashMap compared to HashMap, LinkedHashMap maintains a bidirectional linked list with additional entries.
-
The traversal order of a HashMap element is not necessarily the same as the insertion order, whereas a LinkedHashMap obtains elements by traversing a bidirectional linked list, so the traversal order is equal to the insertion order under certain conditions.
-
LinkedHashMap can specify whether an element changes position in the bidirectional list after it is accessed by constructing the accessOrder parameter.
After reading this article, we can easily answer the difference between LinkedHashMap and HashMap. That’s the end of this article. Check out my previous analysis of the source code for other collections if you can’t get enough. (Skin a little, I am very happy ~)
reference
- JDK 1.8 LinkedHashMap & HashMap source code
- Understand the Java HashMap source code
- LinkedHashMap (JDK1.8)