Author: Pz cnblogs.com/panzi/p/10845079.html

LinkedHashMap is a key-ordered HashMap, which can be interpreted as LinkList + HashMap.

So look at the HashMap code before exploring LinkedHashMap, which I won’t go over here.

LinkedHashMap is nothing more than a linked list of data stored in a HashMap that is joined by beofre,after.

As a head,tail is essential

/**
 * 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;Copy the code

There is also a data structure that stores the front and back nodes

/** * HashMap.Node subclass for normal LinkedHashMap entries. */ 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

Finally, the accessOrder variable was added to enable nodes to update node order based on access frequency

/**
 * 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 code

The put method in LinkedHashMap is not overridden; it is actually the put method in HashMap. It does, however, leave methods for subclasses to override.

AfterNodeAccess (e) and afterNodeInsertion (evict);

final 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) 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 (e ! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; // afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); // afterNodeInsertion(evict); return null; }Copy the code

afterNodeInsertionWhether to delete the first node when a new node is inserted,removeEldestEntryFalse is returned in this class, so no nodes are deleted.

// possibly remove eldest
void afterNodeInsertion(boolean evict) {
  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

Additionally, LinkedHashMap overrides the newNode method. To insert the new node into the last node in the list

tab[i] = newNode(hash, key, value, null); 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; } 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 code

AfterNodeAccess This method is executed depending on whether accessOrder is true or false when a node is updated or when the get or getOrDefault methods are called.

void afterNodeAccess(Node<K,V> e) { LinkedHashMap.Entry<K,V> last; If (accessOrder && (last = tail)! <K,V> p = (linkedhashmap. Entry<K,V>)e, b = p.before, a = p.after; // after = null p.after = null; If (B->P->A ===> B->P->E) head = A; Else // otherwise set b.after to a b.after = a; // B->P->A ===> B->A if (a ! = null) a.before = b; else // B->P->NULL ===> B->A last = b; If (last == null) head = p; else { //B -> P -> NULL p.before = last; last.after = p; } // set tail to p; ++modCount; }}Copy the code

A brief look at the code structure, although I did not see many details, but in general implementation is a layer of encapsulation, through the linked list structure to achieve sequential storage and also can achieve O(1) insert and delete, find operations.

Read more on my blog:

1.Java JVM, Collections, Multithreading, new features series tutorials

2.Spring MVC, Spring Boot, Spring Cloud series tutorials

3.Maven, Git, Eclipse, Intellij IDEA series tools tutorial

4.Java, backend, architecture, Alibaba and other big factory latest interview questions

Life is good. See you tomorrow