HashSet、LinkedHashSet、TreeSet 有什么区别？分别怎么选？

简化版

三者都不允许重复元素，区别在底层结构和顺序：HashSet 底层是 HashMap，无序，增删查 O(1)，最常用；LinkedHashSet 是 HashSet + 一条双向链表，保持插入顺序，性能几乎不变；TreeSet 底层是 TreeMap（红黑树），按元素排序，增删查 O(log n)，能做范围查询。选择口诀：不在乎顺序用 HashSet，要插入顺序用 LinkedHashSet，要排序/范围查询用 TreeSet。

详细版

三者都实现 Set 接口（去重），但底层各托一个 Map：

维度	HashSet	LinkedHashSet	TreeSet
底层	HashMap	LinkedHashMap	TreeMap（红黑树）
顺序	无序	插入顺序	排序（自然序或 Comparator）
增删查	O(1)	O(1)	O(log n)
null 元素	允许一个	允许一个	不允许
去重依据	hashCode + equals	hashCode + equals	compareTo/compare
额外能力	无	保持插入顺序	first/last/floor/ceiling/subSet

Set<String> hash = new HashSet<>();        // 无序：遍历顺序不确定
Set<String> linked = new LinkedHashSet<>(); // 插入顺序：加入什么顺序，遍历就什么顺序
Set<String> tree = new TreeSet<>();         // 排序：遍历时按字典序

for (String s : List.of("banana", "apple", "cherry")) {
    hash.add(s); linked.add(s); tree.add(s);
}
// hash:   顺序不定，如 banana, cherry, apple
// linked: banana, apple, cherry      （插入顺序）
// tree:   apple, banana, cherry      （排序）

⚠️ 三个 Set 本质是「只用 key 的 Map」：Set 的元素就是 Map 的 key，value 填一个固定占位对象。所以它们的顺序、复杂度、去重规则，全部继承自对应的 Map。

完整版教学

一、核心认知：Set 都是「阉割版 Map」

理解这三个 Set 只需一句话：它们内部各自 new 了一个对应的 Map，把元素当 key 存进去，value 用同一个占位对象。

HashSet       → 内部 HashMap<E, Object>       元素当 key
LinkedHashSet → 内部 LinkedHashMap<E, Object>
TreeSet       → 内部 TreeMap<E, Object>
add(e)  → map.put(e, PRESENT)   // PRESENT 是一个 static final Object
contains(e) → map.containsKey(e)

Map 的 key 天然不重复，正好就是 Set「去重」的能力来源。所以 Set 三兄弟的所有差异（顺序、复杂度、null、去重依据），都是它们背后 HashMap / LinkedHashMap / TreeMap 差异的直接投影。记住这点，就不用单独背 Set，全从 Map 推导。

二、HashSet：无序但最快

HashSet 背后是 HashMap，元素放在哈希桶里，位置由 hash & (n-1) 决定，跟插入先后无关，所以无序——而且扩容 rehash 后顺序还会变。好处是增删查都是平均 O(1)，是三者里最快、最省的，也是 90% 场景的默认选择。

去重依据是 hashCode + equals：先用 hashCode 定位桶，同桶内再用 equals 精判。所以放进 HashSet 的自定义对象必须正确重写 hashCode 和 equals，否则两个「逻辑相等」的对象会被当成不同元素，去重失效。

class Point { int x, y; }  // 没重写 hashCode/equals
Set<Point> set = new HashSet<>();
set.add(new Point());
set.add(new Point());
set.size();  // 2 ！两个逻辑相同的点没被去重，因为默认按对象地址判等

三、LinkedHashSet：插入顺序的秘密

LinkedHashSet 继承 HashSet，底层换成 LinkedHashMap——在哈希桶之外，额外用一条双向链表把所有元素按插入顺序串起来。哈希桶负责 O(1) 定位，链表负责记住顺序，遍历时走链表，于是既有 O(1) 性能又能保持插入顺序。

HashSet 的桶（无序）：       LinkedHashSet 额外的顺序链：
桶0: C                       head → A → B → C → D → tail
桶1: A                       （按加入先后串联，遍历走这条链）
桶2: D → B

代价只是每个节点多两个指针（before/after）和一点内存，时间复杂度仍是 O(1)。需要「去重 + 保持加入顺序」时它最合适，比如做有序去重、缓存最近访问列表。它不排序，只忠实记录你加入的先后。

四、TreeSet：有序与导航查询

TreeSet 背后是 TreeMap（红黑树），元素按排序组织，中序遍历即升序。代价是增删查都要沿树下行，O(log n)，比 HashSet 慢。但它换来了 HashSet 给不了的能力——范围查询和最接近查询：

TreeSet: [10, 20, 30, 40, 50]
first()      → 10        last()       → 50
floor(35)    → 30        ceiling(35)  → 40    （≤35 最大 / ≥35 最小）
lower(30)    → 20        higher(30)   → 40    （严格小于 / 大于）
headSet(30)  → [10,20]   subSet(20,40)→ [20,30]

去重依据是 compareTo/compare 返回 0（不看 equals！），元素必须可比较（实现 Comparable 或传 Comparator），且不允许 null（没法和别的元素比较大小）。这跟 HashSet 用 hashCode/equals 判重是本质区别——若 Comparator 写得让两个不同元素 compare 返回 0，它们会被当成重复而丢一个。

五、三者复杂度与顺序对照

操作	HashSet	LinkedHashSet	TreeSet
add/remove/contains	O(1)	O(1)	O(log n)
遍历顺序	不确定	插入顺序	排序
找最小/最大	O(n)（要扫全部）	O(n)	O(log n)（first/last）
范围查询	不支持	不支持	O(log n)
内存开销	最小	中（多一条链表）	较大（红黑树节点）

一个数字直觉：往三者各放 100 万个元素并做 100 万次 contains，HashSet 最快，LinkedHashSet 略慢（多维护链表），TreeSet 明显慢（每次 log n 次比较）。所以不需要顺序就别用 TreeSet，log n 的常数在大数据量下拖累明显。

六、选型决策与常见搭配

需要去重吗？──否──▶ 用 List
   │是
是否需要顺序？
   ├─ 不在乎顺序 ──────────▶ HashSet（默认，最快）
   ├─ 要「加入的先后」顺序 ──▶ LinkedHashSet
   └─ 要「排序 / 范围查询」──▶ TreeSet

实战：给列表去重又想保持原顺序，用 new LinkedHashSet<>(list)；要去重后排序，用 new TreeSet<>(list)；只是判断「有没有见过」，HashSet 足矣。

记忆钩子：「Hash 无序最快、Linked 记住插入顺序、Tree 帮你排序」——一个背后 HashMap、一个 LinkedHashMap、一个 TreeMap，Set 只是它们的 keySet。

七、常见误区与追问

误区：HashSet 的元素有固定顺序。 完全无序，且扩容后顺序还会变；要顺序请用 LinkedHashSet 或 TreeSet。
误区：TreeSet 判重用 equals。 用的是 compareTo/compare 返回 0；Comparator 写不好会把不同元素误判为重复而丢数据。
误区：三个 Set 都能存 null。 HashSet、LinkedHashSet 允许一个 null；TreeSet 不允许（null 无法比较大小，抛 NPE）。
误区：LinkedHashSet 是排序的。 它是插入顺序，不是排序；排序只有 TreeSet。
追问：往 HashSet 放自定义对象要注意什么？ 必须正确重写 hashCode 和 equals，且保持一致，否则去重失效；用不可变对象当元素更安全。
追问：TreeSet 的元素没实现 Comparable 会怎样？ 若也没传 Comparator，add 时抛 ClassCastException；需让元素实现 Comparable 或构造时传 Comparator。
追问：如何给 List 去重并保持原顺序？ new ArrayList<>(new LinkedHashSet<>(list))；用 HashSet 会打乱顺序，用 TreeSet 会变成排序。

八、加强记忆

把 Set 三兄弟记成「三个只留 key 的 Map」：HashSet 托 HashMap，哈希桶定位、无序、增删查 O(1)、按 hashCode+equals 去重，是默认首选；LinkedHashSet 托 LinkedHashMap，在桶之外多挂一条双向链表记录插入先后，于是「去重 + 保持加入顺序」且性能几乎不变；TreeSet 托 TreeMap 红黑树，按大小排序、O(log n)、按 compare 去重且不容 null，唯一能做 first/last/floor/ceiling/subSet 等范围与最接近查询。选型就一句「不在乎顺序 HashSet、要插入顺序 LinkedHashSet、要排序或范围 TreeSet」；所有细节都从背后的 Map 推导，不用死记。

简化版

详细版