Set与Map实现类对比#
一句话答案#
Set 本质是只用 key 的 Map：
HashSet底层是HashMap（无序、O(1)）、LinkedHashSet加双向链表（保插入序）、TreeSet底层是TreeMap（红黑树排序、O(logn)）。Map 三兄弟同理：HashMap 无序、LinkedHashMap 保序（可做 LRU）、TreeMap 红黑树有序。
核心要点
一、HashSet 的本质：就是一个 HashMap
public boolean add(E e) {
return map.put(e, PRESENT) == null; // value 是固定的占位 Object PRESENT
}- 元素存为 HashMap 的 key，value 是同一个占位对象
PRESENT。 - 去重依赖
hashCode()+equals()，所以自定义对象入 Set 必须重写这两个方法。
二、Set 三实现对比
| 实现 | 底层 | 顺序 | 时间复杂度 | 排序依赖 |
|---|---|---|---|---|
| HashSet | HashMap | 无序 | O(1) | hashCode+equals |
| LinkedHashSet | LinkedHashMap | 插入顺序 | O(1) | hashCode+equals |
| TreeSet | TreeMap | 排序 | O(logn) | Comparable/Comparator |
三、Map 三实现对比
| 实现 | 底层结构 | 顺序 | 性能 | null key |
|---|---|---|---|---|
| HashMap | 数组+链表+红黑树 | 无序 | O(1) | 允许 1 个 |
| LinkedHashMap | HashMap + 双向链表 | 插入序 / 访问序 | O(1) | 允许 |
| TreeMap | 红黑树 | key 排序 | O(logn) | 不允许(需比较) |
四、LinkedHashMap 与 LRU
- 维护一条贯穿所有 entry 的双向链表记录顺序。
- 构造参数
accessOrder=true时按访问顺序排列（最近访问的移到尾部）。 - 重写
removeEldestEntry即可实现 LRU 缓存：
new LinkedHashMap<>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry e) { return size() > CAP; }
};五、TreeMap 要点
- 基于红黑树，key 必须可比较（实现 Comparable 或传 Comparator）。
- 支持范围查询：
firstKey/lastKey/floorKey/ceilingKey/subMap/headMap/tailMap。 - key 为 null 会抛 NPE（除非自定义 Comparator 允许）。
面试回答（2分钟版）
Set 和 Map 的实现类是一一对应的，因为 Set 本质上就是只用 key 不用 value 的 Map。HashSet 底层直接就是一个 HashMap，add 元素其实是把元素当 key 放进去，value 是一个固定的占位对象 PRESENT，所以 HashSet 去重完全依赖 hashCode 和 equals，自定义对象放进 Set 一定要重写这两个方法。三种 Set：HashSet 无序、查询 O(1)；LinkedHashSet 底层是 LinkedHashMap，用一条双向链表维护插入顺序；TreeSet 底层是 TreeMap，基于红黑树排序，操作 O(logn)，元素必须可比较。Map 也是对应的三兄弟：HashMap 是数组加链表加红黑树、无序、允许一个 null key；LinkedHashMap 在 HashMap 基础上加双向链表，默认保持插入顺序，如果构造时把 accessOrder 设成 true 就变成访问顺序，再重写 removeEldestEntry 就能实现 LRU 缓存，这是面试常考点；TreeMap 基于红黑树，key 有序，支持 floorKey、ceilingKey、subMap 这些范围查询，但 key 不能为 null 因为要比较。选型上：要快用 Hash 系，要保顺序用 Linked 系，要排序或范围查询用 Tree 系。
追问与易错
追问方向：
- “HashSet 怎么保证元素不重复？”→ 底层 HashMap put，依赖 key 的 hashCode 定位桶 + equals 比较，相同则不插入
- “怎么用 LinkedHashMap 实现 LRU？”→ 构造时 accessOrder=true 按访问顺序，重写 removeEldestEntry 返回 size>容量 时自动淘汰最久未访问的头节点
- “TreeMap 的 key 能为 null 吗？”→ 默认不能，插入时要调 compareTo 会 NPE；自定义 Comparator 处理 null 才行
- “TreeSet 自定义对象排序怎么做？”→ 对象实现 Comparable，或构造 TreeSet 时传入 Comparator
- “LinkedHashMap 比 HashMap 多了什么开销？”→ 每个节点多两个指针维护双向链表，内存略高，但迭代顺序可预测
易错点：
- ❌ “HashSet 和 HashMap 没关系”——HashSet 内部就是 HashMap
- ❌ “TreeSet 去重靠 equals”——靠比较器返回 0（见 Comparable与Comparator）
- ❌ “LinkedHashMap 只能插入序”——accessOrder=true 可切访问序，这是 LRU 基础