LinkedHashMap | JavaSE

LinkedHashMap

一、学习目标

完成本章后，你应该能够：

  • 能够解释 LinkedHashMap 与 HashMap 的继承关系。
  • 能够说明 LinkedHashMap 为什么既具有哈希查询能力，又拥有确定的遇见顺序。
  • 能够解释“哈希表 + 双向链表”的职责分工。
  • 能够区分插入顺序（Insertion Order）与访问顺序（Access Order）。
  • 能够解释重复 put() 为什么默认不会改变插入顺序。
  • 能够使用 JDK 21 SequencedMap 的首尾映射和反向视图能力。
  • 能够解释 access-order LinkedHashMap 为什么适合实现 LRU 思路。
  • 能够理解 removeEldestEntry() 在受限缓存模型中的作用。
  • 能够根据业务需求在 HashMap、LinkedHashMap、TreeMap 之间进行初步选型。

二、核心知识

2.1 LinkedHashMap 是什么

LinkedHashMap 是：

HashMap

的子类。

关系：

Map
 ↑
HashMap
 ↑
LinkedHashMap

基本使用：

Map<String, Integer> map =
        new LinkedHashMap<>();

它继承了 HashMap 的核心能力：

key 唯一
value 可重复
哈希查找
平均高效 get / put

同时进一步提供：

明确的映射遇见顺序。

2.2 LinkedHashMap 与 HashMap 的核心区别

HashMap：

key → value
+
哈希表
+
不保证遍历顺序

LinkedHashMap：

key → value
+
哈希表
+
双向链表
+
确定的遇见顺序

因此可以概括：

LinkedHashMap
=
HashMap
+
顺序维护能力

2.3 底层结构

项目原教学资料将 LinkedHashMap 概括为：

基于哈希表，同时每个键值对额外通过双向链表记录元素顺序。

这个模型非常准确。

可抽象为：

哈希结构：

table
├── bucket 0
├── bucket 1 → Entry
├── bucket 2
├── bucket 3 → Entry → Entry
└── ...


另外还有顺序链：

Entry A ⇄ Entry B ⇄ Entry C ⇄ Entry D

因此一组 Entry 同时属于：

哈希表结构

和：

顺序链结构

2.4 两套结构分别干什么

哈希表

负责：

get(key)
put(key,value)
containsKey(key)
remove(key)

核心目标：

快速定位 key。

双向链表

负责：

谁在前面
谁在后面

核心目标：

维护明确的 encounter order。

因此要牢牢记住：

哈希表
→ 快速查找

双向链表
→ 维护顺序

不能反过来。

2.5 默认是插入顺序

普通：

LinkedHashMap<String, Integer> map =
        new LinkedHashMap<>();

默认采用：

插入顺序（Insertion Order）

例如：

map.put("Java", 1);
map.put("MySQL", 2);
map.put("Redis", 3);

遍历：

Java
MySQL
Redis

按照映射首次插入的顺序。

2.6 重复 put 不会默认移动位置

例如：

map.put("Java", 1);
map.put("MySQL", 2);
map.put("Redis", 3);

map.put("Java", 100);

最终 value：

Java → 100

但是默认插入顺序仍然：

Java
MySQL
Redis

并不会自动变成：

MySQL
Redis
Java

因为：

重新为已有 key 设置 value，不等于第一次插入这个 key。

2.7 LinkedHashMap 的“有序”不是排序

例如：

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

默认 LinkedHashMap 遍历：

C
A
B

而不是：

A
B
C

因此：

LinkedHashMap

维护的是：

遇见 / 插入顺序

而：

TreeMap

才根据：

key 比较规则

进行排序。

三、使用方法

3.1 创建 LinkedHashMap

Map<String, Integer> map =
        new LinkedHashMap<>();

如果需要顺序相关专用 API：

LinkedHashMap<String, Integer> map =
        new LinkedHashMap<>();

3.2 基本操作与 HashMap 基本一致

map.put("Java", 95);
map.put("MySQL", 90);

Integer javaScore =
        map.get("Java");

map.remove("MySQL");

boolean exists =
        map.containsKey("Java");

所以：

LinkedHashMap 不是需要重新学习一套 Map API。

主要新增的是：

顺序语义

3.3 遍历时保持确定顺序

LinkedHashMap<String, Integer> map =
        new LinkedHashMap<>();

map.put("Java", 95);
map.put("MySQL", 90);
map.put("Redis", 88);

map.forEach((key, value) ->
        System.out.println(
                key + "=" + value
        )
);

输出遇见顺序：

Java
MySQL
Redis

具有明确契约。

3.4 从其他 Map 创建有序副本

例如：

Map<String, Integer> source = ...;

Map<String, Integer> copy =
        new LinkedHashMap<>(source);

LinkedHashMap 会按照：

source 提供映射时的遍历顺序

建立自己的插入顺序。

这在：

接收某个 Map
↓
希望保存当时的遍历顺序
↓
后续稳定输出

时很有价值。

四、原理与进阶

4.1 Entry 如何维护顺序

可以把 LinkedHashMap Entry 抽象成：

┌────────┬────────┬────────┬────────┐
│ before │ key    │ value  │ after  │
└────────┴────────┴────────┴────────┘

实际还需要继承 HashMap 节点具有的：

hash
next

等信息。

因此 Entry 同时具有：

哈希桶链接

和：

全局顺序链接

两个维度。

4.2 为什么遍历速度不完全依赖 capacity

HashMap 遍历：

capacity + size

都会影响成本。

而 LinkedHashMap 可以沿着：

双向顺序链

逐个遍历真实 Entry。

因此其集合视图迭代：

主要与实际 size 成比例。

这也是 LinkedHashMap 在“需要稳定遍历”时的一个特征。

当然代价是：

额外顺序节点信息

带来的内存开销。

4.3 顺序不是免费的

LinkedHashMap 相比 HashMap 需要额外维护：

before
after

以及：

head
tail

一类顺序信息。

所以：

HashMap

如果已经满足业务要求，就没有必要无脑替换成 LinkedHashMap。

选择 LinkedHashMap 的理由应该是：

业务真正需要顺序。

4.4 LinkedHashMap 还有第二种顺序：Access Order

这是 LinkedHashMap 非常重要但常被初学教程忽略的能力。

构造器：

LinkedHashMap(
        int initialCapacity,
        float loadFactor,
        boolean accessOrder
)

例如：

LinkedHashMap<String, Integer> map =
        new LinkedHashMap<>(
                16,
                0.75f,
                true
        );

最后一个参数：

true

表示：

按访问顺序（Access Order）维护 Entry。

4.5 什么是访问顺序

假设加入：

A
B
C

最初：

A → B → C

此时：

map.get("A");

在 access-order 模式中，A 被认为刚刚访问。

于是顺序会调整为：

B → C → A

其中：

最前面
→ 最久没有访问

最后面
→ 最近访问

这就是：

Least Recently Used / Most Recently Used

模型的基础。

4.6 哪些操作算访问

在 access-order LinkedHashMap 中，一些操作会让 Entry 被认为“访问过”。

典型包括：

get()
getOrDefault()

put()
putIfAbsent()

compute()
computeIfAbsent()
computeIfPresent()

merge()

当对应映射存在或最终存在时，会参与访问顺序更新。

所以 access-order 不只是：

get 才算访问

需要根据具体 API 契约理解。

4.7 为什么 access-order 非常适合 LRU

LRU：

Least Recently Used，最近最少使用。

假设缓存最多保存：

3

条记录。

当前：

A → B → C

其中 A 最久未访问。

后来访问：

A

顺序：

B → C → A

B 现在成为：

最久未访问

如果再放入：

D

需要淘汰一个：

B

这就是经典：

LRU Cache

思路。

4.8 removeEldestEntry()

LinkedHashMap 提供：

protected boolean removeEldestEntry(
        Map.Entry<K, V> eldest
)

可以通过继承：

class LruCache<K, V>
        extends LinkedHashMap<K, V> {
}

并重写：

@Override
protected boolean removeEldestEntry(
        Map.Entry<K, V> eldest
) {
    return size() > MAX_SIZE;
}

当：

size 超过上限

返回 true：

自动删除当前 eldest entry

这使 LinkedHashMap 很适合学习：

容量受限缓存
LRU

的基础思想。

4.9 一个简单 LRU 示例

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

public class LruCache<K, V>
        extends LinkedHashMap<K, V> {

    private final int maxSize;

    public LruCache(int maxSize) {
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(
            Map.Entry<K, V> eldest
    ) {
        return size() > maxSize;
    }
}

使用：

LruCache<String, String> cache =
        new LruCache<>(3);

cache.put("A", "a");
cache.put("B", "b");
cache.put("C", "c");

cache.get("A");

cache.put("D", "d");

此时可以分析：

谁最近被访问？
谁最久没被访问？
谁应该被淘汰？

这比死记 API 更重要。

4.10 JDK 21：LinkedHashMap 实现 SequencedMap

JDK 21 中：

LinkedHashMap<K,V>

实现：

SequencedMap<K,V>

于是：

Java 正式把“具有明确首尾顺序的 Map”抽象成统一接口。

LinkedHashMap 获得了一系列统一顺序 API。

4.11 firstEntry()

Map.Entry<String, Integer> first =
        map.firstEntry();

表示：

获取 encounter order 中第一个映射。

4.12 lastEntry()

Map.Entry<String, Integer> last =
        map.lastEntry();

表示：

获取最后一个映射。

4.13 pollFirstEntry()

Map.Entry<String, Integer> first =
        map.pollFirstEntry();

表示：

删除并返回第一个映射。

4.14 pollLastEntry()

Map.Entry<String, Integer> last =
        map.pollLastEntry();

表示：

删除并返回最后一个映射。

4.15 putFirst()

JDK 21：

map.putFirst("Redis", 88);

可以显式把映射定位到：

encounter order 最前面

如果 key 已经存在：

更新 value
+
重新调整到最前面

4.16 putLast()

map.putLast("Java", 100);

可以把对应 mapping：

定位到最后

如果 key 已经存在，不会产生重复 key。

4.17 reversed()

SequencedMap<String, Integer> reversed =
        map.reversed();

得到：

反向顺序视图。

原 Map：

A → B → C

反向视图：

C → B → A

注意：

这是视图，不是默认复制出的独立 Map。

4.18 insertion-order 与 access-order 的区别

这是本章最核心的高级区别。

插入顺序

默认：

new LinkedHashMap<>()

顺序主要根据：

第一次插入 mapping 的顺序

普通 get：

get(key)

不会改变顺序。

访问顺序

new LinkedHashMap<>(
        16,
        0.75f,
        true
)

顺序根据：

最近访问情况

变化。

所以：

insertion-order
→ 谁先来

access-order
→ 谁最近被用过

这两个概念必须严格区分。

五、实践应用

5.1 去重并保持 key 插入顺序

假设需要：

商品编号 → 商品信息

同时要求：

后续输出按商品第一次加入顺序。

LinkedHashMap 非常适合。

5.2 配置项

例如：

server.port
spring.application.name
database.url

如果需要：

key-value
+
稳定输出顺序

LinkedHashMap 是一种常见选择。

5.3 API 返回数据顺序

例如某个模块收到：

Map<String, Object>

希望后续返回数据时仍保持某种既定顺序。

可以考虑复制到：

LinkedHashMap

中。

5.4 最近访问记录

例如：

用户最近访问页面
最近打开文件
最近访问项目

可以利用：

access-order LinkedHashMap

建立数据结构模型。

5.5 LRU 缓存

如果需求是：

最多缓存 N 条
+
每次访问更新“最近使用”
+
超过 N 自动淘汰最久未使用

LinkedHashMap 提供：

accessOrder
+
removeEldestEntry

可以非常直观地实现基础 LRU。

5.6 HashMap、LinkedHashMap、TreeMap 初步选型

可以建立：

需要 key → value
       ↓
是否需要排序？
 ┌─────┴─────┐
 │           │
是           否
 │           │
TreeMap    是否需要固定遇见顺序？
           ┌─────┴─────┐
           │           │
          是           否
           │           │
   LinkedHashMap     HashMap

更加简单地说：

HashMap
→ 不关心遍历顺序

LinkedHashMap
→ 关心确定遇见顺序

TreeMap
→ 需要 key 排序

六、常见问题

6.1 LinkedHashMap 是不是排序 Map？

不是。

默认 LinkedHashMap：

按照插入顺序

并不是：

按照 key 大小排序

后者是：

TreeMap

6.2 LinkedHashMap 比 HashMap 多了什么？

核心：

维护所有 Entry encounter order 的双向链表

6.3 LinkedHashMap 查询是不是走双向链表？

主要 key 查询仍然依赖：

HashMap 哈希表机制

双向链表主要负责：

顺序

6.4 重复 put 会不会把 key 移到最后？

默认 insertion-order 模式：

put(existingKey, newValue)

不会因为重新 put 就自动移动原 mapping。

但：

putFirst()
putLast()

可以显式改变位置。

access-order 模式下，某些访问操作又会根据访问规则调整位置。

所以要先判断：

当前是哪种 ordering mode？

6.5 LinkedHashMap 为什么比 HashMap 占内存更多？

因为每个 Entry 除了哈希结构信息之外，还要维护：

before
after

等顺序链接。

6.6 access-order 是不是默认的？

不是。

默认：

insertion-order

需要通过特殊构造器：

new LinkedHashMap<>(
        initialCapacity,
        loadFactor,
        true
)

启用 access-order。

6.7 get() 会改变 LinkedHashMap 顺序吗？

默认 insertion-order：

不会

access-order：

会将被访问 Entry 调整到最近访问位置

因此不能脱离 ordering mode 回答这个问题。

6.8 LinkedHashMap 可以实现真正生产级缓存吗？

它可以非常好地表达：

LRU 核心数据结构思想

但真实生产缓存还可能涉及：

  • 并发安全；
  • 过期时间；
  • 最大内存；
  • 淘汰策略；
  • 统计；
  • 持久化；
  • 分布式；

等大量问题。

所以：

LinkedHashMap LRU 是非常好的数据结构案例，但不是 Redis/Caffeine 等缓存系统的完整替代品。

6.9 LinkedHashMap 是线程安全的吗？

不是。

和 HashMap 一样：

LinkedHashMap 默认不是线程安全集合

6.10 LinkedHashMap 可以保存 null 吗？

LinkedHashMap 继承 HashMap 的相关行为：

允许 null key
允许 null value

但是这仍然只是：

HashMap / LinkedHashMap

的具体实现规则，不应推广成所有 Map。

七、练习与验收

7.1 知识问答

  1. LinkedHashMap 继承谁？
  2. LinkedHashMap 与 HashMap 最大区别是什么？
  3. LinkedHashMap 底层总体结构是什么？
  4. 哈希表负责什么？
  5. 双向链表负责什么？
  6. 什么是 encounter order？
  7. 默认 LinkedHashMap 使用什么顺序？
  8. 重复 put 已有 key 默认是否改变位置？
  9. LinkedHashMap 的“有序”是不是自动排序？
  10. 什么是 access-order？
  11. insertion-order 与 access-order 有什么区别？
  12. access-order 中 get 为什么可能改变顺序？
  13. 什么是 LRU？
  14. LinkedHashMap 为什么适合实现 LRU？
  15. removeEldestEntry 解决什么问题？
  16. JDK 21 中 SequencedMap 解决什么问题？
  17. firstEntry() 与 lastEntry() 分别做什么？
  18. putFirst()、putLast() 有什么作用？
  19. reversed() 返回什么？
  20. 为什么 LinkedHashMap 内存开销高于 HashMap？

7.2 代码阅读

禁止运行：

LinkedHashMap<String, Integer> map =
        new LinkedHashMap<>();

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

map.put("A", 100);
map.get("B");

System.out.println(map);

回答：

  1. 最终 value 中 A 是多少？
  2. A 是否移动到最后？
  3. get B 是否改变顺序？
  4. 最终 encounter order 是什么？
  5. 如果改成 access-order，哪些答案会变化？

7.3 手写代码

任务一：有序映射

创建：

LinkedHashMap<String, Integer>

按顺序加入：

Java → 95
MySQL → 88
Redis → 90

要求：

  • 修改 Java value；
  • 验证普通 put 不改变插入位置；
  • 遍历全部映射。

任务二：JDK 21 顺序 API

依次使用：

firstEntry()
lastEntry()

putFirst()
putLast()

pollFirstEntry()
pollLastEntry()

reversed()

并在纸上记录每一步 Map 的 encounter order。

任务三：访问顺序

创建：

new LinkedHashMap<>(
        16,
        0.75f,
        true
)

添加：

A B C D

然后依次：

get("B");
get("A");

禁止运行，先预测最终顺序，再运行验证。

7.4 Debug

业务需求：

按最近访问顺序维护用户页面。

程序却写：

LinkedHashMap<String, String> map =
        new LinkedHashMap<>();

map.put("home", "首页");
map.put("blog", "博客");
map.put("about", "关于");

map.get("home");

程序员认为调用 get("home") 后：

home

会自动移动到末尾。

回答：

  1. 这个判断为什么错误？
  2. 默认 LinkedHashMap 使用什么 order？
  3. 应该如何创建 access-order LinkedHashMap？
  4. 修改后 get 会产生什么顺序影响？

7.5 综合训练

实现一个最多保存 5 条记录的 LRU 缓存。

要求：

  • 使用 LinkedHashMap；
  • access-order；
  • 最大容量 5；
  • get() 后更新最近访问顺序；
  • 插入第 6 条数据时淘汰最久未使用；
  • 打印每一步缓存顺序。

完成后回答：

  1. 为什么不能直接使用普通 HashMap？
  2. 为什么 insertion-order 不够？
  3. access-order 解决了什么？
  4. removeEldestEntry() 解决了什么？
  5. 这个实现为什么仍不等于完整生产缓存系统？

7.6 本章验收

  • [ ] 能画出 HashMap 与 LinkedHashMap 的继承关系。
  • [ ] 能画出“哈希表 + 双向链表”。
  • [ ] 能准确区分两套数据结构职责。
  • [ ] 能解释默认 insertion-order。
  • [ ] 能解释 access-order。
  • [ ] 能解释普通重复 put 为什么不移动位置。
  • [ ] 能解释 access-order 下 get 为什么移动 Entry。
  • [ ] 能解释 LRU。
  • [ ] 能从零写一个基础 LRU LinkedHashMap。
  • [ ] 能使用 JDK 21 firstEntry/lastEntry。
  • [ ] 能使用 putFirst/putLast/reversed。
  • [ ] 能正确选择 HashMap 或 LinkedHashMap。