一、HashMap 的设计盲区它完全不记得你什么时候插入的HashMap 的核心设计目标是最快的随机访问。它通过hashCode()把 key 打散到数组的不同槽位查找是 O(1)。但 HashMap 在设计上做了一个明确的取舍它完全不维护任何顺序信息。MapInteger, String map new HashMap(); map.put(1, A); map.put(2, B); map.put(3, C); // 遍历结果可能是 2, 3, 1完全不可预测 for (Integer key : map.keySet()) { System.out.println(key); }没有 LinkedHashMap 会出现什么弊端弊端 1插入顺序丢失假设你在写一个 HTTP 请求处理器需要按用户提交表单字段的先后顺序处理参数。用 HashMap 存储的话遍历出来的字段顺序是乱的用户先填的用户名可能出现在密码之后这会导致处理逻辑出错。弊端 2无法判断谁最久没被访问假设你在写一个缓存系统内存满了需要淘汰数据。HashMap 能告诉你某个 key 是否存在但它不知道哪个 key 是最久没被访问的。你只知道有还是没有不知道谁先来谁后到。弊端 3自己维护顺序的代价极高你可能会想那我同时用一个ArrayList记录插入顺序不就行了MapK, V map new HashMap(); ListK order new ArrayList(); // 自己维护顺序 // 每次 put 都要维护两个结构 map.put(key, value); order.add(key); // 删除时也要同步 map.remove(key); order.remove(key); // O(n) 的线性搜索这个设计的弊端是两个数据结构需要手动同步漏掉一步就会不一致bug 很难排查ArrayList.remove()是 O(n)删除中间元素要移动后面所有元素如果还要支持访问顺序谁最近被 get 过ArrayList 无法高效地把一个元素从中间移到末尾所以LinkedHashMap 被设计出来的核心动机就是在保留 HashMap O(1) 查找能力的同时让遍历顺序变得可预测、可控制。二、设计决策为什么不从零写而是继承 HashMapLinkedHashMap 的设计者面临一个选择是完全重写一个带顺序的 Map还是在 HashMap 基础上扩展他们选择了继承 HashMap这是一个非常关键的架构决策原因如下2.1 HashMap 的底层逻辑极其复杂HashMap 内部涉及哈希算法与扰动函数数组扩容resize时的 rehash链表长度超过 8 转红黑树红黑树的左旋、右旋、变色负载因子的动态调整这些逻辑经过多年打磨非常成熟。如果重写不仅工作量大还容易引入 bug。2.2 顺序维护和哈希存储是两个正交的职责HashMap 负责怎么存、怎么找LinkedHashMap 负责按什么顺序排。这两个职责可以解耦。所以设计思路是HashMap 继续负责所有哈希相关的复杂逻辑LinkedHashMap 只负责在 HashMap 的节点之间额外拉一条双向链表用来记录顺序在 HashMap 的关键操作点插入、访问、删除插入钩子让 LinkedHashMap 有机会维护这条链表这就是模板方法模式的经典应用。三、核心结构一条额外的双向链表3.1 Entry 节点的设计LinkedHashMap 没有重新定义整个节点结构而是继承HashMap 的 Node只增加了两个指针static class EntryK,V extends HashMap.NodeK,V { EntryK,V before, after; // 双向链表的前驱和后继 Entry(int hash, K key, V value, NodeK,V next) { super(hash, key, value, next); } }一个 Entry 节点同时参与两个结构┌─────────────────────────────────────────┐ │ LinkedHashMap.Entry │ ├─────────────────────────────────────────┤ │ hash │ key │ value │ next │ ← 继承自 HashMap.Node用于哈希表 ├─────────────────────────────────────────┤ │ before │ after │ ← LinkedHashMap 新增用于双向链表 └─────────────────────────────────────────┘next指向哈希冲突链上的下一个节点HashMap 的链表/红黑树逻辑before/after指向双向链表上的前一个/后一个节点LinkedHashMap 的顺序逻辑为什么要用双向链表而不是单向链表因为 LinkedHashMap支持访问顺序模式。在这个模式下每次get()一个已存在的 key需要把这个节点从链表中间摘下来然后移到链表尾部。如果用单向链表你知道当前节点但不知道它的前驱节点要删除当前节点必须从链表头部开始遍历找到前驱时间复杂度 O(n)这就失去了设计的意义双向链表的好处是任意节点都有before指针指向前驱删除和重新插入都是O(1)只需要改几个指针。3.2 链表的头尾指针transient LinkedHashMap.EntryK,V head; // 链表头部最老的节点 transient LinkedHashMap.EntryK,V tail; // 链表尾部最新的节点遍历 LinkedHashMap 时它不走哈希表的数组而是直接沿着head → after → after → ... → tail这条链表走所以遍历顺序是完全可控的。四、HashMap 的钩子方法LinkedHashMap 的精髓这是整个设计中最精妙的部分。HashMap 在内部预留了三个空方法专门给子类扩展// HashMap 中的钩子方法空实现留给子类重写 void afterNodeInsertion(boolean evict) { } // 节点插入后调用 void afterNodeAccess(NodeK,V p) { } // 节点访问后调用 void afterNodeRemoval(NodeK,V p) { } // 节点删除后调用LinkedHashMap 重写了这三个方法在 HashMap 的 put/get/remove 流程中自动维护双向链表而不需要重写整个 put/get/remove 方法。4.1 插入时afterNodeInsertionHashMap 的put()在插入新节点后会调用afterNodeInsertion()。LinkedHashMap 的重写逻辑void afterNodeInsertion(boolean evict) { LinkedHashMap.EntryK,V first; // 如果开启了淘汰机制evicttrue且链表头部存在 if (evict (first head) ! null removeEldestEntry(first)) { K key first.key; removeNode(hash(key), key, null, false, true); // 删除最老的节点 } }这里有一个重要的设计removeEldestEntry()默认返回false所以默认不会自动删除。但你可以重写这个方法来实现缓存淘汰// 实现一个固定容量的 LRU 缓存 MapK, V cache new LinkedHashMapK, V(16, 0.75f, true) { Override protected boolean removeEldestEntry(Map.EntryK,V eldest) { return size() 100; // 超过 100 个就删除最老的 } };4.2 访问时afterNodeAccess访问顺序模式当accessOrder true时每次get()或put()已存在的 keyHashMap 会调用afterNodeAccess()。LinkedHashMap 把它从当前位置摘下来移到链表尾部void afterNodeAccess(NodeK,V e) { LinkedHashMap.EntryK,V last; if (accessOrder (last tail) ! e) { LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e; // 1. 从链表中摘除 p LinkedHashMap.EntryK,V b p.before; LinkedHashMap.EntryK,V a p.after; if (b null) head a; else b.after a; if (a ! null) a.before b; else last b; // 2. 把 p 插到链表尾部 p.after null; p.before last; if (last null) head p; else last.after p; tail p; } }这个设计的意义链表头部始终是最久未被访问的尾部是最近访问的。当需要淘汰时直接删头部就是标准的LRULeast Recently Used策略。4.3 删除时afterNodeRemovalHashMap 删除节点后调用LinkedHashMap 负责把该节点从双向链表中也移除保持链表和哈希表的一致性。五、两种顺序模式LinkedHashMap 通过accessOrder字段控制行为// 默认构造accessOrder false按插入顺序 public LinkedHashMap() { super(); accessOrder false; } // 可以指定 accessOrder true按访问顺序 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder accessOrder; }5.1 插入顺序accessOrder false默认LinkedHashMapInteger, String map new LinkedHashMap(); map.put(3, C); map.put(1, A); map.put(2, B); // 遍历结果3, 1, 2和插入顺序一致 for (Integer key : map.keySet()) { System.out.println(key); }新节点始终插入到链表尾部。已经存在的 key 被重新 put 时不会改变它的位置。5.2 访问顺序accessOrder trueLinkedHashMapInteger, String map new LinkedHashMap(16, 0.75f, true); map.put(3, C); map.put(1, A); map.put(2, B); map.get(1); // 访问 key1把它移到链表尾部 // 遍历结果3, 2, 11 因为被访问过移到了最后 for (Integer key : map.keySet()) { System.out.println(key); }每次get()或put()已存在的 key该节点会被移到链表尾部。链表头部就是最久未访问的。六、为什么这个设计是优雅的6.1 职责分离HashMap负责哈希存储、冲突解决、扩容、树化——怎么存LinkedHashMap负责双向链表的维护——按什么顺序两者通过钩子方法协作互不侵入。6.2 性能无损LinkedHashMap 的查找、插入、删除仍然是O(1)和 HashMap 一样。双向链表的维护操作指针修改也是 O(1)。代价只是每个节点多了两个引用before和after内存开销略大。6.3 扩展性极强通过重写removeEldestEntry()几行代码就能实现一个工业级的 LRU 缓存。这是设计模式模板方法带来的扩展性。七、Map 家族对比特性HashMapLinkedHashMapTreeMap底层结构数组 链表/红黑树数组 链表/红黑树 双向链表红黑树查找复杂度O(1)O(1)O(log n)有序性完全无序插入顺序 / 访问顺序键的排序顺序遍历可预测性不可预测完全可预测按 key 大小排序内存开销最小中等多两个指针最大典型用途通用查找保持插入顺序、LRU 缓存排序、范围查询八、总结LinkedHashMap 的设计逻辑链问题解决方案设计原因HashMap 遍历无序额外维护一条双向链表不改动 HashMap 的核心逻辑只增加顺序信息自己维护顺序容易出错继承 HashMap内部自动同步哈希表和链表在同一个 Entry 上天然一致单向链表无法 O(1) 移动节点双向链表before/after支持访问顺序模式下任意节点的快速重排需要扩展点来维护链表HashMap 预留钩子方法模板方法模式子类只关心自己的逻辑需要缓存淘汰能力removeEldestEntry()可重写几行代码实现 LRU头部就是最久未访问的一句话记住 LinkedHashMap它就是在 HashMap 的每个节点上多挂了两个指针before/after把所有节点串成一条双向链表。HashMap 负责找得到双向链表负责排好序两者通过钩子方法无缝协作。九、什么是访问顺序模式先记住一句话LinkedHashMap 不仅可以按照“插入顺序”维护元素还可以按照“访问顺序”维护元素。1. 先理解什么叫“访问”比如LinkedHashMapString, Integer map new LinkedHashMap(); map.put(A, 1); map.put(B, 2); map.put(C, 3);默认情况下遍历for (String key : map.keySet()) { System.out.println(key); }结果A B C这是插入顺序。也就是谁先put进去谁就在前面。2. 什么叫“访问顺序”LinkedHashMap可以通过这个构造方法开启new LinkedHashMap(16, 0.75f, true);最后这个true就是accessOrder true意思是按照元素最近一次被访问的时间来排序。例如LinkedHashMapString, Integer map new LinkedHashMap(16, 0.75f, true); map.put(A, 1); map.put(B, 2); map.put(C, 3);现在顺序A B C然后map.get(A);虽然我们没有修改 A但是A 被访问了。所以顺序会变成B C A因为B最近没有访问 C最近没有访问 A刚刚被访问再执行map.get(B);顺序变成C A B再map.get(C);变成A B C3. 为什么get()会改变顺序这是理解LinkedHashMap的关键。普通的HashMap你执行map.get(A);不会影响什么。但是LinkedHashMap(accessOrder true)执行map.get(A);相当于把 A 移动到链表的末尾。可以想象成A → B → C访问 Aget(A)变成B → C → A访问 Bget(B)变成C → A → B所以你可以把它理解成谁刚刚被访问谁就被放到队尾。4. 为什么要设计这个功能因为它特别适合实现LRULeast Recently Used最近最少使用缓存LRU 的思想是如果缓存满了就把“最久没有被使用”的数据淘汰掉。例如缓存容量只有 3A B C现在访问get(A);变成B C A再访问get(B);变成C A B此时C最久没有被访问 A其次 B刚刚访问如果现在加入D就可以淘汰最前面的C最终A B D这就是 LRU 的核心思想。5. LinkedHashMap 为什么能做到你前面刚学过HashMap这里可以把它们联系起来。LinkedHashMap本质上是在HashMap的基础上额外维护了一条双向链表。大概可以理解成HashMap 数组 ↓ [ ] → Node [ ] → Node [ ] → Node而LinkedHashMap额外维护HashMap负责 快速找到元素 双向链表负责 维护元素顺序例如A ⇄ B ⇄ C开启访问顺序以后get(A)就会调整链表B ⇄ C ⇄ A所以HashMap解决“快速查找”双向链表解决“顺序维护”。6. 小结LinkedHashMap 有哪两种顺序LinkedHashMap有两种顺序模式插入顺序默认模式按照元素插入 Map 的顺序进行遍历。访问顺序通过构造方法accessOrder true开启元素每次被访问后会移动到链表末尾因此可以用来实现 LRU 缓存。例如new LinkedHashMap(16, 0.75f, true);最后一个true就代表accessOrder true7. 你现在可以这样理解整个 LinkedHashMap你刚开始学TreeMap、HashMap、LinkedHashMap可以先形成这个体系集合核心特点HashMap快速查找不保证顺序LinkedHashMap快速查找 维护顺序TreeMap按 Key 排序其中LinkedHashMap的顺序又分LinkedHashMap │ ├── 插入顺序默认 │ └── 访问顺序accessOrdertrue │ └── 常用于 LRU 缓存 LinkedHashMap 讲解
一、HashMap 的设计盲区它完全不记得你什么时候插入的HashMap 的核心设计目标是最快的随机访问。它通过hashCode()把 key 打散到数组的不同槽位查找是 O(1)。但 HashMap 在设计上做了一个明确的取舍它完全不维护任何顺序信息。MapInteger, String map new HashMap(); map.put(1, A); map.put(2, B); map.put(3, C); // 遍历结果可能是 2, 3, 1完全不可预测 for (Integer key : map.keySet()) { System.out.println(key); }没有 LinkedHashMap 会出现什么弊端弊端 1插入顺序丢失假设你在写一个 HTTP 请求处理器需要按用户提交表单字段的先后顺序处理参数。用 HashMap 存储的话遍历出来的字段顺序是乱的用户先填的用户名可能出现在密码之后这会导致处理逻辑出错。弊端 2无法判断谁最久没被访问假设你在写一个缓存系统内存满了需要淘汰数据。HashMap 能告诉你某个 key 是否存在但它不知道哪个 key 是最久没被访问的。你只知道有还是没有不知道谁先来谁后到。弊端 3自己维护顺序的代价极高你可能会想那我同时用一个ArrayList记录插入顺序不就行了MapK, V map new HashMap(); ListK order new ArrayList(); // 自己维护顺序 // 每次 put 都要维护两个结构 map.put(key, value); order.add(key); // 删除时也要同步 map.remove(key); order.remove(key); // O(n) 的线性搜索这个设计的弊端是两个数据结构需要手动同步漏掉一步就会不一致bug 很难排查ArrayList.remove()是 O(n)删除中间元素要移动后面所有元素如果还要支持访问顺序谁最近被 get 过ArrayList 无法高效地把一个元素从中间移到末尾所以LinkedHashMap 被设计出来的核心动机就是在保留 HashMap O(1) 查找能力的同时让遍历顺序变得可预测、可控制。二、设计决策为什么不从零写而是继承 HashMapLinkedHashMap 的设计者面临一个选择是完全重写一个带顺序的 Map还是在 HashMap 基础上扩展他们选择了继承 HashMap这是一个非常关键的架构决策原因如下2.1 HashMap 的底层逻辑极其复杂HashMap 内部涉及哈希算法与扰动函数数组扩容resize时的 rehash链表长度超过 8 转红黑树红黑树的左旋、右旋、变色负载因子的动态调整这些逻辑经过多年打磨非常成熟。如果重写不仅工作量大还容易引入 bug。2.2 顺序维护和哈希存储是两个正交的职责HashMap 负责怎么存、怎么找LinkedHashMap 负责按什么顺序排。这两个职责可以解耦。所以设计思路是HashMap 继续负责所有哈希相关的复杂逻辑LinkedHashMap 只负责在 HashMap 的节点之间额外拉一条双向链表用来记录顺序在 HashMap 的关键操作点插入、访问、删除插入钩子让 LinkedHashMap 有机会维护这条链表这就是模板方法模式的经典应用。三、核心结构一条额外的双向链表3.1 Entry 节点的设计LinkedHashMap 没有重新定义整个节点结构而是继承HashMap 的 Node只增加了两个指针static class EntryK,V extends HashMap.NodeK,V { EntryK,V before, after; // 双向链表的前驱和后继 Entry(int hash, K key, V value, NodeK,V next) { super(hash, key, value, next); } }一个 Entry 节点同时参与两个结构┌─────────────────────────────────────────┐ │ LinkedHashMap.Entry │ ├─────────────────────────────────────────┤ │ hash │ key │ value │ next │ ← 继承自 HashMap.Node用于哈希表 ├─────────────────────────────────────────┤ │ before │ after │ ← LinkedHashMap 新增用于双向链表 └─────────────────────────────────────────┘next指向哈希冲突链上的下一个节点HashMap 的链表/红黑树逻辑before/after指向双向链表上的前一个/后一个节点LinkedHashMap 的顺序逻辑为什么要用双向链表而不是单向链表因为 LinkedHashMap支持访问顺序模式。在这个模式下每次get()一个已存在的 key需要把这个节点从链表中间摘下来然后移到链表尾部。如果用单向链表你知道当前节点但不知道它的前驱节点要删除当前节点必须从链表头部开始遍历找到前驱时间复杂度 O(n)这就失去了设计的意义双向链表的好处是任意节点都有before指针指向前驱删除和重新插入都是O(1)只需要改几个指针。3.2 链表的头尾指针transient LinkedHashMap.EntryK,V head; // 链表头部最老的节点 transient LinkedHashMap.EntryK,V tail; // 链表尾部最新的节点遍历 LinkedHashMap 时它不走哈希表的数组而是直接沿着head → after → after → ... → tail这条链表走所以遍历顺序是完全可控的。四、HashMap 的钩子方法LinkedHashMap 的精髓这是整个设计中最精妙的部分。HashMap 在内部预留了三个空方法专门给子类扩展// HashMap 中的钩子方法空实现留给子类重写 void afterNodeInsertion(boolean evict) { } // 节点插入后调用 void afterNodeAccess(NodeK,V p) { } // 节点访问后调用 void afterNodeRemoval(NodeK,V p) { } // 节点删除后调用LinkedHashMap 重写了这三个方法在 HashMap 的 put/get/remove 流程中自动维护双向链表而不需要重写整个 put/get/remove 方法。4.1 插入时afterNodeInsertionHashMap 的put()在插入新节点后会调用afterNodeInsertion()。LinkedHashMap 的重写逻辑void afterNodeInsertion(boolean evict) { LinkedHashMap.EntryK,V first; // 如果开启了淘汰机制evicttrue且链表头部存在 if (evict (first head) ! null removeEldestEntry(first)) { K key first.key; removeNode(hash(key), key, null, false, true); // 删除最老的节点 } }这里有一个重要的设计removeEldestEntry()默认返回false所以默认不会自动删除。但你可以重写这个方法来实现缓存淘汰// 实现一个固定容量的 LRU 缓存 MapK, V cache new LinkedHashMapK, V(16, 0.75f, true) { Override protected boolean removeEldestEntry(Map.EntryK,V eldest) { return size() 100; // 超过 100 个就删除最老的 } };4.2 访问时afterNodeAccess访问顺序模式当accessOrder true时每次get()或put()已存在的 keyHashMap 会调用afterNodeAccess()。LinkedHashMap 把它从当前位置摘下来移到链表尾部void afterNodeAccess(NodeK,V e) { LinkedHashMap.EntryK,V last; if (accessOrder (last tail) ! e) { LinkedHashMap.EntryK,V p (LinkedHashMap.EntryK,V)e; // 1. 从链表中摘除 p LinkedHashMap.EntryK,V b p.before; LinkedHashMap.EntryK,V a p.after; if (b null) head a; else b.after a; if (a ! null) a.before b; else last b; // 2. 把 p 插到链表尾部 p.after null; p.before last; if (last null) head p; else last.after p; tail p; } }这个设计的意义链表头部始终是最久未被访问的尾部是最近访问的。当需要淘汰时直接删头部就是标准的LRULeast Recently Used策略。4.3 删除时afterNodeRemovalHashMap 删除节点后调用LinkedHashMap 负责把该节点从双向链表中也移除保持链表和哈希表的一致性。五、两种顺序模式LinkedHashMap 通过accessOrder字段控制行为// 默认构造accessOrder false按插入顺序 public LinkedHashMap() { super(); accessOrder false; } // 可以指定 accessOrder true按访问顺序 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder accessOrder; }5.1 插入顺序accessOrder false默认LinkedHashMapInteger, String map new LinkedHashMap(); map.put(3, C); map.put(1, A); map.put(2, B); // 遍历结果3, 1, 2和插入顺序一致 for (Integer key : map.keySet()) { System.out.println(key); }新节点始终插入到链表尾部。已经存在的 key 被重新 put 时不会改变它的位置。5.2 访问顺序accessOrder trueLinkedHashMapInteger, String map new LinkedHashMap(16, 0.75f, true); map.put(3, C); map.put(1, A); map.put(2, B); map.get(1); // 访问 key1把它移到链表尾部 // 遍历结果3, 2, 11 因为被访问过移到了最后 for (Integer key : map.keySet()) { System.out.println(key); }每次get()或put()已存在的 key该节点会被移到链表尾部。链表头部就是最久未访问的。六、为什么这个设计是优雅的6.1 职责分离HashMap负责哈希存储、冲突解决、扩容、树化——怎么存LinkedHashMap负责双向链表的维护——按什么顺序两者通过钩子方法协作互不侵入。6.2 性能无损LinkedHashMap 的查找、插入、删除仍然是O(1)和 HashMap 一样。双向链表的维护操作指针修改也是 O(1)。代价只是每个节点多了两个引用before和after内存开销略大。6.3 扩展性极强通过重写removeEldestEntry()几行代码就能实现一个工业级的 LRU 缓存。这是设计模式模板方法带来的扩展性。七、Map 家族对比特性HashMapLinkedHashMapTreeMap底层结构数组 链表/红黑树数组 链表/红黑树 双向链表红黑树查找复杂度O(1)O(1)O(log n)有序性完全无序插入顺序 / 访问顺序键的排序顺序遍历可预测性不可预测完全可预测按 key 大小排序内存开销最小中等多两个指针最大典型用途通用查找保持插入顺序、LRU 缓存排序、范围查询八、总结LinkedHashMap 的设计逻辑链问题解决方案设计原因HashMap 遍历无序额外维护一条双向链表不改动 HashMap 的核心逻辑只增加顺序信息自己维护顺序容易出错继承 HashMap内部自动同步哈希表和链表在同一个 Entry 上天然一致单向链表无法 O(1) 移动节点双向链表before/after支持访问顺序模式下任意节点的快速重排需要扩展点来维护链表HashMap 预留钩子方法模板方法模式子类只关心自己的逻辑需要缓存淘汰能力removeEldestEntry()可重写几行代码实现 LRU头部就是最久未访问的一句话记住 LinkedHashMap它就是在 HashMap 的每个节点上多挂了两个指针before/after把所有节点串成一条双向链表。HashMap 负责找得到双向链表负责排好序两者通过钩子方法无缝协作。九、什么是访问顺序模式先记住一句话LinkedHashMap 不仅可以按照“插入顺序”维护元素还可以按照“访问顺序”维护元素。1. 先理解什么叫“访问”比如LinkedHashMapString, Integer map new LinkedHashMap(); map.put(A, 1); map.put(B, 2); map.put(C, 3);默认情况下遍历for (String key : map.keySet()) { System.out.println(key); }结果A B C这是插入顺序。也就是谁先put进去谁就在前面。2. 什么叫“访问顺序”LinkedHashMap可以通过这个构造方法开启new LinkedHashMap(16, 0.75f, true);最后这个true就是accessOrder true意思是按照元素最近一次被访问的时间来排序。例如LinkedHashMapString, Integer map new LinkedHashMap(16, 0.75f, true); map.put(A, 1); map.put(B, 2); map.put(C, 3);现在顺序A B C然后map.get(A);虽然我们没有修改 A但是A 被访问了。所以顺序会变成B C A因为B最近没有访问 C最近没有访问 A刚刚被访问再执行map.get(B);顺序变成C A B再map.get(C);变成A B C3. 为什么get()会改变顺序这是理解LinkedHashMap的关键。普通的HashMap你执行map.get(A);不会影响什么。但是LinkedHashMap(accessOrder true)执行map.get(A);相当于把 A 移动到链表的末尾。可以想象成A → B → C访问 Aget(A)变成B → C → A访问 Bget(B)变成C → A → B所以你可以把它理解成谁刚刚被访问谁就被放到队尾。4. 为什么要设计这个功能因为它特别适合实现LRULeast Recently Used最近最少使用缓存LRU 的思想是如果缓存满了就把“最久没有被使用”的数据淘汰掉。例如缓存容量只有 3A B C现在访问get(A);变成B C A再访问get(B);变成C A B此时C最久没有被访问 A其次 B刚刚访问如果现在加入D就可以淘汰最前面的C最终A B D这就是 LRU 的核心思想。5. LinkedHashMap 为什么能做到你前面刚学过HashMap这里可以把它们联系起来。LinkedHashMap本质上是在HashMap的基础上额外维护了一条双向链表。大概可以理解成HashMap 数组 ↓ [ ] → Node [ ] → Node [ ] → Node而LinkedHashMap额外维护HashMap负责 快速找到元素 双向链表负责 维护元素顺序例如A ⇄ B ⇄ C开启访问顺序以后get(A)就会调整链表B ⇄ C ⇄ A所以HashMap解决“快速查找”双向链表解决“顺序维护”。6. 小结LinkedHashMap 有哪两种顺序LinkedHashMap有两种顺序模式插入顺序默认模式按照元素插入 Map 的顺序进行遍历。访问顺序通过构造方法accessOrder true开启元素每次被访问后会移动到链表末尾因此可以用来实现 LRU 缓存。例如new LinkedHashMap(16, 0.75f, true);最后一个true就代表accessOrder true7. 你现在可以这样理解整个 LinkedHashMap你刚开始学TreeMap、HashMap、LinkedHashMap可以先形成这个体系集合核心特点HashMap快速查找不保证顺序LinkedHashMap快速查找 维护顺序TreeMap按 Key 排序其中LinkedHashMap的顺序又分LinkedHashMap │ ├── 插入顺序默认 │ └── 访问顺序accessOrdertrue │ └── 常用于 LRU 缓存