LinkHashMap analysis
1. Where is link reflected?
LinkHashmap inherits from HashMap. Several of these methods have been overridden. And a two-way list is maintained on top of the hashMap. Used to join all entities, the order in which the list is joined is usually the order in which it is inserted. Note that it is common and can be changed. In simple terms, LinkHashmap maintains a linked list that keeps nodes in order (insert or find).
From the source point of view
public class LinkedHashMap<K.V>
extends HashMap<K.V>
implements Map<K.V>
{
/** * The head (eldest) of the doubly linked list. */
transient LinkedHashMap.Entry<K,V> head;
/** * The tail (youngest) of the doubly linked list. */
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial* /
final boolean accessOrder;
}
Copy the codeIn LinkHashMap. Several attributes have been added
-
Linkedhashmap. Entry<K,V> head: the head node of the list
-
Linkedhashmap. Entry<K,V> tail: tail node of the linked list
-
Boolean accessOrder: Specifies the order in which the list is joined
instructions
When the list is built, it is built in insertion order, and the functionality of LRU can be implemented with accessOrder. In fact, he implemented this function himself
- True: Access mode, which means that the accessed element is moved to the end of the list when accessed.
- False: Insert mode, which concatenates the element to the end of the list. But not when you visit.
When do lists link? How to link lists?
NewNode is linked to the list in the put method. And by tail insertion
LinkHashMap overrides the newNode method of HashMap and writes its own internal class Entry, which links the list. This will maintain the order of inserts through a linked list, based on the previous HashMap, as well as loop through the list for subsequent operations.
Node<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);
linkNodeLast(p);
return p;
}
// 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); }}// Join the list in the linkNodeLast method
// The connection operation here is also very simple, tail insert method.
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else{ p.before = last; last.after = p; }}Copy the code2. What’s different from HashMap?
Rewrite several extended methods and store different types of nodes, as well as iterator related parts.
-
Support order
-
Overrides the newNode method to create the LinkedhashMap.Entry object. This object was introduced above.
-
The following three important extension methods have been rewritten
void afterNodeAccess(Node<K,V> p) {}// Access the node void afterNodeInsertion(boolean evict) {}// Insert the node void afterNodeRemoval(Node<K,V> p) {}// Remove the node Copy the codeThrough these three methods and in combination with bidirectional linked lists. You can do a lot of interesting things. The time complexity of the list movement is O (1).
-
Support for extension during insertion and access.
-
Iterators and entrysets are different from HashMap
3. AccessOrder analysis
AccessOrder is true, what the accessOrder is, what the implementation looks like.
Let’s start with the examples
@Test
public void testLinkHashMap(a){
LinkedHashMap<String, String> hashMap = new LinkedHashMap<>(16.0.75 F.true);
hashMap.put("b"."b");
hashMap.put("a"."a");
hashMap.put("c"."c");
System.out.println(hashMap);
hashMap.get("a");
System.out.println(hashMap);
}
Copy the codeResults:
{b=b, a=a, c=c} {b=b, c=c, a=a}
As you can see, setting this to true moves the currently accessed node to the end of the list when accessed. This makes the head of the list the oldest element (that has not been accessed), and to implement LRU, simply remove the first node of the list. If the length of the list is not infinite, then the LRU is really meaningless.
How do you do that?
To start with the GET method, enter from the GET method and see the following code
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
// Whether it is an access order.
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
// The afterNodeAccess method can be succeeded
Copy the codeafterNodeAccess
// The code logic here is also very simple, is the operation of the bidirectional list.
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// First, the current node is not the last node.
if(accessOrder && (last = tail) ! = e) {//p is e, b is p.before,a is p.after;
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
// There is no predecessor node, which means that the current node is the head node
if (b == null)
// Set the header to a.
head = a;
else
// if it is not a header, it will connect normally.
b.after = a;
//a is not null
if(a ! =null)
// A comes before B
a.before = b;
else / / a = = null.
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
// Assign p to the last node.
tail = p;
// This is the key to fast failure. Record the actual number of changes.++modCount; }}Copy the codeSo you move p to the tail node, and in the middle you evaluate a couple of things, like the head node, the tail node.
AccessOrder is false, what the accessOrder is, what the implementation looks like.
Let’s start with the examples
@Test
public void testLinkHashMap(a){
LinkedHashMap<String, String> hashMap = new LinkedHashMap<>(16.0.75 F);
hashMap.put("b"."b");
hashMap.put("a"."a");
hashMap.put("c"."c");
System.out.println(hashMap);
hashMap.get("a");
System.out.println(hashMap);
hashMap.remove("a");
System.out.println(hashMap);
hashMap.put("a"."a");
System.out.println(hashMap);
}
Copy the codeThe results of
{b=b, a=a, c=c} {b=b, a=a, c=c} {b=b, c=c} {b=b, c=c, a=a}
So if you look at the put method, which is where the list is built, newNode, because accesOrder is false, AfterNodeInsertion method afterNodeAccess is not implemented in get
// Evict is true, passed in from putVal
// What does the removeEldestEntry method do? If evict is true, head is not null, and removeEldestEntry is true, the head node is removed. This sounds like an IMPLEMENTATION of LRU.
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if(evict && (first = head) ! =null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null.false.true); }}Copy the codeLinkHashMap returns false by default. So if you override this method and return true based on some condition, for example, that the number of elements cannot exceed 100, then the head node is removed. With accessOrder being true, the node is moved to the end of the list after being used once. Doesn’t that implement LRU? I recommend looking at the comments above the removeEldestEntry method. That was very clear. Let’s look at the examples and we’ll see that in section 4.
In the grandparents’ room, the element was removed from the table after it was removed from the table, in order to clean the table, the item was removed from the list.
// Unlink unlink
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 codeLinkHashMap implements LRU
Description:
If you look at LinkHashMap class diagram, see. The next one is my own demo
class MyLruCache<K.V> extends LinkedHashMap<K.V>{
public MyLruCache(a){
super(16.0.75 F.true);
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return this.size()>3; }}@Test
public void testLruCache(a){
MyLruCache<String, String> lruCache = new MyLruCache<>();
lruCache.put("b"."b");
lruCache.put("a"."a");
lruCache.put("c"."c");
System.out.println("Initialize :" + lruCache);
lruCache.get("a");
System.out.println("After obtaining a:" + lruCache);
lruCache.put("d"."d");
System.out.println("After putting D" + lruCache);
}
Copy the codeInitialization: {b = b, a = a, c = c} after obtaining a: {b = b, c = c, a = a} after put d {c = c, a = a, d = d}
As you can see, after getting a, A is placed at the end of the queue, and after putting D, B is the first queue. B is removed.
Found a funny thing
@Test
public voidTestLinkHashMap (){LinkedHashMap<String, String> hashMap =new LinkedHashMap<>(16.0.75 F.true);
hashMap.put("b"."b");
hashMap.put("a"."a");
hashMap.put("c"."c");
System.out.println(hashMap);
hashMap.put("a"."a1");
System.out.println(hashMap);
}
Copy the codeThe answer:
{b=b, a=a, c=c} {b=b, a=a1, c=c}
If accessOrder is true. If the key is repeated, and onlyIfAbsent is false. If the key is the same and onlyIfAbsent is false or the value corresponding to the key is null, the original value is overwritten. Invokes the afterNodeAccess (e); Methods. The currently accessed key is placed at the end of the list.
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
Copy the codeSo much for LinkHashMap. Please point out any inaccuracies. thank you