Java的LinkedHashMap 源码解析

LinkedHashMap 是 Java 中的一种有序 Map，它扩展了 HashMap，提供了有序的元素存储方式。在 LinkedHashMap 中，元素的有序性可以按照插入顺序或访问顺序来维护，而这个有序性是通过维护一个双向链表来实现的，这也是实现 LRU Cache 功能的基础。在接下来的源码解析中，我们将深入探讨 LinkedHashMap 的实现。

主要结论

在开始分析源码之前，让我们首先总结一些关键结论：

1. LinkedHashMap 继承了 HashMap，因此它的底层数据结构与 HashMap 相同，都是由数组、链表或红黑树组成，同时也使用相同的扩容机制。

   /*** 用指定的初始容量、加载因子和排序模式构造一个空的LinkedHashMap实例。** @param initialCapacity 初始容量* @param loadFactor      加载因子* @param accessOrder     排序模式 - <tt>true</tt> 表示按访问顺序，<tt>false</tt> 表示按插入顺序* @throws IllegalArgumentException 如果初始容量为负数或加载因子为非正数*/
   public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {// 调用 HashMap 的构造方法，继承了 HashMap 的底层数据结构和扩容机制super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
   }
   

2. LinkedHashMap 使用双向链表来维护数据的顺序，与 HashMap 的拉链式存储方式不同。

   /** 实现说明。此类的先前版本在内部结构上略有不同。由于超类 HashMap 现在对一些节点使用树结构，类 LinkedHashMap.Entry 现在被视为中介节点类，也可以转换为树形结构。在当前上下文中，此类的名称 LinkedHashMap.Entry 在几个方面都有点令人困惑，但不能更改。否则，即使它不被导出到此包外，已知一些现有源代码依赖于调用 removeEldestEntry 时的符号解析特例规则，以抑制由于模糊的用法而导致的编译错误。因此，我们保留名称以保持编译性不变。** 节点类的更改还需要使用两个字段（head、tail）而不是指向头节点的指针来维护双向链接的前后列表。该类以前也使用了不同风格的回调方法来进行访问、插入和删除。*//*** 用于常规 LinkedHashMap 条目的 HashMap.Node 子类。*/
   static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, value, Node<K,V> next) {super(hash, key, value, next);}
   }
   

3. LinkedHashMap 存储顺序与添加顺序一致，但也可以通过 accessOrder 参数决定是否在访问元素时移动元素，以实现 LRU 缓存功能。

   /*** 在删除元素之后，将元素从双向链表中删除*/
   void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.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;elseb.after = a;if (a == null)tail = b;elsea.before = b;
   }/*** 在访问元素之后，将该元素放到双向链表的尾巴处*/
   void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
   }
   

内部结构

LinkedHashMap 内部类 Entry 继承自 HashMap 的 Node，同时增加了 “前继节点” 和 “后继节点” 来支持双向链表的特性。此外，LinkedHashMap 中还有两个重要的成员变量：

• head：记录 LinkedHashMap 的头节点。
• tail：记录 LinkedHashMap 的尾节点。
• accessOrder：表示是否根据访问顺序进行排序，如果 accessOrder 为 true，LinkedHashMap 会在元素被访问时将其移至链表末尾，实现 LRU 缓存。

内部方法

LinkedHashMap 定义了一些私有的内部方法，用于操作双向链表：

• linkNodeLast(LinkedHashMap.Entry<K,V> p)：将元素连接到链表尾部。

  /*** 将元素连接到链表尾部。** @param p 要连接到链表尾部的元素*/
  private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {LinkedHashMap.Entry<K,V> last = tail;tail = p;if (last == null)head = p;else {p.before = last;last.after = p;}
  }
  

• transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst)：将一个节点的前继节点和后继节点链接到另一个节点。

  /*** 将一个节点的前继节点和后继节点链接到另一个节点。** @param src 要转移链接的源节点* @param dst 目标节点*/
  private void transferLinks(LinkedHashMap.Entry<K,V> src,LinkedHashMap.Entry<K,V> dst) {LinkedHashMap.Entry<K,V> b = dst.before = src.before;LinkedHashMap.Entry<K,V> a = dst.after = src.after;if (b == null)head = dst;elseb.after = dst;if (a == null)tail = dst;elsea.before = dst;
  }
  

• afterNodeRemoval(Node<K,V> e)：在删除元素后，将元素从双向链表中删除。

  /*** 在删除元素后，将元素从双向链表中删除。** @param e 要删除的元素*/
  void afterNodeRemoval(Node<K,V> e) { 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;elseb.after = a;if (a == null)tail = b;elsea.before = b;
  }
  

• afterNodeInsertion(boolean evict)：在插入元素后，可能删除最老的元素。

  /*** 在插入元素后，可能删除最老的元素。** @param evict 如果为 true，可能会删除最老的元素*/
  void afterNodeInsertion(boolean evict) { // 可能删除最老的元素LinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}
  }
  

• afterNodeAccess(Node<K,V> e)：在访问元素后，将元素放到链表的尾部。

  /*** 在访问元素后，将元素放到链表的尾部。** @param e 要移动的元素*/
  void afterNodeAccess(Node<K,V> e) { // 将节点移动到最后LinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) { // 如果 accessOrder 与 (last = tail) != e 为 trueLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}
  }
  

构造方法

LinkedHashMap 提供了多个构造方法，包括：

• LinkedHashMap(int initialCapacity, float loadFactor)：指定初始容量和加载因子的构造方法。

  /*** 指定初始容量和加载因子的构造方法。** @param initialCapacity 初始容量* @param loadFactor 加载因子*/
  public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;
  }
  

• LinkedHashMap(int initialCapacity)：指定初始容量的构造方法。

  /*** 指定初始容量的构造方法。** @param initialCapacity 初始容量*/
  public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;
  }
  

• LinkedHashMap()：默认构造方法。

  /*** 默认构造方法。*/
  public LinkedHashMap() {super();accessOrder = false;
  }
  

• LinkedHashMap(Map<? extends K, ? extends V> m)：使用现有映射初始化构造方法。

  /*** 使用现有映射初始化构造方法。** @param m 要使用的映射*/
  public LinkedHashMap(Map<? extends K, ? extends V> m) {super();accessOrder = false;putMapEntries(m, false);
  }
  

• LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)：可以设置 accessOrder 参数以决定是否按照访问顺序排序。

  /*** 可以设置 accessOrder 参数以决定是否按照访问顺序排序。** @param initialCapacity 初始容量* @param loadFactor 加载因子* @param accessOrder 如果为 true，则按照访问顺序排序；否则按照插入顺序排序*/
  public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
  }
  

LinkedHashMap 的源码解析包括实现 newNode、replacementNode、newTreeNode、replacementTreeNode 等节点插入和替换的方法，以及实现 containsValue、get、getOrDefault、keySet、entrySet 等其他操作。这些方法负责在 LinkedHashMap 中维护元素的顺序和实现 LRU 缓存功能。

总结

LinkedHashMap 是一个有序的 Map，它维护元素的有序性，可以按照插入顺序或访问顺序排列元素。这个有序性是通过维护一个双向链表来实现的。另外，LinkedHashMap 提供了 accessOrder 参数来决定是否在访问元素时移动元素，以实现 LRU 缓存功能。这使得 LinkedHashMap 成为一个非常有用的数据结构，适用于需要有序性和缓存功能的场景。