java Set底层如何实现

在 Java 中，Set 是一个接口，本身没有“底层实现”，真正的实现是由不同的类来完成的。常见的 Set 实现有：

• HashSet
• LinkedHashSet
• TreeSet
• EnumSet（较少用）
• CopyOnWriteArraySet（并发）
• ConcurrentHashMap.newKeySet()（并发）

下面重点讲最常用的三种 Set 的底层实现原理。

一、HashSet（最常用）

底层结构

HashSet -> HashMap

HashSet 的底层其实就是 HashMap

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

原理

• HashSet 中的元素，作为 HashMap 的 key
• value 统一使用一个静态对象 PRESENT
• 利用 HashMap 的 key 不可重复 来保证 Set 元素唯一

添加元素流程

map.put(e, PRESENT)

• 如果 key 已存在 → 不覆盖（Set 不去重）
• 如果 key 不存在 → 插入成功

HashSet 的底层细节

• JDK 1.8 之前：数组 + 链表
• JDK 1.8 及以后：数组 + 链表 + 红黑树
• 默认初始容量：16
• 负载因子：0.75
• 链表长度 ≥ 8 且数组长度 ≥ 64 → 转红黑树

二、LinkedHashSet

底层结构

LinkedHashSet -> LinkedHashMap -> HashMap

特点

• 继承 HashSet
• 在 HashMap 基础上增加了 双向链表
• 保证 插入顺序

底层实现

• 使用 LinkedHashMap
• 每个节点同时存在于：
  • HashMap 的哈希桶中
  • 双向链表中（维护顺序）

✅ 所以：LinkedHashSet = HashSet + 维护顺序

三、TreeSet

底层结构

TreeSet -> TreeMap -> 红黑树（Red-Black Tree）

特点

• 元素 有序（自然顺序或自定义 Comparator）
• 底层是 自平衡二叉搜索树（红黑树）

添加流程

map.put(e, PRESENT)

• 根据 compareTo() 或 Comparator 比较
• 左小右大
• 自动平衡（旋转）

时间复杂度

• 插入 / 删除 / 查找：O(log n)

四、对比总结

五、线程安全问题

HashSet / TreeSet 都不是线程安全

线程安全方案

Set<String> set = Collections.synchronizedSet(new HashSet<>());

或

Set<String> set = ConcurrentHashMap.newKeySet();

六、一句话总结

Java 的 Set 基本都是“借壳”Map 实现的：

• HashSet → HashMap
• LinkedHashSet → LinkedHashMap
• TreeSet → TreeMap

如果你愿意，我也可以画一张 HashMap / HashSet 底层结构图 或结合 源码逐行讲解。