面试官问："HashSet 底层是怎么实现的？"
候选人小项答："HashSet 底层用的是 HashMap。"
面试官追问："具体是怎么用 HashMap 实现的？"
小项说不上来。
【面试官心理】 HashSet 依赖 HashMap 实现是 Java 集合框架的经典设计。能说出 HashSet 用 HashMap 存储元素作为 key、固定 value 作为占位符的候选人，说明对 JDK 源码有过研究。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
// HashSet 内部持有一个 HashMap
private transient HashMap<E, Object> map;
// HashMap 的 value 固定为一个占位符
private static final Object PRESENT = new Object();
// 构造函数
public HashSet() {
map = new HashMap<>();
}
// add 方法
public boolean add(E e) {
return map.put(e, PRESENT) == null; // 添加成功返回 true
}
// 其他方法都是委托给 map
}// HashSet 只关心 key（元素本身）
// value 没有实际用途，只需要一个占位符
private static final Object PRESENT = new Object();
// add 操作：
// map.put(e, PRESENT) → 如果 key 已存在，返回旧 value（PRESENT）
// add 返回 map.put() == null → 已存在返回 false
// remove 操作：
// map.remove(e) → 返回 PRESENT 表示删除成功
// 因为 key 是元素，value 总是 PRESENT| 维度 | HashSet | HashMap |
|---|---|---|
| 存储内容 | 单个元素 | 键值对 |
| 内部结构 | HashMap（键=元素，值=占位符） | 哈希桶数组 |
| 唯一性保证 | 元素的 hashCode 和 equals | Key 的 hashCode 和 equals |
| null 支持 | 可以有一个 null 元素 | key 可以有一个 null，value 可以有多个 null |
| 添加方法 | add(E e) | put(K k, V v) |
| 取出方法 | 不能直接取出，只能遍历 | get(K k) |
| 时间复杂度 | O(1) 均摊（和 HashMap 相同） | O(1) 均摊 |
// LinkedHashSet 同样依赖 LinkedHashMap
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E> {
public LinkedHashSet() {
super(16, 0.75f, true); // accessOrder = true
}
// 继承 HashSet 的 add 方法
// HashSet 构造函数传入 LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
}// 需要去重 + 不需要顺序 → HashSet（O(1)）
// 需要去重 + 需要插入顺序 → LinkedHashSet（O(1)）
Set<String> insertOrder = new LinkedHashSet<>();
// 需要去重 + 需要排序 → TreeSet（O(log n)）
Set<String> sorted = new TreeSet<>();
// 需要去重 + 多线程安全 → ConcurrentHashSet（JDK 8+）
// 或 Collections.newSetFromMap(new ConcurrentHashMap<>())
Set<String> concurrent = Collections.newSetFromMap(
new ConcurrentHashMap<>());面试官："HashSet 的 contains 操作时间复杂度是多少？"
// HashSet 的 contains 委托给 HashMap 的 containsKey
public boolean contains(Object o) {
return map.containsKey(o); // O(1) 均摊
}
// 流程：
// 1. 计算 hash = key.hashCode()
// 2. 定位桶：i = (n-1) & hash
// 3. 在桶内遍历链表/红黑树查找
// 4. 比较 equals
// 最坏情况：所有元素都在同一个桶 → O(n)
// 均摊情况：O(1)