Detailed explanation of LinkedHashMap source code analysis of Java collection framework

This article mainly introduces the detailed explanation of LinkedHashMap in Java collection framework source code analysis. The content includes the introduction and source code analysis of linkedhashmap and the source code summary of LinkedHashMap. It is rich in content and friends in need can refer to it.

Introduction to LinkedHashMap

LinkedHashMap is a subclass of HashMap. It has the same storage structure as HashMap, but it adds the head node of a doubly linked list. All nodes put into LinkedHashmap are strung together into a bidirectional circular linked list, so it retains the order of node insertion and can make the output order of nodes the same as the input order.

LinkedHashMap can be used to implement the LRU algorithm (this will be analyzed in the source code below).

LinkedHashMap is also non-thread-safe and can only be used in a single-threaded environment.

LinkedHashMap source code analysis

LinkedHashMap source code is as follows (with detailed comments added):

package java.util; 
import java.io.*; 
public class LinkedHashMap<K,V> 
  extends HashMap<K,V> 
  implements Map<K,V> 
{ 
  private static final long serialVersionUID = 3801124242820219131L; 
  //双向循环链表的头结点，整个LinkedHashMap中只有一个header， 
  //它将哈希表中所有的Entry贯穿起来，header中不保存key-value对，只保存前后节点的引用 
  private transient Entry<K,V> header; 
  //双向链表中元素排序规则的标志位。 
  //accessOrder为false，表示按插入顺序排序 
  //accessOrder为true，表示按访问顺序排序 
  private final boolean accessOrder; 
  //调用HashMap的构造方法来构造底层的数组 
  public LinkedHashMap(int initialCapacity, float loadFactor) { 
    super(initialCapacity, loadFactor); 
    accessOrder = false;  //链表中的元素默认按照插入顺序排序 
  } 
  //加载因子取默认的0.75f 
  public LinkedHashMap(int initialCapacity) { 
    super(initialCapacity); 
    accessOrder = false; 
  } 
  //加载因子取默认的0.75f，容量取默认的16 
  public LinkedHashMap() { 
    super(); 
    accessOrder = false; 
  } 
  //含有子Map的构造方法，同样调用HashMap的对应的构造方法 
  public LinkedHashMap(Map<? extends K, ? extends V> m) { 
    super(m); 
    accessOrder = false; 
  } 
  //该构造方法可以指定链表中的元素排序的规则 
  public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) { 
    super(initialCapacity, loadFactor); 
    this.accessOrder = accessOrder; 
  } 
  //覆写父类的init()方法（HashMap中的init方法为空）， 
  //该方法在父类的构造方法和Clone、readObject中在插入元素前被调用， 
  //初始化一个空的双向循环链表，头结点中不保存数据，头结点的下一个节点才开始保存数据。 
  void init() { 
    header = new Entry<K,V>(-1, null, null, null); 
    header.before = header.after = header; 
  } 
  //覆写HashMap中的transfer方法，它在父类的resize方法中被调用， 
  //扩容后，将key-value对重新映射到新的newTable中 
  //覆写该方法的目的是为了提高复制的效率， 
  //这里充分利用双向循环链表的特点进行迭代，不用对底层的数组进行for循环。 
  void transfer(HashMap.Entry[] newTable) { 
    int newCapacity = newTable.length; 
    for (Entry<K,V> e = header.after; e != header; e = e.after) { 
      int index = indexFor(e.hash, newCapacity); 
      e.next = newTable[index]; 
      newTable[index] = e; 
    } 
  } 
  //覆写HashMap中的containsValue方法， 
  //覆写该方法的目的同样是为了提高查询的效率， 
  //利用双向循环链表的特点进行查询，少了对数组的外层for循环 
  public boolean containsValue(Object value) { 
    // Overridden to take advantage of faster iterator 
    if (value==null) { 
      for (Entry e = header.after; e != header; e = e.after) 
        if (e.value==null) 
          return true; 
    } else { 
      for (Entry e = header.after; e != header; e = e.after) 
        if (value.equals(e.value)) 
          return true; 
    } 
    return false; 
  } 
  //覆写HashMap中的get方法，通过getEntry方法获取Entry对象。 
  //注意这里的recordAccess方法， 
  //如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做， 
  //如果链表中元素的排序规则是按照访问的先后顺序排序的话，则将e移到链表的末尾处。 
  public V get(Object key) { 
    Entry<K,V> e = (Entry<K,V>)getEntry(key); 
    if (e == null) 
      return null; 
    e.recordAccess(this); 
    return e.value; 
  } 
  //清空HashMap，并将双向链表还原为只有头结点的空链表 
  public void clear() { 
    super.clear(); 
    header.before = header.after = header; 
  } 
  //Enty的数据结构，多了两个指向前后节点的引用 
  private static class Entry<K,V> extends HashMap.Entry<K,V> { 
    // These fields comprise the doubly linked list used for iteration. 
    Entry<K,V> before, after; 
    //调用父类的构造方法 
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { 
      super(hash, key, value, next); 
    } 
    //双向循环链表中，删除当前的Entry 
    private void remove() { 
      before.after = after; 
      after.before = before; 
    } 
    //双向循环立链表中，将当前的Entry插入到existingEntry的前面 
    private void addBefore(Entry<K,V> existingEntry) { 
      after = existingEntry; 
      before = existingEntry.before; 
      before.after = this; 
      after.before = this; 
    } 
    //覆写HashMap中的recordAccess方法（HashMap中该方法为空）， 
    //当调用父类的put方法，在发现插入的key已经存在时，会调用该方法， 
    //调用LinkedHashmap覆写的get方法时，也会调用到该方法， 
    //该方法提供了LRU算法的实现，它将最近使用的Entry放到双向循环链表的尾部， 
    //accessOrder为true时，get方法会调用recordAccess方法 
    //put方法在覆盖key-value对时也会调用recordAccess方法 
    //它们导致Entry最近使用，因此将其移到双向链表的末尾 
    void recordAccess(HashMap<K,V> m) { 
      LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 
      //如果链表中元素按照访问顺序排序，则将当前访问的Entry移到双向循环链表的尾部， 
      //如果是按照插入的先后顺序排序，则不做任何事情。 
      if (lm.accessOrder) { 
        lm.modCount++; 
        //移除当前访问的Entry 
        remove(); 
        //将当前访问的Entry插入到链表的尾部 
        addBefore(lm.header); 
      } 
    } 
    void recordRemoval(HashMap<K,V> m) { 
      remove(); 
    } 
  } 
  //迭代器 
  private abstract class LinkedHashIterator<T> implements Iterator<T> { 
  Entry<K,V> nextEntry  = header.after; 
  Entry<K,V> lastReturned = null; 
  /** 
   * The modCount value that the iterator believes that the backing 
   * List should have. If this expectation is violated, the iterator 
   * has detected concurrent modification. 
   */ 
  int expectedModCount = modCount; 
  public boolean hasNext() { 
      return nextEntry != header; 
  } 
  public void remove() { 
    if (lastReturned == null) 
    throw new IllegalStateException(); 
    if (modCount != expectedModCount) 
    throw new ConcurrentModificationException(); 
      LinkedHashMap.this.remove(lastReturned.key); 
      lastReturned = null; 
      expectedModCount = modCount; 
  } 
  //从head的下一个节点开始迭代 
  Entry<K,V> nextEntry() { 
    if (modCount != expectedModCount) 
    throw new ConcurrentModificationException(); 
      if (nextEntry == header) 
        throw new NoSuchElementException(); 
      Entry<K,V> e = lastReturned = nextEntry; 
      nextEntry = e.after; 
      return e; 
  } 
  } 
  //key迭代器 
  private class KeyIterator extends LinkedHashIterator<K> { 
  public K next() { return nextEntry().getKey(); } 
  } 
  //value迭代器 
  private class ValueIterator extends LinkedHashIterator<V> { 
  public V next() { return nextEntry().value; } 
  } 
  //Entry迭代器 
  private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { 
  public Map.Entry<K,V> next() { return nextEntry(); } 
  } 
  // These Overrides alter the behavior of superclass view iterator() methods 
  Iterator<K> newKeyIterator()  { return new KeyIterator();  } 
  Iterator<V> newValueIterator() { return new ValueIterator(); } 
  Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } 
  //覆写HashMap中的addEntry方法，LinkedHashmap并没有覆写HashMap中的put方法， 
  //而是覆写了put方法所调用的addEntry方法和recordAccess方法， 
  //put方法在插入的key已存在的情况下，会调用recordAccess方法， 
  //在插入的key不存在的情况下，要调用addEntry插入新的Entry 
  void addEntry(int hash, K key, V value, int bucketIndex) { 
    //创建新的Entry，并插入到LinkedHashMap中 
    createEntry(hash, key, value, bucketIndex); 
    //双向链表的第一个有效节点（header后的那个节点）为近期最少使用的节点 
    Entry<K,V> eldest = header.after; 
    //如果有必要，则删除掉该近期最少使用的节点， 
    //这要看对removeEldestEntry的覆写,由于默认为false，因此默认是不做任何处理的。 
    if (removeEldestEntry(eldest)) { 
      removeEntryForKey(eldest.key); 
    } else { 
      //扩容到原来的2倍 
      if (size >= threshold) 
        resize(2 * table.length); 
    } 
  } 
  void createEntry(int hash, K key, V value, int bucketIndex) { 
    //创建新的Entry，并将其插入到数组对应槽的单链表的头结点处，这点与HashMap中相同 
    HashMap.Entry<K,V> old = table[bucketIndex]; 
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old); 
    table[bucketIndex] = e; 
    //每次插入Entry时，都将其移到双向链表的尾部， 
    //这便会按照Entry插入LinkedHashMap的先后顺序来迭代元素， 
    //同时，新put进来的Entry是最近访问的Entry，把其放在链表末尾 ，符合LRU算法的实现 
    e.addBefore(header); 
    size++; 
  } 
  //该方法是用来被覆写的，一般如果用LinkedHashmap实现LRU算法，就要覆写该方法， 
  //比如可以将该方法覆写为如果设定的内存已满，则返回true，这样当再次向LinkedHashMap中put 
  //Entry时，在调用的addEntry方法中便会将近期最少使用的节点删除掉（header后的那个节点）。 
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
    return false; 
  } 
}

Summary

Regarding the source code of LinkedHashMap, the following important summaries are given:

1. From the source code, you can It can be seen that a head node is added to the LinkedHashMap, and all Entries inserted into the LinkedHashMap are added to the end of the two-way circular linked list with head as the head node in the order of insertion.

1. It is actually a combination of the storage structures of the two collection classes HashMap and LinkedList. In LinkedHashMapMap, all put entries are saved in the hash table, but it also defines an empty two-way circular linked list with head as the head node. Every time an entry is put, in addition to saving it to the hash table In addition to the corresponding position in the table, it must be inserted into the end of the doubly circular linked list.

2. Since LinkedHashMap inherits from HashMap, it has all the characteristics of HashMap and also allows key and value to be null.

3. Pay attention to the accessOrder flag in the source code. When it is false, it means that the elements in the doubly linked list are sorted according to the order in which the Entry is inserted into the LinkedHashMap, that is, each time the Entry is put into the LinkedHashMap are placed at the end of the doubly linked list, so that when traversing the doubly linked list, the output order of Entry will be consistent with the order of insertion. This is also the default storage order of the doubly linked list; when it is true, it means that the elements in the doubly linked list are accessed in the order Arranged in order, you can see that although the order in which Entries are inserted into the linked list is still in the order in which they are put into LinkedHashMap, both the put and get methods call the recordAccess method (the put method overwrites the original Entry when the key is the same) Call the recordAccess method), which determines whether accessOrder is true. If so, the currently accessed Entry (the Entry put in or the Entry obtained) is moved to the end of the doubly linked list (when the keys are different, when putting a new Entry, addEntry will be called, which will call creatEntry. This method also puts the newly inserted element at the end of the doubly linked list, which is consistent with the order of insertion and the order of access, because the Entry is also accessed at this time), Otherwise, do nothing.

4. Pay attention to the construction method. The first four construction methods all set accessOrder to false, indicating that the default is to sort according to the insertion order, while the fifth construction method can customize the incoming accessOrder. value, so you can specify the sorting rules for elements in a doubly circular linked list. Generally, if you want to use LinkedHashMap to implement the LRU algorithm, you must use this construction method and set accessOrder to true.

5. LinkedHashMap does not overwrite the put method in HashMap, but overwrites the addEntry method and recordAccess method called in the put method. Let's go back and look at the put method of HashMap:

// 将“key-value”添加到HashMap中   
public V put(K key, V value) {   
  // 若“key为null”，则将该键值对添加到table[0]中。   
  if (key == null)   
    return putForNullKey(value);   
  // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。   
  int hash = hash(key.hashCode());   
  int i = indexFor(hash, table.length);   
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {   
    Object k;   
    // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！   
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {   
      V oldValue = e.value;   
      e.value = value;   
      e.recordAccess(this);   
      return oldValue;   
    }   
  }   
  // 若“该key”对应的键值对不存在，则将“key-value”添加到table中   
  modCount++;  
  //将key-value添加到table[i]处  
  addEntry(hash, key, value, i);   
  return null;   
}

When the key of the Entry to be put already exists in the hash table, the recordAccess method will be called. When the key does not exist, addEntry will be called. The method inserts a new Entry into the head of the singly linked list of the corresponding slot.

Let’s look at the recordAccess method first:

//覆写HashMap中的recordAccess方法（HashMap中该方法为空）， 
//当调用父类的put方法，在发现插入的key已经存在时，会调用该方法， 
//调用LinkedHashmap覆写的get方法时，也会调用到该方法， 
//该方法提供了LRU算法的实现，它将最近使用的Entry放到双向循环链表的尾部， 
//accessOrder为true时，get方法会调用recordAccess方法 
//put方法在覆盖key-value对时也会调用recordAccess方法 
//它们导致Entry最近使用，因此将其移到双向链表的末尾 
   void recordAccess(HashMap<K,V> m) { 
     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 
  //如果链表中元素按照访问顺序排序，则将当前访问的Entry移到双向循环链表的尾部， 
  //如果是按照插入的先后顺序排序，则不做任何事情。 
     if (lm.accessOrder) { 
       lm.modCount++; 
    //移除当前访问的Entry 
       remove(); 
    //将当前访问的Entry插入到链表的尾部 
       addBefore(lm.header); 
     } 
   }

This method will determine whether accessOrder is true. If it is true, , it will move the currently accessed Entry (here the put entry) to the end of the doubly linked list, thereby sorting the elements in the doubly linked list according to the order of access (the most recently accessed Entry is placed at the end of the linked list, so many times, the front element is the element that has not been visited recently. When implementing the LRU algorithm, when the number of nodes in the doubly linked list reaches the maximum, just delete the front element, because the front element is the least recently used) , otherwise do nothing.

Let’s look at the addEntry method:

//覆写HashMap中的addEntry方法，LinkedHashmap并没有覆写HashMap中的put方法， 
//而是覆写了put方法所调用的addEntry方法和recordAccess方法， 
//put方法在插入的key已存在的情况下，会调用recordAccess方法， 
//在插入的key不存在的情况下，要调用addEntry插入新的Entry 
  void addEntry(int hash, K key, V value, int bucketIndex) { 
  //创建新的Entry，并插入到LinkedHashMap中 
    createEntry(hash, key, value, bucketIndex); 
    //双向链表的第一个有效节点（header后的那个节点）为近期最少使用的节点 
    Entry<K,V> eldest = header.after; 
  //如果有必要，则删除掉该近期最少使用的节点， 
  //这要看对removeEldestEntry的覆写,由于默认为false，因此默认是不做任何处理的。 
    if (removeEldestEntry(eldest)) { 
      removeEntryForKey(eldest.key); 
    } else { 
    //扩容到原来的2倍 
      if (size >= threshold) 
        resize(2 * table.length); 
    } 
  } 
  void createEntry(int hash, K key, V value, int bucketIndex) { 
  //创建新的Entry，并将其插入到数组对应槽的单链表的头结点处，这点与HashMap中相同 
    HashMap.Entry<K,V> old = table[bucketIndex]; 
  Entry<K,V> e = new Entry<K,V>(hash, key, value, old); 
    table[bucketIndex] = e; 
  //每次插入Entry时，都将其移到双向链表的尾部， 
  //这便会按照Entry插入LinkedHashMap的先后顺序来迭代元素， 
  //同时，新put进来的Entry是最近访问的Entry，把其放在链表末尾 ，符合LRU算法的实现 
    e.addBefore(header); 
    size++; 
  }

also inserts the new Entry into the corresponding slot in the table. into the head node of the singly linked list, but it can be seen that in createEntry, the newly put Entry is also inserted into the tail of the doubly linked list. From the perspective of the insertion order, the new Entry is inserted into the tail of the doubly linked list. It can The implementation iterates Entries according to the order of insertion. From the perspective of access sequence, the newly put Entry is the most recently accessed Entry and should be placed at the end of the doubly linked list.

There is also a removeEldestEntry method above, which is as follows:

 //该方法是用来被覆写的，一般如果用LinkedHashmap实现LRU算法，就要覆写该方法， 
  //比如可以将该方法覆写为如果设定的内存已满，则返回true，这样当再次向LinkedHashMap中put 
  //Entry时，在调用的addEntry方法中便会将近期最少使用的节点删除掉（header后的那个节点）。 
  protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
    return false; 
  } 
}

该方法默认返回false，我们一般在用LinkedHashMap实现LRU算法时，要覆写该方法，一般的实现是，当设定的内存（这里指节点个数）达到最大值时，返回true，这样put新的Entry（该Entry的key在哈希表中没有已经存在）时，就会调用removeEntryForKey方法，将最近最少使用的节点删除（head后面的那个节点，实际上是最近没有使用）。

6、LinkedHashMap覆写了HashMap的get方法：

//覆写HashMap中的get方法，通过getEntry方法获取Entry对象。 
//注意这里的recordAccess方法， 
//如果链表中元素的排序规则是按照插入的先后顺序排序的话，该方法什么也不做， 
//如果链表中元素的排序规则是按照访问的先后顺序排序的话，则将e移到链表的末尾处。 
  public V get(Object key) { 
    Entry<K,V> e = (Entry<K,V>)getEntry(key); 
    if (e == null) 
      return null; 
    e.recordAccess(this); 
    return e.value; 
  }

先取得Entry，如果不为null，一样调用recordAccess方法，上面已经说得很清楚，这里不在多解释了。

7、最后说说LinkedHashMap是如何实现LRU的。

首先，当accessOrder为true时，才会开启按访问顺序排序的模式，才能用来实现LRU算法。我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此便把该Entry加入到了双向链表的末尾（get方法通过调用recordAccess方法来实现，put方法在覆盖已有key的情况下，也是通过调用recordAccess方法来实现，在插入新的Entry时，则是通过createEntry中的addBefore方法来实现），这样便把最近使用了的Entry放入到了双向链表的后面，多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除的最前面的Entry(head后面的那个Entry)便是最近最少使用的Entry。

结束语

The above is the detailed content of Detailed explanation of LinkedHashMap source code analysis of Java collection framework. For more information, please follow other related articles on the PHP Chinese website!