Lesson 08 · 集合框架源码

HashSet 与 TreeSet 底层原理：Map 的「马甲」

中级·#集合·#源码

第 1 站

从一道高频面试题开始

面试中被问到 Set 集合，很多人的回答只停留在"不允许重复"。但面试官想听的是——你知道 HashSet 底层用的是什么吗？

面试官问："HashSet 和 TreeSet 底层分别是什么数据结构？两者的本质区别是什么？"

如果你只能回答"一个用 HashMap，一个用 TreeMap"，那你只说对了结论，还没展示出理解深度。面试官真正想听到的是：委托模式——Set 的所有操作如何转发给 Map，以及这种设计背后的工程思想。

本篇文章的核心观点只有一句话：Set 就是 Map 的马甲。理解了这个委托模式，一个知识点就能覆盖 HashSet、TreeSet、LinkedHashSet 三个类。我们从源码出发，逐层拆解。

第 2 站

Set 接口与委托模式

Set 接口继承自 Collection，定义了"不允许重复元素"的契约。但 Set 本身只是一个接口规范，它的三个主要实现类——HashSet、LinkedHashSet、TreeSet——全部通过委托一个 Map 来完成工作。

以 HashSet 为例，打开源码你会看到两个关键成员：

HashSet.java · JDK 核心字段

// 底层存储：所有元素都作为 key 存入这个 HashMap
private transient HashMap<E, Object> map;

// 占位 value —— 所有 entry 共享同一个对象引用
private static final Object PRESENT = new Object();

元素作为 HashMap 的 key 存储，value 统一指向一个静态常量 PRESENT。这就是委托模式的精髓：Set 不自己实现存储逻辑，而是把一切交给 Map。

图 1委托模式：HashSet 将所有操作转发给内部的 HashMap，元素作为 key，PRESENT 作为占位 value

为什么 value 要用固定的 PRESENT 对象？

HashSet 只关心"元素是否存在"，不需要存 value。如果 value 设为 null，add() 中 map.put(e, PRESENT) == null 的判断就会失效——无法区分"key 不存在"和"value 本身就是 null"。用静态 final 对象引用既省内存（所有 entry 共享），又保证逻辑正确。

第 3 站

HashSet 源码解读：四行代码看透本质

HashSet 整个类不到 300 行，核心方法各只有一行——全部委托给 HashMap：

HashSet.java · 核心方法实现

// add：元素作为 key，PRESENT 作为 value
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// remove：直接调用 HashMap 的 remove
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

// contains：直接调用 HashMap 的 containsKey
public boolean contains(Object o) {
    return map.containsKey(o);
}

// size：直接返回 HashMap 的 size
public int size() {
    return map.size();
}

核心等式：HashSet.add(e) = HashMap.put(e, PRESENT)
去重原理：put 返回 null 说明 key 不存在（新增成功），返回旧 value 说明 key 已存在（add 返回 false）

关键洞察：你对 HashMap 了解的一切，直接适用于 HashSet。

HashMap 的哈希冲突解决（链表 + 红黑树）→ HashSet 的去重性能保证
HashMap 的扩容机制（2 倍扩容，load factor 0.75）→ HashSet 的扩容行为
HashMap 要求 key 重写 equals() + hashCode() → HashSet 要求元素重写这两个方法
HashMap 允许 1 个 null key → HashSet 允许 1 个 null 元素

面试加分回答模板：
"HashSet 底层委托 HashMap，元素作为 key 存入，value 使用静态常量 PRESENT 占位。因此 HashMap 的哈希表结构、扩容策略、冲突处理机制，全部直接决定了 HashSet 的行为。"

一句话把 Set 和 Map 串联起来，展示的不是死记硬背，而是体系化理解。

第 4 站

TreeSet 与 TreeMap：红黑树上的有序集合

TreeSet 同样采用委托模式，但底层 Map 换成了 NavigableMap（通常是 TreeMap）。TreeMap 基于红黑树实现，保证每次插入、删除、查找的时间复杂度为 O(log n)。

TreeSet.java · JDK 核心字段与方法

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, Serializable {

    // 底层存储：NavigableMap（通常是 TreeMap）
    private transient NavigableMap<E, Object> m;

    // 占位 value（同 HashSet 的 PRESENT）
    private static final Object PRESENT = new Object();

    // 默认构造：自然排序 → 元素必须实现 Comparable
    public TreeSet() { this(new TreeMap<>()); }

    // 自定义比较器
    public TreeSet(Comparator<? super E> comp) {
        this(new TreeMap<>(comp));
    }

    // 核心方法同样委托
    public boolean add(E e)    { return m.put(e, PRESENT) == null; }
    public boolean remove(Object o) { return m.remove(o) == PRESENT; }

    // TreeSet 独有的有序操作（TreeSet 有而 HashSet 没有）
    public E first()   { return m.firstKey(); }
    public E last()    { return m.lastKey(); }
    public E lower(E e)    { return m.lowerKey(e); }    // < e 的最大元素
    public E higher(E e)   { return m.higherKey(e); }   // > e 的最小元素
    public E ceiling(E e)  { return m.ceilingKey(e); }  // >= e 的最小元素
    public E floor(E e)    { return m.floorKey(e); }    // <= e 的最大元素
}

元素在红黑树中按 Comparable.compareTo() 或 Comparator.compare() 进行比较定位，中序遍历即为升序序列。

为什么 TreeSet 不允许插入 null？

TreeSet 需要对元素进行比较排序。插入 null 时会调用 null.compareTo(...) 或 comparator.compare(null, ...)，直接抛出 NullPointerException。而 HashSet 只依赖 hashCode() 和 equals()，null 的 hashCode 被特殊处理为 0，所以允许一个 null。

第 5 站

对比总结表：一张表覆盖三个 Set

掌握了委托模式后，三个 Set 实现类的区别就转化为三个 Map 的区别：

特性	HashSet	LinkedHashSet	TreeSet
底层 Map	HashMap	LinkedHashMap	TreeMap
元素顺序	无序	插入顺序	自然排序 / Comparator
add / remove / contains	O(1) 平均	O(1) 平均	O(log n)
是否允许 null	允许 1 个	允许 1 个	不允许（NPE）
Comparable 要求	不需要	不需要	必须实现
内存开销	较小	中等（多链表）	较大（每节点约 48B）
独有方法	无	无	first/last/lower/higher/ceiling/floor/subSet

图 2Set 家族继承树：每个 Set 实现类都委托给对应的 Map 实现

第 6 站

实战使用场景

场景一：去重 —— HashSet

UserService.java · 用户 ID 去重

// 收集所有不重复的用户 ID
Set<Long> uniqueUserIds = new HashSet<>();
for (Order order : orderList) {
    uniqueUserIds.add(order.getUserId());
}
// O(1) 插入 + 自动去重，最适合海量数据的去重场景

场景二：有序去重 —— TreeSet

Leaderboard.java · 排行榜

// 排行榜：自动排序 + 去重，支持范围查询
TreeSet<Player> leaderboard = new TreeSet<>(
    Comparator.comparingInt(Player::getScore).reversed()
);
leaderboard.add(new Player("Alice", 2800));
leaderboard.add(new Player("Bob", 3200));
leaderboard.add(new Player("Carol", 2800));

Player top = leaderboard.first();  // 最高分
SortedSet<Player> top3 = leaderboard.headSet(leaderboard.toArray(new Player[0])[2], true);

场景三：保持插入顺序 —— LinkedHashSet

TagService.java · 有序标签

// 文章标签：去重且保持添加顺序
Set<String> tags = new LinkedHashSet<>();
tags.add("Java");
tags.add("集合框架");
tags.add("面试");
tags.add("Java");  // 重复，忽略
// 遍历顺序：Java → 集合框架 → 面试（保持插入顺序）

选型口诀

只要去重 → HashSet（最快，O(1)）
去重 + 排序 → TreeSet（O(log n)，支持范围查询）
去重 + 保持插入顺序 → LinkedHashSet（O(1)，LRU 缓存的基础）

第 7 站

总结：从 Set 讲到 Map 底层

记住 Set 是 Map 的马甲，面试时从 Set 讲到 Map 底层，展示你的知识深度：

核心观点：Set 接口本身不实现存储，三个实现类全部通过委托 Map 完成工作。理解了这个模式，一个知识点覆盖整个 Set 家族。

HashSet → 内部持有 HashMap<E, Object>，元素作 key，PRESENT 作 value。add/remove/contains 各只一行代码，全部委托 HashMap。O(1) 性能，无序。

TreeSet → 内部持有 NavigableMap<E, Object>（通常是 TreeMap），红黑树保证 O(log n)，元素自动有序。额外提供 first/last/lower/higher/ceiling/floor 等导航方法。不允许 null。

LinkedHashSet → 继承 HashSet，构造时用 LinkedHashMap，通过双向链表保持插入顺序。

面试加分点：不要只说"HashSet 用 HashMap"，要讲清楚委托模式——元素作为 key、PRESENT 作为占位 value、add 返回 put 的结果判 null。从 Set 出发自然串联到 Map 的哈希表、红黑树、扩容等底层知识，展示体系化理解。