The last post looked at how HashMap works. Some people wanted to see the LinkedHashMap analysis.

LinkedHashMap is a subclass of HashMap, which maintains a two-way linked list of all entries on top of the original HashMap data structure. This list defines the order of iteration, usually the order of insertion.

In the figure above, I just drew a linked list, but the nodes in a red-black tree are the same, just different types of nodes

That is, we traverse the LinkedHashMap from the node pointed to by the head pointer to the node pointed by tail.

The source code

public class LinkedHashMap<K.V> extends HashMap<K.V> implements Map<K.V>
{
  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);
    }

    // Two-way list head node
    transient LinkedHashMap.Entry<K,V> head;

    // End node of bidirectional list
    transient LinkedHashMap.Entry<K,V> tail;

    // Specify the order in which the LinkedHashMap is traversed,true in order of access and false in order of insertion. The default is false
    final booleanaccessOrder; }}Copy the code

As you can see from the definition of LinkedHashMap, it maintains a separate bidirectional linked list for the order in which elements are inserted. This is why we print the LinkedHashMap in insertion order. The accessOrder property specifies the order in which the traversal should be accessed, and we can specify the order ourselves through its constructor.

public LinkedHashMap(int initialCapacity,float loadFactor,
                   boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
}
Copy the code

What does the output of the accessOrder mean when accessOrder=true? Take a look at the code below

LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(8.0.75 f.true);

map.put(1.1);
map.put(2.2);
map.put(3.3);

map.get(2);

System.out.println(map);

Copy the code

The output is

1 = {1, 3 = 3, 2 = 2}Copy the code

As you can see, the data that gets is put at the end of the bidirectional list, so it’s sorted by access time, so that’s what access order means.

LinkedHashMap overwrites the HashMap’s newNode and newTreeNode methods when inserted, and updates the pointing relationship within the methods.

AfterNodeAccess () and afterNodeInsertion() methods are called at the same time. In the HashMap, these two methods are empty implementation, and in the LinkedHashMap, there are concrete implementation, these two methods are also dedicated to the LinkedHashMap Line callback processing.

AfterNodeAccess () moves nodes to the end of the bidirectional list if accessOrder=true. This method is also called when we call map.get() if accessOrder=true, which is why elements accessed in order output are moved to the end of the list.

AfterNodeInsertion (

// If evict is false, the table is in create mode, which we are in when we new HashMap(Map Map)
void afterNodeInsertion(boolean evict) { // possibly remove eldest
  LinkedHashMap.Entry<K,V> first;

  // removeEldestEntry always returns false, so the following code will not execute.
  if(evict && (first = head) ! =null && removeEldestEntry(first)) {
      K key = first.key;
      removeNode(hash(key), key, null.false.true); }}Copy the code

I have an idea that we can implement LRU(Least Recently Used) with LinkedHashMap and remove the head node as long as the conditions are met.

public class LRUCache<K,V> extends LinkedHashMap<K,V> { private int cacheSize; Public LRUCache(int cacheSize) {super(160.75f,true); this.cacheSize = cacheSize; } @override protected Boolean removeEldestEntry(map.entry <K, V> younger) {returnsize() > cacheSize; }}Copy the code

If the interviewer asks you to implement an LRU Cache, write it this way. If the interviewer asks you to implement an LRU Cache in a different way, implement it with a linked list using the same thinking. Then you can harvest the offer.

After the HashMap’s deletion logic was completed,LinkedHashMap called the visting emoval callback method to correct the pointer relation of the linked list.

LinkedHashMap (JDK8 HashMap); LinkedHashMap (JDK8 HashMap); LinkedHashMap (JDK8 HashMap);