Detaillierte Erläuterung der LinkedHashMap-Quellcodeanalyse des Java-Sammlungsframeworks

Dieser Artikel stellt hauptsächlich die detaillierte Erklärung von LinkedHashMap in der Quellcode-Analyse des Java-Sammlungs-Frameworks vor. Der Inhalt umfasst die Einführung und Quellcode-Analyse von LinkedHashMap. Es ist reich an Inhalten und kann von Freunden verwendet werden dazu.

Einführung in LinkedHashMap

LinkedHashMap ist eine Unterklasse von HashMap. Sie hat die gleiche Speicherstruktur wie HashMap, fügt jedoch den Kopfknoten einer doppelten Verknüpfung hinzu Alle in LinkedHashmap eingefügten Knoten werden zu einer bidirektionalen zirkulären verknüpften Liste zusammengefasst, sodass die Reihenfolge der Knoteneinfügung erhalten bleibt und die Ausgabereihenfolge der Knoten mit der Eingabereihenfolge übereinstimmen kann.

LinkedHashMap kann zur Implementierung des LRU-Algorithmus verwendet werden (dies wird im Quellcode unten analysiert).

LinkedHashMap ist außerdem nicht threadsicher und kann nur in einer Single-Threaded-Umgebung verwendet werden.

LinkedHashMap-Quellcode-Analyse

Der LinkedHashMap-Quellcode lautet wie folgt (detaillierte Kommentare hinzugefügt):

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

Zusammenfassung

Bezüglich des Quellcodes von LinkedHashMap werden die folgenden wichtigen zusammenfassenden Punkte angegeben:

1. Aus dem Quellcode Wie aus der Abbildung ersichtlich ist, wird der LinkedHashMap ein Kopfknoten hinzugefügt, und alle in die LinkedHashMap eingefügten Einträge werden am Ende der bidirektionalen zirkulären verknüpften Liste hinzugefügt, wobei der Kopf der Kopfknoten in der Reihenfolge ist des Einfügens.

1. Es handelt sich tatsächlich um eine Kombination der Speicherstrukturen der beiden Sammlungsklassen HashMap und LinkedList. In LinkedHashMapMap werden alle Put-Einträge in der Hash-Tabelle gespeichert, es wird jedoch auch jedes Mal, wenn ein Eintrag in die Hash-Tabelle eingefügt wird, eine leere, zirkulär verknüpfte Liste mit dem Kopf definiert An der entsprechenden Position in der Tabelle muss es am Ende der doppelt zirkulär verknüpften Liste eingefügt werden.

2. Da LinkedHashMap von HashMap erbt, verfügt es über alle Eigenschaften von HashMap und ermöglicht außerdem, dass Schlüssel und Wert null sind.

3. Achten Sie auf das AccessOrder-Flag im Quellcode. Wenn es falsch ist, bedeutet dies, dass die Elemente in der doppelt verknüpften Liste entsprechend der Reihenfolge sortiert werden, in der der Eintrag eingefügt wird Die LinkedHashMap wird jedes Mal, wenn der Eintrag in die LinkedHashMap eingefügt wird, am Ende der doppelt verknüpften Liste platziert, sodass beim Durchlaufen der doppelt verknüpften Liste die Ausgabereihenfolge des Eintrags mit der Einfügereihenfolge übereinstimmt ist auch die Standardspeicherreihenfolge der doppelt verknüpften Liste. Wenn dies der Fall ist, bedeutet dies, dass auf die Elemente in der doppelt verknüpften Liste in der Reihenfolge zugegriffen wird Die verknüpfte Liste befindet sich immer noch in der Reihenfolge, in der sie in LinkedHashMap eingefügt werden. Sowohl die Put- als auch die Get-Methode rufen die RecordAccess-Methode auf (die Put-Methode überschreibt den ursprünglichen Eintrag, wenn der Schlüssel derselbe ist. Rufen Sie die RecordAccess-Methode auf), die bestimmt, ob accessOrder Wenn dies der Fall ist, wird der aktuell aufgerufene Eintrag (der eingegebene Eintrag oder der erhaltene Eintrag) an das Ende der doppelt verknüpften Liste verschoben (wenn die Schlüssel unterschiedlich sind, wird beim Einfügen eines neuen Eintrags addEntry aufgerufen, was Diese Methode ruft auch das neu eingefügte Element am Ende der doppelt verknüpften Liste auf, was mit der Einfügereihenfolge und der Zugriffsreihenfolge übereinstimmt, da zu diesem Zeitpunkt auch auf den Eintrag zugegriffen wird. Andernfalls wird nichts unternommen .

4. Achten Sie auf die Konstruktionsmethode. Die ersten vier Konstruktionsmethoden setzen accessOrder auf false, was darauf hinweist, dass standardmäßig nach der Einfügereihenfolge sortiert wird, während die fünfte Konstruktionsmethode angepasst werden kann eingehender accessOrder.-Wert, damit Sie die Sortierregeln für Elemente in einer doppelt zirkulären verknüpften Liste angeben können. Wenn Sie LinkedHashMap zum Implementieren des LRU-Algorithmus verwenden möchten, müssen Sie diese Konstruktionsmethode verwenden und accessOrder auf true setzen.

5. LinkedHashMap überschreibt nicht die put-Methode in HashMap, sondern überschreibt die in der put-Methode aufgerufene addEntry-Methode und die recordAccess-Methode. Schauen wir uns noch einmal die put-Methode von HashMap an:

// 将“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;   
}

Wenn der Schlüssel des einzufügenden Eintrags bereits in der Hash-Tabelle vorhanden ist, wird die Methode „recordAccess“ aufgerufen. Wenn der Schlüssel nicht vorhanden ist, wird die Methode „recordAccess“ aufgerufen Rufen Sie die Methode addEntry auf, um den neuen Eintrag in den Kopf der einfach verknüpften Liste des entsprechenden Slots einzufügen.

Schauen wir uns zunächst die Methode „recordAccess“ an:

//覆写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); 
     } 
   }

Diese Methode bestimmt, ob accessOrder wahr ist. Wenn „true“, wird der aktuell aufgerufene Eintrag (hier der Put-Eintrag) an das Ende der doppelt verknüpften Liste verschoben, wodurch die Elemente in der doppelt verknüpften Liste entsprechend der Zugriffsreihenfolge sortiert werden (der Eintrag, auf den zuletzt zugegriffen wurde, wird an platziert). Das Ende der verknüpften Liste ist das Element, das in letzter Zeit nicht besucht wurde. Wenn die Anzahl der Knoten in der doppelt verknüpften Liste das Maximum erreicht, wird einfach das vordere Element gelöscht Element, da das vordere Element das am längsten verwendete Element ist), andernfalls wird nichts unternommen.

Schauen wir uns die addEntry-Methode an:

//覆写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++; 
  }

Sie fügt auch den neuen Eintrag in den entsprechenden Slot ein in der Tabelle in den Kopfknoten der entsprechenden einfach verknüpften Liste, aber es ist ersichtlich, dass in createEntry der neu eingefügte Eintrag auch in das Ende der doppelt verknüpften Liste eingefügt wird. Aus Sicht der Einfügereihenfolge ist der neue Eintrag In das Ende der doppelt verknüpften Liste eingefügt, ist es möglich, Einträge entsprechend der Einfügungsreihenfolge zu iterieren. Aus Sicht der Zugriffsreihenfolge ist der neu eingefügte Eintrag der Eintrag, auf den zuletzt zugegriffen wurde, und sollte am Ende der Liste platziert werden doppelt verkettete Liste.

Oben gibt es auch eine Methode zum EntfernenEldestEntry, die wie folgt lautet:

 //该方法是用来被覆写的，一般如果用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。

结束语

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der LinkedHashMap-Quellcodeanalyse des Java-Sammlungsframeworks. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!