本教程共 100 篇 · 第 79 篇 · 更新于 2026-08-05 · 约 5 分钟阅读

79. LinkedHashMap、TreeMap 与 Hashtable

本节目标：认清 LinkedHashMap 保序并能做缓存、TreeMap 按键排序，同时把 Hashtable 列为历史兼容类，学完知道这三个 Map 实现各自该不该用。

LinkedHashMap：记住顺序的 HashMap

LinkedHashMap 在 HashMap 基础上加了一条链表，所以遍历时按「插入顺序」来，而不是像 HashMap 那样乱序。

Map<String, Integer> m = new LinkedHashMap<>();
m.put("甲", 1);
m.put("乙", 2);
m.put("丙", 3);
System.out.println(m); // {甲=1, 乙=2, 丙=3}，顺序稳定
```bash

它还有个 HashMap 没有的本事：可以改成「按访问顺序」排列。你查一下某个键，它就被挪到末尾。这个特性天生适合做 LRU 缓存（最近用过的放后面，最久不用的在前面）。

```java
// 第三个参数 true 表示按访问顺序，而不是插入顺序
LinkedHashMap<String, String> cache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 3; // 超过 3 个就淘汰最久没用过的
    }
};

Note

上面这种写法用了「匿名子类 + 重写 removeEldestEntry」，属于进阶技巧。初学只要知道 LinkedHashMap 能做缓存、能保序即可，真要写缓存库还有更专业的轮子。

TreeMap：按键自动排序

TreeMap 和 TreeSet 是亲兄弟，底层都是红黑树。它按键排序，而不是按插入顺序，而且要求键「可比较」（实现 Comparable 或构造时传 Comparator）。

Map<String, Integer> m = new TreeMap<>();
m.put("banana", 3);
m.put("apple", 1);
m.put("cherry", 2);
System.out.println(m); // {apple=1, banana=3, cherry=2}，按键字典序排好
```bash

因为内部有序，TreeMap 也能做 `firstKey`、`lastKey`、`subMap` 这类范围操作，适合「要按 key 顺序遍历」或「取某一段 key」的场景。代价和 TreeSet 一样：比 HashMap 慢一点，且键不能为 null。

> [!WARNING]
> 把没实现 Comparable、又没传 Comparator 的对象当 TreeMap 的键，会抛 `ClassCastException`。另外 TreeMap 的键不允许 null，而 HashMap 允许一个 null 键——这就是两者行为不一致的地方。

## Hashtable：又一个古董

`Hashtable` 和 `Vector` 一样，是 Java 1.0 的遗产，方法全加了同步锁，设计也过时。它的坑还在于：不允许 null 键、null 值，一旦传入就抛异常。

```java
// 历史兼容写法，新代码不要这么写
Hashtable<String, Integer> t = new Hashtable<>(); // 慢，且不能放 null

Warning

别用 Hashtable。单线程下用 HashMap（更快、还能放一个 null 键）；多线程下用 ConcurrentHashMap（真正为并发优化的实现，而不是给每个方法都上锁）。Hashtable 两头不讨好，纯粹是历史包袱。

三个 Map 怎么选

HashMap：只要键值存取、不在乎顺序，默认首选，性能最好。
LinkedHashMap：要保插入顺序，或想顺手做个简易 LRU 缓存。
TreeMap：要按键自动排序、或做 key 的范围查询，键必须可比。
Hashtable：历史兼容，新代码禁用。

Tip

选型逻辑和 Set 完全平行：HashMap 对应 HashSet，TreeMap 对应 TreeSet，LinkedHashMap 对应 LinkedHashSet。记住 Set 那一套，Map 这套照着套就行。

一个容易混的点：顺序是谁的顺序

有人搞不清 LinkedHashMap 和 TreeMap 的区别：LinkedHashMap 保的是「你放进去的先后」，TreeMap 保的是「键排好序的大小」。一个是时间顺序，一个是逻辑顺序，两码事。需要哪个就选哪个，别混。

LinkedHashMap 的访问顺序怎么玩

前面说 LinkedHashMap 能按访问顺序排。默认是插入顺序（accessOrder=false）；构造时传 true 变成访问顺序：你 get/put 某个键，它就跑到末尾。

LinkedHashMap<String, Integer> m = new LinkedHashMap<>(16, 0.75f, true);
m.put("a", 1);
m.put("b", 2);
m.get("a"); // 访问 a，a 被挪到末尾
System.out.println(m.keySet()); // [b, a]，a 因为被访问跑到后面
```bash

最久没被碰的键永远在队首，配合 `removeEldestEntry` 淘汰它，就是经典 LRU 缓存。虽然手写缓存不如专业库，但理解这个机制能帮你读懂很多框架源码。

## TreeMap 能做的范围操作

和 TreeSet 类似，TreeMap 因为按键有序，能做 `firstKey`/`lastKey`/`subMap`/`headMap`/`tailMap`。比如想取「键在 a 到 m 之间」的所有条目，`subMap("a", "n")` 一步到位。这是 HashMap 给不了的能力。

```java
TreeMap<String, Integer> tm = new TreeMap<>();
tm.put("apple", 1); tm.put("banana", 2); tm.put("cherry", 3);
System.out.println(tm.subMap("b", "d")); // {banana=2, cherry=3}

Note

subMap(from, to) 是左闭右开：from 含、to 不含。想含右端点，用 subMap(from, true, to, true) 显式指定开闭。

三者底层一句话

HashMap 是哈希表（数组 + 链表/红黑树），LinkedHashMap 是哈希表加双向链表，TreeMap 是红黑树。记住这个，性能特征（谁快谁慢、谁有序）就都能推出来，不用死背。日常默认 HashMap，要保序或排序再换。

三者选型再强调一遍

怕你记混，再用一句人话总结：HashMap 是「快但不讲顺序」的默认值；LinkedHashMap 是「快 + 记得你放的顺序」，偶尔还能当缓存；TreeMap 是「慢一点但永远按键排好序」。Hashtable 直接划掉，别碰。

对应到 Set：HashMap→HashSet，LinkedHashMap→LinkedHashSet，TreeMap→TreeSet。Map 和 Set 的底层实现是同一套哈希/红黑树逻辑，学通一边，另一边自动会。

TreeMap 的键比较与 null

TreeMap 的键必须可比，且不允许 null 键。如果你用自定义类当键又没保证可比，构造时不报错，但第一次 put 就抛 ClassCastException。另外，传给 TreeMap 的 Comparator 必须对所有键自洽，否则排序和查找都会出错，这个问题排查起来很费劲，写 Comparator 时多用 Integer.compare 这种稳妥写法，别手写相减。

小提醒：访问顺序的代价

LinkedHashMap 的访问顺序很好用，但每次 get/put 都要维护链表指针，比纯 HashMap 多一点点开销。做高频读写、且不需要顺序时，还是用 HashMap 更划算。缓存场景才值得为顺序买单，除非明确要做 LRU 或顺序敏感的展示，否则别为用而用，徒增一点点开销。

Hashtable 和 HashMap 的细节对照

除了线程安全和对 null 的态度，两者方法名也几乎一致（Hashtable 是老式命名如 elements()）。现代代码一律 HashMap：更快、能放一个 null 键、API 更现代。Hashtable 仅出现在历史代码和面试「过时考点」里，新项目别碰。

小结

LinkedHashMap 保插入顺序、还能按访问顺序做缓存；TreeMap 按键排序、要求键可比；Hashtable 是过时的古董，用 HashMap 或 ConcurrentHashMap 替代。下一章看专门操作集合的 Collections 工具类。