This is the 10th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.
HashMap element inserts are unordered. In order to keep the traversal order consistent with the insert order, we can use LinkedHashMap, which maintains a bidirectional linked list to store the order of elements, and we can control the traversal order through the accessOrder attribute to insert order or accessOrder.
Class structure
LinkedHashMap Class hierarchy diagram:
LinkedHashMap descends from HashMap, and most methods use HashMap directly. Then look at the member variables:
// Head node of bidirectional list (earliest inserted, oldest node)
transient LinkedHashMap.Entry<K,V> head;
// End node of the bidirectional list (latest inserted, youngest node)
transient LinkedHashMap.Entry<K,V> tail;
// Use to control the access order. If true, insert order; If false, access order is used
final boolean accessOrder;
Copy the codeHead and tail use transient decorations for reasons discussed in the HashMap source code.
LinkedHashMap inherits from HashMap, so it stores data internally in the same way as HashMap, using an array plus a linked list (red-black tree) structure. LinkedHashMap maintains an additional two-way linked list compared to HashMap, which stores node order. This bidirectional list is of type linkedhashmap.Entry:
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 codeLinkedhashmap. Entry Class hierarchy diagram:
Linkedhashmap.entry inherits from the Node class of HashMap, adding before and after attributes to maintain the preceding and succeeding nodes to form a bidirectional list.
The constructor
The constructor of LinkedHashMap is nothing special. It calls the parent class’s constructor to initialize the HashMap, with the addition of initializing the accessOrder property of the LinkedHashMap:
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(a) {
super(a); 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;
}
Copy the codeSimple to use
Before analyzing the implementation of the LinkedHashMap method, we first feel the characteristics of LinkedHashMap through an example:
LinkedHashMap<String, Object> map = new LinkedHashMap<>(16.0.75 f.false);
map.put("1"."a");
map.put("6"."b");
map.put("3"."c");
System.out.println(map);
map.get("6");
System.out.println(map);
map.put("4"."d");
System.out.println(map);
//{1=a, 6=b, 3=c}
//{1=a, 6=b, 3=c}
//{1=a, 6=b, 3=c, 4=d}
Copy the codeYou can see that the output order of the elements is the order in which we inserted them.
Change the accessOrder attribute to true:
{1=a, 6=b, 3=c}
{1=a, 3=c, 6=b}
{1=a, 3=c, 6=b, 4=d}
Copy the codeAs you can see, the initial output {1=a, 6=b, 3=c}. {1=a, 3=c, 6=b} when we access the key-value pair with key 6 through get. That is, when the accessOrder attribute is true, the elements are sorted in accessOrder, that is, the most recently accessed elements are moved to the end of the two-way list. This is not the only “access” method. The “access” operations are put, putIfAbsent, GET, getOrDefault, compute, computeIfAbsent, computeIfPresent, and merge methods.
We can see how LinkedHashMap controls the element access order by analyzing the method source code below.
Method resolution
put(K key, V value)
LinkedHashMap does not override the PUT (K key, V value) method, but uses the PUT (K key, V value) method of HashMap directly. The question is, how does LinkedHashMap maintain element order through an internal bidirectional list, since it does not override put(K key, V value)? Put (K key, V value) method source code can be found (because put(K key, V value) source code is analyzed in the java-HashMap implementation principles section, So let’s comment only the code related to the LinkedHashMap function:
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)
// Create a node
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)
// The method contains operations for newTreeNode
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// Create a node
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;
// Subsequent operations on node access
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
// Perform subsequent operations after node insertion
afterNodeInsertion(evict);
return null;
}
Copy the codeLinkedHashMap overrides the newNode method used to create list nodes:
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// Create the linkedhashmap.Entry instance
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// Add the new node to the end of the bidirectional list maintained by LinkedHashMap
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
// If the tail node is empty, the bidirectional list is empty, so assign this node to the head node to initialize the bidirectional list
if (last == null)
head = p;
else {
// Otherwise put the node at the end of the bidirectional listp.before = last; last.after = p; }}Copy the codeAs you can see, for the LinkedHashMap instance, the node type created inside the put operation is LinkedhashMap. Entry. In addition to inserting data into the internal table of the HashMap, data is also inserted into the end of the LinkedHashMap bidirectional list.
If you’re inserting data into a red-black tree, put will call putTreeVal to insert a node into the red-black tree. PutTreeVal internally creates the tree node through the newTreeNode method. LinkedHashMap overrides the newTreeNode method:
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
// Create TreeNode instance
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
// Add the new node to the end of the bidirectional list maintained by LinkedHashMap
linkNodeLast(p);
return p;
}
Copy the codeThe node type is TreeNode, so where is this type defined? TreeNode is defined in HashMap.
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 codeTreeNode inherits from linkedhashMap.Entry:
Therefore, TreeNode also contains before and after attributes. Even if the inserted node type is TreeNode, the order of nodes can still be maintained using LinkedHashMap bidirectional linked list.
In the PUT method, afterNodeAccess is also performed if the inserted key already exists, which is empty in the HashMap:
void afterNodeAccess(Node<K,V> p) {}Copy the codeThe afterNodeAccess method, as its name implies, does something when a node is accessed. LinkedHashMap overrides this method:
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
If accessOrder is true and the current node is not the last node of the bidirectional list
if(accessOrder && (last = tail) ! = e) {// The logic is easy to understand: move the current node to the end of the bidirectional list and change the sequence of related nodes
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
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; }}Copy the codeSo when accessOrder is true, we call the put method of LinkedHashMap and insert a key/value pair with the same key value, that key/value pair is moved to the tail:
LinkedHashMap<String, Object> map = new LinkedHashMap<>(16.0.75 f.true);
map.put("1"."a");
map.put("6"."b");
map.put("3"."c");
System.out.println(map);
map.put("6"."b");
System.out.println(map);
//{1=a, 6=b, 3=c}
//{1=a, 3=c, 6=b}
Copy the codeAt the end of the PUT method, afterNodeInsertion method is called to perform operations after inserting nodes, which is empty in the HashMap:
void afterNodeInsertion(boolean evict) {}Copy the codeLinkedHashMap overrides this method:
// here evict is true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
If the header node is not empty and removeEldestEntry returns true
if(evict && (first = head) ! =null && removeEldestEntry(first)) {
// Get the key of the header node
K key = first.key;
// Call the removeNode method of the parent HashMap class to remove the node
removeNode(hash(key), key, null.false.true); }}protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
In LinkedHashMap, this method always returns false
return false;
}
Copy the codeBased on this feature, we can override the removeEldestEntry method to implement LRU by inheritting the LinkedHashMap, as we’ll see below.
RemoveNode removes nodes from the HashMap’s table, you might ask, so shouldn’t a bidirectional linked list that maintains the order of nodes also remove the head node? Why doesn’t the code above see this? If you look at the removeNode method, you can see this:
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;
// After the node is deleted, perform subsequent operations
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the codeThe visting method, as its name implies, is used to perform follow-up operations after a node is deleted. This method is empty in the HashMap:
void afterNodeRemoval(Node<K,V> p) {}Copy the codeLinkedHashMap overrides this method:
// Change the sequential references to nodes
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;
}
Copy the codeIn this way, we remove the header from the bidirectional LinkedHashMap list.
We already know how LinkedHashMap maintains the order of key-value pairs by using the put method, but to make this article a bit fuller, let’s look at the source code for several methods.
get(Object key)
LinkedHashMap overrides the get method of HashMap:
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
// When the accessOrder property is true, the key-value pair corresponding to the key is moved to the end of the two-way list
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
Copy the coderemove(Object key)
LinkedHashMap does not override the remove method, check the remove method of HashMap:
public V remove(Object key) {
Node<K,V> e;
// removeNode was called to remove the node, and the removeNode method visted deremoval, which describes put
// The method has been analyzed, so it will not be repeated
return (e = removeNode(hash(key), key, null.false.true)) = =null ?
null : e.value;
}
Copy the codeThe iterator
Since the order of key-value pairs is maintained internally through a bidirectional linked list, we can guess that traversing the LinkedHashMap is actually traversing the bidirectional linked list maintained by LinkedHashMap:
Check the implementation of the entrySet method of the LinkedHashMap class:
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
/ / create LinkedEntrySet
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K.V>> {
public final int size(a) { return size; }
public final void clear(a) { LinkedHashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
// The iterator type is LinkedEntryIterator
return newLinkedEntryIterator(); }... }// LinkedEntryIterator inherits from LinkedHashIterator
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K.V>> {
// The next method internally calls the nextNode method of LinkedHashIterator
public final Map.Entry<K,V> next(a) { returnnextNode(); }}abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
// At initialization, assign the head node of the bidirectional list to Next, indicating that the LinkedHashMap is traversed from
// LinkedHashMap starts at the head of the bidirectional list
next = head;
// It also has the ability to fail quickly
expectedModCount = modCount;
current = null;
}
public final boolean hasNext(a) {
returnnext ! =null;
}
final LinkedHashMap.Entry<K,V> nextNode(a) {
LinkedHashMap.Entry<K,V> e = next;
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
// Continuously get the after node of the current node, traversal
next = e.after;
returne; }... }Copy the codeThe above code fits our guess.
LRU simple implementation
LRU (Least Recently Used) refers to the Least Recently Used algorithm, which is a cache elimination algorithm.
We know that the removeEldestEntry method in LinkedHashMap always returns false and does not perform element deletion, so we can implement LRU by inheritingLinkedhashMap and overriding the removeEldestEntry method.
Suppose we now have the following needs:
The LinkedHashMap cache can store up to 5 elements, and when the number of elements exceeds 5, the least recently used data is deleted (eliminated) and only the hot data is stored.
Create a new LRUCache class and inherit LinkedHashMap:
public class LRUCache<K.V> extends LinkedHashMap<K.V> {
/** * Maximum capacity allowed by cache */
private final int maxSize;
public LRUCache(int initialCapacity, int maxSize) {
// accessOrder must be true
super(initialCapacity, 0.75 f.true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// When the number of key/value pairs exceeds the maximum capacity, return true to trigger the deletion operation
return size() > maxSize;
}
public static void main(String[] args) {
LRUCache<String, String> cache = new LRUCache<>(5.5);
cache.put("1"."a");
cache.put("2"."b");
cache.put("3"."c");
cache.put("4"."d");
cache.put("5"."e");
cache.put("6"."f"); System.out.println(cache); }}// {2=b, 3=c, 4=d, 5=e, 6=f}
Copy the codeYou can see that the earliest insertion of 1=a has been removed.
It is quite common to implement LRU via LinkedHashMap, such as the LRUMessageCache of the LogBack framework:
class LRUMessageCache extends LinkedHashMap<String.Integer> {
private static final long serialVersionUID = 1L;
final int cacheSize;
LRUMessageCache(int cacheSize) {
super((int) (cacheSize * (4.0 f / 3)), 0.75 f.true);
if (cacheSize < 1) {
throw new IllegalArgumentException("Cache size cannot be smaller than 1");
}
this.cacheSize = cacheSize;
}
int getMessageCountAndThenIncrement(String msg) {
// don't insert null elements
if (msg == null) {
return 0;
}
Integer i;
// LinkedHashMap is not LinkedHashMap. See also LBCLASSIC-255
synchronized (this) {
i = super.get(msg);
if (i == null) {
i = 0;
} else {
i = i + 1;
}
super.put(msg, i);
}
return i;
}
// called indirectly by get() or put() which are already supposed to be
// called from within a synchronized block
protected boolean removeEldestEntry(Map.Entry eldest) {
return (size() > cacheSize);
}
@Override
synchronized public void clear(a) {
super.clear(); }}Copy the code