摘要：linkedHashMap 是 Java 集合框架中一个非常重要的类，它确实是一种有顺序的 Map 数据结构。 它继承自 HashMap，但在 HashMap 的基础上，增加了保持元素插入顺序或者访问顺序的功能。
linkedHashMap 是 Java 集合框架中一个非常重要的类，它确实是一种有顺序的 Map 数据结构。 它继承自 HashMap，但在 HashMap 的基础上，增加了保持元素插入顺序或者访问顺序的功能。
让我们详细了解一下 LinkedHashMap 的有序性：
1. LinkedHashMap 的有序性来源
HashMap 是无序的，它不保证元素的顺序，迭代顺序可能会发生变化。而 LinkedHashMap 为了实现有序性，在 HashMap 的基础上，额外维护了一个双向链表 (doubly-linked list)。
HashMap: 使用数组 + 链表/红黑树 来存储键值对，通过哈希函数确定元素在数组中的位置，不维护元素顺序。LinkedHashMap: 除了 HashMap 的数据结构外，还使用一个双向链表来维护所有键值对的插入顺序或访问顺序。链表中的每个节点都记录了元素的插入顺序。2. 两种类型的顺序：插入顺序和访问顺序
LinkedHashMap 提供了两种类型的顺序：
插入顺序 (Insertion Order - 默认): 这是 LinkedHashMap 的默认行为。它会按照键值对被插入到 Map 中的顺序来维护顺序。当你迭代 LinkedHashMap 时，你会按照元素被插入的先后顺序得到它们。访问顺序 (Access Order): 可以通过 LinkedHashMap 的构造函数指定使用访问顺序。在这种模式下，LinkedHashMap 会按照键值对被访问 (get 或 put) 的顺序来维护顺序。最近被访问的元素会被移动到链表的尾部。这种模式常用于实现 LRU (Least Recently Used) 缓存。3. 如何指定顺序类型
LinkedHashMap 提供了多个构造函数，其中一个构造函数可以用来指定顺序类型：
java复制代码public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)accessOrder 参数:accessOrder = false (默认): 使用 插入顺序。accessOrder = true: 使用 访问顺序。例如：
java复制代码// 使用插入顺序 (默认)LinkedHashMap insertionOrderMap = new LinkedHashMap;// 使用访问顺序LinkedHashMap accessOrderMap = new LinkedHashMap(16, 0.75f, true);4. 插入顺序示例
java复制代码import java.util.LinkedHashMap;import java.util.Map;public class LinkedHashMapInsertionOrderExample {public static void main(String args) {LinkedHashMap linkedHashMap = new LinkedHashMap;linkedHashMap.put("Apple", 1);linkedHashMap.put("Banana", 2);linkedHashMap.put("Orange", 3);linkedHashMap.put("Grape", 4);System.out.println("Insertion Order LinkedHashMap:");for (Map.Entry entry : linkedHashMap.entrySet) {System.out.println(entry.getKey + ": " + entry.getValue);}}}输出:
复制代码Insertion Order LinkedHashMap:Apple: 1Banana: 2Orange: 3Grape: 4可以看到，输出的顺序与元素插入的顺序一致。
5. 访问顺序示例 (LRU 缓存模拟)
java复制代码import java.util.LinkedHashMap;import java.util.Map;public class LinkedHashMapAccessOrderExample {public static void main(String args) {// 创建一个容量为 3 的 LRU 缓存 (使用访问顺序)LinkedHashMap lrucache = new LinkedHashMap(3, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {// 当缓存容量超过 3 时，移除最老的元素 (最少被访问的元素)return size > 3;}};lruCache.put("A", 1);lruCache.put("B", 2);lruCache.put("C", 3);System.out.println("Initial LRU Cache:");printCache(lruCache);lruCache.get("B"); // 访问 "B"，将其移动到链表尾部 (最近访问)System.out.println("\nAfter accessing 'B':");printCache(lruCache);lruCache.put("D", 4); // 添加 "D"，由于容量超过 3，最老的元素 "A" 会被移除System.out.println("\nAfter adding 'D':");printCache(lruCache);}private static void printCache(LinkedHashMap cache) {for (Map.Entry entry : cache.entrySet) {System.out.println(entry.getKey + ": " + entry.getValue);}}}输出:
复制代码Initial LRU Cache:A: 1B: 2C: 3After accessing 'B':A: 1C: 3B: 2After adding 'D':C: 3B: 2D: 4在这个 LRU 缓存示例中：
我们创建了一个 LinkedHashMap，并设置 accessOrder = true，使其使用访问顺序。我们重写了 removeEldestEntry 方法，当缓存容量超过 3 时，返回 true，表示需要移除最老的元素。初始状态下，缓存是 A -> B -> C (插入顺序)。访问 lruCache.get("B") 后，“B” 被移动到链表尾部，顺序变为 A -> C -> B (最近访问的在尾部)。添加 “D” 时，由于容量超过 3，最老的元素 “A” 被移除，顺序变为 C -> B -> D。6. LinkedHashMap 的数据结构
LinkedHashMap 的数据结构可以概括为：
HashMap 的数据结构 (数组 + 链表/红黑树): 用于快速查找键值对。双向链表: 维护所有键值对的插入顺序或访问顺序。每个 LinkedHashMap 的节点 (Entry 或 TreeNode) 除了包含 HashMap 节点的属性 (hash, key, value, next) 外，还额外维护了指向前一个节点 (before) 和后一个节点 (after) 的引用，用于构建双向链表。
7. LinkedHashMap 的应用场景
LinkedHashMap 在以下场景中非常有用：
需要保持元素顺序的场景: 例如，需要按照用户输入顺序展示数据，或者需要按照元素插入顺序进行处理。实现 LRU 缓存: 利用访问顺序的特性，可以方便地实现 LRU 缓存，淘汰最近最少使用的元素。构建有序的 Map 数据结构: 当需要一个既有 Map 的快速查找性能，又需要保持元素顺序的数据结构时，LinkedHashMap 是一个很好的选择。8. LinkedHashMap 与 HashMap 和 TreeMap 的比较
HashMap:无序。查找、插入、删除操作平均时间复杂度 O(1)。性能通常比 LinkedHashMap 略好 (因为不需要维护链表)。适用于不需要顺序的场景，追求性能。LinkedHashMap:有序 (插入顺序或访问顺序)。迭代操作时间复杂度 O(n) (与元素数量成正比)，迭代效率比 HashMap 高，因为是链表结构。维护链表需要额外的内存开销，插入和删除操作略慢于 HashMap (需要维护链表)。适用于需要保持元素顺序的场景，例如缓存、需要按顺序处理数据的场景。TreeMap:有序 (按照键的自然顺序或自定义比较器排序)。查找、插入、删除操作时间复杂度 O(log n)。迭代操作按照键的排序顺序进行。基于红黑树实现，内存开销比 HashMap 和 LinkedHashMap 大。适用于需要按照键的排序顺序进行操作的场景，例如字典、排序列表等。总结
LinkedHashMap 是一种非常有用的有序 Map 数据结构，它在 HashMap 的基础上增加了顺序维护功能，可以根据插入顺序或访问顺序来迭代元素。这使得 LinkedHashMap 在需要保持元素顺序的场景，特别是实现缓存等应用中非常实用。理解 LinkedHashMap 的有序性原理和使用场景，可以帮助我们更好地选择合适的 Map 实现来解决实际问题。
来源：晓月科技观