Set 与 Map 家族：去重、保序与排序
更新时间：2026-09-20。List 解决「有序可重复」，Map 解决「键值映射」，Set 解决「去重」。本篇在 HashMap 底层原理 与 ArrayList/LinkedList 之上，讲清三大变体的顺序语义。
一、Map 三兄弟
| 实现 | 底层 | 键顺序 | 平均复杂度 | null 键 | 典型场景 |
|---|---|---|---|---|---|
HashMap | 数组+链表/红黑树 | 不保证 | get/put O(1) | 允许 1 个 | 绝大多数查找场景 |
LinkedHashMap | HashMap + 双向链表 | 插入顺序（或访问顺序） | O(1) | 允许 | 保序遍历、LRU |
TreeMap | 红黑树 | 按 key 排序 | get/put O(log n) | 键不能 null | 范围查询、有序键 |
java
Map<String,Integer> hm = new HashMap<>(); // 遍历顺序随哈希，别依赖
Map<String,Integer> lm = new LinkedHashMap<>(); // 按 put 顺序遍历
lm.put("b",2); lm.put("a",1); lm.put("c",3);
lm.forEach((k,v)-> System.out.println(k)); // b a c
// 访问顺序模式：最近访问的排到尾部，天然 LU 缓存骨架
Map<Integer,String> lru = new LinkedHashMap<>(16, 0.75f, true);
Map<String,Integer> tm = new TreeMap<>(); // 按 key 自然排序
tm.put("c",3); tm.put("a",1);
tm.firstKey(); tm.subMap("a","c"); // 有序才有范围操作
// 自定义排序：按字符串长度
Map<String,Integer> byLen = new TreeMap<>(Comparator.comparingInt(String::length));二、Set：底层就是 Map
HashSet 内部持有一个 HashMap，元素作为 map 的 key（value 是同一个固定 Object），所以「去重」完全由 key 的 hashCode/equals 决定：
| 实现 | 底层 | 顺序 |
|---|---|---|
HashSet | HashMap | 无序 |
LinkedHashSet | LinkedHashMap | 插入顺序 |
TreeSet | TreeMap（红黑树） | 自然顺序/Comparator |
java
Set<String> set = new HashSet<>(List.of("a","b","a")); // [a, b]，去重
set.contains("a"); // O(1)
三、去重的前提：hashCode 与 equals 契约
自定义对象放进 HashSet 或作 Map 键时，必须同时重写 equals 与 hashCode（用 IDE/record 生成）。契约：equals 相等的两个对象 hashCode 必须相等；否则逻辑相等的对象会被当成两个键，去重失效。重写后对象字段不可再变，否则在哈希桶里「找不回来」。
java
record Point(int x, int y) {} // record 自动生成 equals/hashCode/toString
Set<Point> ps = new HashSet<>();
ps.add(new Point(1,2));
ps.contains(new Point(1,2)); // true坑
- 依赖 HashMap 遍历顺序：扩容/树化会改变顺序，要稳定顺序用 LinkedHashMap。
- 可变对象做键：put 后修改参与 hashCode 的字段，get/remove 失效，键尽量用不可变类型（String、Integer、record）。
- TreeMap 键没实现 Comparable 又不给 Comparator：put 即抛 ClassCastException；比较器要满足与 equals 一致，否则 Set 去重会「误杀」。
- 以为 LinkedHashMap 一定 LRU：默认是插入顺序，构造第三参
accessOrder=true才是访问顺序；还要重写removeEldestEntry才会自动淘汰。 - 用 contains 在 List 上去重：List.contains 是 O(n)，大数据去重换 HashSet。
总结
Map/Set 家族按「顺序」选型：HashMap/HashSet 用哈希表换来 O(1) 但不保证顺序；LinkedHashMap/LinkedHashSet 额外挂双向链表保留插入（或 accessOrder 访问）顺序，是 LRU 缓存骨架；TreeMap/TreeSet 用红黑树让键有序、支持 O(log n) 的范围与首尾查询；Set 的去重本质是把元素当 Map 的 key，所以自定义对象务必成对重写 equals/hashCode 且保持不可变。 并发场景的选择见 ConcurrentHashMap。