LinkedHashMap

This is the 20th day of my participation in the August Text Challenge.More challenges in August

Class first

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.
Copy the code

• On the basis of hashMap, for the bin of array, additional bidirectional linked list storage structure is added.

Class declaration

public class LinkedHashMap<K.V>
    extends HashMap<K.V>
    implements Map<K.V>
Copy the code

• Override method:

  newNode()
  replacementNode() // In hashMap, the production method used for tree degradation is used in conjunction with transferLinks in LHM
  newTreeNode()
  replacementTreeNode()
  internalWriteEntries()//IO serialization is related
  get()// and related methods
  reinitialize()//super () + first and last =null
  Copy the code

• Three special methods that implement leaving in a parent class:

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

The comments for these three methods in the hashMap are:

Callbacks to allow LinkedHashMap post-actions

Maintain the variable

• Data structure correlation

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;
Copy the code

The key managed structure of the bidirectional linked list is declared: the beginning and end nodes, which conforms to the above

it maintains a doubly-linked list running through all of its entries

• Traverse the related

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

This variable means (from blog.csdn.net/weixin_3691…

value	meaning
true	The accessed elements are placed after the linked list in the order in which they were accessed
false	Traverse in insertion order

Main storage structure

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

Class method

Structure specialization method

LinkNodeLast (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

• There is nothing special in itself, except to hang the node behind the last node.

  • The method that calls this method:

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

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

  • You can see that LinkedHashMap does not, in essence, replace the array in HashMap with a list, but maintains an additional two-way list to store data.

transferLinks

// apply src's links to dst
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

• Assign all SRC nodes to DST
  • The method that calls the method

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}
Copy the code

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}
Copy the code

• One is called when a tree node is called, and one is called when a non-tree node is called, and it’s just a swap of Pointers.

HashMap leave method

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

afterNodeAccess

• Operations performed after a node is accessed

  • If accessOrder is true, the accessed node is placed last

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

afterNodeInsertion

• Operations performed after a node is inserted

  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); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }Copy the code

afterNodeRemoval

 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

Get the relevant

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

This is where you can see one of the uses of accessOrder: control of the query node.

• However, the get method has not been completely rewritten. It is probably because the hash + node data structure is intuitively faster than the list + node data structure.

public boolean containsValue(Object value) { for (LinkedHashMap.Entry<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; }Copy the code

• The containsValue method is completely rewritten.

There are also subclass methods and overrides of some of the Map methods in 1.8, which are similar to the implementation of HashMap, except for a few key points:

• The foreach method uses the head node to traverse.
• The traverser method also uses the head node for next’s query traversal.

conclusion

As you can see, LinkedHashMap is not a complete collection interface:

• The head and tail nodes are maintained, but not the main data structure; the main functional structure is still the Table array in the HashMap.

  • Use of head and tail nodes: values and foreach methods

• Here’s an interesting question:

Is the linkedHashMap ordered?

In a way, it is. But there are a few disagreements about this order:

• Is accessOrder true? If so, there is no guarantee of overall orderliness (because queries cause nodes to be postpositioned)
• Has it been rewrittenremoveEldestEntry? If the method may return a value, the insertion may be accompanied by a deletion of the old node.

LinkedHashMap is more about inheriting and rewriting in other middleware, taking advantage of the maintained bidirectional linked list nature for secondary development.

• Example: By rewritingremoveEldestEntry, you can easily construct a LRUcache.