Codeegg’s 833rd tweet

Author: Diao Erlang Dang

Blog: https://www.jianshu.com/p/494246f9ae51

Size girls see the world

Conflict situation

LruCache cache mechanism, simple to understand, found a source bug, we introduced the use and principle of LruCache, but also mentioned that LruCache is essentially maintaining a LinkedHashMap. Why is this LinkedHashMap and not some other object explained by the following questions.

1. What is LinkedHashMap?

2. What is LinkedHashMap for?

3. How to use LinkedHashMap?

4. How does LinkedHashMap work? How do you do that?

1. 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.

2. 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.

3. How to 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 E/TAG: key->12019-11-21 14:32:17. 333310-3310 /com.we E/TAG: value->12019-11-21 14:32:17.333310-3310 /com.we E/TAG: key->22019-11-21 14:32:17. 333310-3310 /com.we E/TAG: value->22019-11-21 14:32:17.333310-3310 /com.we E/TAG: key->32019-11-21 14:32:17. 333310-3310 /com.we E/TAG: value->3Copy the code

  • In 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 E/TAG: key->22019-11-21 14:34:17.708 3421-3421/com.we E/TAG: value->22019-11-21 14:34:17.708 3421-3421/com.we E/TAG: key->32019-11-21 14:34:17.708 3421-3421/com.we E/TAG: value->3Copy the code

  • Compared 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) {                return linkedHashMap.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 3843-3843/com.we E/TAG: key->1We E/TAG: value->1 we E/TAG: value->12019-11-21 14:55:08.481 3843-3843/com.we E/TAG: key->22019-11-21 14:55:08.481 3843-3843/com.we E/TAG: value->2Copy the code

As 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. Like this:

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 argument, the default is false.LinkedHashMap = new linkedHashMap <Integer, Integer>(2,0.75f,true) {             @Override             protected boolean removeEldestEntry(Entry eldest) {                 return linkedHashMap.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 15:07:46.672 4071-4071/com.we E/TAG: key->22019-11-21 15:07:468 /com.we E/TAG: value->22019-11-21 15:07:46.672 4071-4071/com.we E/TAG: key->12019-11-21 15:07:468 /com.we. We E/TAG: value->1Copy the code

After 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.

4. How does LinkedHashMap work? How do you do that?

4.1. First we look at the inheritance diagram of LinkedHashMap

Solid lines represent inheritance relationships and dashed 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.

4.2. What attributes does the LinkedHashMap bidirectional list object contain?

The LinkedHashMap bidirectional list object is maintained by the LinkedHashMapEntry object.

//LinkedHashMap.LinkedHashMapEntry// Inherit from hashmap. Node to get the ability of a normal linked list with the internal attributes before, after; Maintain bidirectional linked lists. static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {// Maintain bidirectional lists.    LinkedHashMapEntry<K,V> before, after;    LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {         super(hash, key, value, next);      }  }// HashMap.Node// List element object static class Node<K,V> implements Map.Entry<K,V> {        final int hash;// Element key        final K key;/ / value the value        V value;// Data for the next element        Node<K,V> next;. Omit some code    }// HashMap.TreeNode// Red black tree object, mainly depends on the inheritance relationship, if you need to understand the internal logic can be through the principle of HashMap.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(int hash, K key, V val, Node<K,V> next) {        super(hash, key, val, next);    } }Copy the code

In 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.

4.3. 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.

// The HashMap put() method is also the LinkedHashMap put methodpublic V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}    // Look directly at the key parts of the code, look at the parts I commentedfinal 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)// Calls the newNode() method, which uses an object-oriented polymorphism feature, while LinkedHashMap overrides the newNode() method// newNode() is overwritten by LinkedHashMap.        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 mapping for key            V oldValue = e.value;if (! onlyIfAbsent || oldValue == null)                e.value = value;// This method does nothing in HashMap. LinkedHashMap is overwritten and called.// This method mainly moves the current node to the end of the bidirectional list for further analysis                afterNodeAccess(e);               return oldValue;           }       }        ++modCount;        if (++size > threshold)            resize();// Put is called every time a new element is put (not if it is updating an existing element, because there is no new element).// But this method does nothing in HashMap. LinkedHashMap is overwritten.// It is mainly used to remove the earliest element for further parsing        afterNodeInsertion(evict);        return null;    }/ / the newNode HashMap    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {        return new Node<>(hash, key, value, next);    }//LinkedHashMap overwritten newNode    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {// Construct an object with a bidirectional list attribute.        LinkedHashMapEntry<K,V> p =            new LinkedHashMapEntry<K,V>(hash, key, value, e);// Two-way list maintenance        linkNodeLast(p);        return p;    }  private void linkNodeLast(LinkedHashMapEntry<K,V> p) {// First get the last element of the current list     LinkedHashMapEntry<K,V> last = tail;// 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// The last element before put is set to the one before the current put element.         p.before = last;// The current put element is set to the element next to the last element before put         last.after = p;     } }Copy the code

The 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.

1. Create a new element, hash its location, and store it.

2. Every time newNode creates an element, it calls linkNodeLast () to maintain the bidirectional linked list of the newly inserted element (the newly inserted element is placed at the end).

3. Each put new element is determined by afterNodeInsertion () in LinkedHashMap to determine whether to delete the head node element.

// This method is called in the HashMap code, and evict is passed true when called in the put methodvoid afterNodeInsertion(boolean evict) { // possibly remove eldest    LinkedHashMapEntry<K,V> first;Evict is true, (first = head)=true, and the removeEldestEntry() method returns false by default, so the logic inside if is not executed by default.if (evict && (first = head) ! = null && removeEldestEntry(first)) {       K key = first.key;// Remove the element at the head of the list       removeNode(hash(key), key, null, false, true);    }}// The removeNode method in HashMap is used to remove an elementfinal 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;. Omit some code}Copy the code

AfterNodeInsertion () 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.

4. If the put key already exists, overwrite it with the new value and call afterNodeAccess () overridden by LinkedHashMap 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 = accessOrder = accessOrder = accessOrder = accessOrder = accessOrder = accessOrder = accessOrder = accessOrder = accessOrderif (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 was p, and p.before is a.before           a.before = b;     else// Last refers to p.before if p was the last node           last = b;     if (last == null)// There is only one node in the list, so head refers to p           head = p;     else {// The previous tail node is not empty because p moves to the end, so p.before references the original tail node, the original tail node. After references p         p.before = last;         last.after = p;     }       tail = p;// The counter increases by 1       ++modCount;  }}Copy the code

All 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.

4.4. Why does LinkedHashMap call get () trigger sorting?

Example 4 above shows the scenario for calling get () sort. Scroll up if you don’t remember the logic in Example 4.

Old rules, point to see the source code a look….

//LinkedHashMap overrides the get methodpublic V get(Object key) {  Node<K,V> e;// The getNode() call is hashmap.getNode ()  if ((e = getNode(hash(key), key)) == null)      return null;  if (accessOrder)// I'm not sure how to do that.      afterNodeAccess(e);    return e.value;}Copy the code

AfterNodeAccess () is triggered each time LinkedHashMap calls the get method before the result is returned, and afterNodeAccess () moves the current element to the last node.

4.4. How to maintain LinkedHashMap after calling remove ()?

So first of all, let’s guess, if we were to implement this logic ourselves, what would we do? For example, if I call remove () and delete an element in the middle of the list, what should I do?

  1. 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.

  2. 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;}// hashmap.removenode (), the core removal methodfinal 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;// Maintain bidirectional list after... () method, which is empty in the HashMap.              afterNodeRemoval(node);           return node;         }      }    return null;}//LinkedHashMap visted deremoval (    void afterNodeRemoval(Node<K,V> e) { // unlink        LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;// First delete the element before and after the node references are empty        p.before = p.after = null;    if (b == null)// If the previous node of the current element is null, 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 code

Through the above source code visible with our guess, we simply summarize.

  1. Linkedhashmap.remove () actually calls hashmap.remove ()

  2. Hashmap.removenode () is called in hashmap.remove ().

  3. 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.

1. LinkedHashMap containsValue () has been rewritten to significantly improve performance over HashMap.

//LinkedHashMap.containsValue()public boolean containsValue(Object value) {// Loop through all key/value pairs to find the same data as valuefor (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) {// Double for loop to find data        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 code

In 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.

. 2. 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 bucket        do {} while (index < t.length && (next = t[index++]) == null);        }      return e;   }Copy the code

In 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.

Summary and a few tips

  • All dimensions of LinkedHashMap have been analyzed in a long way, and if you have already 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.

  • LruCache is essentially maintaining a LinkedHashMap, and LruCache has the ability to control the cache size. In fact, the removeEldestEntry () method mentioned above is the switch method to remove the earliest element. Simply rewrite this method to control whether to remove the earliest data. But it’s not used in LruCache. Instead, you manually remove the data by calling the trimToSize () method with each put (). Actually, this could be improved.

Related articles:

  • Night read source code to find Android source bugs

  • Save the kids! Look at an interview question!

  • Lifting the veil of HTTP/2: How does HTTP/2 establish connections

Question of the day:

What to learn from LinkedHashMap today!

Exclusive upgrade community: I Finally Figured it out