The overview

Opening diagramLinkedHashMap source code overall structure

  • public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

LinkedHashMap descends from HashMap, so what’s the difference?

The new variable

  • final boolean accessOrder;
  • transient LinkedHashMap.Entry<K,V> tail;
  • transient LinkedHashMap.Entry<K,V> head;

Head,tail, accessOrder, accessOrder, accessOrder, accessOrder

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

New Inner class

  • static class Entry<K,V> extends HashMap.Node<K,V>
  • final class LinkedKeySet extends AbstractSet
  • final class LinkedValues extends AbstractCollection
  • final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>>
  • abstract class LinkedHashIterator
  • final class LinkedKeyIterator extends LinkedHashIterator implements Iterator
  • final class LinkedValueIterator extends LinkedHashIterator implements Iterator
  • final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>>

details

AccessOrder variable impact

public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; } /** * {@inheritDoc} */ public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; Void afterNodeAccess(Node<K,V> e) {// Move Node to last linkedhashmap.entry <K,V> last; if (accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a ! = null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the code

The construction of linked lists

LinkHashMap does not override the PUT method. How are those lists built?

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; } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); // 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

Remember the three methods of HashMap?

    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }
Copy the code
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); } } void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }Copy the code