Java 集合面试题精讲
底层原理类
Q1: HashMap 的底层数据结构是什么？
🎯 面试直答版
JDK8 的 HashMap 底层是数组 + 链表 + 红黑树。数组是主体，链表解决哈希冲突，当链表长度 ≥ 8 且数组长度 ≥ 64 时链表转为红黑树，将查找从 O(n) 优化为 O(log n)。
📖 深度解析版
- 数组（Node[] table）：HashMap 的骨架，每个位置叫一个”桶”（bucket），默认初始长度 16，必须是 2 的幂
- 链表：当多个 key 的 hash 值映射到同一个桶时，用链表串起来（拉链法）。JDK8 采用尾插法（JDK7 是头插法）
- 红黑树：当链表过长时查找退化为 O(n)，转为红黑树后为 O(log n)。树化需要两个条件同时满足：
- 链表长度 ≥ 8（TREEIFY_THRESHOLD）
- 数组长度 ≥ 64（MIN_TREEIFY_CAPACITY），否则优先扩容
💡 加分项
- 为什么 JDK8 从头插法改为尾插法？因为头插法在多线程 resize 时会导致链表形成环，造成死循环（CPU 100%）。尾插法不会改变链表顺序，避免了这个问题
- 红黑树退化为链表的阈值是 6（不是 8），中间留了缓冲区防止频繁转换抖动
Q2: HashMap 的 put 过程？
🎯 面试直答版
- 计算 key 的 hash（高低 16 位异或扰动）
- 用
(n-1) & hash定位桶 - 桶为空直接放入；不为空则遍历链表/红黑树，找到相同 key 就覆盖 value，没找到就插入末尾
- 插入后判断是否需要树化（链表≥8）或扩容（size > threshold）
📖 深度解析版
① 对 key 做 hash 运算：hash = (h = key.hashCode()) ^ (h >>> 16)
高 16 位和低 16 位异或，让所有位都参与运算，减少碰撞
② 如果 table 为空或长度为 0，调用 resize() 初始化
③ 计算桶索引 i = (n - 1) & hash
- 桶为空 → 直接创建节点放入
- 桶不为空：
a. 首节点 key 相同 → 覆盖
b. 首节点是 TreeNode → 红黑树插入
c. 遍历链表 → 尾部插入，插入后判断链表长度是否 ≥ 8
④ 如果 key 已存在（覆盖），返回旧 value
⑤ modCount++，size++，判断 size > threshold 则 resize()💡 加分项
- null key 固定放在 table[0]，因为 hash(null) = 0
- 扰动函数将碰撞概率从 hashCode 的质量中”解救”出来，即使 hashCode 实现不好，扰动后分布也相对均匀
Q3: HashMap 的扩容机制？
🎯 面试直答版
当元素数量超过 容量 × 负载因子（默认 16×0.75=12）时触发扩容。新数组容量翻倍，然后将旧元素重新分配到新数组中。JDK8 优化了重新分配逻辑：元素要么在原位置，要么在”原位置 + 旧容量”位置。
📖 深度解析版
- 触发条件：
size > capacity * loadFactor - 扩容大小：新容量 = 旧容量 × 2（左移一位）
- 元素迁移（JDK8 优化）：
- 不需要重新计算 hash
- 只需判断
hash & oldCap的结果：- 等于 0 → 留在原位置
- 不等于 0 → 移到原位置 + oldCap
- 链表拆分为高位链表和低位链表，分别放入新数组
旧容量 = 16 (10000)，新容量 = 32 (100000)
元素 hash = ...0_1010 → hash & 16 = 0 → 留在 index=10
元素 hash = ...1_1010 → hash & 16 ≠ 0 → 移到 index=10+16=26💡 加分项
- 负载因子 0.75 是空间和时间的折中：太小浪费空间，太大碰撞增多
- JDK7 在多线程扩容时，头插法会导致链表成环 → 死循环。JDK8 用尾插法解决了这个问题，但 HashMap 仍然不是线程安全的（并发 put 可能数据丢失）
Q4: 为什么链表长度到 8 才转红黑树？
🎯 面试直答版
根据泊松分布计算，在 hash 均匀分布的情况下，链表长度达到 8 的概率只有千万分之六。所以 8 是一个极端情况下的兜底策略，平时几乎不会触发。
📖 深度解析版
HashMap 源码注释中给出了泊松分布下桶中元素个数的概率：
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006 ← 六千万分之一红黑树的节点大小约为链表节点的 2 倍（TreeNode 需要维护 parent、left、right、color 等字段），如果太早树化会浪费空间。8 这个阈值保证了只有在 hash 分布极不均匀的异常场景下才会树化。
💡 加分项
- 退化阈值设为 6（不是 7 或 8）是为了避免抖动：如果树化和退化用同一个阈值，某个桶反复在阈值附近增删就会频繁转换
- 树化还有第二个条件：数组长度 ≥ 64。因为数组太小时，碰撞多是正常现象，应该优先扩容
Q5: ConcurrentHashMap 怎么保证线程安全？
🎯 面试直答版
JDK7 用分段锁（Segment，16 个 ReentrantLock），不同段可以并发操作。JDK8 改用 CAS + synchronized，锁粒度从段级别细化到桶级别——空桶用 CAS 无锁写入，非空桶用 synchronized 锁住桶的头节点。
📖 深度解析版
JDK7 分段锁：
- 将数据分为 16 个 Segment，每个 Segment 是一个独立的小 HashMap + ReentrantLock
- 最大并发度 = Segment 数量 = 16
- 缺点：锁粒度大，16 个线程以上就有锁竞争
JDK8 CAS + synchronized：
- 取消 Segment，结构和 HashMap 一样（数组 + 链表 + 红黑树）
- put 流程：
- 计算 hash，定位桶
- 桶为空 →
CAS写入（无锁，最快路径） - 正在扩容 → 帮助扩容（多线程协作）
- 桶不为空 →
synchronized(头节点)→ 链表/红黑树操作
- 最大并发度 = 数组长度（远大于 16）
💡 加分项
size()的实现类似 LongAdder：baseCount + CounterCell[]，分散 CAS 竞争- JDK8 中 synchronized 经过了大量优化（偏向锁→轻量级锁→重量级锁），性能不比 ReentrantLock 差
- ConcurrentHashMap 不允许 null key 和 null value，因为
get(key)==null时无法区分”key 不存在”还是”value 就是 null”（在并发场景下这种歧义更危险）
Q6: HashMap 的 hash 函数为什么要用高低位异或？
🎯 面试直答版
桶定位公式是 (n-1) & hash，当数组长度 n 较小时（如 16），只有低 4 位参与运算，高位完全被忽略。高低 16 位异或让高位信息也能影响桶定位，降低碰撞概率。
📖 深度解析版
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}假设 n = 16，则 (n-1) & hash 取 hash 的低 4 位。如果两个 key 的 hashCode 低 4 位相同但高位不同，不扰动的话它们会 100% 碰撞。异或后，高位的差异被混入低位，碰撞概率大幅下降。
💡 加分项
- 用异或而不是与/或，是因为异或的信息保留最好：AND 倾向产生 0，OR 倾向产生 1，XOR 能均匀保留两边的信息
- JDK7 做了 4 次扰动（4次位移+异或），JDK8 简化为 1 次，因为实验表明收益递减，1 次就够用了
对比类
Q7: ArrayList 和 LinkedList 的区别？
🎯 面试直答版
ArrayList 基于动态数组，支持 O(1) 随机访问，尾部增删 O(1)，中间增删 O(n)。LinkedList 基于双向链表，不支持随机访问，头尾增删 O(1)。实际开发中 99% 的场景用 ArrayList，因为 CPU 缓存对连续内存更友好。
📖 深度解析版
| 维度 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 | O(1)，直接计算偏移 | O(n)，从头/尾遍历 |
| 尾部插入 | 均摊 O(1) | O(1) |
| 头部插入 | O(n)，要移动所有元素 | O(1) |
| 中间插入 | O(n)，移动后续元素 | O(n)，先遍历定位再 O(1) 插入 |
| 内存占用 | 紧凑（可能有尾部空闲） | 每个节点额外两个指针（16字节/节点） |
| CPU 缓存 | 友好（连续内存） | 不友好（节点散落堆中） |
💡 加分项
- LinkedList 实现了 Deque 接口，可以当栈和队列用，但 ArrayDeque 在这两个场景都更快
- ArrayList 的
elementData被transient修饰，序列化时只写入实际有数据的部分，避免空槽浪费
Q8: HashMap、Hashtable 和 ConcurrentHashMap 的区别？
🎯 面试直答版
- HashMap：非线程安全，允许 null key/value，性能最好
- Hashtable：线程安全（所有方法加 synchronized），不允许 null，性能差，已淘汰
- ConcurrentHashMap：线程安全，不允许 null，细粒度锁（JDK8 锁桶头节点），高并发首选
📖 深度解析版
| 特性 | HashMap | Hashtable | ConcurrentHashMap |
|---|---|---|---|
| 线程安全 | ❌ | ✅（方法级 synchronized） | ✅（CAS + synchronized 桶头节点） |
| null key | ✅ 允许 1 个 | ❌ | ❌ |
| null value | ✅ 允许 | ❌ | ❌ |
| 初始容量 | 16 | 11 | 16 |
| 扩容 | 2 倍 | 2倍+1 | 2 倍 |
| 数据结构 | 数组+链表+红黑树 | 数组+链表 | 数组+链表+红黑树 |
| 迭代器 | fail-fast | fail-fast | fail-safe |
| 继承关系 | AbstractMap | Dictionary（已废弃） | AbstractMap |
| 并发性能 | — | 极差（全表锁） | 高（锁粒度=桶） |
💡 加分项
- ConcurrentHashMap 不允许 null 的原因：
get(key)返回 null 时，无法区分”key 不存在”还是”value 是 null”。单线程下可以用containsKey()再判断一次，但并发场景下两次调用之间状态可能已变 - Hashtable 是 JDK1.0 的遗留类，和 Vector 一样不推荐使用
Q9: HashMap 和 TreeMap 怎么选？
🎯 面试直答版
需要按 key 排序或范围查询用 TreeMap（O(log n)），否则用 HashMap（O(1)）。绝大多数场景用 HashMap。
📖 深度解析版
| 维度 | HashMap | TreeMap |
|---|---|---|
| 底层结构 | 数组+链表+红黑树 | 红黑树 |
| 查找/插入 | O(1) | O(log n) |
| 是否有序 | 无序 | 按 key 排序 |
| null key | 允许 | 不允许（无法比较） |
| 适用场景 | 通用键值映射 | 需要排序/范围查询 |
// TreeMap 独有能力
TreeMap<Integer, String> map = new TreeMap<>();
map.firstKey(); // 最小 key
map.lastKey(); // 最大 key
map.headMap(50); // 所有 < 50 的
map.tailMap(50); // 所有 ≥ 50 的
map.subMap(20, 50); // 20 ≤ key < 50
map.floorKey(45); // ≤ 45 的最大 key
map.ceilingKey(45); // ≥ 45 的最小 key💡 加分项
- 如果只需要插入顺序，用 LinkedHashMap 而不是 TreeMap，因为它底层是 HashMap + 链表，O(1) 性能
- TreeMap 的 key 必须实现 Comparable 或构造时传入 Comparator
Q10: HashSet 如何保证元素不重复？
🎯 面试直答版
HashSet 底层就是 HashMap，元素作为 HashMap 的 key 存储。HashMap 通过 hashCode() 定位桶 + equals() 判断相等 来保证 key 不重复，所以 HashSet 的去重也依赖这两个方法。
📖 深度解析版
// add 的本质
public boolean add(E e) {
return map.put(e, PRESENT) == null;
// put 返回 null 说明是新 key → add 成功
// put 返回旧 value 说明 key 已存在 → add 失败（返回 false）
}去重流程：
- 计算元素的
hashCode()，通过扰动函数得到 hash - 用
hash & (n-1)定位桶 - 遍历桶中元素，用
equals()逐一比较 - 找到相等的 → 元素已存在，不插入
- 没找到 → 插入新元素
💡 加分项
- 所以自定义对象放入 HashSet 时，必须同时重写 hashCode() 和 equals()。只重写 equals 不重写 hashCode，两个”相等”的对象可能落在不同桶中，导致去重失败
- hashCode 的契约：
a.equals(b) == true则a.hashCode() == b.hashCode()必须成立。反之不要求（不同对象可以有相同 hashCode）
Q11: Collection 和 Collections 的区别？
🎯 面试直答版
Collection 是集合框架的根接口（List、Set、Queue 都继承它）。Collections 是工具类，提供排序、查找、同步包装等静态方法。
📖 深度解析版
// Collection：接口，定义集合的基本行为
public interface Collection<E> extends Iterable<E> {
boolean add(E e);
boolean remove(Object o);
int size();
// ...
}
// Collections：工具类，操作集合的静态方法集
public class Collections {
public static <T> void sort(List<T> list) { ... }
public static <T> List<T> unmodifiableList(List<T> list) { ... }
public static <T> List<T> synchronizedList(List<T> list) { ... }
public static <T> List<T> emptyList() { ... }
// ...
}💡 加分项
- 类似的设计还有
Array（反射类）和Arrays（数组工具类），Executor（接口）和Executors（工厂类）
Q12: Comparable 和 Comparator 的区别？
🎯 面试直答版
Comparable 是类自己实现的排序规则（“内比较器”），只能定义一种排序方式。Comparator 是外部传入的排序规则（“外比较器”），可以定义多种排序方式。
📖 深度解析版
| 维度 | Comparable | Comparator |
|---|---|---|
| 包 | java.lang | java.util |
| 方法 | compareTo(T o) | compare(T o1, T o2) |
| 使用方式 | 类实现接口 | 外部传入 Lambda/匿名类 |
| 排序规则数 | 一种（自然排序） | 无限种 |
| 侵入性 | 需要修改类 | 无需修改类 |
// Comparable：类自身定义排序
public class User implements Comparable<User> {
@Override
public int compareTo(User other) {
return this.age - other.age; // 按年龄升序
}
}
// Comparator：外部定义排序（更灵活）
users.sort(Comparator.comparing(User::getName)); // 按姓名
users.sort(Comparator.comparing(User::getAge).reversed()); // 按年龄降序
users.sort(Comparator.comparing(User::getAge)
.thenComparing(User::getName)); // 先年龄后姓名💡 加分项
- TreeMap/TreeSet 优先使用构造时传入的 Comparator；没传才用 key 的 Comparable
- JDK8 后 Comparator 提供了大量静态方法和默认方法（
comparing、thenComparing、reversed、nullsFirst），实际开发中几乎不需要手写比较逻辑
场景设计类
Q13: 如何设计一个线程安全的 LRU 缓存？
🎯 面试直答版
用 LinkedHashMap（accessOrder=true）重写 removeEldestEntry() 控制容量上限，外层用 Collections.synchronizedMap() 或 ReentrantReadWriteLock 保证线程安全。
📖 深度解析版
方案一：LinkedHashMap + 同步包装（简单场景）
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxSize;
public LRUCache(int maxSize) {
super(maxSize * 4 / 3 + 1, 0.75f, true); // accessOrder=true
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
// 线程安全版本
public static <K, V> Map<K, V> createThreadSafe(int maxSize) {
return Collections.synchronizedMap(new LRUCache<>(maxSize));
}
}方案二：生产环境直接用 Caffeine
Cache<String, Object> cache = Caffeine.newBuilder()
.maximumSize(10000)
.expireAfterAccess(Duration.ofMinutes(30))
.recordStats()
.build();💡 加分项
- 面试时先说 LinkedHashMap 方案展示你懂原理，然后补充说生产环境用 Caffeine/Guava Cache
- Caffeine 底层用了 W-TinyLFU 算法，命中率优于纯 LRU
Q14: 大数据量去重应该用什么？
🎯 面试直答版
数据量不大用 HashSet。数据量大（百万以上）且允许少量误判用布隆过滤器（BloomFilter）。海量数据精确去重可以用位图（BitSet）或外部排序 + 归并去重。
📖 深度解析版
| 方案 | 适用数据量 | 内存占用 | 精确性 | 说明 |
|---|---|---|---|---|
| HashSet | 百万以内 | 高（对象开销大） | 精确 | 最简单直接 |
| BitSet | 亿级整数 | 极低（1bit/数） | 精确 | 只能用于整数范围已知的场景 |
| BloomFilter | 亿级任意类型 | 低 | 有误判（假阳性） | Guava/Redisson 都有实现 |
| 外部排序 | 磁盘级 | 不受内存限制 | 精确 | MapReduce 思想 |
| Redis Set/HyperLogLog | 分布式场景 | 取决于方案 | Set精确/HLL估算 | 跨服务去重 |
// BloomFilter 示例（Guava）
BloomFilter<String> filter = BloomFilter.create(
Funnels.stringFunnel(Charset.defaultCharset()),
10_000_000, // 预期元素数量
0.001 // 误判率
);
filter.put("user:1001");
filter.mightContain("user:1001"); // true
filter.mightContain("user:9999"); // false（大概率），可能 true（0.1% 概率误判）💡 加分项
- 10 亿个整数去重，用 BitSet 只需要 125MB 内存（10^9 / 8 bytes）
- BloomFilter 不支持删除，需要删除功能可用 Counting Bloom Filter 或 Cuckoo Filter
Q15: 如何选择合适的 Map 实现？
🎯 面试直答版
- 通用场景 → HashMap
- 需要线程安全 → ConcurrentHashMap
- 需要按 key 排序 → TreeMap
- 需要保持插入顺序 → LinkedHashMap
- 枚举作为 key → EnumMap
- 需要弱引用 key → WeakHashMap
📖 深度解析版
需要 Map
│
需要线程安全？
┌── 是 ──┤── 否 ──┐
│ │
ConcurrentHashMap 需要有序？
┌── 是 ──┤── 否 ──┐
│ │
按什么排序？ HashMap
┌─── key ───┤─── 插入顺序 ──┐
│ │
TreeMap LinkedHashMap💡 加分项
IdentityHashMap：用==而非equals()判断 key 相等，适用于序列化/拓扑遍历等需要”引用相等”的场景WeakHashMap：key 是弱引用，GC 时自动回收无外部引用的 entry，常用于缓存（如 ThreadLocalMap 的设计灵感来源）
Q16: 遍历 Map 有几种方式？哪种最优？
🎯 面试直答版
4 种方式。推荐用 entrySet()（或 JDK8 的 forEach），因为一次拿到 key 和 value，避免二次查找。
📖 深度解析版
Map<String, Integer> map = new HashMap<>();
// 方式一：entrySet()（推荐）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
}
// 方式二：forEach（JDK8+，最简洁）
map.forEach((key, value) -> {
System.out.println(key + "=" + value);
});
// 方式三：keySet()（需要二次 get，性能稍差）
for (String key : map.keySet()) {
Integer value = map.get(key); // 多一次 hash 查找
}
// 方式四：values()（只需要 value 时）
for (Integer value : map.values()) {
// ...
}💡 加分项
keySet()方式在 HashMap 中多一次 O(1) 查找，影响不大。但在 TreeMap 中多一次 O(log n) 查找，差距明显
Q17: ArrayList 和 Vector 的区别？
🎯 面试直答版
Vector 是线程安全的（方法加 synchronized），ArrayList 不是。Vector 扩容翻倍，ArrayList 扩 1.5 倍。Vector 是 JDK1.0 的遗留类，已被淘汰，线程安全场景用 CopyOnWriteArrayList。
📖 深度解析版
| 维度 | ArrayList | Vector |
|---|---|---|
| 线程安全 | 否 | 是（所有方法 synchronized） |
| 扩容 | 1.5 倍 | 2 倍（或指定增量） |
| 性能 | 高 | 低（锁开销） |
| 迭代器 | Iterator（fail-fast） | Iterator + Enumeration |
| JDK 版本 | 1.2 | 1.0 |
| 状态 | 活跃使用 | 已淘汰 |
💡 加分项
- Vector 的
elements()方法返回 Enumeration，这也是一个遗留接口 - 需要线程安全 List 的三种方案对比：
Vector：全方法加锁，粒度太粗 ❌Collections.synchronizedList()：包装器，遍历时需手动加锁 ⚠️CopyOnWriteArrayList：读无锁，写时复制，读多写少场景最优 ✅
Q18: CopyOnWriteArrayList 的原理？
🎯 面试直答版
写操作时复制一份新数组，在新数组上修改，再用新数组替换旧数组。读操作直接读旧数组，无需加锁。适合读多写少的场景。
📖 深度解析版
// 写操作（add/set/remove）
public boolean add(E e) {
synchronized (lock) { // 写加锁
Object[] es = getArray();
int len = es.length;
es = Arrays.copyOf(es, len + 1); // 复制新数组
es[len] = e;
setArray(es); // 替换引用（volatile）
return true;
}
}
// 读操作（get）
public E get(int index) {
return elementAt(getArray(), index); // 直接读，无锁
}写时复制过程：
线程A 读取（读旧数组） 线程B 写入
│ │
↓ ↓
[a, b, c] (旧数组) 复制 → [a, b, c, d] (新数组)
│ │
↓ ↓
看到 [a, b, c] 引用指向新数组
│
↓
后续读取看到 [a, b, c, d]缺点：
- 写操作开销大（每次都要复制数组）
- 数据弱一致（读可能读到旧数据）
- 不适合大数组频繁写
💡 加分项
- CopyOnWriteArrayList 的迭代器是 fail-safe 的：创建迭代器时拿到的是当时的数组快照，后续修改不影响迭代
- 适用场景：事件监听器列表、配置信息缓存、黑白名单等读远多于写的场景
Q19: 什么是 fail-fast 和 fail-safe？
🎯 面试直答版
fail-fast：遍历时如果集合被修改，立即抛出 ConcurrentModificationException。ArrayList、HashMap 都是 fail-fast 的。
fail-safe：遍历时操作的是副本或快照，不会抛异常但可能读到旧数据。CopyOnWriteArrayList、ConcurrentHashMap 是 fail-safe 的。
📖 深度解析版
fail-fast 原理：
// 集合维护一个 modCount，每次结构性修改 modCount++
// 创建 Iterator 时记录 expectedModCount = modCount
// 每次 next() 检查 modCount != expectedModCount → 抛异常fail-safe 原理：
- CopyOnWriteArrayList：Iterator 遍历的是创建时的数组快照
- ConcurrentHashMap：Iterator 弱一致性，能看到创建后的部分修改（不保证全部）
💡 加分项
- fail-fast 是一种”尽早暴露错误”的设计策略，不是线程安全保证。即使在单线程中，用 for-each 遍历时调用
list.remove()也会触发 - 用
iterator.remove()不会触发 fail-fast，因为它会同步更新 expectedModCount
Q20: HashMap 中 key 可以是可变对象吗？
🎯 面试直答版
技术上可以，但强烈不建议。如果 key 放入后被修改导致 hashCode 变了，就再也找不到这个 entry 了——它待在旧 hash 对应的桶里，但你用新 hash 去找，会去另一个桶。
📖 深度解析版
List<String> key = new ArrayList<>();
key.add("hello");
Map<List<String>, String> map = new HashMap<>();
map.put(key, "world");
System.out.println(map.get(key)); // "world" ✅
key.add("changed"); // 修改了 key → hashCode 变了
System.out.println(map.get(key)); // null 💥
// key 对应的 entry 还在 map 里，但你找不到了
// 因为 get 用新 hashCode 定位到了另一个桶
System.out.println(map.size()); // 1 —— entry 确实还在最佳实践：HashMap 的 key 应该用不可变对象（String、Integer、Long 等）。如果必须用自定义对象，保证参与 hashCode 计算的字段不可变。
💡 加分项
- 这也是为什么 String 是最常用的 HashMap key：String 是 final 类、不可变、hashCode 会缓存
- String 的 hashCode 缓存：第一次计算后存在
hash字段中，后续直接返回
Q21: HashMap 在 JDK7 和 JDK8 中的区别？
🎯 面试直答版
四个关键区别：①数据结构从”数组+链表”变为”数组+链表+红黑树”；②插入方式从头插法改为尾插法；③扩容时不再重新计算 hash，用位运算判断新位置；④hash 扰动从 4 次简化为 1 次。
📖 深度解析版
| 维度 | JDK7 | JDK8 |
|---|---|---|
| 数据结构 | 数组 + 链表 | 数组 + 链表 + 红黑树 |
| 插入方式 | 头插法 | 尾插法 |
| 扩容 | 重新计算 hash & (newCap-1) | hash & oldCap 判断高低位 |
| hash 扰动 | 4 次位移 + 异或 | 1 次（高低 16 位异或） |
| 链表遍历 | 无树化优化 | 链表 ≥ 8 且数组 ≥ 64 → 红黑树 |
| 初始化 | 构造时分配数组 | 懒初始化（首次 put 时分配） |
💡 加分项
- JDK7 的头插法为什么会造成死循环？两个线程同时 resize，线程A 把链表反转了一半被挂起，线程B 完成了反转。线程A 恢复后继续反转，导致节点互相指向形成环。后续 get() 遍历到这个桶就会死循环
- JDK8 的尾插法保持链表原始顺序，不会形成环
Q22: 为什么 HashMap 的容量必须是 2 的幂？
🎯 面试直答版
为了用位运算（hash & (n-1)）代替取模（hash % n），位运算比取模快得多。同时保证 hash 值能均匀分布到各个桶。
📖 深度解析版
当 n = 2^k 时：
n - 1 的二进制是全 1（如 n=16, n-1=15=0b01111）
hash & (n-1) 等价于取 hash 的低 k 位，保证结果在 [0, n-1] 范围内
如果 n 不是 2 的幂：
n-1 的二进制中有 0，某些桶永远不会被映射到 → 分布不均匀
例如 n=10, n-1=9=0b1001
hash & 0b1001 只可能得到 0b0000, 0b0001, 0b1000, 0b1001 → 只有 4 个可能的桶HashMap 如何保证容量是 2 的幂？
// tableSizeFor：找到 ≥ cap 的最小 2 的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 原理：把最高位的 1 往右"涂满"，再 +1 就是 2 的幂
// 例如：cap=10 → n=9(0b1001) → 涂满→0b1111(15) → +1→16💡 加分项
- 即使你传入一个非 2 的幂的初始容量（如
new HashMap<>(10)），HashMap 内部也会自动向上取到最近的 2 的幂（16）
Q23: List.of() 和 Arrays.asList() 的区别？
🎯 面试直答版
Arrays.asList() 返回固定大小的 List（不能 add/remove，但能 set）。List.of()（JDK9+）返回完全不可变的 List（add/remove/set 都不行，且不允许 null 元素）。
📖 深度解析版
| 特性 | Arrays.asList() | List.of() (JDK9+) |
|---|---|---|
| 可变性 | 固定大小（不能增删，能改） | 完全不可变 |
| null 元素 | 允许 | 不允许（抛 NPE） |
| 与原数组关系 | 共享底层数组（互相影响） | 独立副本 |
| 序列化 | 是 | 是 |
String[] arr = {"a", "b", "c"};
List<String> asList = Arrays.asList(arr);
arr[0] = "x";
System.out.println(asList.get(0)); // "x" ← 被原数组影响了！
List<String> listOf = List.of("a", "b", "c");
// listOf.add("d"); // 💥 UnsupportedOperationException
// listOf.set(0, "x"); // 💥 UnsupportedOperationException💡 加分项
- 需要可变 List 时，统一用
new ArrayList<>(List.of(...))或new ArrayList<>(Arrays.asList(...)) List.of()内部实现针对元素数量做了优化：0个用空单例、1-2个用特殊字段、3+个用数组
Q24: 如何实现一个线程安全的 List？
🎯 面试直答版
三种方式：
Collections.synchronizedList(new ArrayList<>())— 包装器，遍历需手动加锁CopyOnWriteArrayList— 读多写少场景最优- 使用并发队列如
ConcurrentLinkedDeque— 不需要随机访问时
📖 深度解析版
// 方案一：synchronizedList
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// ⚠️ 遍历时必须手动加锁，否则仍可能 ConcurrentModificationException
synchronized (syncList) {
for (String s : syncList) { /* ... */ }
}
// 方案二：CopyOnWriteArrayList（推荐：读多写少）
List<String> cowList = new CopyOnWriteArrayList<>();
cowList.add("a"); // 写加锁 + 复制数组
cowList.get(0); // 读无锁
// 遍历无需加锁，遍历的是快照
// 方案三：并发队列（不需要随机访问时）
Deque<String> deque = new ConcurrentLinkedDeque<>();💡 加分项
synchronizedList的锁粒度是整个 list 对象，并发性能不如 CopyOnWriteArrayList 的读无锁方案- 如果写频繁且需要线程安全 List，考虑用
ConcurrentLinkedDeque+ 有限的 API，或者用分段设计自己实现
Q25: HashMap 的 key 用 String 最合适的原因？
🎯 面试直答版
String 是不可变类（final 修饰，char[] 不可修改），保证 hashCode 不变，且 String 会缓存 hashCode 值，作为 HashMap 的 key 安全且高效。
📖 深度解析版
String 作为 HashMap key 的优势：
- 不可变性：放入 Map 后不会被意外修改，hashCode 不会变
- hashCode 缓存：String 内部有
private int hash字段，第一次计算后缓存，后续 O(1) - equals 高效：先比 hashCode（int 比较），再比长度，最后逐字符比
- 广泛使用：JSON key、配置 key、数据库字段名等天然是 String
// String 源码
public final class String { // final：不可继承，不可修改
private final char[] value; // JDK9 后改为 byte[]
private int hash; // 缓存 hashCode
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
for (char c : value) {
h = 31 * h + c;
}
hash = h; // 缓存
}
return h;
}
}💡 加分项
- 为什么乘数是 31？因为 31 是奇素数，且
31 * i可以被 JVM 优化为(i << 5) - i（位运算更快） - 如果必须用自定义对象作 key，建议让参与 hashCode 的字段都是 final 的
Q26: 说说你对红黑树的理解？
🎯 面试直答版
红黑树是一种自平衡二叉搜索树，通过”着色 + 旋转”保证最长路径不超过最短路径的 2 倍，所有操作 O(log n)。HashMap 在链表过长时用它来优化查找性能。
📖 深度解析版
五条性质：
- 每个节点非红即黑
- 根节点是黑色
- 叶子节点（NIL）是黑色
- 红色节点的两个子节点必须是黑色（不能有两个连续红节点）
- 从任一节点到其所有叶子的路径上，黑色节点数相同（黑高相同）
为什么这五条性质能保证平衡？
- 性质 4 + 5 共同保证：最长路径（红黑交替）≤ 2 × 最短路径（全黑）
- 所以树高最多 2log(n+1)，操作都是 O(log n)
与 AVL 树对比：
| 红黑树 | AVL 树 | |
|---|---|---|
| 平衡程度 | 弱平衡（最长 ≤ 2×最短） | 严格平衡（左右高度差 ≤ 1） |
| 查找 | 稍慢 | 更快 |
| 插入/删除 | 旋转少（最多 3 次） | 旋转多 |
| 适用场景 | 增删频繁（HashMap、TreeMap） | 查找密集（数据库索引） |
💡 加分项
- HashMap 选择红黑树而非 AVL 树，是因为 HashMap 的增删操作频繁，红黑树的插入/删除平均旋转次数少于 AVL
- Java 中的 TreeMap、TreeSet、HashMap（JDK8链表树化）都用红黑树
Q27: HashMap 和 LinkedHashMap 有什么区别？
🎯 面试直答版
LinkedHashMap 继承自 HashMap，额外维护了一条双向链表来记录插入顺序（或访问顺序）。遍历 LinkedHashMap 时是按链表顺序而非 hash 桶顺序。
📖 深度解析版
// HashMap：遍历顺序不确定
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("c", 3);
hashMap.put("a", 1);
hashMap.put("b", 2);
// 遍历顺序可能是 a,b,c 或其他任意顺序
// LinkedHashMap（默认 accessOrder=false）：按插入顺序
Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("c", 3);
linkedMap.put("a", 1);
linkedMap.put("b", 2);
// 遍历顺序一定是 c, a, b
// LinkedHashMap（accessOrder=true）：按访问顺序（LRU）
Map<String, Integer> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put("a", 1);
lruMap.put("b", 2);
lruMap.put("c", 3);
lruMap.get("a");
// 遍历顺序：b, c, a（a 最近被访问，移到末尾）💡 加分项
- LinkedHashMap 的节点继承自 HashMap.Node，额外增加了 before 和 after 两个指针
- 内存开销比 HashMap 稍大（每个节点多两个指针），但遍历性能更稳定（只遍历实际元素，不像 HashMap 要跳过空桶）
Q28: ArrayDeque 和 LinkedList 作为队列/栈有什么区别？
🎯 面试直答版
ArrayDeque 基于循环数组，LinkedList 基于双向链表。ArrayDeque 在队列和栈两种场景下性能都优于 LinkedList（连续内存 + 无节点分配开销），且不允许 null 元素。
📖 深度解析版
| 维度 | ArrayDeque | LinkedList |
|---|---|---|
| 底层 | 循环数组 | 双向链表 |
| 内存 | 紧凑（可能有空位） | 每个节点额外 24 字节 |
| 扩容 | 翻倍 | 无需扩容 |
| null | 不允许 | 允许 |
| 随机访问 | 不支持 | O(n) |
| 作为栈 | 比 Stack 和 LinkedList 快 | 可用但不推荐 |
| 作为队列 | 比 LinkedList 快 | 可用但不推荐 |
// ✅ 推荐：ArrayDeque 作为栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 头部入
stack.pop(); // 头部出
// ✅ 推荐：ArrayDeque 作为队列
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 尾部入
queue.poll(); // 头部出💡 加分项
- JDK 的官方文档推荐：作为栈用 ArrayDeque 替代 Stack，作为队列也用 ArrayDeque 替代 LinkedList
- ArrayDeque 不是线程安全的，多线程场景用
ConcurrentLinkedDeque
Q29: 怎么保证 HashMap 线程安全？
🎯 面试直答版
三种方式：
ConcurrentHashMap（首选，分段锁/CAS，并发性能最好）Collections.synchronizedMap(new HashMap<>())（全表锁，性能差）Hashtable（已淘汰，不推荐）
📖 深度解析版
// 方案一：ConcurrentHashMap（推荐）
Map<String, Object> map = new ConcurrentHashMap<>();
// JDK8: CAS + synchronized(桶头节点)
// 并发度 = 数组长度
// 不允许 null key/value
// 方案二：Collections.synchronizedMap
Map<String, Object> map = Collections.synchronizedMap(new HashMap<>());
// 所有方法用同一把互斥锁
// 遍历时需要手动加锁：synchronized(map) { for(...) }
// 允许 null（因为底层还是 HashMap）
// 方案三：Hashtable（不要用）
Map<String, Object> map = new Hashtable<>();
// 所有方法加 synchronized，性能差
// 不允许 null key/value💡 加分项
- ConcurrentHashMap 的
size()不是精确值（并发下），如果需要精确 size，可以用mappingCount()返回 long 类型 - ConcurrentHashMap 的复合操作（check-then-act）仍然需要注意原子性，使用
computeIfAbsent、compute、merge等原子方法
Q30: Iterator 和 ListIterator 的区别？
🎯 面试直答版
Iterator 只能单向向前遍历所有 Collection。ListIterator 是 Iterator 的子接口，专用于 List，支持双向遍历、获取索引、添加和修改元素。
📖 深度解析版
| 能力 | Iterator | ListIterator |
|---|---|---|
| 适用范围 | 所有 Collection | 仅 List |
| 遍历方向 | 单向（forward） | 双向（forward + backward） |
| hasNext/next | ✅ | ✅ |
| hasPrevious/previous | ❌ | ✅ |
| remove | ✅ | ✅ |
| add | ❌ | ✅ |
| set | ❌ | ✅ |
| nextIndex/previousIndex | ❌ | ✅ |
List<String> list = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
String s = it.next();
if ("b".equals(s)) {
it.set("B"); // 替换当前元素
it.add("b2"); // 在当前位置后插入
}
}
// list: [a, B, b2, c]💡 加分项
listIterator(index)可以从任意位置开始遍历- 实际开发中很少直接用 ListIterator，大多数操作用 Stream API 更简洁