Java集合（二）：Set 与 Map 体系

星辰逐梦2026/5/5大约 4 分钟

Java集合（二）：Set 与 Map 体系

导语：本篇聚焦 Set 与 Map 两大体系：去重原理、底层实现、null 支持与选型取舍，共 12 题。

一、Set 体系

1. `Set` 是如何保证元素不可重复的？

答：依赖元素的 equals() 与 hashCode()。HashSet 先比 hashCode 定位桶，再 equals 比对；TreeSet 依赖 Comparable/Comparator 的 compareTo/compare 返回 0 判定重复。两个对象 equals 为 true 则必视为同一元素。

2. `HashSet` 的实现原理？为什么查询快？

答： HashSet 底层就是 HashMap——元素作为 HashMap 的 key，value 统一为一个静态常量 PRESENT。因此去重、查找都委托给 HashMap，时间复杂度接近 O(1)。

private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public boolean add(E e) { return map.put(e, PRESENT) == null; }

3. `HashSet` 如何检查重复？

答：加入元素时：

计算 hashCode() 得到桶位置；
若桶空，直接存入；
若桶非空，遍历桶内节点用 equals() 逐个比较：返回 true 则判定重复、不添加；false 则作为冲突节点挂在桶中（链表/树）。

这也说明：若两个对象 equals 为真但 hashCode 不同，会被放进不同桶，去重失效——故必须同时重写二者。

4. `LinkedHashSet` 与 `HashSet` 的区别？

答： LinkedHashSet 继承 HashSet，底层用 LinkedHashMap 实现，在哈希结构基础上维护一条双向链表记录插入顺序，遍历时按插入序输出。HashSet 遍历顺序不确定。LinkedHashSet 性能略低于 HashSet（多维护链表指针）。

答： TreeSet 底层是 TreeMap（同样以元素为 key、PRESENT 为 value），基于红黑树实现，元素按排序规则有序（自然排序 Comparable 或定制 Comparator）。要求元素必须实现 Comparable 或在构造时传入 Comparator，否则运行时抛 ClassCastException。增删查复杂度 O(log n)，比 HashSet 慢，但能有序遍历。

6. `TreeSet` 和 `TreeMap` 的关系是什么？

答： TreeSet 内部直接持有一个 NavigableMap（实际就是 TreeMap）成员变量，所有 add/remove/contains 操作都委托给该 TreeMap，只是 value 固定为 PRESENT。即 TreeSet ≈ TreeMap 的 key 集合。

二、Map 体系

7. `HashMap`、`Hashtable`、`TreeMap`、`LinkedHashMap` 各自特点？

答：

实现	底层	线程安全	允许 null	顺序
`HashMap`	数组+链表+红黑树	否	key/value 均可 null	无序
`Hashtable`	数组+链表	是（方法 `synchronized`）	都不行	无序
`TreeMap`	红黑树	否	key 不可 null，value 可	按 key 排序
`LinkedHashMap`	`HashMap`+双向链表	否	key/value 均可 null	插入序（或访问序）

重要：ConcurrentHashMap 的 key 和 value 都不允许为 null（存 null 会抛 NPE），这与 HashMap 不同，常被考到。

8. `HashMap` 和 `Hashtable` 的区别？

答：

父类不同：HashMap 继承 AbstractMap；Hashtable 继承遗留类 Dictionary。
线程安全：Hashtable 方法级 synchronized（整个表加锁，低效）；HashMap 不安全。
null 支持：Hashtable key/value 都不允许 null；HashMap 允许。
初始容量与扩容：Hashtable 默认 11，扩容 old*2+1；HashMap 默认 16，扩容 2 倍（且容量始终为 2 的幂）。
迭代器：Hashtable 用 Enumeration（fail-safe 风格）；HashMap 用 Iterator（fail-fast）。
现状：Hashtable 已被标记为遗留类，官方建议用 HashMap（单线程）或 ConcurrentHashMap（并发）替代。

9. `HashMap` 与 `TreeMap` 如何选择？

答：需要快速插入/删除/定位用 HashMap（O(1)）；需要按 key 有序遍历用 TreeMap（O(log n)）。若数据已用 HashMap 且只需偶尔排序，可转 TreeMap 排序后再遍历。

10. `LinkedHashMap` 了解吗？如何实现 LRU 缓存？

答： LinkedHashMap 继承 HashMap，额外用双向链表维护顺序，构造参数 accessOrder=true 时按访问顺序排列（get/put 会把节点移到链表尾）。重写 removeEldestEntry 可在容量超限时移除最久未访问节点，从而轻松实现 LRU 缓存：

class LRUCache<K,V> extends LinkedHashMap<K,V> {
    private final int cap;
    public LRUCache(int cap){ super(cap, 0.75f, true); this.cap = cap; }
    @Override protected boolean removeEldestEntry(Map.Entry<K,V> e){ return size() > cap; }
}

11. `HashMap` 能用任何类作为 key 吗？为什么 `String`/`Integer` 适合做 key？

答：理论上可以，但作为 key 的类应满足：

不可变（或至少作为 key 期间不修改参与 hashCode/equals 的字段），否则哈希定位会失效；
正确重写 hashCode() 与 equals()。

String/Integer 是 final、不可变、且重写了 hashCode/equals 并缓存哈希值，因此是理想的 key。若用自定义对象做 key，务必重写这两个方法并保证不可变。

12. `HashMap` 为什么不直接用 `hashCode()` 的值作数组下标？

答： hashCode() 返回 int（范围约 ±21 亿），不能直接作为数组下标（会越界）。需将其映射到 [0, n-1] 范围内。HashMap 做法：先对 hashCode 做扰动（h ^ (h >>> 16)，混合高 16 位降低碰撞），再用 (n - 1) & hash 取模（n 为 2 的幂，等价于取低位）。