集合面试题：高频问题与解答

Q1：ArrayList vs LinkedList？

操作	ArrayList	LinkedList
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)	O(1)
中间插入	O(n)	O(n)
CPU 缓存	友好	不友好

结论：大多数场景用 ArrayList；只有头插/头删极多时才考虑 LinkedList。

---

Q2：HashMap 底层实现？

JDK 1.7：数组 + 链表（头插法）
JDK 1.8+：数组 + 链表/红黑树（尾插法）

关键参数：

参数	值
默认容量	16
负载因子	0.75
链表转红黑树阈值	8
红黑树转链表阈值	6

为什么是 8 和 6？泊松分布：负载因子 0.75 时链表长度达到 8 的概率极低，设为阈值是防止哈希攻击。

---

Q3：HashMap put 流程？

put("hello", 1) 时：

1. 计算 hash = hash("hello")
2. 计算 index = hash & (capacity - 1)
3. bucket[index] 为空？→ 直接插入 Node
4. bucket[index] 不为空？
   - key 相同 → 替换旧值
   - 红黑树节点 → 插入树
   - 链表 → 遍历，找到相同 key 替换；否则尾插
5. 链表长度 ≥ 8 → 转红黑树
6. size > threshold → 扩容

---

Q4：HashMap vs ConcurrentHashMap？

特性	HashMap	ConcurrentHashMap
线程安全	❌	✅
null 支持	✅ key/value 都可 null	❌ 都不行
锁粒度	无锁	分段锁 / CAS（JDK 8+）
迭代安全	Fail-Fast	Fail-Safe

---

Q5：HashSet 底层实现？

HashSet = HashMap 的 key 集合，value 用一个固定对象 PRESENT 填充。

public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

所以 HashSet 的所有特性都继承自 HashMap。

---

Q6：fail-fast vs fail-safe？

机制	集合	特点
Fail-Fast	ArrayList、HashMap	遍历时修改 → 抛异常
Fail-Safe	CopyOnWriteArrayList、ConcurrentHashMap	遍历副本，不抛异常

Fail-Fast 的原理：每个集合维护 modCount，迭代器创建时记录 expectedModCount，每次 next() 检查是否一致。

---

Q7：HashMap 扩容机制？

容量翻倍：16 → 32 → 64 → 128...

新位置计算（高位分流）：
  hash & oldCap == 0 → 原位置不变
  hash & oldCap != 0 → 新位置 = 原位置 + oldCap

为什么高位分流更快？不需要重新计算所有元素的 hash，直接用 hash 的高位决定。

---

Q8：equals 和 hashCode 的契约？

相等的对象必须有相等的 hashCode。

class Student {
    String name;
    int age;

    // 必须同时重写
    @Override
    public boolean equals(Object o) { ... }
    @Override
    public int hashCode() { return Objects.hash(name, age); }
}

HashSet/HashMap 的判断逻辑：先比 hashCode，再比 equals。

---

Q9：如何实现线程安全？

场景	推荐
高并发 Map	ConcurrentHashMap
高并发 List	ConcurrentLinkedQueue
读多写少 List	CopyOnWriteArrayList
偶尔并发	Collections.synchronizedList
生产者-消费者	BlockingQueue

---

Q10：TreeMap vs HashMap？

特性	TreeMap	HashMap
有序性	✅ 按 key 排序	❌ 无序
查找速度	O(log n)	O(1) 均摊
导航操作	✅ first/last/subMap	❌ 不支持
key 要求	必须可比较	任意

---

总结

核心要点	掌握程度
ArrayList vs LinkedList	理解适用场景
HashMap 底层结构	能画图说明
HashMap put 流程	能手写伪代码
扩容机制	理解高位分流
fail-fast 原理	理解 modCount
线程安全方案	知道各自适用场景

---

相关链接

• HashMap 底层实现
• ArrayList vs LinkedList
• Fail-Fast 机制