Java 수집 프레임워크의 LinkedHashMap 소스 코드 분석에 대한 자세한 설명

이 글은 주로 Java 수집 프레임워크 소스 코드 분석의 LinkedHashMap에 대한 자세한 설명을 소개합니다. 내용에는 linkedhashmap의 소개 및 소스 코드 분석과 LinkedHashMap의 소스 코드 요약이 포함되어 있으며 내용이 풍부하여 도움이 필요한 친구들이 참고할 수 있습니다. .

LinkedHashMap 소개

LinkedHashMap은 HashMap의 하위 클래스입니다. 이는 HashMap과 동일한 저장 구조를 가지고 있지만 이중 연결 목록의 헤드 노드를 추가하여 LinkedHashmap에 삽입된 모든 노드를 두 개로 묶습니다. 순환 연결 리스트이므로 노드가 삽입되는 순서를 유지하고 노드의 출력 순서를 입력 순서와 동일하게 만들 수 있습니다.

LinkedHashMap을 사용하여 LRU 알고리즘을 구현할 수 있습니다(이 내용은 아래 소스 코드에서 분석됩니다).

LinkedHashMap은 스레드로부터 안전하지 않으며 단일 스레드 환경에서만 사용할 수 있습니다.

LinkedHashMap 소스 코드 분석

LinkedHashMap 소스 코드는 다음과 같습니다. (자세한 설명 추가)

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

LinkedHashMap 소스 코드는 다음과 같습니다. 주어진 요약 :

1 소스 코드를 보면 LinkedHashMap에 헤드 노드가 추가되고 LinkedHashMap에 삽입된 모든 항목이 헤드 노드를 순서대로 양방향 순환 연결 목록 끝에 추가되는 것을 볼 수 있습니다. 삽입의 .

1. 실제로 두 컬렉션 클래스 HashMap과 LinkedList의 저장 구조를 결합한 것입니다. LinkedHashMapMap에서는 모든 입력 항목이 해시 테이블에 저장되지만 항목이 입력될 때마다 헤드 노드로 해시 테이블에 저장되는 빈 양방향 순환 연결 목록도 정의합니다. 테이블의 해당 위치에 연결하려면 이중 순환 연결 목록의 끝에 삽입해야 합니다.

2. LinkedHashMap은 HashMap을 상속하므로 HashMap의 모든 기능을 가지며 키와 값이 null일 수도 있습니다.

3. 소스 코드의 accessOrder 플래그에 주의하세요. 이는 이중 연결 목록의 요소가 LinkedHashMap에 삽입된 순서에 따라 정렬된다는 의미입니다. Entry가 LinkedHashMap에 들어갈 때마다 이중 연결 리스트 tail에 배치되므로 이중 연결 리스트를 순회할 때 Entry의 출력 순서가 기본 저장소인 삽입 순서와 일치하게 됩니다. 이중 연결 리스트의 순서; true인 경우, 보시다시피 이중 연결 리스트의 요소가 액세스 순서대로 정렬되어 있음을 의미합니다. 목록은 여전히 ​​LinkedHashMap에 배치된 순서대로 되어 있으므로 put 및 get 메소드는 모두 RecordAccess 메소드를 호출합니다(Put 메소드는 키가 동일할 때 RecordAccess 메소드를 호출하고 원래 항목을 덮어씁니다). true인 경우 현재 액세스된 항목(입력된 항목 또는 획득한 항목)은 이중 연결 목록의 끝으로 이동됩니다(키가 다른 경우 새 항목을 넣을 때 addEntry가 호출되며 이는 creatEntry를 호출합니다. 또한 이 메소드는 새로 삽입된 요소를 이중 연결 목록의 끝에 배치합니다. 이는 삽입 순서 및 액세스 순서와 일치합니다. 왜냐하면 항목도 이때 액세스되기 때문입니다. 그렇지 않으면 아무 작업도 수행되지 않습니다. .

4. 처음 네 가지 구성 방법은 모두 accessOrder를 false로 설정합니다. 이는 기본적으로 삽입 순서에 따라 정렬하는 것임을 나타냅니다. 순환 연결 리스트의 요소 정렬 규칙은 일반적으로 LinkedHashMap을 사용하여 LRU 알고리즘을 구현하며 이 구성 방법을 사용하여 accessOrder를 true로 설정합니다.

5. LinkedHashMap은 HashMap의 put 메소드를 덮어쓰지 않지만, put 메소드에서 호출된 addEntry 메소드와 RecordAccess 메소드를 덮어씁니다. 다시 돌아가서 HashMap의 put 메소드를 살펴보겠습니다.

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

넣을 Entry가 이미 해시 테이블에 존재하는 경우, RecordAccess 메소드가 호출됩니다. 키가 존재하지 않으면 addEntry 메소드가 호출되어 해당 슬롯의 단일 연결 리스트의 헤드에 새 Entry가 삽입됩니다. .

recordAccess 메소드를 먼저 살펴보겠습니다.

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

이 메소드는 accessOrder가 true인지 확인합니다. true인 경우 현재 액세스된 항목(여기서는 put 항목)을 양방향으로 이동합니다. 이중 연결 목록의 요소가 액세스 순서에 따라 정렬되도록 하는 원형 연결 목록의 꼬리(가장 최근에 액세스한 항목은 연결 목록의 끝에 배치되므로 여러 번 앞의 요소가 LRU 알고리즘을 구현할 때 이중 연결 리스트의 노드 수가 최대값에 도달하면 이전 요소가 가장 최근에 사용되지 않았으므로 이전 요소를 삭제하면 됩니다. 아무것도 아님.

addEntry 메소드를 다시 살펴보겠습니다.

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

또한 테이블의 해당 슬롯에 해당하는 단일 연결 리스트의 헤드 노드에 새 Entry를 삽입하지만 createEntry에서 이를 볼 수 있습니다. , 테이블의 해당 슬롯에 해당하는 단일 연결 리스트의 헤드 노드에도 새 항목이 삽입됩니다. 삽입 순서의 관점에서 보면 새 항목은 이중 연결 목록의 끝에 삽입됩니다. 이중 연결 목록의 끝에 삽입됩니다. 삽입 순서에 따라 항목을 반복할 수 있습니다. 액세스 순서의 관점에서 새 항목은 이중 연결 목록의 끝에 삽입됩니다. 최근에 액세스한 항목이며 이중 연결 목록의 끝에 배치되어야 합니다.

위에는 다음과 같은 RemoveEldestEntry 메소드도 있습니다.

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

结束语

위 내용은 Java 수집 프레임워크의 LinkedHashMap 소스 코드 분석에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!