preface
LruCache is essentially maintaining a LinkedHashMap. Specifically, why is it LinkedHashMap instead of other objects? We will explain the reasons through the following questions.
- What is LinkedHashMap?
- What is LinkedHashMap for?
- How do I use LinkedHashMap?
- How does LinkedHashMap work? How do you do that?
# text
What is LinkedHashMap?
LinkedHashMap is a stored list of key-value pairs that inherit from HashMap and implement the Map interface with a predictable iteration order. Unlike HashMap, LinkedHashMap maintains a bidirectional list of all key-value pairs, which defines the iteration order, and the access order. To put it simply: LinkedHashMap = HashMap + two-way linked list.
What is LinkedHashMap for?
The LinkedHashMap is mainly used in scenarios where the access order is required. For example, in LruCache, data is maintained in put order or access time order. Or you may need to use a fixed-length cache.
How do I use LinkedHashMap?
Let’s start with an example of common use of LinkedHashMap.
Case 1
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2);
linkedHashMap.put(1.1);
linkedHashMap.put(2.2);
linkedHashMap.put(3.3);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG"."key->" + a.getKey() + "");
Log.e("TAG"."value->" + a.getValue() + ""); }}}2019-11-21 14:32:17.332 3310-3310/com.we.we E/TAG: key->1
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: value->1
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: key->2
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: value->2
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: key->3
2019-11-21 14:32:17.333 3310-3310/com.we.we E/TAG: value->3
Copy the codeIn common use, LinkedHashMap and HashMap are no different. They are instantiated and put data. When initializing, we set the initial capacity to be 2, but put three data, and print three data. So an initialized 2 does not represent the maximum size of the LinkedHashMap. What’s the difference between LinkedHashMap and HashMap? Let’s do another example. Case 2
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return linkedHashMap.size() > 2; }}; linkedHashMap.put(1.1);
linkedHashMap.put(2.2);
linkedHashMap.put(3.3);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG"."key->" + a.getKey() + "");
Log.e("TAG"."value->" + a.getValue() + ""); }}}2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: key->2
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: value->2
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: key->3
2019-11-21 14:34:17.708 3421-3421/com.we.we E/TAG: value->3
Copy the codeCompared to the first example, the removeEldestEntry() method is overwritten during the LinkedHashMap instantiation process and returns data based on the current linkedhashmap.size () and the set capacity. Print only prints the last 2 put entries, which confirms two points.
- The size of the LinkedHashMap is manageable.
- LinkedHashMap has an insertion order.
How does the LinkedHashMap access order work? Does it sort automatically by calling get() directly? Let’s test it out by writing code. Example 3
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
returnlinkedHashMap.size() > 2; }}; linkedHashMap.put(1, 1); linkedHashMap.put(2, 2); // Call get to sort linkedhashmap.get (1);for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG"."key->" + a.getKey() + "");
Log.e("TAG"."value->" + a.getValue() + ""); }} 2019-11-21 14:55:08.481 3842-3843 /com.we E/TAG: >1 2019-11-21 14:55:08.481 3847-3843 /com.we E/TAG: >1 2019-11-21 14:55:08.481 3847-3843 /com.we E/TAG: >1 2019-11-21 14:55:08.489 3847-3843 /com.we E/TAG: >1 2019-11-21 14:55:08.489 Value ->1 2019-11-21 14:55:08.481 3842-3843 /com.we. We E/TAG: value->1 2019-11-21 14:55:08.481 3847-3843 /com.we. We E/TAG: value->2Copy the codeAs in the previous example, we called get(1) after we put the log and found that we did not put 1 last in the order we expected, because the LinkedHashMap sort by access order is turned off by default and can be turned on when instantiating through the constructor. For example: Example 4
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map); // Look at the last parameter, the default isfalse. LinkedHashMap = new linkedHashMap <Integer, Integer>(2,0.75f,true) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
returnlinkedHashMap.size() > 2; }}; linkedHashMap.put(1, 1); linkedHashMap.put(2, 2); // Call get to sort linkedhashmap.get (1);for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG"."key->" + a.getKey() + "");
Log.e("TAG"."value->" + a.getValue() + ""); We E/TAG: >2 2019-11-21 15:07:468 /com.we E/TAG: >2 2019-11-21 15:07:468 /com.we E/TAG: >2 2019-11-21 15:07:468 /com.we E/TAG: >2 2019-11-21 15:07:468 /com.we E/TAG: Value ->2 2019-11-21 15:07:46.672 4071-4071/com.we E/TAG: 1 2019-11-21 15:07:46.672 4071-4071/com.we E/TAG: 1 2019-11-21 15:07:46.672 4071-4071/com.we E/TAG: value->1Copy the codeAfter the access sorting function is enabled during initialization, the log shows that 1 is the last one, and the access sorting effect is achieved. The above examples are the basic use of LinkedHashMap, but specifically why this effect can be achieved, let’s dig into the source code to understand the principle of LinkedHashMap. How does LinkedHashMap work?
How do you do that?
First we look at the inheritance diagram of LinkedHashMap, where solid lines represent inheritance and dotted lines represent implementation interfaces.
In the above inheritance relationship, it can be found that LinkedHashMap inherits from HashMap, so the underlying LinkedHashMap is also based on linked list. If JDK1.8 is above, it is linked list + red-black tree. LinkedHashMap differs in that it maintains a two-way list.
What attributes does the LinkedHashMap bidirectional list object contain?
The LinkedHashMap bidirectional list object is maintained by the LinkedHashMapEntry object.
/ / LinkedHashMap LinkedHashMapEntry / / inheritance in a HashMap. Node, obtain the ability of ordinary chain table, at the same time through internal properties before and after; Maintain bidirectional linked lists. Static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {// Maintains a bidirectional list. LinkedHashMapEntry<K,V> before, after; LinkedHashMapEntry(inthash, K key, V value, Node<K,V> next) {
super(hash, key, value, next); Static class Node<K,V> implements map. Entry<K,V> {final inthash; // Element key final K key; // value value V value; // Next element data Node<K,V> next; . } // hashmap. TreeNode // red and black tree object. static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<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(inthash, K key, V val, Node<K,V> next) {
super(hash, key, val, next); }}Copy the codeIn the above source code LinkedHashMapEntry is every key and value object in LinkedHashMap, which maintains the first and last two objects of the current key and value pair through the before and after attributes. The inheritance relationship of the above source code is as follows:
A little bit of knowledge
HashMap. TreeNode inherit LinkedHashMap. LinkedHashMapEntry and LinkedHashMap. LinkedHashMapEntry and inherit the HashMap. Node, So why doesn’t hashmap.treenode inherit hashmap.node directly? What’s the point of this circle? TreeNode has two more references (LinkedHashMapEntry<K,V> before, after;) ; At the same time, the memory will be relatively large, why do so? A TreeNode is only used when there are enough nodes in a HashMap bucket. A TreeNode is converted to a red-black tree when there are more than eight elements in a bucket. TreeNode is less likely to be used if the hash algorithm is not bad, so it’s worth wasting that bit of space in exchange for the ability to form a bidirectional list. If TreeNode extends Node directly, then Node extentds LinkedHashMapEntry is required. Node is used a lot, which wastes a lot of space.
How does the LinkedHashMap object maintain each bidirectional list object?
Since every element in a LinkedHashMap contains two element objects before and after it, this must be maintained during the put object, so let’s look at the Linkedhashmap.put method first. Because LinkedHashMap inherits from HashMap and does not override put(), LinkedHashMap calls the put of its HashMap parent class.
Public V put(K key, V value) {public V put(K key, V value) {return putVal(hash(key), key, value, false.true); } final V putVal(int) final V putVal(inthash, 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) // Call the newNode() method, which uses an object-oriented polymorphism feature, while LinkedHashMap overwrites the newNode() method NewNode () 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 there is a duplicate key, the old value is overwritten by the value to be inserted.if(e ! = null) { // existing mappingfor key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue == null) e.value = value; // This method does nothing in HashMap. LinkedHashMap is overwritten and called. AfterNodeAccess (e); afterNodeAccess(e);return oldValue;
}
}
++modCount;
if(++size > threshold) resize(); // This method is called every time a new element is put (it is not called when updating an existing element because there is no new element) // This method does nothing in HashMap, and is overwritten. AfterNodeInsertion (EVICT);returnnull; } // newNode in HashMap Node<K,V> newNode(inthash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next); } //LinkedHashMap overriding newNode Node<K,V> newNode(inthash, K key, V value, Node<K,V> e) {// Construct an object with bidirectional list attributes. LinkedHashMapEntry<K,V> p = new LinkedHashMapEntry<K,V>(hash, key, value, e); // linkNodeLast(p);returnp; } private void linkNodeLast(LinkedHashMapEntry<K,V> p) {private void linkNodeLast(LinkedHashMapEntry<K,V> p); // The currently inserted element is defined as the last element tail = p;if(last == null) // If the previous last element is null, the previous list is empty, so the current element is an element. head = p;else{// If the previous list is not null // set the last element before put to the one before the current PUT element. p.before = last; // The current put element is set to the last element before put last. After = p; }}Copy the codeThe source code is a bit long, you can directly see my comments, comments can describe the new key value pair bidirectional linked list maintenance details. All that logic does is simple.
- Create a new element, hash the location and store it.
- Each time newNode creates an element, linkNodeLast() is called to maintain the bidirectional linked list of the newly inserted element (the newly inserted element is placed at the end).
- AfterNodeInsertion () is rewritten in LinkedHashMap to determine whether to delete the header element each time a new element is put.
// This method is called in the HashMap code, and evict is passed when called in the put methodtruevoid afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMapEntry<K,V> first; / / is evicttrue, (first = head) =true, the removeEldestEntry() method returns by defaultfalse, soifIs not executed by default.if(evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; RemoveNode (hash(key), key, null, false.true); 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; . Omit some code}Copy the codeAfterNodeInsertion () if removeEldestEntry() returns false. AfterNodeInsertion () if removeEldestEntry() However, you can manually return true by overriding the removeEldestEntry() method so that the header element is removed with each additional element. If the key of the put already exists, it is overwritten with the new value and afterNodeAccess() overridden by LinkedHashMap is called to move the new value to the end of the list.
void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMapEntry<K,V> last; //accessOrder is an input parameter to the LinkedHashMap instantiation, which needs to be passed manuallytrueThe logic for the method is enabled.if(accessOrder && (last = tail) ! = e) { LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; //p is the current tail node, so p.after = null; p.after = null; //p.before==null, indicating that p used to be the head node, but now p needs to be placed on the tail node.if (b == null)
head = a;
else// The original order is b <-> p <-> a... Now p needs to move to the tail, so it becomes b <-> a...... <->p b.after = a;if(a ! = null) // a.before is p, p is moved, and p.before = b;else// Last refers to p.before last = b;if(last == null) // There is only one node in the list, so head references p head = p;else{// The previous tail is not empty because p moves to the end, so p.before refers to the original tail, the original tail. last.after = p; } tail = p; // counter increment 1 ++modCount; }}Copy the codeAll of the above complex operations handle various exceptions to list movement, with the ultimate goal of moving the put element to the end of the list. Note: In the afterNodeAccess() function, modCount variables are modified, and iterating over LinkedHashMap while querying access data will also cause fail-fast because the order of iteration has changed. **LinkedHashMap why does calling get() trigger sorting? ** Example 4 above shows the scenario for calling get() sort. If you don’t remember the logic of Example 4, scroll up to see it. Old rules, point to see the source code a look….
Public V get(Object key) {Node<K,V> e; // The getNode() call is hashmap.getNode ()if ((e = getNode(hash(key), key)) == null)
return null;
ifAccessOrder = accessOrder = accessOrder = accessOrder afterNodeAccess(e);return e.value;
}
Copy the codeAfterNodeAccess () is triggered each time LinkedHashMap calls the get method before the result is returned, and afterNodeAccess() moves the current element to the last node. **LinkedHashMap how to maintain the list after calling remove()? ** First of all, let’s guess how we would implement this logic ourselves. For example, if I call remove() and delete an element in the middle of the list, what should I do?
- First we get the front and back nodes from the elements before and after the current element, and then we have the front and back nodes associated, but we need to pay attention to the first node.
- If LinkedHashMap overwrites remove(), the logic is implemented in the overridden method. If hashmap.remove () is called, afterNodeAccess() must have after… () method, and after… The () method is called in the remove() method.
Let’s see if our guess is correct.
//HashMap.remove()
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;
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;
elsep.next = node.next; ++modCount; --size; // Maintain bidirectional list after... () method, which is empty in the HashMap. afterNodeRemoval(node);returnnode; }}returnnull; } // unlink LinkedHashMapEntry<K,V> p = void void visting (Node<K,V> e) {// LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after; P.before = p.after = null;if(b == null) // If the previous node of the current element is null, then the current element is the original head node. // So when the current element is deleted, the last node of the current element becomes the head node. head = a;else// If the previous node is not null, the after of the previous node refers to the after node. b.after = a;if(a == null) // If the last node of the current element is null, the current element is the last node. After the current element is deleted, the last node becomes the previous node of the current element. tail = b;else// The tail node is not null, and the front node of the tail node refers to the front node of the deleted element. a.before = b; }Copy the codeThrough the above source code visible with our guess, we simply summarize.
- Linkedhashmap.remove () actually calls hashmap.remove ()
- Hashmap.removenode () is called in hashmap.remove ().
- In hashmap.removenode (), they washed deremoval () in the morning, and in LinkedHashMap, they washed many books in the morning, So the final maintenance chain table logic is in the LinkedHashMap. AfterNodeRemoval ().
So far, LinkedHashMap inheritance relationship, add, obtain, remove three main methods, as well as the internal sorting processing logic has been analyzed, HashMap with a powerful design pattern, let LinkedHashMap rewrite the following three necessary methods to basically achieve all functions.
- void afterNodeAccess(Node<K,V> p) { }
- void afterNodeInsertion(boolean evict) { }
- void afterNodeRemoval(Node<K,V> p) { }
** Let’s add a little information about some of the features of LinkedHashMap. **LinkedHashMap containsValue() has been rewritten to significantly improve performance over HashMap.
/ / LinkedHashMap. ContainsValue () public Boolean containsValue (Object value) {/ / cycle find all key/value pair and the value of duplicate datafor(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;
}
//HashMap.containsValue()
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if((tab = table) ! = null && size > 0) {// doubleforLoop to find datafor (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 codeIn the case of containsValue(), LinkedHashMap loops through all valid data, whereas in the case of HashMap, there is a double for loop, which loops through buckets and then each bucket. The next HashMap loop is for all buckets, but not all buckets have data. LinkedHashMap. LinkedHashIterator. NextNode () relative HashMap. HashIterator. NextNode () greatly enhance the performance.
// LinkedHashMap.LinkedHashIterator.nextNode()
final LinkedHashMapEntry<K,V> nextNode() {
LinkedHashMapEntry<K,V> e = next;
if(modCount ! = expectedModCount) throw new ConcurrentModificationException();if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
//HashMap.HashIterator.nextNode()
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();
if((next = (current = e).next) == null && (t = table) ! = null) {// loop through the HashMap for each bucketdo {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
Copy the codeIn the same way that LinkedHashMap loops through valid linked list data, HashMap loops through all buckets, regardless of whether there is data in the bucket. The dimensions of LinkedHashMap have been analyzed in a long way, and if you have seen this, you have a relatively comprehensive understanding of LinkedHashMap. However, it is recommended to write more code and test more. Practice is the only criterion to test the principle.
Ali P6P7【 android 】 Advanced information sharing + salary job-hopping essential interview questions