Java에서 LinkedHashMap 소스 코드를 구문 분석하는 예

이 문서는 주로 모든 사람을 위한 Java의 LinkedHashMap 소스 코드를 분석합니다. 관심 있는 친구가 참조할 수 있습니다.

개요:

LinkedHashMap은 맵 상속 HashMap, 맵 기반 해시 테이블 및 이 목록을 연결합니다. 예측 가능한 반복 순서로 구현합니다.

LinedHashMap은 모든 항목에 대해 작동하는 이중 연결 목록 구조를 유지합니다. 연결 목록은 삽입 순서 또는 액세스 순서일 수 있는 반복 순서를 정의합니다.

LintHashMap의 노드 객체는 HashMap의 노드 객체를 상속하고 포인터 전후에 추가합니다:

/**
 * 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 초기화:

accessOrder, 간단히 말해서 이것은 요소의 순서를 제어하는 ​​데 사용됩니다.
accessOrder는 다음과 같습니다. true: 액세스 순서에 따라 즉, 먼저 액세스한 사람이 먼저 순위가 지정됨을 의미하고, accessOrder가 false인 경우 요소를 넣을 때의 순서대로 저장된다는 의미입니다.

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)는 상위 클래스 HashMap의 메소드를 호출한 후 HashMap의 put에 따라 데이터를 삽입합니다.

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

put은 put 메소드를 호출합니다. HashMap, 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;
 }

해시맵의 빨간색 부분은 비어 있습니다.

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

그런 다음 LinkedHashMap이 이 두 가지 메서드를 구현하는 방법을 살펴보겠습니다.

현재 변경 node e 이중 연결 리스트의 끝으로 이동합니다. LinkedHashMap의 요소에 액세스할 때마다 액세스 순서에 따라 정렬되며, 먼저 액세스된 요소는 이중 연결 목록의 맨 앞에 배치되고 나중에 액세스되는 요소는 끝에 가까워집니다. 물론 이 작업은 accessOrder가 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 메소드 evict는 이중 연결 리스트의 헤드 노드를 삭제하기 위해 true입니다

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

삭제 작업은 요소 삭제를 구현하기 위해 HashMap의 제거 메소드를 호출하고, 제거는 RemoveNode를 호출하며, RemoveNode에는 메소드가 있습니다. 이를 구현하려면 LinkedHashMap이 필요합니다.

이중 연결 목록에서 e 노드를 삭제하고 e 전후 노드 간의 참조 관계를 변경한 다음 완전한 이중 연결 목록으로 다시 연결합니다.

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

읽기:

e가 비어 있지 않으면 e의 값을 가져와 반환합니다.

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

LinkedHashMap의 여러 반복자:

Abstract 클래스 LinkedHashIterator는 특정 삭제를 구현하고 다음 노드가 있는지 여부를 결정하며 반복 논리를 수행합니다.

LinkedKeyIterator는 LinkedHashIterator에서 상속하고 Iterator 인터페이스를 구현하며 LinkedHashMap의 키를 반복합니다.

LinkedValueIterator는 LinkedHashIterator에서 상속하고, Iterator 인터페이스를 구현하고, LinkedHashMap에서 값을 반복합니다.
LinkedEntryIterator는 LinkedHashIterator에서 상속하고, Iterator 인터페이스를 구현하고, 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(); }
 }

위 내용은 Java에서 LinkedHashMap 소스 코드를 구문 분석하는 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!