Example of parsing LinkedHashMap source code in Java

This article mainly analyzes the source code of LinkedHashMap in Java, which has certain reference value. Interested friends can refer to

Overview:

LinkedHashMap implementation Map inherits HashMap, based on Map's hash table and chain list implementation, with a predictable iteration order.

LinedHashMap maintains a double linked list structure that operates on all entries. The linked list defines the iteration order, which can be insertion or access order.

The node object of LintHashMap inherits the node object of HashMap, and adds before and after pointers:

##

/**
 * LinkedHashMap节点对象
 */
 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);
  }
 }

lintHashMap initialization:

accessOrder , simply put, this is used to control the order of elements.

accessOrder is true: it means that it is in the order of access, that is, whoever accesses it first will be ranked first.
accessOrder is false, which means it is in the order of storage. , which is the order in which you put the elements.

public LinkedHashMap(int initialCapacity, float loadFactor) {
  super(initialCapacity, loadFactor);
  accessOrder = false;
 }

 /**
  * 生成一个空的LinkedHashMap,并指定其容量大小，负载因子使用默认的0.75，
  * accessOrder为false表示按照存放顺序来，就是你put元素的时候的顺序
  * accessOrder为true: 表示按照访问的顺序来，也就是谁最先访问，就排在第一位
  */
 public LinkedHashMap(int initialCapacity) {
  super(initialCapacity);
  accessOrder = false;
 }
 /**
  * 生成一个空的HashMap,容量大小使用默认值16，负载因子使用默认值0.75
  * 默认将accessOrder设为false，按插入顺序排序.
  */
 public LinkedHashMap() {
  super();
  accessOrder = false;
 }
 /**
  * 根据指定的map生成一个新的HashMap,负载因子使用默认值，初始容量大小为Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)
  * 默认将accessOrder设为false，按插入顺序排序.
  */
 public LinkedHashMap(Map<? extends K, ? extends V> m) {
  super();
  accessOrder = false;
  putMapEntries(m, false);
 }
 /**
  * 生成一个空的LinkedHashMap,并指定其容量大小和负载因子，
  * 默认将accessOrder设为true，按访问顺序排序
  */
 public LinkedHashMap(int initialCapacity,
       float loadFactor,
       boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
 }

putMapEntries(m,false) calls the method of the parent class HashMap, and then inserts data according to the put of HashMap:

 /**
  * Implements Map.putAll and Map constructor
  *
  * @param m the map
  * @param evict false when initially constructing this map, else
  * true (relayed to method afterNodeInsertion).
  */
 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
  int s = m.size();
  if (s > 0) {
   if (table == null) { // pre-size
    float ft = ((float)s / loadFactor) + 1.0F;
    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
       (int)ft : MAXIMUM_CAPACITY);
    if (t > threshold)
     threshold = tableSizeFor(t);
   }
   else if (s > threshold)
    resize();
   for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
    K key = e.getKey();
    V value = e.getValue();
    putVal(hash(key), key, value, false, evict);
   }
  }
 }

Storage:

The put method of HashMap called by put calls two empty methods, implemented by LinkedHashMap

##

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
 }

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;
 }

The red part in the hashmap is empty and implemented:

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

Then look at how LinkedHashMap implements these two methods:

Move the current node e to the end of the doubly linked list. Every time an element in LinkedHashMap is accessed, it will be sorted according to the order of access. The elements accessed first are at the front of the doubly linked list, and the elements accessed later are closer to the end. Of course, this operation will only be performed when accessOrder is true.

void afterNodeAccess(Node<K,V> e) {
  LinkedHashMap.Entry<K,V> last;
  // 若访问顺序为true，且访问的对象不是尾结点
  if (accessOrder && (last = tail) != e) {
   // 向下转型，记录p的前后结点
   LinkedHashMap.Entry<K,V> p =
    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
   // p的后结点为空
   p.after = null;
   // 如果p的前结点为空
   if (b == null)
    // a为头结点
    head = a;
   else // p的前结点不为空
    // b的后结点为a
    b.after = a;
   // p的后结点不为空
   if (a != null)
    // a的前结点为b
    a.before = b;
   else // p的后结点为空
    // 后结点为最后一个结点
    last = b;
   // 若最后一个结点为空
   if (last == null)
    // 头结点为p
    head = p;
   else { // p链入最后一个结点后面
    p.before = last;
    last.after = p;
   }
   // 尾结点为p
   tail = p;
   // 增加结构性修改数量
   ++modCount;
  }
 }

AfterNodeInsertion method evict is true to delete the head node of the doubly linked list

 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);
  }
 }

The deletion operation calls the remove of HashMap Method to implement element deletion, remove calls removeNode, and removeNode has a method that requires LinkedHashMap to implement:

Delete the e node from the doubly linked list, change the reference relationship between the nodes before and after e, and reconnect it into a complete doubly linked list .

 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;
 }

Read:

e is not empty, then get the value of e and return it.

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;
 }

accessOrder is true, which means that the content is obtained in the order of access.

 void afterNodeAccess(Node<K,V> e) {
  LinkedHashMap.Entry<K,V> last;
  // 若访问顺序为true，且访问的对象不是尾结点
  if (accessOrder && (last = tail) != e) {
   // 向下转型，记录p的前后结点
   LinkedHashMap.Entry<K,V> p =
    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
   // p的后结点为空
   p.after = null;
   // 如果p的前结点为空
   if (b == null)
    // a为头结点
    head = a;
   else // p的前结点不为空
    // b的后结点为a
    b.after = a;
   // p的后结点不为空
   if (a != null)
    // a的前结点为b
    a.before = b;
   else // p的后结点为空
    // 后结点为最后一个结点
    last = b;
   // 若最后一个结点为空
   if (last == null)
    // 头结点为p
    head = p;
   else { // p链入最后一个结点后面
    p.before = last;
    last.after = p;
   }
   // 尾结点为p
   tail = p;
   // 增加结构性修改数量
   ++modCount;
  }
 }

Several iterators of LinkedHashMap:

Abstract class LinkedHashIterator implements specific deletion, determines whether there is the next node, and iterative logic.

LinkedKeyIterator inherits from LinkedHashIterator, implements the Iterator interface, and iterates the keys in LinkedHashMap.

LinkedValueIterator inherits from LinkedHashIterator, implements the Iterator interface, iterates over the Value in LinkedHashMap

LinkedEntryIterator inherits from LinkedHashIterator, implements the Iterator interface, and iterates over the nodes in LinkedHashMap

abstract class LinkedHashIterator {
  //下一个节点
  LinkedHashMap.Entry<K,V> next;
  //当前节点
  LinkedHashMap.Entry<K,V> current;
  //期望的修改次数
  int expectedModCount;

  LinkedHashIterator() {
   //next赋值为头结点
   next = head;
   //赋值修改次数
   expectedModCount = modCount;
   //当前节点赋值为空
   current = null;
  }
  //是否存在下一个结点
  public final boolean hasNext() {
   return next != null;
  }

  final LinkedHashMap.Entry<K,V> nextNode() {
   LinkedHashMap.Entry<K,V> e = next;
   //检查是否存在结构性改变
   if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
   //结点为null NoSuchElementException
   if (e == null)
    throw new NoSuchElementException();
   //不为null,赋值当前节点
   current = e;
   //赋值下一个结点
   next = e.after;
   return e;
  }
  //删除操作
  public final void remove() {
   Node<K,V> p = current;
   if (p == null)
    throw new IllegalStateException();
   if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
   current = null;
   K key = p.key;
   //移除结点操作
   removeNode(hash(key), key, null, false, false);
   expectedModCount = modCount;
  }
 }

 final class LinkedKeyIterator extends LinkedHashIterator
  implements Iterator<K> {
  public final K next() { return nextNode().getKey(); }
 }

 final class LinkedValueIterator extends LinkedHashIterator
  implements Iterator<V> {
  public final V next() { return nextNode().value; }
 }

 final class LinkedEntryIterator extends LinkedHashIterator
  implements Iterator<Map.Entry<K,V>> {
  public final Map.Entry<K,V> next() { return nextNode(); }
 }

The above is the detailed content of Example of parsing LinkedHashMap source code in Java. For more information, please follow other related articles on the PHP Chinese website!