HashMap JDK1.8 base and source code analysis
// LinkedHashMap descends from HashMap, Public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> Public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, SerializableCopy the codeBefore and after can point to the LinkedHashMapEntry of other buckets. AccessOrder determines the order of iteration output, first in the order of insertion and second in the order of access.
Next can only point to other nodes in this bucket. JDK1.7 is a header interpolation method, JDK1.8 is a tail interpolation method.
The core of the LruCache/DiskLruCache cache is as follows: LRU(Least Recently Used) Algorithm. When the cache is about to be full, the Least Recently Used cache objects are discarded. If it is full, use the LinkedHashMap iterator to delete the header element. removeEldestEntry
Let’s take a look at what LinkedHashMap can do:
-
AccessOrder = false traverses nodes in the order in which they were inserted
-
The assessOrder = true is the order of the accesses
System.out.println("Here is accessOrder=false: the default is false");
Map<String, String> map = new LinkedHashMap<>();
map.put("1"."a");
map.put("2"."b");
map.put("3"."c");
map.put("2"."d");
map.get("1");
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("Here is accessOrder=true :");
map = new LinkedHashMap<String, String>(16, 0.75f, true);
map.put("1"."a");
map.put("2"."b");
map.put("3"."c");
map.put("5", null);
map.put("3"."e"); //3 adjust to the end of map.get("2"); Iterator = map.entryset ().iterator(); iterator = map.entryset ().iterator();while(iterator.hasNext()) { System.out.println(iterator.next()); } The following is accessOrder=falseThe default value isfalse1=a 2=d // The value is updated, but the traversal order is not changedtrue5= NULL 3=e 2=b // The most recently accessed map, and the last outputCopy the codeLinkedHashMap
Head /tail The head node and the tail node
The constructor has an additional accessOrder, which defaults to false
<K,V> head; // Tail /youngest transient LinkedHashMapEntry<K,V> tail; 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, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
Copy the codeLinkedHashMapEntry: Node structure of the LinkedHashMap
The LinkedHashMap node has more references to before and after than the HashMap node, but the constructor does not have before and after. We overwrite the NewNode() of the HashMap to assign before and after indirectly.
LinkedHashMap does not overwrite put(K key, V value), but instead calls the HashMap put(key, value), and does not create a new Node through HashMap’s new Node(). Instead, call newNode() to create a LinkedHashMapEntry node.
By default, a LinkedHashMapEntry is created by placing the newly inserted node at the end of the bidirectional list.
Static class LinkedHashMapEntry<K,V> extends Hashmap. Node<K,V> {LinkedHashMapEntry<K,V> before, after; LinkedHashMapEntry(inthash, K key, V value, Node<K,V> next) {
super(hash, key, value, next); } // return a LinkedHashMapEntry Node<K,V> newNode(inthash, K key, V value, Node<K,V> e) {
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
linkNodeLast(p);
returnp; Private void linkNodeLast(LinkedHashMapEntry<K,V> p) {LinkedHashMapEntry<K,V> last = tail; // tail = p;if(last == null) // If the last node is null, then it is an empty list, head points to the new node head = p;else{// If the last node is not empty, p is inserted into the end of the list; After points to the new node. P.before = last; last.after = p; }}Copy the codeNewNode() of the hashMap returns the Node constructor directly to get a Node
// Implementation of HashMap Node<K,V> newNode(inthash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
Copy the codePut (K key, V value) Insert/update operation
Add put, remove, change PUT, and find GET on a HashMap all call the following methods. HashMap is an empty implementation. The real implementation is in LinkedHashMap.
// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node<K,V> p) {} void afterNodeAccess(Node<K,V> p) { afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node<K,V> p) { }Copy the codeLinkedHashMap does not override the put operation, but instead calls the HashMap put(key, value). If no identical key exists, newNode() creates a LinkedHashMapEntry node, which is added to the end of the two-way list.
-
Analysis 1: The afterNodeAccess(e) callback, the changed operation, may change the access order when there is key-like data
-
Analysis 2: Insert a new data at afterNodeInsertion(True) if no data with the same key exists.
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) {
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 {
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)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
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 mappingfor key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // See analysis 1return oldValue;
}
}
++modCount;
if(++size > threshold) resize(); afterNodeInsertion(evict); // See analysis 2return null;
}
Copy the codeafterNodeAccess(Node<K,V> e)
AfterNodeAccess () is called when newValue is used instead of oldValue when the same key exists in the put operation.
Only if the accessOrder is true, i.e. iterating through the accessOrder, will the Node be moved to the end of the bidirectional list, achieving the last output of the most recent access, and at the head of the bidirectional list that has not been updated for a long time.
- Analysis 1: When accessOrder is true and e! = tail; That is, it is traversed in access order, and e is not a tail node (the current node has already been added to the end of the list through newNode (), so no operation is required).
- Analysis 2: If e is a header, i.e. e.before is null, head points to E. after. Otherwise, after of the previous node of E will point to e.after
- Analysis 3: If e is the tail node, that is, e.after is null and tail points to E. before. Otherwise, the before of the next node of e will point to E.before
- Analysis 4: If the tail node is null, head points to E; Otherwise add e to the end of the list, e.before=tail, tail.after=e;
- Analysis 5: The tail node points to the changed node E
Void afterNodeAccess(Node<K,V> e) {// Move Node to last LinkedHashMapEntry<K,V> last;if(accessOrder && (last = tail) ! 1 LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; p.after = null;if(b == null) head = a;else
b.after = a;
if(a ! = null) // end node, see analysis 3 a.before = b;else
last = b;
if(last == null);else{ p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the codeafterNodeInsertion(boolean evict)
AfterNodeAccess () is called when adding a new map through newNode() if the same key does not exist during the put operation.
AfterNodeInsertion (true) does not need to perform before/after/head/tail operations because newNode() will add the newNode to the end of the list.
When evict is true and is not an empty list, and the oldest node needs to be removed, the head header is removed. RemoveNode is an implementation in the HashMap. The default is to delete an invalid node. Building a LruCache returns true when it reaches the upper limit of the Cache and deletes the least recently used node when the container is nearly full.
Void afterNodeInsertion(Boolean evict) {// Possibly remove Eldest LinkedHashMapEntry<K,V> first;if(evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false.true); }} // Return by defaultfalseThe node is not deleted. Building a LruCache returns when the Cache reaches its upper limittrue
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
Copy the codeRemove (Object key) Delete operation
When LinkedHashMap did not implement Remove (), I visted deremoval () to delete the pointer of the linked list.
//hashPublic 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(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
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;
if (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) node = p;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);
}
}
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;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the codeafterNodeRemoval(Node<K,V> e)
Analysis 1: If e is the header, head points to e.after; Otherwise, after of the previous node of e points to e.after
Analysis 2: If e is the tail node, tail points to e.befor. Otherwise, the before of the next node of e points to e.before
// Unlink LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<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) // see 2 tail = b;else
a.before = b;
}
Copy the codeGet (Object key) Query operation
Get for LinkedHashMap is basically the same as get() for HashMap, except when accessOrder is true, the accessOrder is changed, putting the current node at the end of the bidirectional list to achieve the last output of the most recent access.
Public V get(Object key) {Node<K,V> e;if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
Copy the codecontainsValue(Object value)
LinkedHashMap traversal matches against the head of a bidirectional list;
The HashMap loops twice, first through the array of tables and then through the single linked list of each table[I] in the table.
Public Boolean containsValue(Object value) {for(LinkedHashMapEntry<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;
}
Copy the codePublic Boolean containsValue(Object value) {Node<K,V>[] TAB; V v;if((tab = table) ! = null && size > 0) {for (int i = 0; i < tab.length; ++i) {
for(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 codeconclusion
1. Array + single linked list, in addition to the implementation of a bidirectional list structure (bidirectional list is sequential), hashMap has all the features.
2. If accessOrder is false, iterate in insert order; An accessOrder of true iterates over in accessOrder (the default accessOrder is false).
3, put insertion, afterNodeInsertion() Whether to delete the oldest nodes that have not been accessed and updated for a long time.
AfterNodeAccess () only changes the order of links in a bidirectional list if accessOrder is true.
The order of the link in the two-way linked list will be changed when they are washed, visting deremoval ()
AfterNodeAccess will only change the order of links in two-way lists if accessOrder is true.