Exemple d'analyse du code source LinkedHashMap en Java

Cet article analyse principalement le code source de LinkedHashMap en Java, qui a une certaine valeur de référence. Les amis intéressés peuvent se référer à

Aperçu :

Implémentation de LinkedHashMap Map hérite de HashMap. , basé sur l'implémentation de la table de hachage et de la liste de chaînes de Map, avec un ordre d'itération prévisible.

LinedHashMap maintient une structure de liste chaînée double qui fonctionne sur toutes les entrées. La liste chaînée définit l'ordre d'itération, qui peut être un ordre d'insertion ou d'accès.

L'objet nœud de LintHashMap hérite de l'objet nœud de HashMap, et ajoute des pointeurs avant et après :

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

initialisation de LintHashMap :

accessOrder, en termes simples, est utilisé pour contrôler l'ordre des éléments
accessOrder est vrai : cela signifie qu'il est stocké dans l'ordre d'accès, c'est-à-dire que celui qui y accède en premier sera classé premier. accessOrder est faux, ce qui signifie qu'il est stocké dans l'ordre d'accès. L'ordre est l'ordre dans lequel vous placez les éléments.

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) appelle la méthode de la classe parent HashMap, puis insère des données en fonction du put de 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);
   }
  }
 }

Stockage :

La méthode put de HashMap appelée par put appelle deux méthodes vides, implémentées par 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;
 }

La partie rouge dans la hashmap est une implémentation vide :

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

Regardez ensuite Comment implémenter ces deux méthodes dans LinkedHashMap :

Déplacez le nœud actuel e à la fin de la liste doublement chaînée. Chaque fois qu'un élément de LinkedHashMap est accédé, il sera trié selon l'ordre d'accès. Les éléments accédés en premier seront au début de la liste doublement chaînée, et les éléments accédés ultérieurement seront plus proches de la fin. Bien entendu, cette opération ne sera effectuée que lorsque accessOrder est vrai.

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

Supprimer le nœud principal de la liste doublement chaînée lorsque la méthode afterNodeInsertion evict est vraie

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

Opération de suppression Appelez la méthode Remove de HashMap pour supprimer des éléments, supprimez les appels RemoveNode, et RemoveNode a une méthode qui nécessite l'implémentation de LinkedHashMap :

Supprimez le nœud e de la liste doublement liée, modifiez la relation de référence entre les nœuds avant et après e, et reconnectez-les. Complétez la liste doublement chaîné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;
 }

Lire :

e n'est pas vide, puis récupérez la valeur de e et renvoyez-la.

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 est vrai, ce qui signifie que le contenu est obtenu dans l'ordre d'accès.

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

Plusieurs itérateurs de LinkedHashMap :

La classe abstraite LinkedHashIterator implémente une suppression spécifique, détermine s'il existe un nœud suivant et itère la logique.

LinkedKeyIterator hérite de LinkedHashIterator, implémente l'interface Iterator et itère les clés dans LinkedHashMap.

LinkedValueIterator hérite de LinkedHashIterator, implémente l'interface Iterator, itère la valeur dans LinkedHashMap
LinkedEntryIterator hérite de LinkedHashIterator, implémente l'interface Iterator et itère les nœuds dans LinkedHashMap

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!