如何在Java中使用LinkedHashMap_技术教程_奈瑶·映南科技互联网学院

LinkedHashMap通过哈希表和双向链表结合，既保证O(1)操作性能，又维护插入或访问顺序，适用于需顺序迭代或实现LRU缓存的场景。

在Java中，

LinkedHashMap

是一个非常实用的集合类，它继承自

HashMap

，但在此基础上增加了一个关键特性：它能记住元素被插入的顺序（或访问的顺序）。这意味着当你遍历

LinkedHashMap

时，元素的顺序会和你当初放入时的顺序保持一致，这对于很多需要保持数据序列的场景来说，简直是量身定制。它本质上是

HashMap

和双向链表的结合体，既提供了哈希表的快速查找能力，又通过链表维护了元素的顺序。

解决方案

使用

LinkedHashMap

其实和使用

HashMap

大同小异，核心API都是那些。

首先，你需要实例化它：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        // 创建一个LinkedHashMap，默认是按插入顺序
        LinkedHashMap userScores = new LinkedHashMap<>();

        // 添加元素，就像HashMap一样
        userScores.put("Alice", 95);
        userScores.put("Bob", 88);
        userScores.put("Charlie", 92);
        userScores.put("David", 76);

        System.out.println("按插入顺序遍历：");
        for (Map.Entry entry : userScores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 访问一个元素，如果LinkedHashMap是以访问顺序排序的，这个元素会被移到链表末尾
        userScores.get("Bob");
        System.out.println("\n访问Bob后，再次遍历（如果accessOrder为true，Bob会移到末尾）：");
        for (Map.Entry entry : userScores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 移除元素
        userScores.remove("Charlie");
        System.out.println("\n移除Charlie后：");
        for (Map.Entry entry : userScores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

你会发现，上面的代码中，第一次遍历时输出的顺序是Alice, Bob, Charlie, David。即便我们访问了"Bob"，在默认的插入顺序模式下，它的位置并不会改变。但如果我们在构造

LinkedHashMap

时传入

true

作为

accessOrder

参数，那么访问操作就会影响元素的顺序，被访问的元素会被移到链表的末尾，这对于实现LRU（最近最少使用）缓存非常有用。

LinkedHashMap与HashMap、TreeMap有什么区别？何时选择LinkedHashMap？

这真的是个好问题，因为它们都是

Map

接口的实现，但内部机制和适用场景却截然不同。在我看来，理解它们之间的差异是选择正确工具的关键。

HashMap
: 这是最常用的
```
Map
```
实现，它不保证任何顺序。元素存储的顺序完全取决于哈希码和内部的哈希表结构。它的优势在于性能极高，对于
```
put
```
、
```
get
```
、
```
remove
```
等基本操作，平均时间复杂度是O(1)。如果你只关心快速存取，对元素的顺序没有任何要求，那
```
HashMap
```
就是你的首选。
TreeMap
:
```
TreeMap
```
实现了
```
SortedMap
```
接口，它会根据键的自然顺序（或者你提供的
```
Comparator
```
）对元素进行排序。这意味着当你遍历
```
TreeMap
```
时，元素总是按键的升序（或自定义顺序）排列。它的操作时间复杂度是O(logN)，因为它的底层是红黑树。当你需要一个始终保持有序的映射时，
```
TreeMap
```
是最佳选择。
LinkedHashMap
: 就像前面说的，它在
```
HashMap
```
的基础上增加了顺序保证。默认情况下是按插入顺序，也可以配置为按访问顺序。它的操作性能与
```
HashMap
```
相近，基本也是O(1)，但由于需要维护双向链表，会比纯粹的
```
HashMap
```
略微消耗更多内存。

何时选择

LinkedHashMap

？

需要保持插入顺序的场景：比如你有一个配置列表，你希望配置项的显示顺序和你在文件中定义的顺序一致；或者一个任务队列，任务的执行顺序应该和添加顺序一致。
实现LRU（最近最少使用）缓存：这是
```
LinkedHashMap
```
一个非常经典的用途，利用它的访问顺序特性可以高效地实现LRU策略。
迭代顺序很重要但又不想牺牲太多性能：如果
```
TreeMap
```
的O(logN)性能开销在你看来有点大，而你又需要一个可预测的迭代顺序，那么
```
LinkedHashMap
```
的O(1)平均性能加上顺序保证，就显得非常平衡了。

总的来说，如果你对顺序有要求，但又不需要键的自然排序，那么

LinkedHashMap

通常会是比

TreeMap

更轻量且性能更好的选择。

如何利用LinkedHashMap实现LRU缓存机制？

用

LinkedHashMap

实现LRU缓存，这简直是教科书般的用法。它的一个构造函数允许你指定

accessOrder

参数，如果设置为

true

，那么每次对

Map

中的元素进行

get

或

put

操作时，该元素都会被移动到链表的末尾，这样链表头部就是最久未使用的元素。

更巧妙的是，

LinkedHashMap

提供了一个受保护的方法

removeEldestEntry(Map.Entry eldest)

。你可以重写这个方法，来定义何时移除最老的（也就是链表头部的）元素。

下面是一个简单的LRU缓存实现示例：

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache extends LinkedHashMap {
    private final int capacity;

    public LRUCache(int capacity) {
        // 调用LinkedHashMap的构造函数
        // initialCapacity: 初始容量
        // loadFactor: 负载因子
        // accessOrder: true表示按访问顺序排序，get或put会把元素移到链表末尾
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    // 重写这个方法来判断何时移除最老的条目
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        // 当Map的大小超过容量时，返回true，LinkedHashMap会自动移除最老的条目
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache<>(3); // 容量为3

        cache.put("A", 1); // A
        cache.put("B", 2); // A, B
        cache.put("C", 3); // A, B, C

        System.out.println("初始缓存: " + cache); // {A=1, B=2, C=3}

        cache.get("A"); // 访问A，A变为最新 {B=2, C=3, A=1}
        System.out.println("访问A后: " + cache);

        cache.put("D", 4); // 添加D，超出容量，最老的B被移除 {C=3, A=1, D=4}
        System.out.println("添加D后: " + cache);

        cache.put("E", 5); // 添加E，超出容量，最老的C被移除 {A=1, D=4, E=5}
        System.out.println("添加E后: " + cache);
    }
}

这段代码清晰地展示了LRU缓存的核心逻辑。通过

accessOrder = true

，每次访问（

get

或

put

）都会把元素提到“最新”的位置；通过重写

removeEldestEntry

，我们定义了缓存满时移除“最老”元素的策略。这简直是优雅和高效的完美结合。

LinkedHashMap的内部实现原理是什么？它如何保证插入顺序或访问顺序？

要理解

LinkedHashMap

的精髓，就得稍微深入它的内部实现。我个人觉得，理解这些底层机制，能帮助我们更好地预判和解决问题。

LinkedHashMap

的核心在于它巧妙地结合了两种数据结构：

哈希表（Hash Table）：这部分和
```
HashMap
```
是一样的，它负责通过键的哈希值快速定位到对应的键值对（
```
Entry
```
对象）。哈希表提供了O(1)的平均查找、插入和删除性能。
双向链表（Doubly Linked List）：这是
```
LinkedHashMap
```
与众不同之处。每一个
```
Entry
```
对象除了包含键、值和指向哈希表中下一个元素的指针外，还额外包含了指向链表中前一个元素（
```
before
```
）和后一个元素（
```
after
```
）的指针。这个双向链表将所有键值对按照它们被插入（或访问）的顺序连接起来。

如何保证插入顺序？

当

accessOrder

设置为

false

（默认值）时，

LinkedHashMap

维护的是插入顺序。

插入（
put
）操作：
- 如果键是新的，
```
LinkedHashMap
```
  会在哈希表中找到或创建一个新的
```
Entry
```
  。同时，这个新的
```
Entry
```
  会被添加到双向链表的末尾。
- 如果键已经存在，它会更新对应的值，但该
```
Entry
```
  在链表中的位置保持不变。
删除（
remove
）操作：
- 从哈希表中移除
```
Entry
```
  。
- 同时，从双向链表中移除对应的
```
Entry
```
  ，通过调整其前后元素的
```
before
```
  和
```
after
```
  指针来“跳过”它。

所以，当遍历

LinkedHashMap

时，它会沿着这个双向链表从头到尾遍历，自然就得到了插入时的顺序。

如何保证访问顺序？

当

accessOrder

设置为

true

时，

LinkedHashMap

维护的是访问顺序。

插入（
put
）操作：
- 如果键是新的，行为和插入顺序模式一样，新
```
Entry
```
  添加到链表末尾。
- 如果键已经存在，更新值后，对应的
```
Entry
```
  会从它当前在链表中的位置移除，然后重新添加到链表的末尾。
访问（
get
）操作：
- 当通过
```
get
```
  方法访问一个
```
Entry
```
  时，如果
```
accessOrder
```
  为
```
true
```
  ，这个
```
Entry
```
  也会从它当前在链表中的位置移除，然后重新添加到链表的末尾。