One shortcoming of HashMap is that the insertion order is inconsistent when iterating over elements. Most people like to do things in order, so LinkedHashMap extends HashMap to this point by adding ** “two iterations” ** :

  • Insert order – Ensures that the order of the iterated elements is the same as the insert order
  • Access order – a special iteration order, from the least recently accessed to the most accessed elements, is ideal for building LRU caches

The focus of LinkedHashMap is on these two points, and once you know it, you know it. Since it is derived from HashMap, it is important to take a look at the source code of HashMap before analyzing the source code, as you can see in this article “In-depth Analysis of HashMap principles, Implementation, and optimization in JDK8”.

In JDK 8, because of the LinkedHashMap subclass, HashMap introduced red-black trees, conversion between normal mode and tree mode is complicated, so how is it designed and simplified? Let’s take a look at the design and implementation of the LinkedHashMap source code in JDK 8.

1. Iterate in insert order

Why is the HashMap cluttered during iteration? Take a look at the way it retrieves the next element during iteration:

final Node<K,V> nextNode(a) {
  Node<K,V>[] t;
  Node<K,V> e = next; // The next element accesses the node
  if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
  if (e == null) throw new NoSuchElementException();
  // First iterate over the list itself
  if ((next = (current = e).next) == null&& (t = table) ! =null) {
    // If the list access ends, iterate over the next non-empty element in the hash bucket array
    do {} while (index < t.length && (next = t[index++]) == null);
  }
  return e;
}
Copy the code

As you can see, the HashMap is traversed by the non-empty slots in the hash bucket array, which, combined with hash collisions (linked lists), is even more chaotic than the insertion order.

How does LinkedHashMap work? It maintains a bidirectional list that runs through all elements. Iterators iterate directly over the bidirectional list to ensure the same insertion order. Key member attributes and node information are defined as follows:

// The head node of the bidirectional list, which is also the longest unaccessed element
transient LinkedHashMap.Entry<K,V> head;
// The last element of the bidirectional list
transient LinkedHashMap.Entry<K,V> tail;
// Iterate in true- access order, false- insert order, false by default
final boolean accessOrder;
// Added precursor and successor Pointers to build bidirectional lists
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 code

The HashMap defines and calls Hook methods when elements are inserted, deleted, and accessed. These methods make the mechanism for maintaining order within the LinkedHashMap relatively independent, reducing the complexity of normal and tree mode transformations.

In addition, the red-black tree node inherits the Entry of the LinkedHashMap, which may have two more Pointers, but is implemented to help avoid confusion when manipulating Pointers.

When LinkedHashMap is inserted, the callback methods overwritten are newNode, replacementNode, replacementTreeNode, and newTreeNode, which maintain the bidirectional list. The core methods are as follows:

// Insert to the end of the bidirectional list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
  LinkedHashMap.Entry<K,V> last = tail; // Temporarily remember the last node
  tail = p; // Point the tail pointer to the new node
  if (last == null)
    head = p; // The first node to insert
  else { // Associate the front and back nodesp.before = last; last.after = p; }}// Connect the front and back Pointers between two nodes
private void transferLinks(LinkedHashMap.Entry
       
         src, LinkedHashMap.Entry
        
          dst)
        ,v>
       ,v> {
  LinkedHashMap.Entry<K,V> b = dst.before = src.before;
  LinkedHashMap.Entry<K,V> a = dst.after = src.after;
  if (b == null)
    head = dst;
  else
    b.after = dst;
  if (a == null)
    tail = dst;
  else
    a.before = dst;
}
Copy the code

The implementation of the iterator is relatively simple, just iterate over the bidirectional list, then insert the order of iteration.

2. Iterate in the access order

To arrange elements in order of access, HashMap defines the following Hook methods for implementation of LinkedHashMap:

void afterNodeAccess(Node<K,V> p) {}void afterNodeInsertion(boolean evict) {}void afterNodeRemoval(Node<K,V> p) {}Copy the code

The principles of each method are as follows:

  • The idea behind afterNodeAccess is that if an element is not a tail node, it is swapped with the tail node, so as the element is accessed, the more frequently the element is accessed, the further it goes
  • In addition, the chain was disconnected normally without special operation, and they visted deremoval
  • AfterNodeInsertion deletes the oldest and least visited elements, namely the head nodes

Focus on the implementation after insertion:

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 code

Whether the head node is removed is determined by the removeEldestEntry method, which returns false by default. When overwriting this method, you cannot simply return true, as this may result in an empty LinkedHashMap, which is usually deleted after inserting a specified number of elements, as shown in the LRU cache implementation below.

3. Implement an LRU cache

We can easily implement an LRU cache data structure using LinkedHashMap by setting accessOrder to true and overriding the removeEldestEntry method:

final int MAX_CACHE_SIZE = 100;
LinkedHashMap<Object, Object> lru = new LinkedHashMap<Object, Object>(MAX_CACHE_SIZE, 0.75 f.true) {
    private static final long serialVersionUID = 1L;
    protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
      returnsize() > MAX_CACHE_SIZE; }};Copy the code

4. Summary

The LinkedHashMap code is relatively simple, and all the hard ones are implemented by HashMap 🙂

  • It’s all arrays, linked lists, red black trees.
  • Iterators fail fast and are not thread-safe
  • LinkedHashMap iterates in insert and access order, while HashMap iterates out of order and in unpredictable order

Look at the source code of this class, the most important or look at HashMap definition Hook method, keep LinkedHashMap mechanism orderly relatively independent design, this is the application of template pattern.

Search the public account “Epiphany source code” for more source code analysis and build wheels.