JavaLinkedHashMap：结合哈希表与链表的数据结构
LinkedHashMap是 Java 集合框架中的一种数据结构，结合了HashMap的高效查找特性和LinkedList的顺序维护特性。与普通的HashMap不同，LinkedHashMap保留了插入元素的顺序或访问顺序，使得它在许多场景下非常有用，尤其是需要保持元素顺序的场景。
1.LinkedHashMap类概述
LinkedHashMap继承自HashMap，因此它包含HashMap的所有特性，但额外实现了双向链表来维护元素的顺序。具体来说，LinkedHashMap中的每个元素都包含了前后指针，确保可以在插入时记录元素的顺序。
关键源码：LinkedHashMap类声明
java复制
public class LinkedHashMap<K,V> extends HashMap<K,V> { private transient LinkedHashMap.Entry<K,V> head; private transient LinkedHashMap.Entry<K,V> tail; public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } }head和tail：表示链表的头节点和尾节点。accessOrder：控制顺序是基于插入顺序（false）还是访问顺序（true）。
2. 双向链表的结构
LinkedHashMap内部使用了一个双向链表来维护元素的顺序。每个元素不仅存储了键值对，还包含了指向前后元素的指针，形成了一个链表。
关键源码：Entry类
java复制
static class Entry<K,V> extends HashMap.Entry<K,V> { Entry<K,V> before, after; Entry(K key, V value, int hash, Entry<K,V> next) { super(key, value, hash, next); } }before：指向前一个元素。after：指向后一个元素。 通过这两个指针，LinkedHashMap可以快速地维护插入顺序或访问顺序。
3. 插入元素的流程
当我们向LinkedHashMap中插入元素时，除了会进行HashMap的常规插入操作外，还会在链表中插入元素，并更新head和tail指针。
关键源码：put方法
putVal会在哈希表中查找元素，如果没有找到，就创建一个新的Entry并调用addEntry方法将其插入到哈希表中。afterNodeAccess用于更新访问顺序，如果是访问顺序，它会将当前元素移到链表的末尾。
关键源码：addEntry方法
- 插入操作：
addEntry将元素插入到哈希表的指定位置，并且在链表中将其添加到header（头部）后面。 - 链表更新：通过
e.after和e.before指针将新插入的元素与前后元素连接起来，确保顺序不变。
4. 查找元素的流程
LinkedHashMap中的查找过程与HashMap相似，都是通过哈希表来实现高效查找，但LinkedHashMap额外提供了一个功能：维护元素的顺序。
关键源码：get方法
get方法通过getEntry查找元素。如果找到元素并且accessOrder为true，则调用afterNodeAccess更新元素在链表中的顺序。
关键源码：afterNodeAccess方法
moveToLast：将元素移到链表的末尾，确保元素访问顺序正确。
5. 删除元素的流程
删除元素时，LinkedHashMap会首先从哈希表中移除元素，然后在链表中删除该元素。这里需要注意的是，链表操作是双向的，删除时需要更新前后节点的指针。
关键源码：removeNode方法
- 在删除元素时，除了在哈希表中移除元素外，还需要调整链表中的指针，确保删除操作后链表的完整性。
6.LinkedHashMap的迭代器
LinkedHashMap的迭代器LinkedHashIterator采用了双向链表的结构，能够按顺序返回元素。它通过维护head和tail指针，在顺序遍历时非常高效。
关键源码：LinkedHashIterator
nextEntry：指向链表中的下一个元素，遍历时按顺序访问。hasNext：判断是否有下一个元素，遍历结束时返回false。
7. 访问顺序与插入顺序
LinkedHashMap提供了两种顺序：插入顺序和访问顺序。通过构造函数中的accessOrder参数，我们可以指定使用哪种顺序。
- 插入顺序：元素按插入顺序排列。
- 访问顺序：元素根据访问顺序排列，访问过的元素会被移动到链表的末尾。
8.LinkedHashMap的性能
LinkedHashMap的查找、插入和删除操作与HashMap相似，都是O(1)的时间复杂度。然而，由于其额外的链表维护操作，插入和删除操作的开销稍微大一些。对于需要维护顺序的场景，LinkedHashMap提供了非常高效且灵活的解决方案。
