Java 集合框架

集合框架是 Java 面试的重中之重，尤其是 HashMap、ConcurrentHashMap 几乎必问。掌握底层原理和选型策略是关键。

Q1: Java 集合框架的整体结构？List/Set/Map 有什么区别？「🟢 校招/初级」

考察点：对 Java 集合框架的整体认知，是否清楚各接口的层级关系和设计意图。筛掉只会用 ArrayList 和 HashMap、对整体结构没有概念的人。

参考答案：

整体结构

Java 集合框架主要分为两大分支：Collection 和 Map。

Iterable
└── Collection                          （单列集合根接口）
    ├── List                            （有序、可重复）
    │   ├── ArrayList
    │   ├── LinkedList
    │   ├── Vector
    │   └── CopyOnWriteArrayList
    ├── Set                             （无序、不可重复）
    │   ├── HashSet
    │   ├── LinkedHashSet
    │   ├── TreeSet
    │   └── CopyOnWriteArraySet
    └── Queue                           （队列）
        ├── LinkedList
        ├── ArrayDeque
        ├── PriorityQueue
        └── BlockingQueue
            ├── ArrayBlockingQueue
            ├── LinkedBlockingQueue
            ├── SynchronousQueue
            ├── PriorityBlockingQueue
            └── DelayQueue

Map                                     （双列集合，键值对）
├── HashMap
├── LinkedHashMap
├── TreeMap
├── Hashtable
├── ConcurrentHashMap
└── Properties

Collection 三大子接口对比

特性	List	Set	Queue
元素顺序	有序（按插入顺序）	无序（HashSet）/ 有序（TreeSet/LHS）	有序（FIFO）
元素重复	可重复	不可重复	可重复
null 元素	允许（多个）	允许一个（HashSet）	不建议放 null
常见实现	ArrayList、LinkedList、Vector	HashSet、TreeSet、LinkedHashSet	ArrayBlockingQueue、LinkedList
访问方式	索引遍历、Iterator	Iterator	入队出队（offer/poll）
典型场景	按索引访问、有序列表	去重、集合运算	生产者消费者、任务队列

Map 接口

Map 不是 Collection 的子接口，是独立的双列集合体系。
存储 键值对（key-value），key 不允许重复，value 可以重复。

特性	说明
key	不可重复，最多一个 null（HashMap）
value	可重复，可以多个 null
常见实现	HashMap、TreeMap、LinkedHashMap、Hashtable、ConcurrentHashMap
遍历方式	keySet、entrySet、values、forEach

List / Set / Map 核心区别

维度	List	Set	Map
元素形式	单个元素	单个元素	键值对（K-V）
有序性	有序（插入顺序）	不一定（HashSet无序，TreeSet有序）	不一定（HashMap无序，LinkedHashMap有序）
重复性	可重复	不可重复（equals/hashCode）	key 不可重复，value 可重复
索引访问	支持（按 index 访问）	不支持	不支持（按 key 访问）
典型实现	ArrayList、LinkedList	HashSet、TreeSet	HashMap、TreeMap

集合框架的设计特点

接口与实现分离：List/Set/Map 是接口，ArrayList/HashMap 等是实现类，面向接口编程。
统一的迭代方式：所有 Collection 都实现了 Iterable 接口，可以用 Iterator 或 for-each 遍历。
泛型支持：编译期类型安全，避免运行时强转错误。
工具类：Collections 提供排序、查找、同步包装等工具方法；Arrays 提供数组操作。
并发集合：java.util.concurrent 包提供线程安全的集合实现。

追问延伸：

Collection 和 Collections 的区别？（Collection 是接口，Collections 是工具类）
为什么 Map 不继承 Collection？（设计理念不同，Map 是键值对，Collection 是单列；Map 有 keySet/entrySet/values 方法返回 Collection 视图）
你项目中最常用哪些集合类？为什么选它们？
集合和数组有什么区别？（数组固定大小，集合动态扩容；数组可以存基本类型，集合只能存对象）
Iterator 和 ListIterator 的区别？（ListIterator 可以双向遍历、添加修改元素，只能用于 List）

Q2: ArrayList 和 LinkedList 的区别？ArrayList 扩容机制？「🟢 校招/初级」

考察点：对 List 两大实现类的底层理解，动态数组和链表的特性对比，以及 ArrayList 扩容细节。筛掉只会用不会原理的人。

参考答案：

核心区别

维度	ArrayList	LinkedList
底层结构	动态数组（Object[]）	双向链表（Node 节点）
随机访问	O(1)，直接按索引定位	O(n)，需要遍历
头插/中间插	O(n)，需要移动元素	O(1)，修改指针（但定位要 O(n)）
尾插	O(1)（不扩容时）	O(1)
删除	O(n)，需要移动元素	O(1)，修改指针（但定位要 O(n)）
内存占用	连续内存，有空间浪费（扩容冗余）	不连续，每个节点多存两个指针
缓存友好性	好（空间局部性，CPU 缓存命中率高）	差（节点分散，缓存命中率低）
线程安全	不安全	不安全

ArrayList 详解

底层结构

基于 Object[] elementData 数组实现。
size 字段记录实际元素个数（不是数组长度）。

扩容机制

默认容量：初始为 0（JDK 7 是 10，JDK 8 优化为懒加载，首次 add 时初始化为 10）。
扩容时机：添加元素时，如果 size + 1 > elementData.length，触发扩容。
扩容倍数：1.5 倍（newCapacity = oldCapacity + (oldCapacity >> 1)）。
扩容方式：Arrays.copyOf(elementData, newCapacity)，底层是 System.arraycopy native 方法，创建新数组并复制元素。

java

// ArrayList 扩容源码（简化）
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

优化建议

如果能预估数据量，构造时指定初始容量，减少扩容次数：new ArrayList<>(1000)。
批量添加用 addAll()，只触发一次扩容检查。
已知不会再添加元素时，可以调用 trimToSize() 释放多余空间。

LinkedList 详解

底层结构

基于双向链表实现，每个节点是 Node 对象，包含 item、prev、next。
有 first 和 last 指针分别指向头尾节点。

java

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

特点

实现了 List 和 Deque（双端队列）接口，所以既可以当 List 用，也可以当队列/栈用。
头尾插入删除都是 O(1)。
按下标访问是 O(n)，但做了优化：index < size/2 从头遍历，否则从尾遍历。

实际性能对比

很多人以为 LinkedList 插入删除快，但实际情况要具体分析：

尾部插入：两者都是 O(1)，ArrayList 更快（数组连续内存，缓存友好）。
中间插入：
- ArrayList：需要移动元素，O(n)。
- LinkedList：需要先定位到位置（O(n)），再修改指针（O(1)），整体也是 O(n)。
- 实际测试中，ArrayList 往往更快，因为数组移动是连续内存操作（System.arraycopy 是 native 优化的），而链表遍历是跳跃访问，缓存命中率低。
随机访问：ArrayList 秒杀 LinkedList。
内存占用：ArrayList 有扩容浪费，但 LinkedList 每个节点都要存两个指针，数据量大时内存开销也不小。

结论：绝大多数场景用 ArrayList 就够了，只有在频繁头尾操作（如栈、队列）时才考虑 LinkedList。

追问延伸：

ArrayList 初始容量是多少？扩容是几倍？用什么方式扩容？
为什么 ArrayList 扩容是 1.5 倍而不是 2 倍？（1.5 倍可以复用之前释放的连续空间；2 倍增长太快，空间浪费多）
ArrayList 和数组的区别？怎么转换？（Arrays.asList / list.toArray）
LinkedList 可以当栈或队列用吗？有哪些方法？（push/pop/peek 栈操作；offer/poll 队列操作）
Arrays.asList() 返回的 List 和 ArrayList 有什么区别？（返回的是 Arrays 内部类 ArrayList，不是 java.util.ArrayList，大小固定，不能 add/remove）
你在项目中怎么选择 ArrayList 和 LinkedList？

Q3: ArrayList 和 Vector 的区别？「🟢 校招/初级」

考察点：对 List 历史演进的了解，线程安全集合的发展。筛掉不了解 Vector、对线程安全集合认知模糊的人。

参考答案：

核心区别

维度	ArrayList	Vector
线程安全	非线程安全	线程安全（方法加 synchronized）
扩容倍数	1.5 倍	2 倍
性能	高（无同步开销）	低（所有方法都加锁）
出现版本	JDK 1.2	JDK 1.0（最古老的集合类之一）
迭代器	Iterator、ListIterator	Enumeration（旧）、Iterator
推荐使用	推荐	不推荐（已过时）

线程安全的实现

Vector：几乎所有方法都加了 synchronized 关键字，锁的是整个 Vector 对象。
- 读操作也加锁，即使没有写操作，多线程读也串行化，性能差。
- 复合操作（如 if (!vector.contains(x)) vector.add(x)）仍然不安全，需要额外加锁。

java

// Vector 源码（简化）
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    return elementData(index);
}

ArrayList：没有任何同步措施，多线程下并发读写会有问题。

扩容机制对比

java

// ArrayList：1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

// Vector：2 倍（可通过 capacityIncrement 调整）
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

Vector 默认 2 倍扩容，空间浪费更多，但扩容次数少。
ArrayList 1.5 倍扩容更节省空间。

为什么不推荐用 Vector

性能差：所有方法都加 synchronized，即使在读多写少的场景也全加锁，并发性能极低。
粒度粗：锁整个对象，同一时刻只能有一个线程操作，并发度低。
复合操作仍不安全：虽然单个方法线程安全，但多个方法组合使用（如先检查再添加）仍需外部加锁。
有更好的替代：
- 单线程：用 ArrayList
- 多线程读多写少：用 CopyOnWriteArrayList
- 多线程通用：用 Collections.synchronizedList（也是全加锁，但更灵活）
- 并发队列：用 ArrayBlockingQueue / ConcurrentLinkedQueue

ArrayList 线程安全的替代方案

Collections.synchronizedList(list)：
- 包装 ArrayList，方法加 synchronized（锁的是包装对象 mutex）。
- 和 Vector 类似，性能也差不多，但可以包装任意 List。
- 遍历需要手动加锁：synchronized(list) { Iterator iter = list.iterator(); ... }
CopyOnWriteArrayList：
- 写时复制，读无锁，写加锁。
- 适合读多写少的场景，性能比 Vector 好很多。
ArrayBlockingQueue / LinkedBlockingQueue：
- 如果是队列场景，用阻塞队列。
ConcurrentLinkedQueue：
- 非阻塞队列，CAS 实现，高并发性能好。

追问延伸：

Vector 是线程安全的，为什么不推荐用？（上面已答，性能差、粒度粗、有更好替代）
ArrayList 怎么变成线程安全的？（Collections.synchronizedList、CopyOnWriteArrayList）
Vector 和 Hashtable 有什么共同点？（都是 JDK 1.0 的古老类、全 synchronized、都不推荐）
Collections.synchronizedList 和 Vector 的区别？（一个是包装类、一个是类本身；锁对象不同；synchronizedList 可以指定锁对象）
你在项目中用过哪些线程安全的集合？在什么场景下用的？

Q4: HashMap 的实现原理？JDK 1.7 和 1.8 有什么区别？「🟡 中级」

考察点：HashMap 是面试必考题，考察对底层数据结构、哈希算法、扩容机制、红黑树优化的理解深度。筛掉只会用不会原理的人。

参考答案：

整体结构

HashMap 底层是哈希表（数组 + 链表/红黑树），用于存储键值对（Node<K,V>）。

数组（桶数组）：Node<K,V>[] table，每个元素是一个链表/红黑树的头节点。
链表：哈希冲突时，同一桶中的元素以链表形式存储。
红黑树：JDK 1.8 引入，当链表长度超过阈值时转为红黑树，优化查询性能。

table[0] → Node → Node → ...
table[1] → 红黑树节点
...
table[n] → null

JDK 1.7 vs JDK 1.8 对比

维度	JDK 1.7	JDK 1.8
底层结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法	尾插法
扩容时顺序	会反转链表顺序	保持原顺序
扩容死循环	有（头插法 + 并发）	无（尾插法，但仍线程不安全）
哈希算法	4次位运算 + 5次异或（扰动大）	1次位运算 + 1次异或（扰动小）
红黑树优化	无	链表长度 > 8 且数组长度 > 64 时转红黑树
扩容优化	全部 rehash	用高低位拆分优化（hash & oldCap 判断）
节点类型	Entry	Node（链表）、TreeNode（红黑树）

哈希计算与定位

Hash 计算（扰动函数）

java

// JDK 1.8
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key 为 null 时 hash 值为 0（HashMap 支持一个 null key）。
将 hashCode 的高 16 位和低 16 位异或，让高位也参与到桶定位中，减少哈希碰撞。
为什么不直接用 hashCode？因为数组长度是 2 的幂，低位才有用，高位不参与的话碰撞会很多。

桶定位

java

int index = (n - 1) & hash;  // n 是数组长度

用 (n - 1) & hash 代替取模运算，因为 n 是 2 的幂时，hash % n 等价于 hash & (n - 1)，位运算性能更高。
这也是为什么 HashMap 数组长度必须是 2 的幂。

扩容机制

重要参数

参数	默认值	说明
initialCapacity	16	初始容量（数组长度）
loadFactor	0.75	负载因子
threshold	16 * 0.75 = 12	扩容阈值 = 容量 * 负载因子
TREEIFY_THRESHOLD	8	链表转红黑树阈值
UNTREEIFY_THRESHOLD	6	红黑树退化为链表阈值
MIN_TREEIFY_CAPACITY	64	转红黑树的最小数组容量

扩容时机

当 size > threshold 时，触发扩容。

扩容过程

新数组容量是旧数组的 2 倍（保证 2 的幂）。
创建新数组。
遍历旧数组的每个桶，将元素重新计算位置放到新数组中。
JDK 1.8 优化：不需要重新计算 hash，而是用 hash & oldCap 判断：
- 结果为 0：元素在新数组中的位置不变（原索引）。
- 结果为 1：元素在新数组中的位置 = 原索引 + oldCap。
- 这样可以保持链表顺序，避免反转，也减少了 rehash 的计算量。

红黑树相关

为什么用红黑树

当链表很长时，查询性能退化为 O(n)。
转红黑树后，查询性能为 O(log n)，提升查询效率。

为什么链表长度 > 8 且数组 > 64 才转树

为什么是 8：根据泊松分布，在负载因子 0.75 的情况下，链表长度达到 8 的概率约为 0.00000006（千万分之六），概率极低。
为什么还要数组 > 64：如果数组很小就转树，可能是因为数组容量不够导致的碰撞多，此时应该优先扩容而不是转树。
退化阈值 6：扩容时如果红黑树节点数 <= 6，退化为链表，避免树结构的维护开销。
8 和 6 之间有个差值（7），是为了防止链表和树频繁转换（抖动）。

追问延伸：

HashMap 的 put 方法流程？（下一题详解）
HashMap 为什么线程不安全？（后题详解）
为什么数组长度必须是 2 的幂？（保证 (n-1) & hash 等价于取模，且所有桶都能被用到）
为什么负载因子默认是 0.75？（时间和空间的折中；太高碰撞多，太低空间浪费多；0.75 时碰撞概率符合泊松分布）
HashMap 怎么解决哈希冲突的？（链地址法 + 红黑树优化）
如果重写了 key 的 equals 方法，一定要重写 hashCode 吗？为什么？（必须，否则相等的对象 hash 不同，HashMap 中会被当成两个 key）
HashMap 的 key 可以为 null 吗？value 呢？（key 可以一个 null，value 可以多个 null）

Q5: HashMap 的 put 方法流程？「🟡 中级」

考察点：对 HashMap 核心方法的细节掌握，是否真正理解插入过程。筛掉只知道大概结构、说不清楚具体流程的人。

参考答案：

JDK 1.8 put 方法流程

HashMap 的 put() 方法实际调用的是 putVal()，流程如下：

计算 key 的 hash 值
    ↓
判断数组是否为空/为 null → 是 → 首次扩容（resize）初始化数组
    ↓
计算桶下标 (n - 1) & hash
    ↓
该桶是否为空？
    ├── 是 → 直接创建新节点放入桶中 → 到步骤 6
    └── 否 → 桶中第一个节点的 key 是否相同（hash 相等 && equals 相等）？
        ├── 是 → 这就是要找的节点 → 到步骤 5
        └── 否 → 该节点是红黑树节点吗？
            ├── 是 → 调用红黑树的 putTreeVal 插入 → 到步骤 5
            └── 否 → 遍历链表（尾插法）
                ├── 找到 key 相同的节点 → 到步骤 5
                └── 遍历到末尾还没找到 → 尾部插入新节点
                    → 插入后判断链表长度是否 > 8？
                        ├── 是 → 判断数组长度是否 < 64？
                        │   ├── 是 → 扩容（resize）
                        │   └── 否 → 链表转红黑树
                        └── 否 → 到步骤 6
    ↓
5. 找到了相同 key 的节点 → 判断 onlyIfAbsent 或旧值是否为 null
    → 满足条件则用新 value 覆盖旧 value → 返回旧 value
    ↓
6. modCount++（结构性修改计数）
    ↓
7. size++，判断 size > threshold？
    ├── 是 → 扩容（resize）
    └── 否 → 结束
    ↓
返回 null（新增元素）

核心代码解读（JDK 1.8）

java

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. 数组为空则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 桶为空，直接放新节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        
        // 3. 桶头节点就是目标 key
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 桶是红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5. 桶是链表，遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度达到阈值，考虑转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 6. 找到相同 key，覆盖 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    ++modCount;
    
    // 7. 超过阈值则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

几个关键点

先判断再插入：先检查 key 是否存在，存在则覆盖，不存在则插入。
尾插法：JDK 1.8 用尾插法，遍历到链表末尾插入。
转红黑树的条件：链表长度 > 8 并且数组长度 >= 64。如果数组长度 < 64，优先扩容。
hash 相等不代表 key 相等：先比较 hash（快），再用 == 和 equals 比较 key（慢）。
modCount：记录结构性修改次数，用于 fail-fast 机制。
onlyIfAbsent：如果为 true，只有旧值为 null 时才覆盖（putIfAbsent 方法）。
afterNodeAccess / afterNodeInsertion：空方法，留给 LinkedHashMap 回调。

get 方法流程（对比理解）

计算 key 的 hash 值。
数组为空？返回 null。
计算桶下标。
桶头节点是目标 key？返回 value。
是红黑树？调用红黑树查找。
是链表？遍历查找。
没找到返回 null。

追问延伸：

HashMap 的 get 方法流程？（上面已简述）
put 方法中，为什么先比较 hash 再比较 equals？（hash 是 int 比较快，先过滤掉 hash 不同的，减少 equals 调用）
两个对象 hashCode 相同，equals 不同，HashMap 怎么处理？（放在同一个桶的链表/红黑树中，作为两个不同的 key）
HashMap 扩容的时候怎么处理红黑树？（也会用高低位拆分，拆成两棵树，节点数太少则退化为链表）
JDK 1.7 的 put 流程和 1.8 有什么不一样？（头插法、没有红黑树、扩容时全部 rehash）
HashMap 的 resize 过程？（创建新数组、遍历旧桶、高低位拆分迁移元素）

Q6: HashMap 为什么线程不安全？会有什么问题？「🟡 中级」

考察点：对 HashMap 并发问题的理解，线程安全集合的选型。筛掉对并发问题没概念的人。

参考答案：

HashMap 是非线程安全的，在多线程环境下并发修改会导致各种问题。

JDK 1.7 的问题 —— 扩容死循环

原因

JDK 1.7 采用头插法插入链表，扩容（resize）时会反转链表顺序。多线程并发扩容时，可能导致链表形成环形链表，后续 get 操作遍历链表时死循环。

过程简述

两个线程同时触发扩容。
线程 1 刚记录下 e 和 next 就被挂起。
线程 2 完成扩容，链表顺序反转。
线程 1 恢复执行，按照原来的指针继续迁移，导致链表成环。
之后 get 这个桶上的元素时，遍历链表永远走不出来，CPU 100%。

注意：这不是真正的死锁（没有锁），而是死循环。

JDK 1.8 的问题

JDK 1.8 用尾插法解决了扩容死循环问题，但仍然线程不安全，有以下问题：

1. 数据丢失（并发 put 覆盖）

两个线程同时 put，计算出同一个桶位置。
线程 A 遍历到链表末尾，准备插入新节点。
线程 B 也遍历到链表末尾，先插入了新节点。
线程 A 接着插入，覆盖了线程 B 的插入。
结果：线程 B 的数据丢失了。

2. size 不准确

size++ 不是原子操作（读-改-写三步）。
多个线程并发增加 size，会导致计数不准确。

3. 并发 put 和 get 可能 get 到 null

扩容过程中，另一个线程 get，可能读到中间状态的数据。
比如元素正在迁移，旧桶已置空但新桶还没放好，此时 get 返回 null。

4. 其他问题

modCount 计数不准确，可能导致 fail-fast 误判或漏判。
红黑树的并发修改可能导致树结构损坏。

总结

问题	JDK 1.7	JDK 1.8
扩容死循环	有	无（尾插法修复）
数据丢失	有	有
size 不准确	有	有
并发读写异常	有	有

解决方案

Hashtable：全表加 synchronized，性能差，不推荐。
Collections.synchronizedMap：包装 HashMap，方法加 synchronized，和 Hashtable 类似，性能差。
ConcurrentHashMap：分段/分段锁 + CAS，并发性能好，推荐使用。
读写锁实现：自己用 ReentrantReadWriteLock 包装，适合读多写少。

最佳实践：

单线程：用 HashMap。
多线程：用 ConcurrentHashMap。
需要排序：用 TreeMap 或 ConcurrentSkipListMap。
不要在多线程中使用 HashMap！

追问延伸：

JDK 1.7 HashMap 扩容死循环的具体过程？（头插法导致链表反转，并发下成环）
为什么 JDK 1.8 不会死循环了但还是线程不安全？（尾插法解决了成环问题，但还有数据覆盖、size 不准确等问题）
多线程下应该用什么代替 HashMap？（ConcurrentHashMap）
ConcurrentHashMap 的实现原理？（下一题详解）
Hashtable 和 ConcurrentHashMap 的区别？（全表锁 vs 分段锁/CAS；性能差异；null key/value 限制）
你在项目中遇到过 HashMap 并发问题吗？怎么解决的？

Q7: ConcurrentHashMap 的实现原理？JDK 1.7 和 1.8 有什么区别？「🔴 高级」

考察点：对并发集合核心实现的深度理解，分段锁、CAS、synchronized 锁升级等并发编程知识。筛掉对并发原理一知半解的人。

参考答案：

ConcurrentHashMap 是线程安全的 HashMap，JDK 1.7 和 1.8 的实现差异很大。

JDK 1.7 —— 分段锁（Segment）

结构

外层是 Segment 数组，每个 Segment 继承自 ReentrantLock，是一个独立的哈希表（HashEntry 数组 + 链表）。
默认有 16 个 Segment，理论上最多支持 16 个线程并发写（每个写一个 Segment）。

Segment[] segments
├── Segment[0] → HashEntry[] → 链表
├── Segment[1] → HashEntry[] → 链表
├── ...
└── Segment[15] → HashEntry[] → 链表

并发原理

写操作：先根据 hash 定位到 Segment，对该 Segment 加锁（ReentrantLock），然后操作内部的 HashEntry 数组。
读操作：不加锁（用 volatile 保证可见性），因为 HashEntry 的 value 和 next 都是 volatile 的。
size()：先不加锁统计两次，如果两次 modCount 相同则返回结果；如果不同，则锁住所有 Segment 再统计（代价大）。

优缺点

优点：相比 Hashtable 的全表锁，粒度更细，并发度更高。
缺点：
- 分段数固定（初始化后不能再改），并发度有限。
- 空间浪费（每个 Segment 是独立的哈希表）。
- size() 操作在并发大时需要全表加锁，性能差。

JDK 1.8 —— CAS + synchronized 锁桶头

结构

和 HashMap 结构类似：数组 + 链表 + 红黑树。
不再用 Segment 分段锁，而是用 CAS + synchronized 锁桶头节点，粒度更细（锁单个桶）。
节点类型：Node（链表）、TreeNode（红黑树）、ForwardingNode（扩容标记）。

并发原理

put 操作

计算 hash，定位桶。
桶为空？用 CAS 尝试设置头节点，成功则结束，失败则自旋重试。
桶不为空？
- 如果头节点是 ForwardingNode（正在扩容），则帮助扩容（helpTransfer）。
- 否则，synchronized 锁住桶头节点，然后遍历链表/红黑树插入或更新。
插入完成后，检查是否需要转红黑树。
addCount 计数并检查是否需要扩容。

get 操作

不需要加锁！
因为 Node 的 val 和 next 都是 volatile 的，保证可见性。
扩容过程中，如果发现是 ForwardingNode，就去新数组找。
遍历过程中可能读到旧值（弱一致性），但不会读到错误的结构。

扩容（transfer）

多线程协助扩容：一个线程触发扩容后，其他线程 put 时发现正在扩容，也会来帮忙（helpTransfer）。
每个线程领取一段区间的桶迁移任务，并发迁移。
迁移完成的桶用 ForwardingNode 标记，表示已迁移。

size() 计算

用 baseCount + CounterCell 数组 来计数。
没有竞争时直接 CAS 更新 baseCount。
有竞争时，线程根据 probe 哈希到不同的 CounterCell 上 CAS 更新。
size() 就是把 baseCount 和所有 CounterCell 的值加起来。
这是一个估计值（弱一致性），不是精确值。

为什么用 synchronized 而不是 ReentrantLock

JDK 1.8 对 synchronized 做了很多优化（偏向锁、轻量级锁、锁粗化、锁消除），性能已经很好。
synchronized 是 JVM 内置的，更容易优化。
锁粒度已经很小（只锁桶头），synchronized 足够用。
减少内存开销（不需要每个节点都关联一个锁对象）。

JDK 1.7 vs 1.8 对比总结

维度	JDK 1.7	JDK 1.8
底层结构	Segment 数组 + HashEntry 数组 + 链表	Node 数组 + 链表 + 红黑树
锁实现	ReentrantLock（分段锁）	CAS + synchronized（锁桶头）
锁粒度	Segment 段	单个桶（链表头/树根）
并发度	默认 16（Segment 数量）	数组长度（更高）
红黑树	无	有（链表过长时优化）
扩容	单线程扩容	多线程协助扩容
size 计算	两次统计对比，失败则全加锁	baseCount + CounterCell，近似值
性能	较低	较高

其他重要问题

为什么不允许 null key / null value？

HashMap 允许 null key 和 null value，但 ConcurrentHashMap 不允许。
原因：在并发环境下，get(key) 返回 null 有两种可能：
1. key 不存在。
2. value 就是 null。
在单线程下可以用 containsKey 区分，但并发下可能 get 后 key 被删了，无法区分。
为了语义清晰，ConcurrentHashMap 禁止 null value（null key 同理）。

get 方法是否需要加锁？

不需要。
Node 的 val 和 next 都是 volatile 的，保证可见性。
数组 table 也是 volatile 的（通过 Unsafe 操作保证可见性）。
所以 get 能读到最新的值（至少是最近的），但可能是弱一致的（扩容过程中可能读到旧数据）。

追问延伸：

ConcurrentHashMap 的 put 流程？（上面已详述）
为什么 JDK 1.8 放弃了分段锁？（锁粒度更细、并发度更高、红黑树优化、代码更简洁）
ConcurrentHashMap 怎么保证线程安全？（CAS 乐观锁 + synchronized 悲观锁 + volatile 可见性）
size() 方法是怎么实现的？是精确值吗？（baseCount + CounterCell，近似值，弱一致性）
ConcurrentHashMap 和 Hashtable 的区别？（锁粒度、性能、null 限制、底层结构）
ConcurrentHashMap 的扩容过程？（多线程协助、分段迁移、ForwardingNode 标记）
什么是弱一致性？和 fail-safe 有什么关系？（迭代器不会抛 ConcurrentModificationException，因为遍历的是当时的快照或结构）
ConcurrentHashMap 的 key 和 value 为什么不能为 null？

Q8: HashSet 的实现原理？和 HashMap 的关系？「🟢 校招/初级」

考察点：对 Set 实现的理解，是否清楚 HashSet 底层就是 HashMap。筛掉以为 HashSet 是独立实现的人。

参考答案：

HashSet 底层就是 HashMap

HashSet 底层基于 HashMap 实现，使用 HashMap 的 key 来存储元素，value 是一个固定的 Object 对象。
这是典型的组合复用模式。

java

// HashSet 源码
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;
    
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
    
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    public int size() {
        return map.size();
    }
}

核心要点

底层存储：元素存储在 HashMap 的 key 中。
value 占位：所有 key 对应的 value 都是同一个 PRESENT 对象（静态 final），节省内存。
去重原理：利用 HashMap 的 key 不能重复的特性。
- 先比较 hashCode，再比较 equals。
- 所以放入 HashSet 的元素必须正确实现 equals 和 hashCode 方法。
无序：因为 HashMap 的 key 是无序的，所以 HashSet 也是无序的。
允许一个 null：HashMap 允许一个 null key，所以 HashSet 也允许一个 null 元素。
非线程安全：HashMap 非线程安全，所以 HashSet 也非线程安全。
迭代器 fail-fast：和 HashMap 一样，并发修改会抛 ConcurrentModificationException。

HashSet 和 HashMap 的关系

维度	HashSet	HashMap
接口	Set	Map
存储内容	单个元素	键值对
底层实现	内部持有 HashMap	哈希表（数组+链表+红黑树）
添加方法	add(e) → map.put(e, PRESENT)	put(key, value)
去重依据	hashCode + equals（key 不重复）	key 不重复
遍历方式	Iterator（遍历 key）	keySet / entrySet / values
null 元素	允许一个 null	key 允许一个 null，value 允许多个 null

为什么 HashSet 允许 null

因为 HashMap 允许一个 null key（hash 值为 0，放在第 0 个桶）。
HashSet 复用了这个特性，所以可以放一个 null 元素。

LinkedHashSet 和 TreeSet

LinkedHashSet：继承自 HashSet，底层是 LinkedHashMap，保持插入顺序。
TreeSet：底层是 TreeMap，基于红黑树，元素有序（自然排序或定制排序）。

Set 去重原理

添加元素时，先计算元素的 hashCode，定位到桶。
如果桶为空，直接添加。
如果桶不为空，遍历链表/红黑树，逐个比较：
- hashCode 不同 → 不是同一个元素，继续。
- hashCode 相同 → 再用 equals 比较：
  - equals 相同 → 认为是同一个元素，不添加，返回 false。
  - equals 不同 → 不是同一个元素，添加到链表/树中。

所以：两个对象 equals 相等，hashCode 必须相等；hashCode 相等，equals 不一定相等。

追问延伸：

HashSet 怎么保证元素不重复？（利用 HashMap key 不重复的特性，hashCode + equals）
往 HashSet 中放自定义对象要注意什么？（必须重写 equals 和 hashCode）
HashSet 是有序的吗？有没有有序的 Set？（HashSet 无序；LinkedHashSet 按插入顺序；TreeSet 按排序顺序）
HashSet 的 add 方法返回值是什么意思？（true 表示添加成功，false 表示元素已存在）
HashMap 和 HashSet 有什么关系和区别？
你在项目中什么时候用 Set？（去重、判断存在性、集合运算）

Q9: LinkedHashMap 的原理和应用场景？「🟡 中级」

考察点：对 LinkedHashMap 底层结构的理解，双向链表维护顺序的机制，LRU 缓存的实现。筛掉不知道 LinkedHashMap 能做什么的人。

参考答案：

基本概念

LinkedHashMap 继承自 HashMap，在 HashMap 的基础上，额外维护了一条双向链表，用于保持元素的顺序。

继承 HashMap，拥有 HashMap 的所有特性。
额外维护了 head（头）和 tail（尾）指针的双向链表。
每个 Entry 除了 hash、key、value、next（HashMap 的链表指针），还有 before、after（双向链表指针）。

两种顺序模式

1. 插入顺序（默认）

accessOrder = false（默认值）。
按照元素插入的顺序排列，新插入的元素放在双向链表尾部。
注意：如果是更新已有的 key（put 相同 key），不会改变顺序。

2. 访问顺序

accessOrder = true（构造方法指定）。
每次访问（get/put）元素后，该元素会被移到双向链表的尾部（最近访问的在尾部，最久未访问的在头部）。
这是实现 LRU 缓存 的基础。

底层原理

Entry 结构

java

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 双向链表指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

继承自 HashMap.Node，增加了 before 和 after 指针。

关键回调方法

LinkedHashMap 通过重写 HashMap 中的几个空方法（钩子方法）来维护双向链表：

方法	调用时机	LinkedHashMap 中的作用
`afterNodeAccess`	节点被访问时（get/put 已有 key）	将节点移到链表尾部（accessOrder=true 时）
`afterNodeInsertion`	新节点插入后	可能删除最老节点（removeEldestEntry 判断）
`afterNodeRemoval`	节点被删除后	从双向链表中移除节点

java

// afterNodeAccess：访问节点后移到尾部
void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
        LinkedHashMap.Entry<K,V> b = p.before, a = p.after;
        p.after = null;
        // 从原位置移除
        if (b == null) head = a;
        else b.after = a;
        if (a != null) a.before = b;
        else last = b;
        // 放到尾部
        if (last == null) head = p;
        else { p.before = last; last.after = p; }
        tail = p;
        modCount++;
    }
}

LRU 缓存实现

LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略：当缓存满了，优先淘汰最久没被访问的数据。

利用 LinkedHashMap 实现 LRU 缓存非常简单：

java

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;  // 缓存容量
    
    public LRUCache(int capacity) {
        // accessOrder = true 开启访问顺序
        // initialCapacity 和 loadFactor 用默认值
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    // 重写此方法，返回 true 时删除最老的节点
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

// 使用
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");
cache.get(1);      // 访问 1，移到尾部
cache.put(4, "d"); // 超出容量，删除最久未访问的 2
// 此时缓存中：3, 1, 4（按访问顺序从老到新）

应用场景

LRU 缓存：最经典的应用，如上所示。
保持插入顺序：需要记住元素插入顺序的场景（如配置解析、顺序处理）。
FIFO 队列：插入顺序模式下，可以当 FIFO 用。
缓存淘汰策略实现：基于访问顺序实现各种缓存策略。

性能

插入、删除、查找的时间复杂度和 HashMap 一样，都是 O(1) 平均。
因为要维护双向链表，所以插入删除比 HashMap 稍慢一点（多了链表指针操作），但仍然很快。
遍历性能比 HashMap 好，因为只需要遍历双向链表，不用遍历整个数组。

线程安全

和 HashMap 一样，LinkedHashMap 也是非线程安全的。
并发环境下可以用 Collections.synchronizedMap 包装，或者自己加锁。
并发场景下的 LRU 缓存可以考虑用 Caffeine 或 Guava Cache。

追问延伸：

LinkedHashMap 怎么保证插入顺序的？（双向链表 + afterNodeInsertion 等钩子方法）
accessOrder=true 时，get 操作会做什么？（将元素移到链表尾部）
怎么用 LinkedHashMap 实现 LRU 缓存？（继承 + 重写 removeEldestEntry）
LinkedHashMap 和 HashMap 的区别？（双向链表、有序、性能略低）
LRU 缓存的原理是什么？除了 LinkedHashMap 还有什么实现方式？（HashMap + 手动维护双向链表）
LRU 和 LFU 的区别？（LRU 最近最少使用，LFU 最不经常使用）
你在项目中用过 LRU 缓存吗？在什么场景下用的？

Q10: TreeMap 和 TreeSet 的原理？「🟡 中级」

考察点：对红黑树数据结构的理解，排序比较的机制，TreeMap/TreeSet 的应用场景。筛掉对树结构一窍不通的人。

参考答案：

TreeMap 原理

TreeMap 是基于红黑树实现的有序 Map，key 按自然排序或定制排序排列。

底层结构

每个节点是 Entry<K,V>，包含 key、value、left、right、parent、color。
红黑树是一种自平衡的二叉搜索树（BST），保证任何节点的左右子树高度差不超过 1 倍。

红黑树的 5 条规则

节点是红色或黑色。
根节点是黑色。
叶子节点（NIL 空节点）是黑色。
红色节点的两个子节点都是黑色（不能有连续的红色）。
从任一节点到其每个叶子的所有路径包含相同数量的黑色节点。

通过这些规则保证树的平衡，最长路径不超过最短路径的 2 倍。

时间复杂度

操作	时间复杂度
put	O(log n)
get	O(log n)
remove	O(log n)
查找最值	O(log n)（或 O(1) 有缓存）

排序方式

1. 自然排序（Comparable）

key 必须实现 Comparable 接口，实现 compareTo 方法。
如 String、Integer 等都实现了 Comparable。

java

public interface Comparable<T> {
    int compareTo(T o);  // 返回负数：小；0：相等；正数：大
}

2. 定制排序（Comparator）

构造 TreeMap 时传入 Comparator 对象。
优先级比自然排序高（如果有 Comparator 就用它，否则用 key 的 Comparable）。

java

TreeMap<String, Integer> map = new TreeMap<>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);  // 倒序
    }
});

两种方式对比

方式	接口	位置	灵活性
自然排序	Comparable	元素类实现 compareTo	固定一种排序
定制排序	Comparator	外部传入比较器	灵活，可多种排序

TreeMap 常用方法

方法	说明
`firstKey()` / `lastKey()`	最小/最大的 key
`firstEntry()` / `lastEntry()`	最小/最大的 entry
`pollFirstEntry()` / `pollLastEntry()`	弹出并返回最小/最大 entry
`lowerKey(K)` / `higherKey(K)`	小于/大于给定 key 的最大/最小 key
`floorKey(K)` / `ceilingKey(K)`	小于等于/大于等于给定 key 的最大/最小 key
`subMap(from, to)`	子 Map（前闭后开）
`headMap(to)` / `tailMap(from)`	头部/尾部子 Map
`descendingMap()`	逆序视图

TreeSet 原理

TreeSet 底层基于 TreeMap，和 HashSet 类似，value 是固定的 PRESENT 对象。
元素是有序的（排序顺序）。
元素必须实现 Comparable 或构造时传入 Comparator。
不允许 null 元素（因为要比较排序）。

TreeMap vs HashMap

维度	TreeMap	HashMap
底层结构	红黑树	数组 + 链表 + 红黑树
有序性	有序（排序）	无序
时间复杂度	O(log n)	O(1) 平均，O(n) 最坏
性能	较低（树操作）	较高
内存	较大（树节点开销）	较小（数组为主）
适用场景	需要排序、范围查找	通用 key-value 存储
null key	不允许（要比较）	允许一个

TreeSet vs HashSet

维度	TreeSet	HashSet
底层结构	TreeMap（红黑树）	HashMap（哈希表）
有序性	有序（排序）	无序
时间复杂度	O(log n)	O(1) 平均
元素要求	必须可比较（Comparable/Comparator）	需 equals/hashCode
null 元素	不允许	允许一个
适用场景	需要排序的集合	通用去重、查找

追问延伸：

TreeMap 的底层数据结构是什么？（红黑树）为什么用红黑树不用 AVL 树？（红黑树插入删除更快，AVL 查找更快；红黑树通过颜色调整减少旋转次数，更适合插入删除频繁的场景）
Comparable 和 Comparator 的区别？
TreeMap 怎么判断两个 key 相等？（compare/compareTo 返回 0 就认为相等，和 equals 不一定一致）
TreeMap 支持 null key 吗？为什么？（默认不支持，因为要比较；如果自定义 Comparator 支持 null 比较，就可以）
红黑树的插入/删除过程是怎样的？（插入后可能需要左旋/右旋/变色来维持平衡）
你在项目中用过 TreeMap/TreeSet 吗？在什么场景下用的？
如何实现一个按 value 排序的 Map？（将 entrySet 放入 List 中用 Collections.sort 排序；或用 TreeMap 但 key 是 value）

Q11: CopyOnWriteArrayList 的原理？适用场景？「🟡 中级」

考察点：对并发集合的理解，写时复制思想的应用，读写分离的设计思路。筛掉对并发集合只会用 synchronizedList 的人。

参考答案：

基本概念

CopyOnWriteArrayList 是 java.util.concurrent 包下的线程安全 List，基于 写时复制（Copy-On-Write, COW） 思想实现。

核心思想：读写分离。读操作完全不加锁，写操作时复制一份新数组，在新数组上修改，修改完再把引用指向新数组。
这是一种读多写少场景下的优化策略。

底层原理

数据结构

java

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 可重入锁，保护写操作
    final transient ReentrantLock lock = new ReentrantLock();
    
    // 底层数组，volatile 保证可见性
    private transient volatile Object[] array;
    
    final Object[] getArray() { return array; }
    final void setArray(Object[] a) { array = a; }
}

底层是 Object[] array，用 volatile 修饰，保证引用的可见性。
写操作使用 ReentrantLock 加锁，保证同一时间只有一个写操作。

读操作（get）

java

public E get(int index) {
    return get(getArray(), index);
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

无锁！直接读取当前数组，不需要加锁。
因为数组引用是 volatile 的，能保证读到最新的数组引用。
读操作性能极高，和普通 ArrayList 差不多。

写操作（add / set / remove）

以 add 为例：

java

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();  // 加锁
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 1. 复制一份新数组（长度 + 1）
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 2. 在新数组上修改
        newElements[len] = e;
        // 3. 替换引用（volatile 写，保证可见性）
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();  // 解锁
    }
}

写操作的步骤：

加锁（ReentrantLock），保证写操作互斥。
复制当前数组，生成一个新数组（长度 + 1）。
在新数组上做修改。
将 array 引用指向新数组。
解锁。

核心特点

特点	说明
线程安全	写加锁 + 数组不可变 + volatile 可见性
读无锁	读操作完全不加锁，性能极高
写有锁	写操作加 ReentrantLock，且需要复制数组
最终一致	读写不互斥，读可能读到旧数据（弱一致性）
内存占用	写操作会复制整个数组，内存占用翻倍
迭代器安全	迭代的是快照，不会抛 ConcurrentModificationException

优缺点

优点

读性能极高：读操作无锁，和普通 ArrayList 差不多，适合读多写少。
线程安全：并发环境下安全使用。
迭代安全：Fail-Safe，不会抛 ConcurrentModificationException，因为迭代的是快照。

缺点

内存占用大：每次写操作都要复制整个数组，数据量大时内存压力大。
写性能差：写操作需要加锁 + 数组复制，频繁写性能很差。
数据一致性：只能保证最终一致，不能保证实时一致（读可能读到旧数据）。

适用场景

读多写少的场景：

白名单/黑名单：配置项，几乎不修改，频繁查询。
配置列表：系统配置，启动时加载，运行中很少修改。
监听器列表：注册一次，频繁遍历调用。
缓存数据：读多写少的缓存场景。

不适用场景：

写操作频繁的场景（性能差、内存占用大）。
对数据实时一致性要求高的场景（读可能读到旧值）。
数据量很大的场景（数组复制开销大）。

CopyOnWriteArraySet

类似地，CopyOnWriteArraySet 底层基于 CopyOnWriteArrayList 实现。
add 时先遍历检查是否已存在，不存在才添加。
所以 add 是 O(n) 的，比 HashSet 慢很多。
也只适合读多写少的小集合去重场景。

和 synchronizedList 对比

维度	CopyOnWriteArrayList	Collections.synchronizedList
读操作	无锁，性能高	加锁，性能低
写操作	加锁 + 数组复制，性能低	加锁，性能中等
内存占用	高（写时复制整个数组）	低（只有一份数据）
一致性	最终一致（弱一致）	强一致
迭代器	Fail-Safe（快照迭代）	Fail-Fast（需手动加锁）
适用场景	读多写少	通用读写均衡场景

追问延伸：

CopyOnWriteArrayList 的实现原理？（写时复制，读无锁写加锁）
为什么读操作不需要加锁？（数组引用是 volatile 的，数组一旦创建就不会修改，所以读是安全的）
CopyOnWriteArrayList 的迭代器是 Fail-Fast 还是 Fail-Safe？为什么？（Fail-Safe，迭代的是快照，不会抛 ConcurrentModificationException）
CopyOnWriteArrayList 适用于什么场景？（读多写少）
CopyOnWriteArrayList 的 add 是怎么保证线程安全的？（ReentrantLock 加锁 + 复制数组 + volatile 替换引用）
写时复制有什么缺点？（内存占用大、写性能差、数据最终一致）
你在项目中用过 CopyOnWriteArrayList 吗？在什么场景下用的？
什么是弱一致性？和强一致性有什么区别？

Q12: 什么是 Fail-Fast 和 Fail-Safe？「🟡 中级」

考察点：对集合迭代机制的理解，modCount 检测原理，快速失败和安全失败的区别。筛掉对并发修改异常一知半解的人。

参考答案：

Fail-Fast（快速失败）

概念

Fail-Fast 是 Java 集合的一种错误检测机制。在用迭代器遍历集合的过程中，如果集合的结构被修改了（增加、删除元素），迭代器会立即抛出 ConcurrentModificationException。

"快速失败"：一发现问题就立即报错，而不是等到之后出更严重的问题。
这是一种保护机制，防止在不确定的状态下继续运行。

实现原理 —— modCount

集合中有一个 modCount 字段（修改次数），每次结构性修改（add/remove/clear 等）都会让 modCount++。
迭代器创建时，会记录当时的 expectedModCount = modCount。
每次迭代器调用 next() 时，都会检查 modCount == expectedModCount：
- 相等：继续迭代。
- 不相等：抛出 ConcurrentModificationException。

java

// ArrayList.Itr 迭代器源码（简化）
private class Itr implements Iterator<E> {
    int expectedModCount = modCount;  // 记录初始 modCount
    
    public E next() {
        checkForComodification();     // 每次 next 都检查
        // ...
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

触发场景

单线程下，用 for-each 遍历集合时调用集合的 remove/add 方法（不是迭代器的）。
多线程下，一个线程遍历集合，另一个线程修改集合结构。

常见的 Fail-Fast 集合

ArrayList、LinkedList、HashMap、HashSet、TreeMap 等 java.util 包下的非并发集合。

注意事项

Fail-Fast 只是尽力而为的机制，不保证一定检测到（JDK 文档明确说明不能依赖它做并发控制）。
迭代器自己的 remove() 方法不会触发异常，因为它会同步更新 expectedModCount。

java

// 正确：用迭代器的 remove
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (condition) {
        it.remove();  // OK，迭代器自己的 remove，会更新 expectedModCount
    }
}

// 错误：for-each 中调用集合的 remove（会抛 ConcurrentModificationException）
for (String s : list) {
    if (condition) {
        list.remove(s);  // ERROR
    }
}

Fail-Safe（安全失败）

概念

Fail-Safe 指的是迭代器遍历的是集合的一个快照（副本），集合在遍历过程中被修改不会影响迭代器，不会抛出 ConcurrentModificationException。

"安全失败"：遍历是安全的，不会因为并发修改而失败。
代价是数据一致性：迭代器遍历的是开始时的快照，可能读到旧数据。

实现方式

写时复制：如 CopyOnWriteArrayList，迭代的是不变的数组快照。
弱一致迭代器：如 ConcurrentHashMap 的迭代器，遍历过程中集合修改可能可见也可能不可见，但不会抛异常。

常见的 Fail-Safe 集合

CopyOnWriteArrayList、CopyOnWriteArraySet
ConcurrentHashMap、ConcurrentSkipListMap
ConcurrentLinkedQueue
整个 java.util.concurrent 包下的集合基本都是 Fail-Safe 的。

Fail-Fast vs Fail-Safe 对比

维度	Fail-Fast	Fail-Safe
并发修改异常	会抛出 ConcurrentModificationException	不会抛出
遍历对象	原集合	集合快照（或弱一致）
内存占用	低（直接遍历原集合）	高（可能需要复制一份）
数据一致性	强（遍历过程中修改就报错）	弱（可能读到旧数据）
实现原理	modCount 检测	写时复制 / 弱一致
典型集合	ArrayList、HashMap 等	CopyOnWriteArrayList、ConcurrentHashMap 等
包	java.util	java.util.concurrent

常见问题

Q：for-each 遍历中删除元素为什么会抛异常？

A：for-each 底层是迭代器，删除元素用的是集合的 remove 方法，会导致 modCount++，但迭代器的 expectedModCount 没变，所以 next() 时检测到不一致就抛异常。

Q：为什么用迭代器的 remove 就没问题？

A：迭代器的 remove 方法在删除元素后，会同步更新 expectedModCount = modCount，所以检测时是一致的。

Q：多线程环境下遍历 ArrayList 一定会抛异常吗？

A：不一定。Fail-Fast 是尽力而为的，如果修改刚好发生在两次检查之间，可能检测不到。不能依赖这个机制做并发控制。

Q：Fail-Safe 就是完全安全的吗？

A：不是。它只是不会抛异常，但可能读到旧数据（弱一致性）。如果业务需要强一致性，还是要加锁。

追问延伸：

什么是 Fail-Fast？实现原理是什么？（modCount 检测）
什么是 Fail-Safe？有哪些集合是 Fail-Safe 的？
ConcurrentModificationException 是什么情况下抛出的？
迭代器的 remove 和集合的 remove 有什么区别？
怎么在遍历 List 的时候安全地删除元素？（迭代器的 remove、Java 8 的 removeIf、倒序 for 循环）
Fail-Fast 一定能检测到并发修改吗？（不一定，尽力而为）
你在项目中遇到过 ConcurrentModificationException 吗？怎么解决的？

Q13: Java 中的阻塞队列有哪些？有什么区别？「🟡 中级」

考察点：对并发工具类阻塞队列的掌握，各种实现的区别和应用场景。筛掉对并发编程工具不熟悉的人。

参考答案：

阻塞队列（BlockingQueue）是支持两个附加操作的队列：

阻塞插入：队列满时，插入元素的线程被阻塞，直到队列有空间。
阻塞移除：队列空时，移除元素的线程被阻塞，直到队列有元素。

阻塞队列是线程安全的，常用于生产者-消费者模式、线程池等场景。

阻塞队列的核心方法

操作	抛出异常	返回特殊值	阻塞	超时退出
插入	add(e)	offer(e)	put(e)	offer(e, time, unit)
移除	remove()	poll()	take()	poll(time, unit)
检查	element()	peek()	不支持	不支持

常见阻塞队列对比

队列	底层结构	是否有界	锁实现	特点	适用场景
ArrayBlockingQueue	数组	有界（必须指定容量）	一把 ReentrantLock	简单经典，有界	固定容量的生产者消费者
LinkedBlockingQueue	链表	可选有界（默认 Integer.MAX_VALUE）	两把锁（takeLock + putLock）	高并发，两把锁互不干扰	线程池默认队列（无界版有 OOM 风险）
SynchronousQueue	不存储元素	0 容量	CAS + 栈/队列	直接传递，不存储	CachedThreadPool 用的队列
PriorityBlockingQueue	数组（二叉堆）	无界（自动扩容）	一把 ReentrantLock	按优先级出队	优先级任务调度
DelayQueue	PriorityQueue 封装	无界	一把 ReentrantLock	延迟出队，按到期时间排序	定时任务、超时检测
LinkedTransferQueue	链表	无界	CAS + 自旋	可 transfer 直接传递，性能好	高性能无界队列
LinkedBlockingDeque	双向链表	可选有界	一把 ReentrantLock	双端操作，可做工作窃取	工作窃取算法

各队列详解

1. ArrayBlockingQueue

底层：数组实现的有界阻塞队列。
特点：
- 必须指定容量，创建后不能改。
- 一把 ReentrantLock + 两个 Condition（notEmpty、notFull）。
- 公平锁/非公平锁可选（默认非公平）。
适用：需要限制队列大小的场景。

java

ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(100);  // 容量 100

2. LinkedBlockingQueue

底层：单链表实现的阻塞队列。
特点：
- 默认容量是 Integer.MAX_VALUE（无界，可能 OOM），也可以指定容量。
- 两把锁：takeLock（读锁）和 putLock（写锁），读写互不干扰，并发度更高。
- 用 AtomicInteger 统计元素数量。
适用：吞吐量要求高的场景。线程池的 FixedThreadPool 用的就是这个（无界版）。

3. SynchronousQueue

底层：不存储元素，直接传递。
特点：
- 容量为 0，put 一个元素必须等另一个线程 take，反之亦然。
- 支持公平模式（队列）和非公平模式（栈，默认）。
- 性能很高，因为不需要存储。
适用：一对一传递的场景。CachedThreadPool 用的就是这个。

4. PriorityBlockingQueue

底层：基于数组实现的二叉堆（优先级队列），无界。
特点：
- 元素必须可比较（实现 Comparable 或传入 Comparator）。
- 按优先级出队，不是 FIFO。
- 无界（自动扩容），put 永远不会阻塞（可能 OOM）。
- 一把锁 + 一个 notEmpty Condition（因为无界所以不需要 notFull）。
适用：优先级任务调度。

5. DelayQueue

底层：封装 PriorityQueue，按延迟时间排序。
特点：
- 元素必须实现 Delayed 接口，实现 getDelay(TimeUnit unit) 方法。
- 只有延迟到期的元素才能出队。
- 无界队列。
- 队首是最早到期的元素。
适用：定时任务、超时订单关闭、缓存过期等。

java

class DelayedTask implements Delayed {
    private long expireTime;
    
    public DelayedTask(long delayMillis) {
        this.expireTime = System.currentTimeMillis() + delayMillis;
    }
    
    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(expireTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
    }
    
    @Override
    public int compareTo(Delayed o) {
        return Long.compare(this.expireTime, ((DelayedTask) o).expireTime);
    }
}

应用场景

生产者-消费者模式：最经典的应用，生产者往队列里放，消费者从队列里取，解耦生产和消费。
线程池：线程池的工作队列就是阻塞队列（不同线程池用不同的队列实现）。
异步任务处理：任务提交到队列，工作线程异步处理。
流量削峰：请求先放入队列，后端按处理能力消费，防止系统被冲垮。
数据采集/日志处理：采集端（生产者）→ 阻塞队列 → 处理端（消费者）。

线程池和阻塞队列的关系

线程池	工作队列	说明
FixedThreadPool	LinkedBlockingQueue（无界）	无界队列，线程数固定
SingleThreadExecutor	LinkedBlockingQueue（无界）	单线程 + 无界队列
CachedThreadPool	SynchronousQueue	直接传递，线程数弹性
ScheduledThreadPool	DelayedWorkQueue（延迟队列）	定时任务

追问延伸：

什么是阻塞队列？有哪些核心方法？
ArrayBlockingQueue 和 LinkedBlockingQueue 的区别？（数组 vs 链表、有界 vs 可选有界、一把锁 vs 两把锁）
SynchronousQueue 的原理？为什么不存储元素还叫队列？（直接传递，生产者等消费者，消费者等生产者）
DelayQueue 的实现原理？应用场景？（基于 PriorityQueue，按延迟时间排序，元素必须实现 Delayed 接口）
阻塞队列的 put 和 take 是怎么实现阻塞和唤醒的？（Lock + Condition，await/signal）
你在项目中用过阻塞队列吗？在什么场景下用的？
有界队列和无界队列的选型？无界队列有什么风险？（OOM 风险）
什么是生产者-消费者模式？怎么用阻塞队列实现？

Q14: 如何正确地选择集合？有什么选型原则？「🟡 中级」

考察点：对集合框架的整体把控能力，是否能根据场景合理选型。筛掉只会用 ArrayList 和 HashMap 的人。

参考答案：

集合选型是面试中常考的开放式问题，考察对集合的整体理解和实战经验。以下是系统的选型思路。

选型决策树

需要集合吗？
    ├── 是 → 单列还是双列？
    │       ├── 单列（Collection） → 元素是否允许重复？
    │       │   ├── 允许重复（List） → 是否需要随机访问？
    │       │   │   ├── 是 → ArrayList（首选）
    │       │   │   └── 否 → 头尾操作多用 LinkedList/ArrayDeque
    │       │   └── 不允许重复（Set） → 是否需要排序？
    │       │       ├── 是 → TreeSet
    │       │       ├── 否 → 是否需要插入顺序？
    │       │           ├── 是 → LinkedHashSet
    │       │           └── 否 → HashSet（首选）
    │       └── 双列（Map） → 是否需要排序？
    │           ├── 是 → TreeMap
    │           ├── 否 → 是否需要插入/访问顺序？
    │               ├── 是 → LinkedHashMap
    │               └── 否 → HashMap（首选）
    └── 否 → 用数组或单个变量

详细选型原则

1. 单列 vs 双列

单列（Collection）：只存单个元素 → 选 List/Set/Queue。
双列（Map）：存键值对 → 选 HashMap/TreeMap 等。

2. List 选型（元素可重复、有序）

场景	推荐	原因
通用场景、随机访问多	ArrayList	数组实现，随机访问 O(1)，缓存友好
频繁头尾增删、当栈/队列用	ArrayDeque	双端队列，数组实现，比 LinkedList 快
需要 List + 频繁头尾操作	LinkedList	双向链表，但实际用得少
读多写少 + 多线程	CopyOnWriteArrayList	读无锁，写时复制
多线程通用 + 有界队列	ArrayBlockingQueue	有界阻塞队列
多线程高吞吐队列	LinkedBlockingQueue	两把锁，吞吐高

List 选型要点：

90% 以上场景用 ArrayList 就够了。
能用 ArrayList 就不用 LinkedList（链表缓存不友好，实际性能多数情况下不如 ArrayList）。
栈/队列优先用 ArrayDeque，不用 LinkedList（ArrayDeque 更快）。

3. Set 选型（元素不可重复）

场景	推荐	原因
通用去重、查找	HashSet	哈希表，O(1) 平均
需要排序	TreeSet	红黑树，O(log n)，有序
需要插入顺序	LinkedHashSet	哈希表 + 双向链表
读多写少 + 多线程	CopyOnWriteArraySet	写时复制
多线程并发去重	ConcurrentHashMap.newKeySet()	基于 ConcurrentHashMap

4. Map 选型（键值对）

场景	推荐	原因
通用 key-value	HashMap	O(1) 平均，性能最好
需要排序	TreeMap	红黑树，O(log n)，支持范围查找
需要插入/访问顺序	LinkedHashMap	可实现 LRU 缓存
多线程并发	ConcurrentHashMap	分段锁/CAS，高并发性能好
多线程 + 有序	ConcurrentSkipListMap	跳表，并发有序

5. 队列选型

场景	推荐	原因
普通栈/队列（单线程）	ArrayDeque	数组双端队列，性能好
有界阻塞队列	ArrayBlockingQueue	数组实现，容量固定
高吞吐阻塞队列	LinkedBlockingQueue	两把锁，吞吐高
直接传递（不存储）	SynchronousQueue	0 容量，直接交换
优先级队列	PriorityQueue / PriorityBlockingQueue	堆实现
延迟队列	DelayQueue	按延迟时间出队
非阻塞并发队列	ConcurrentLinkedQueue	CAS 实现，高并发

选型时需要考虑的因素

数据量大小：
- 数据量大：注意初始容量设置，减少扩容。
- 数据量小：随便选，差异不大。
读写比例：
- 读多写少：CopyOnWriteArrayList、读写锁。
- 写多读多：ConcurrentHashMap、ConcurrentLinkedQueue。
- 写少读少：普通集合就行。
是否需要排序：
- 需要：TreeMap/TreeSet（排序顺序）、LinkedHashMap/LHS（插入顺序）。
- 不需要：HashMap/HashSet（性能更好）。
是否需要线程安全：
- 单线程：普通集合（HashMap、ArrayList）。
- 多线程：并发包集合（ConcurrentHashMap、CopyOnWriteArrayList 等）。
- 不要用 Hashtable、Vector、Collections.synchronizedXxx（性能差）。
内存限制：
- 内存紧张：优先选内存占用小的（如数组比链表省内存）。
- 内存充足：按性能选。
是否允许 null：
- ConcurrentHashMap 不允许 null key/value。
- TreeMap/TreeSet 不允许 null（要比较）。
- HashMap/HashSet 允许一个 null key。

常见反模式

滥用 Vector 和 Hashtable：性能差，有更好的替代。
LinkedList 当万能药：以为插入删除快就用 LinkedList，实际多数场景 ArrayList 更快。
无界队列 + 快速生产者：可能导致 OOM（如 FixedThreadPool 的无界队列）。
在循环中用 + 拼接字符串：应该用 StringBuilder。
HashMap 不设初始容量：数据量大时频繁扩容影响性能。
并发场景用非并发集合：导致数据错乱、死循环等诡异问题。

选型总结口诀

选单列选双列，List/Set/Map 分清楚；要随机选数组，要排序选红黑树；要并发选 JUC，读多写少 COW；队列选型看需求，有界无界和优先级。

追问延伸：

你在项目中最常用哪些集合？为什么选它们？
ArrayList 和 LinkedList 怎么选？（绝大多数场景用 ArrayList）
多线程环境下怎么选 Map？（ConcurrentHashMap 通用；需要有序用 ConcurrentSkipListMap）
线程池的工作队列怎么选？（根据业务场景：有界/无界/直接传递/优先级）
你在项目中遇到过集合选型不当导致的问题吗？
知道哪些高性能的集合类？（FastUtil、Eclipse Collections、Guava 等第三方）
怎么判断一个集合是不是线程安全的？（看包名，java.util.concurrent 下的基本都是；看源码有没有同步措施）

Q15: HashMap 为什么用红黑树而不是 AVL 树或 B+ 树？「🔴 高级」

考察点：HashMap 数据结构的深度理解。

参考答案：

HashMap 在 JDK 1.8 中，链表长度 >= 8 且数组长度 >= 64 时转为红黑树。

为什么选红黑树：

AVL 树：严格平衡（左右子树高度差 <= 1），查询快 O(log n)，但插入/删除旋转次数多（可能多次旋转）
红黑树：弱平衡（最长路径不超过最短路径的 2 倍），查询略慢于 AVL，但插入/删除旋转次数少（最多 3 次）
HashMap 场景：频繁插入/删除，红黑树的平衡维护成本更低

为什么不用 B+ 树：

B+ 树是磁盘存储结构（MySQL 索引），每个节点存多个元素，减少磁盘 IO
HashMap 是内存数据结构，不需要考虑磁盘 IO，不需要 B+ 树的页结构
B+ 树的查询效率 O(log_M n)（M 为节点元素数），但实现复杂度远高于红黑树

为什么不用跳表（SkipList）：

跳表查询 O(log n)，但需要随机层数，内存开销更大（多个指针）
红黑树查询 O(log n)，内存开销更小
ConcurrentSkipListMap 用了跳表（因为跳表更适合并发）

转换阈值为什么是 8：

泊松分布：负载因子 0.75 下，一个桶中有 8 个元素的 probability ≈ 0.00000006
遇到 hash 碰撞极端情况才转红黑树，正常情况下链表够用
6 退化为链表（留缓冲避免频繁转换）

追问延伸：

红黑树的五个性质是什么？（根黑/叶黑/红不连续/黑高相同/新节点红色）
HashMap 链表转树后还会退化为链表吗？（会，长度降到 6 时退化）

Q16: HashMap 的容量为什么是 2 的 n 次方？loadFactor 是什么？「🟡 中级」

考察点：HashMap 扩容机制的细节。

参考答案：

容量为什么是 2 的 n 次方：

提高 hash 散列均匀性：hash & (capacity - 1) 等价于 hash % capacity，但位运算更快
扩容时元素位置要么不变，要么原位置 + 旧容量（只需检查 hash 的新增高位）
减少 hash 碰撞

java

// HashMap 的 hash 计算
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    // 扰动函数：高 16 位异或低 16 位，减少碰撞
}

// 桶定位
int index = hash & (capacity - 1);  // 位运算代替取模

loadFactor（负载因子）：

默认 0.75，是空间和时间的折中
threshold = capacity * loadFactor：扩容阈值
当 size > threshold 时触发扩容（容量翻倍）

loadFactor	空间	时间	适用场景
0.5	浪费多	碰撞少	对查询性能要求高
0.75（默认）	适中	适中	通用
1.0	省空间	碰撞多	内存紧张

扩容过程（JDK 1.8）：

创建新数组（容量 × 2）
遍历旧数组的每个桶
链表拆分：根据 hash & oldCapacity 判断元素去新数组的哪个位置
- 结果为 0：原位置
- 结果为 1：原位置 + oldCapacity
红黑树拆分类似，退化检查

追问延伸：

为什么不用 hash % capacity？（取模运算比位运算慢，JDK 追求性能）
初始化时指定容量有什么好处？（避免多次扩容，new HashMap<>(expectedSize / 0.75 + 1)）

Q17: HashMap 的 key 可以为 null 吗？为什么 String 适合做 Key？「🟡 中级」

考察点：HashMap key 的选择原则。

参考答案：

HashMap 的 key 和 value 都可以为 null（key 为 null 时 hash 值为 0，存在数组第一个桶）
ConcurrentHashMap 的 key 和 value 都不能为 null

为什么 String 适合做 Key：

不可变：String 是 final 类，创建后不可修改，hashCode 缓存不会失效
hashCode 已缓存：String 计算 hashCode 后会缓存，多次获取不需要重算
equals 实现规范：两个内容相同的 String 的 equals 返回 true，hashCode 相同
线程安全：不可变对象天然线程安全

自定义对象做 Key 的要求：

必须重写 hashCode 和 equals
不可变最佳（否则修改字段后 hashCode 变化，找不到原 key）
不要用可变对象做 Key（List、自定义可变类）

java

// 正确的做法
class User {
    private final String id;  // 不可变
    private final String name;

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User u = (User) o;
        return Objects.equals(id, u.id) && Objects.equals(name, u.name);
    }
}

追问延伸：

如果 HashMap 的 key 的 hashCode 发生变化会怎样？（找不到原来的 Entry，导致内存泄漏）
Integer 做 Key 有什么注意事项？（0-127 是缓存对象，== 比较可能误导）

Q18: 哈希冲突有哪些解决方法？「🟢 校招/初级」

考察点：哈希表的基础算法。

参考答案：

哈希冲突：不同 key 经过 hash 函数后得到相同的哈希值。

方法	说明	优点	缺点	代表
链地址法	同一桶用链表存	简单、不受装填因子限制	链表过长查询慢	HashMap
开放地址法	冲突后找下一个空位	无需指针，缓存友好	容易聚集、删除复杂	ThreadLocalMap
再哈希	换一个 hash 函数	不易聚集	计算 hash 多次	BloomFilter
公共溢出区	冲突元素统一放溢出表	查找快	溢出表可能很大	-

开放地址法三种探测：

线性探测：hash(key) + 1, +2, +3...（容易产生聚集）
二次探测：hash(key) + 1², +2², +3²...（缓解聚集）
双散列：hash1(key) + i * hash2(key)（效果最好）

链地址法 + 红黑树（JDK 1.8 HashMap）：

链表长度 < 8：链表（查询 O(n)）
链表长度 >= 8：转红黑树（查询 O(log n)）

追问延伸：

ThreadLocalMap 用的哪种冲突解决？（开放地址法-线性探测）
为什么 ThreadLocalMap 不用链地址法？（ThreadLocal 数量少，开放地址法更省内存、缓存更友好）

Q19: ConcurrentHashMap 的分段锁原理？JDK 1.7 vs 1.8 的区别？「🔴 高级」

考察点：ConcurrentHashMap 的底层实现细节。

参考答案：

JDK 1.7：Segment 分段锁

结构：Segment[] → HashEntry[] → 链表
每个 Segment 继承 ReentrantLock，是一个小 HashMap
默认 16 个 Segment，并发度 = 16（最多 16 个线程同时写）
put 时只锁对应的 Segment，不影响其他 Segment

JDK 1.8：CAS + synchronized

结构：Node[] → 链表/红黑树（和 HashMap 1.8 一样）
去掉 Segment，直接对数组桶（Node）加锁
put 流程：
1. 计算 hash，定位桶
2. 桥为空 → CAS 插入（无锁）
3. 桥非空 → synchronized 锁住头节点
4. 链表/红黑树插入
size 用 LongAdder 思想（多个 CounterCell 分散计数）

维度	JDK 1.7	JDK 1.8
锁粒度	Segment（一段）	Node（一个桶）
锁实现	ReentrantLock	CAS + synchronized
并发度	默认 16	桶的数量（更高）
数据结构	数组+链表	数组+链表/红黑树
查询效率	链表 O(n)	链表 O(n)/红黑树 O(log n)

为什么 1.8 用 synchronized 而不是 ReentrantLock：

synchronized 在 JDK 1.6 后优化很好（偏向锁→轻量级锁→重量级锁）
锁粒度更细（一个桶），冲突概率低，多数情况下用 CAS 就行
ReentrantLock 需要更多内存（AQS 队列）

追问延伸：

ConcurrentHashMap 的 size 是怎么计算的？（baseCount + CounterCell 数组，类似 LongAdder）
ConcurrentHashMap 的 put 为什么不用 ReentrantLock？（synchronized 经过优化后性能不差，且内存占用更少）

Q20: ArrayList 线程不安全体现在哪里？如何变安全？「🟡 中级」

考察点：ArrayList 并发问题。

参考答案：

ArrayList 线程不安全的具体体现：

数据覆盖：多线程同时 add，size 自增和元素赋值非原子，导致元素被覆盖
数组越界：扩容时另一个线程读取了未初始化的新数组
size 不一致：多线程 add 后 size 值可能小于实际元素数
迭代时 ConcurrentModificationException：modCount 检查 fail-fast

java

// ArrayList.add 源码（简化）
public boolean add(E e) {
    elementData[size++] = e;  // 非原子操作！
    // 1. 写 elementData[size]
    // 2. size++
    // 多线程下可能覆盖
    return true;
}

线程安全方案：

java

// 方案1：Collections.synchronizedList（加 synchronized 包装）
List<String> list = Collections.synchronizedList(new ArrayList<>());

// 方案2：CopyOnWriteArrayList（写时复制）
List<String> list = new CopyOnWriteArrayList<>();

// 方案3：Vector（方法级 synchronized，性能差，不推荐）
List<String> list = new Vector<>();

方案	读性能	写性能	适用场景
synchronizedList	一般	一般	读写均衡
CopyOnWriteArrayList	极快（无锁）	慢（复制数组）	读多写少
Vector	一般	一般	不推荐（遗留类）

追问延伸：

CopyOnWriteArrayList 为什么读不加锁？（写时复制新数组，读始终读旧数组引用，无竞争）
Collections.synchronizedList 的迭代需要加锁吗？（需要，迭代时仍要手动 synchronized）

Q21: ArrayList 和 LinkedList 的应用场景？各自适合什么操作？「🟢 校招/初级」

考察点：集合选型的基本判断。

参考答案：

维度	ArrayList	LinkedList
底层结构	动态数组	双向链表
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	均摊 O(1)	O(1)
中间插入	O(n)	O(n)（查找 O(n) + 插入 O(1)）
内存	连续，缓存友好	每个节点额外存前后指针
实现	List + RandomAccess	List + Deque

ArrayList 适合：

随机访问频繁（get(i)）
尾部追加为主
内存紧凑、缓存友好

LinkedList 适合：

频繁在头部/尾部插入删除（当队列/栈用）
不需要随机访问

实际开发中：

90% 场景用 ArrayList（即使中间插入，数组移动也比链表查找快，因为缓存友好）
需要队列用 ArrayDeque（比 LinkedList 做队列更快）
LinkedList 的价值越来越小，很多场景被 ArrayDeque 替代

追问延伸：

为什么 ArrayList 中间插入比 LinkedList 快？（数组连续内存 → CPU 缓存命中率高 → System.arraycopy 比链表遍历快）
LinkedList 实现了 Deque，能当栈用吗？（能，push/pop，但推荐用 ArrayDeque）

Q22: List 和数组如何互相转换？有什么坑？「🟢 校招/初级」

考察点：日常 API 使用。

参考答案：

数组转 List：

java

// 方式1：Arrays.asList（⚠️ 固定大小，不能 add/remove）
String[] arr = {"a", "b", "c"};
List<String> list1 = Arrays.asList(arr);
// list1.add("d");  // UnsupportedOperationException！

// 方式2：new ArrayList（可变大小）
List<String> list2 = new ArrayList<>(Arrays.asList(arr));
list2.add("d");  // OK

// 方式3：Stream（Java 8+）
List<String> list3 = Arrays.stream(arr).collect(Collectors.toList());

// 方式4：List.of（Java 9+，不可变）
List<String> list4 = List.of(arr);
// list4.add("d");  // UnsupportedOperationException！

List 转数组：

java

List<String> list = Arrays.asList("a", "b", "c");

// 方式1：toArray（需指定类型，否则返回 Object[]）
String[] arr1 = list.toArray(new String[0]);
// 推荐 new String[0]，JDK 8+ 会自动创建正确大小的数组

// 方式2：Stream
String[] arr2 = list.stream().toArray(String[]::new);

// 方式3：toArray 无参（返回 Object[]，不推荐）
Object[] arr3 = list.toArray();

常见坑：

Arrays.asList 返回的是 Arrays$ArrayList（内部类），不是 java.util.ArrayList，不可修改大小

基本类型数组 int[] 用 Arrays.asList 会得到 List<int[]>（只有一个元素），需要先装箱

java

int[] nums = {1, 2, 3};
// 错误：List<int[]> list = Arrays.asList(nums);
// 正确：
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());

toArray(new String[0]) 比 toArray(new String[list.size()]) 更推荐（JDK 8+ 优化）

追问延伸：

Arrays.asList 修改数组会影响 List 吗？（会，底层共享同一个数组引用）
List.of 和 Arrays.asList 的区别？（前者完全不可变，后者可以 set 不能 add/remove）

Q23: HashMap 多线程下有哪些问题？JDK 1.7 的死循环？「🔴 高级」

考察点：HashMap 并发安全深度理解。

参考答案：

JDK 1.7 HashMap 多线程问题：

死循环（链表环）：扩容时头插法导致链表形成环，get 时无限循环 → CPU 100%
数据丢失：多线程 put 同时扩容，部分数据被覆盖
size 不一致：非原子操作

JDK 1.7 死循环原因：

扩容时用头插法转移链表
多线程并发扩容 → 两个线程的转移操作交叉 → A.next = B, B.next = A → 环形链表
get 遍历时 e = e.next 永远不为 null → 死循环

JDK 1.8 改进：

扩容时用尾插法（保持原顺序），不会形成环
但仍然不是线程安全的（数据覆盖、size 不一致等问题仍在）
需要线程安全用 ConcurrentHashMap

java

// JDK 1.7 头插法（可能死循环）
void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) {
        while (e != null) {
            Entry<K,V> next = e.next;
            int i = indexFor(e.hash, newTable.length);
            e.next = newTable[i];  // 头插
            newTable[i] = e;
            e = next;
        }
    }
}

// JDK 1.8 尾插法（保持顺序，不死循环）
// 但 put 仍然不安全（CAS 无同步）

追问延伸：

JDK 1.8 的 HashMap 还会死循环吗？（不会因为扩容死循环，但可能因为红黑树操作不安全出问题）
为什么不用 HashTable？（全表锁性能差，ConcurrentHashMap 更高效）

Q24: 遍历集合的方式有哪些？forEach vs Iterator 的区别？「🟢 校招/初级」

考察点：集合遍历方法。

参考答案：

List 遍历方式：

java

List<String> list = Arrays.asList("a", "b", "c");

// 1. 普通 for 循环（可索引访问）
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 2. 增强 for 循环（底层用 Iterator）
for (String s : list) {
    System.out.println(s);
}

// 3. Iterator
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

// 4. forEach + Lambda（Java 8+）
list.forEach(s -> System.out.println(s));
list.forEach(System.out::println);

// 5. Stream
list.stream().forEach(System.out::println);

Map 遍历方式：

java

Map<String, Integer> map = new HashMap<>();

// 1. entrySet（推荐，一次取出 key-value）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ":" + entry.getValue());
}

// 2. keySet（需 get 两次，稍慢）
for (String key : map.keySet()) {
    System.out.println(key + ":" + map.get(key));
}

// 3. forEach + Lambda
map.forEach((k, v) -> System.out.println(k + ":" + v));

遍历时删除元素：

java

// 错误：增强 for 循环中删除 → ConcurrentModificationException
for (String s : list) {
    if (s.equals("b")) list.remove(s);  // 异常！
}

// 正确1：Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();  // OK
}

// 正确2：Java 8 removeIf
list.removeIf(s -> s.equals("b"));

// 正确3：倒序遍历删除
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("b")) list.remove(i);
}

追问延伸：

为什么增强 for 循环中不能 remove？（Iterator 的 modCheck 检测到 modCount 变化，抛 fail-fast 异常）
forEach 和 stream().forEach 的区别？（前者可能有顺序保证，后者并行流无顺序）

Q25: HashMap 和 Hashtable 的区别？「🟢 校招/初级」

考察点：历史遗留类的了解。

参考答案：

维度	HashMap	Hashtable
线程安全	不安全	安全（全表 synchronized）
null key/value	允许	不允许（NullPointerException）
初始容量	16	11
扩容	×2	×2 + 1
hash 计算	高低16位异或	直接 hashCode
继承	AbstractMap	Dictionary（遗留类）
性能	快	慢（锁粒度大）
推荐	日常使用	不推荐，用 ConcurrentHashMap

Hashtable 是 JDK 1.0 的遗留类，JDK 1.2 后被 HashMap 取代。它和 Collections.synchronizedMap(new HashMap<>()) 效果类似，都是全表锁。

追问延伸：

Properties 继承自哪个类？（Hashtable）
为什么 Hashtable 初始容量是 11？（质数取模散列更均匀，但 HashMap 用 2 的 n 次方位运算替代）

Q26: 如何实现一个 LRU 缓存？「🟡 中级」

考察点：集合的综合应用。

参考答案：

LRU（Least Recently Used）：最近最少使用，淘汰最久没用的元素。

实现方式一：LinkedHashMap（最简洁）

java

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // true = 访问顺序
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;  // 超容量时淘汰最久未使用的
    }
}

实现方式二：HashMap + 双向链表（面试常考）

java

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);  // 哨兵
    private final Node tail = new Node(0, 0);  // 哨兵

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);   // 移到链表头部
        addToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            remove(node);
            addToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

时间复杂度：get/put 均 O(1)。

追问延伸：

LinkedHashMap 的 accessOrder 是怎么实现的？（每次 get/put 后把节点移到链表尾部）
LFU 缓存怎么实现？（HashMap + 频次链表，比 LRU 更复杂）

Q27: 集合的 fail-fast 机制是什么？原理是什么？「🟡 中级」

考察点：集合安全机制。

参考答案：

fail-fast：集合在迭代过程中如果被修改（结构变化），立即抛出 ConcurrentModificationException。

原理：

集合维护一个 modCount 字段，记录结构修改次数（add/remove）
迭代器创建时记录 expectedModCount = modCount
每次 next() 检查 modCount == expectedModCount，不等则抛异常
单线程下防止迭代时修改导致数据不一致
多线程下是一种"尽力检测"机制（不是保证安全）

java

// ArrayList.Itr 源码（简化）
private class Itr implements Iterator<E> {
    int expectedModCount = modCount;

    public E next() {
        checkForComodification();
        // ...
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

fail-safe：java.util.concurrent 包下的集合（CopyOnWriteArrayList、ConcurrentHashMap）

迭代时遍历的是副本/快照，不抛异常
但可能读不到最新数据（弱一致性）
CopyOnWriteArrayList 迭代的是创建时的数组副本

机制	集合	特点	代价
fail-fast	ArrayList/HashMap	及时抛异常	不能并发修改
fail-safe	CopyOnWrite/Concurrent	不抛异常	内存/一致性

注意：fail-fast 不保证并发安全，它只是"尽可能检测到"并发修改。

追问延伸：

Iterator.remove() 为什么不会触发 fail-fast？（它同时更新了 expectedModCount）
ConcurrentHashMap 迭代时是 fail-fast 还是 fail-safe？（弱一致，不抛异常但可能读不到最新值）

Q28: HashMap 往里面存 20 个元素会扩容几次？「🟡 中级」

考察点：HashMap 扩容计算。

参考答案：

默认参数：初始容量 16，负载因子 0.75，阈值 = 16 × 0.75 = 12。

java

HashMap<String, String> map = new HashMap<>();  // 容量16, 阈值12
// 存第 1-12 个元素：不扩容
// 存第 13 个元素：size(13) > 阈值(12) → 扩容到 32, 新阈值 = 24
// 存第 14-20 个元素：不扩容
// 总共扩容 1 次

如果指定初始容量：

java

// 推荐写法（避免多次扩容）
HashMap<String, String> map = new HashMap<>(32);
// 容量32, 阈值24, 存20个不扩容

// 更精确：expectedSize / 0.75 + 1
HashMap<String, String> map = new HashMap<>(20 / 0.75f + 1);  // ≈ 27 → 实际32

HashMap 的 tableSizeFor：

java

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 总是返回 >= cap 的最小 2 的 n 次方
// tableSizeFor(20) = 32
// tableSizeFor(16) = 16
// tableSizeFor(17) = 32

注意：new HashMap<>(20) 实际容量不是 20 而是 32。

追问延伸：

为什么推荐指定初始容量？（减少扩容次数，避免 rehash 开销）
扩容时 rehash 吗？（JDK 1.8 不需要 rehash，通过 hash & oldCapacity 判断位置）

Q29: Collections 和 Collection 的区别？常用工具方法有哪些？「🟢 校招/初级」

考察点：集合工具类的认知。

参考答案：

维度	Collection	Collections
类型	接口	工具类
作用	集合根接口	集合操作的工具方法
继承	List/Set/Queue 的父接口	全是静态方法

Collections 常用方法：

java

// 排序
Collections.sort(list);                    // 自然排序
Collections.sort(list, comparator);        // 自定义排序
Collections.reverse(list);                 // 反转
Collections.shuffle(list);                 // 随机打乱

// 查找
Collections.binarySearch(list, key);       // 二分查找（需先排序）
Collections.max(list);                      // 最大值
Collections.min(list);                      // 最小值

// 线程安全（返回同步包装）
List<T> syncList = Collections.synchronizedList(new ArrayList<>());
Map<K,V> syncMap = Collections.synchronizedMap(new HashMap<>());
Set<T> syncSet = Collections.synchronizedSet(new HashSet<>());

// 不可变集合
List<T> unmodifiable = Collections.unmodifiableList(list);
// 不可变集合：后续修改操作抛 UnsupportedOperationException

// 空集合（避免返回 null）
List<Object> empty = Collections.emptyList();

// 单元素集合
Set<String> singleton = Collections.singleton("only");

追问延伸：

Collections.synchronizedList 和 CopyOnWriteArrayList 有什么区别？（前者全程加锁，后者写时复制读不加锁）
Java 9+ 的 List.of() 和 Collections.unmodifiableList() 有什么区别？（List.of() 更简洁且是真正的不可变）

Q30: List 可以一边遍历一边修改元素吗？ConcurrentModificationException 怎么产生的？「🟡 中级」

考察点：集合遍历的并发修改问题。

参考答案：

一边遍历一边修改会抛 ConcurrentModificationException（fail-fast 机制）：

java

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));

// 错误：遍历时直接 remove → ConcurrentModificationException
for (String s : list) {
    if (s.equals("b")) list.remove(s);  // 抛异常！
}

// 错误：遍历时直接 add → ConcurrentModificationException
for (String s : list) {
    if (s.equals("b")) list.add("d");  // 抛异常！
}

原理：

迭代器内部维护 expectedModCount，初始等于集合的 modCount
每次 next() 检查 expectedModCount == modCount，不等则抛异常
集合的 add/remove 会使 modCount++

正确的遍历修改方式：

java

// 方式1：Iterator.remove()（推荐）
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();  // 安全，更新 expectedModCount
}

// 方式2：Java 8+ removeIf（最简洁）
list.removeIf(s -> s.equals("b"));

// 方式3：倒序遍历（List 专用）
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("b")) list.remove(i);
}

// 方式4：CopyOnWriteArrayList（并发安全，适合读多写少）
CopyOnWriteArrayList<String> list2 = new CopyOnWriteArrayList<>(list);
// 遍历的是副本，修改不影响遍历

追问延伸：

CopyOnWriteArrayList 遍历时修改为什么不会报错？（遍历的是快照副本，修改写在新副本上）
removeIf 底层怎么实现的？（用 BitSet 标记待删元素，最后批量删除）

Q31: List 如何快速删除元素？removeIf vs Iterator.remove 的区别？「🟡 中级」

考察点：集合元素删除的性能和方法选型。

参考答案：

各种删除方式的对比：

方式	时间复杂度	安全性	代码量
`list.remove(index)` 正序	O(n²)	不安全（漏删）	长
`list.remove(index)` 倒序	O(n)	安全	中
`Iterator.remove()`	O(n)	安全	中
`list.removeIf()`	O(n)	安全	最少
`list.clear()`	O(1)	删全部	最少

正序删除的坑（漏删问题）：

java

// 错误：正序删除会漏删
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "b", "c"));
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals("b")) list.remove(i);
}
// 结果：["a", "b", "c"] ← 第二个 "b" 没删掉！
// 原因：删除第一个 "b" 后，后面的元素左移，i++ 跳过了第二个 "b"

高性能批量删除：

java

// removeIf：底层用 BitSet 标记 + 批量删除
list.removeIf(s -> s.startsWith("test"));
// 相当于：遍历一遍标记待删元素，最后一次 System.arraycopy 批量移除

// 大量删除时比逐个 remove 快很多
// 因为逐个 remove 每次触发 arraycopy = O(n)，总 O(n²)
// removeIf 一次 arraycopy = O(n)

追问延伸：

ArrayList.remove(index) 底层做了什么？（检查越界 → arraycopy 左移 → size-- → 返回旧元素）
LinkedList.remove() 和 ArrayList.remove() 哪个快？（LinkedList 删除快 O(1) 查到后删除，ArrayList 删除慢 O(n) 需要移动元素）

Q32: HashMap 的 get 方法一定安全吗？多线程下 get 会有什么问题？「🔴 高级」

考察点：HashMap 并发问题的深入理解。

参考答案：

HashMap 的 get 方法在多线程下不安全，可能出现以下问题：

JDK 1.7 的问题（链表死循环）：

扩容时多个线程并发操作，链表可能形成环 → get 时死循环（CPU 100%）

JDK 1.8 的问题（虽然修复了死循环，但仍不安全）：

get 到 null 值：
- 线程 A put(key, value) 时，正在创建链表节点
- 线程 B get(key) 读到了未完全初始化的节点 → 返回 null

java

// JDK 1.8 put 的 tabAt（Unsafe.compareAndSwapObject）
// 线程 A 还没写完 Node 的 value，线程 B 就读到了

get 到旧值：
- 线程 A 正在扩容，数据迁移到新数组
- 线程 B get(key) 读到了旧数组的数据 → 可能读到旧值
size 不准确：
- 多线程 put 时 size++ 不是原子操作
- size 可能看到中间状态

java

// HashMap 的 size
transient int size;
// 多线程 put → size++ 不是原子的 → size 可能小于实际值

丢数据：
- 两个线程同时 put 到同一个桶 → CAS 可能失败 → 一个写入丢失

正确做法：

java

// 多线程用 ConcurrentHashMap
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
// get/put 都是线程安全的

追问延伸：

JDK 1.8 的 HashMap 还会死循环吗？（不会死循环，但仍有数据丢失/null 值问题）
ConcurrentHashMap 的 get 需要加锁吗？（不需要，用 volatile 保证可见性）

Q33: 重写 equals 和 hashCode 需要注意什么？不重写会怎样？「🟡 中级」

考察点：HashMap/HashSet 的核心约束。

参考答案：

核心原则：重写 equals 必须重写 hashCode，否则 HashMap/HashSet 会出 bug。

不重写 hashCode 的问题：

java

class Person {
    String name;
    int age;

    // 只重写了 equals，没重写 hashCode
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }
    // hashCode 使用 Object 默认实现 → 每个对象 hash 不同
}

Person p1 = new Person("Alice", 20);
Person p2 = new Person("Alice", 20);  // equals 为 true

Map<Person, String> map = new HashMap<>();
map.put(p1, "value");
map.get(p2);  // 返回 null！因为 p1 和 p2 的 hashCode 不同 → 不同桶 → 找不到

hashCode 的约定：

一致性：同一对象多次调用 hashCode 返回值相同
equals 为 true → hashCode 必须相等
equals 为 false → hashCode 可以相等（哈希冲突，但应尽量避免）

正确的重写方式：

java

class Person {
    String name;
    int age;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // 标准做法
    }
}

Objects.hash 的实现：

java

// Objects.hash 内部用 Arrays.hashCode
public static int hash(Object... values) {
    return Arrays.hashCode(values);
}
// 组合多个字段的 hash，保证 equals 相等 → hashCode 相等

用 String 做 Key 为什么好：

String 的 hashCode 已实现且不可变
不可变 → 缓存 hashCode，计算一次
可变对象做 Key 的风险：put 后修改字段 → hashCode 变化 → get 不到

追问延伸：

只重写 equals 不重写 hashCode 会怎样？（HashSet 可能有"重复"元素，HashMap get 不到值）
为什么 String 适合做 HashMap 的 Key？（不可变、hashCode 缓存、分布均匀）

Q34: HashMap 的扩容机制（JDK 1.7 vs 1.8）有什么区别？「🔴 高级」

考察点：HashMap 扩容的底层原理。

参考答案：

扩容触发条件：size > capacity * loadFactor（默认 16 * 0.75 = 12）

JDK 1.7 扩容（头插法）：

java

void transfer(Entry[] newTable) {
    for (Entry<K,V> e : table) {
        while (e != null) {
            Entry<K,V> next = e.next;     // 保存下一个
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];        // 头插法：新节点指向新桶头
            newTable[i] = e;             // 新桶头 = 当前节点
            e = next;                    // 移动到下一个
        }
    }
}

扩容后重新计算 hash（hash & (newCapacity - 1)）
头插法：链表顺序反转
多线程下可能形成环 → 死循环

JDK 1.8 扩容（尾插法 + 优化）：

java

// 1.8 不重新计算 hash，用 hash & oldCapacity 判断位置
// 位 0 = 原位置，位 1 = 原位置 + oldCapacity

final Node<K,V>[] resize() {
    Node<K,V>[] newTab = new Node[newCapacity];
    for (int j = 0; j < oldCap; j++) {
        Node<K,V> e = oldTab[j];
        if (e != null) {
            // 拆分链表为低位链和高位链
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            while (e != null) {
                if ((e.hash & oldCap) == 0) {
                    // 低位链：原位置
                    if (loTail == null) loHead = e; else loTail.next = e;
                    loTail = e;
                } else {
                    // 高位链：原位置 + oldCap
                    if (hiTail == null) hiHead = e; else hiTail.next = e;
                    hiTail = e;
                }
                e = e.next;
            }
            // 放到新数组
            if (loHead != null) newTab[j] = loHead;
            if (hiHead != null) newTab[j + oldCap] = hiHead;
        }
    }
    return newTab;
}

1.8 扩容优化：

不重新计算 hash：用 hash & oldCap 判断是否移到新位置
尾插法：保持链表顺序，不反转
拆分高低位链：一次遍历拆成两条链
不死循环：尾插法不会形成环

维度	JDK 1.7	JDK 1.8
插入方式	头插法	尾插法
hash 计算	重新计算 `hash & (newCap-1)`	用 `hash & oldCap` 判断
链表顺序	反转	保持原顺序
多线程安全	可能死循环	不会死循环（但仍有其他问题）

追问延伸：

为什么 JDK 1.8 用 hash & oldCap 而不是重新算 hash？（性能优化，减少一次位运算）
扩容为什么是 2 倍？（保证 hash & (cap-1) 的位运算有效，且高低位拆分正确）

Q35: ConcurrentHashMap 用了悲观锁还是乐观锁？分段锁是可重入的吗？「🔴 高级」

考察点：ConcurrentHashMap 的锁机制深入理解。

参考答案：

JDK 1.7（分段锁）：

用 ReentrantLock（悲观锁），每个 Segment 一把锁
分段锁是可重入的，因为 ReentrantLock 是可重入锁
锁粒度：Segment 级别（默认 16 个 Segment）

java

// JDK 1.7 结构
ConcurrentHashMap
  └── Segment[16]（继承 ReentrantLock）
        └── HashEntry[]
              └── 链表

// put 时锁 Segment
segment.lock();        // ReentrantLock，可重入
// ... put 操作
segment.unlock();

JDK 1.8（CAS + synchronized）：

用 CAS + synchronized（乐观 + 悲观混合）
锁粒度：桶（Node）级别，更细粒度

java

// JDK 1.8 put 流程
final V putVal(K key, V value, boolean onlyIfAbsent) {
    int hash = spread(key.hashCode());
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;

        // 1. 桶为空 → CAS 插入（乐观）
        if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null, new Node<>(...)))
                break;  // CAS 成功，无需加锁
        }
        // 2. 桶不为空 → synchronized 加锁（悲观）
        else {
            synchronized (f) {  // 锁桶头节点
                // 链表/红黑树操作
            }
        }
    }
}

JDK 1.8 的锁策略：

操作	锁策略	说明
空桶插入	CAS（乐观）	无锁竞争，CAS 直接插入
非空桶操作	synchronized（悲观）	锁住桶头节点
扩容	多线程协助迁移	CAS + synchronized
get	无锁	volatile 读

为什么用 synchronized 而不是 ReentrantLock：

锁粒度更细（桶级别 vs Segment 级别）
JVM 对 synchronized 优化好（偏向锁、轻量级锁）
synchronized 不需要手动 unlock，减少遗漏释放的风险

追问延伸：

ConcurrentHashMap 的 get 为什么不加锁？（Node 的 val 和 next 用 volatile 修饰，保证可见性）
ConcurrentHashMap 的 size 怎么计算的？（用 LongAdder 思想，分散计数后求和）

Q36: HashTable 底层实现原理是什么？和 ConcurrentHashMap 有什么区别？「🟡 中级」

考察点：HashTable 的理解和对比。

参考答案：

HashTable 底层：

数组 + 链表（和 JDK 1.7 HashMap 类似）
所有方法用 synchronized 修饰 → 锁整个表

java

public synchronized V put(K key, V value) { ... }
public synchronized V get(Object key) { ... }
public synchronized V remove(Object key) { ... }
// 所有操作都锁 this → 整个 HashTable

HashTable vs ConcurrentHashMap：

维度	HashTable	ConcurrentHashMap (1.8)
锁粒度	整个表（this）	桶级别（Node）
并发度	1（串行）	高（等于桶数）
null key/value	不允许	不允许
初始容量	11	16
扩容	2n+1	2n
迭代器	fail-fast	弱一致性（安全）
性能	差	好
推荐使用	不推荐	推荐

HashTable vs HashMap：

维度	HashTable	HashMap
线程安全	安全（synchronized）	不安全
null key	不允许	允许 1 个
null value	不允许	允许多个
初始容量	11	16
父类	Dictionary	AbstractMap
扩容	2n+1	2n

HashTable 被淘汰的原因：

锁粒度太粗，并发性能差
迭代时不允许修改（fail-fast 直接抛异常）
不支持 null key/value

追问延伸：

为什么 HashTable 不允许 null？（多线程下 get(key) 返回 null 无法区分"不存在"和"值为 null"）
Collections.synchronizedMap 和 ConcurrentHashMap 有什么区别？（前者锁整个表，后者细粒度锁）

Q37: List 泛型为什么不能用基本数据类型？泛型擦除是什么？「🟡 中级」

考察点：Java 泛型机制的底层理解。

参考答案：

List 不能用基本数据类型：

java

List<int> list = new ArrayList<>();  // 编译错误！
List<Integer> list = new ArrayList<>();  // 正确

原因：Java 泛型只能接受对象类型，基本类型不是对象。基本类型有对应的包装类：

基本类型	包装类
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
boolean	Boolean

自动装箱/拆箱：

java

List<Integer> list = new ArrayList<>();
list.add(1);        // 自动装箱：int → Integer.valueOf(1)
int n = list.get(0); // 自动拆箱：Integer.intValue() → int

// 注意 NPE
Integer a = null;
int b = a;  // NullPointerException！null.intValue() 报错

泛型擦除： Java 泛型在编译时做类型检查，运行时擦除泛型信息。

java

List<String> strList = new ArrayList<>();
List<Integer> intList = new ArrayList<>();

// 运行时泛型被擦除
strList.getClass() == intList.getClass();  // true！都是 ArrayList.class

// 编译后 List<String> 和 List<Integer> 都变成 raw List

泛型擦除的影响：

java

// 不能用泛型类型实例化
new T();           // 编译错误
new T[10];         // 编译错误

// 不能用基本类型参数化
List<int> list;    // 编译错误

// 运行时不能获取泛型类型
if (list instanceof List<String>) { }  // 编译错误
if (list instanceof List<?>) { }      // 正确

追问延伸：

为什么 Java 要泛型擦除而不像 C++ 那样保留泛型信息？（兼容性：Java 5 才有泛型，擦除保证和 Java 4 的字节码兼容）
Integer 的缓存池是什么？（Integer.valueOf(-128~127) 返回缓存对象，== 可能为 true）

Q38: TreeMap 的底层原理？红黑树有哪些特性？「🔴 高级」

考察点：红黑树和 TreeMap 的理解。

参考答案：

TreeMap 基于红黑树实现，按键的自然顺序或自定义 Comparator 排序。

java

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);

// 遍历时按 key 排序输出
// apple=1, banana=2, cherry=3

// 特有操作
map.firstKey();    // "apple"
map.lastKey();     // "cherry"
map.subMap("apple", "cherry");  // {apple=1, banana=2}
map.headMap("cherry");          // {apple=1, banana=2}
map.tailMap("banana");          // {banana=2, cherry=3}

红黑树的五大特性：

节点是红色或黑色
根节点是黑色
叶子节点（NIL）是黑色
红色节点的子节点必须是黑色（不能有两个连续的红色节点）
从任一节点到其每个叶子的所有路径包含相同数目的黑色节点（黑高相同）

红黑树的操作复杂度：

查找：O(log n)
插入：O(log n) + 旋转/变色
删除：O(log n) + 旋转/变色

红黑树 vs AVL 树：

维度	红黑树	AVL 树
平衡条件	弱平衡（黑高相同）	强平衡（左右子树高差 ≤ 1）
插入旋转	最多 2 次旋转	最多 2 次旋转
删除旋转	最多 3 次旋转	可能 O(log n) 次旋转
查找效率	略低（树更高）	略高（树更平衡）
插入/删除效率	略高（旋转少）	略低（旋转多）
适用场景	频繁增删	频繁查找

TreeMap 使用场景：

需要按 key 排序的 Map
范围查询（subMap/headMap/tailMap）
最近最少使用（LRU）的变体实现

追问延伸：

HashMap 什么时候链表转红黑树？（链表长度 ≥ 8 且数组长度 ≥ 64）
为什么 HashMap 选红黑树不选 AVL 树？（红黑树增删旋转次数少，适合频繁修改的场景）

Q39: 集合的 Stream API 有哪些常用操作？「🟡 中级」

考察点：Java 8 Stream API 的实际使用。

参考答案：

Stream API 三步操作：数据源 → 中间操作 → 终端操作

java

List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David", "Eve");

// 过滤 + 映射 + 收集
List<String> result = names.stream()
    .filter(n -> n.length() > 3)           // 中间操作：过滤
    .map(String::toUpperCase)              // 中间操作：映射
    .sorted()                              // 中间操作：排序
    .collect(Collectors.toList());         // 终端操作：收集
// [ALICE, CHARLIE, DAVID]

常用中间操作：

java

stream.filter(Predicate)         // 过滤
      .map(Function)              // 映射（一对一）
      .flatMap(Function)         // 扁平化映射（一对多）
      .sorted()                  // 排序
      .sorted(Comparator)        // 自定义排序
      .distinct()                // 去重
      .limit(n)                  // 取前 n 个
      .skip(n)                   // 跳过 n 个
      .peek(Consumer);           // 查看（调试用）

常用终端操作：

java

// 聚合
stream.count();                              // 计数
stream.min(Comparator);                       // 最小值
stream.max(Comparator);                       // 最大值

// 匹配
stream.anyMatch(Predicate);                   // 任一匹配
stream.allMatch(Predicate);                   // 全部匹配
stream.noneMatch(Predicate);                 // 无匹配

// 查找
stream.findFirst();                           // 第一个
stream.findAny();                             // 任意一个

// 归约
stream.reduce(BinaryOperator);                // 归约
int sum = list.stream().mapToInt(Integer::intValue).sum();

// 收集
stream.collect(Collectors.toList());          // List
stream.collect(Collectors.toSet());           // Set
stream.collect(Collectors.toMap(...));         // Map
stream.collect(Collectors.joining(","));       // 字符串拼接
stream.collect(Collectors.groupingBy(...));   // 分组
stream.collect(Collectors.partitioningBy(...)); // 分区

// 分组示例
Map<Integer, List<String>> byLength = names.stream()
    .collect(Collectors.groupingBy(String::length));
// {3=[Bob, Eve], 5=[Alice, David], 7=[Charlie]}

并行流：

java

// 并行流（底层用 ForkJoinPool）
list.parallelStream()
    .map(this::heavyCompute)
    .collect(Collectors.toList());

// 注意：不一定更快，有线程切换开销
// 适合：数据量大 + 计算密集
// 不适合：数据量小 或 IO 密集

Stream 的特点：

惰性求值：中间操作不会立即执行，直到终端操作触发
一次性：Stream 只能消费一次
不修改源：Stream 操作不改变源集合

追问延伸：

parallelStream 一定比 stream 快吗？（不一定，数据量小或任务轻时反而更慢）
Collectors.groupingBy 底层怎么实现的？（用 HashMap + mergeFunction）

Java 集合框架 ​

Q1: Java 集合框架的整体结构？List/Set/Map 有什么区别？ 「🟢 校招/初级」 ​

整体结构 ​

Collection 三大子接口对比 ​

Map 接口 ​

List / Set / Map 核心区别 ​

集合框架的设计特点 ​

Q2: ArrayList 和 LinkedList 的区别？ArrayList 扩容机制？ 「🟢 校招/初级」 ​

核心区别 ​

ArrayList 详解 ​

底层结构 ​

扩容机制 ​

优化建议 ​

LinkedList 详解 ​

底层结构 ​

特点 ​

实际性能对比 ​

Q3: ArrayList 和 Vector 的区别？ 「🟢 校招/初级」 ​

核心区别 ​

线程安全的实现 ​

扩容机制对比 ​

为什么不推荐用 Vector ​

ArrayList 线程安全的替代方案 ​

Q4: HashMap 的实现原理？JDK 1.7 和 1.8 有什么区别？ 「🟡 中级」 ​

整体结构 ​

JDK 1.7 vs JDK 1.8 对比 ​

哈希计算与定位 ​

Hash 计算（扰动函数） ​

桶定位 ​

扩容机制 ​

重要参数 ​

扩容时机 ​

扩容过程 ​

红黑树相关 ​

为什么用红黑树 ​

为什么链表长度 > 8 且数组 > 64 才转树 ​

Q5: HashMap 的 put 方法流程？ 「🟡 中级」 ​

JDK 1.8 put 方法流程 ​

核心代码解读（JDK 1.8） ​

几个关键点 ​

get 方法流程（对比理解） ​

Q6: HashMap 为什么线程不安全？会有什么问题？ 「🟡 中级」 ​

JDK 1.7 的问题 —— 扩容死循环 ​

原因 ​

过程简述 ​

JDK 1.8 的问题 ​

1. 数据丢失（并发 put 覆盖） ​

2. size 不准确 ​

3. 并发 put 和 get 可能 get 到 null ​

4. 其他问题 ​

总结 ​

解决方案 ​

Q7: ConcurrentHashMap 的实现原理？JDK 1.7 和 1.8 有什么区别？ 「🔴 高级」 ​

JDK 1.7 —— 分段锁（Segment） ​

结构 ​

并发原理 ​

优缺点 ​

JDK 1.8 —— CAS + synchronized 锁桶头 ​

结构 ​

并发原理 ​

put 操作 ​

get 操作 ​

扩容（transfer） ​

size() 计算 ​

为什么用 synchronized 而不是 ReentrantLock ​

JDK 1.7 vs 1.8 对比总结 ​

其他重要问题 ​

为什么不允许 null key / null value？ ​

get 方法是否需要加锁？ ​

Q8: HashSet 的实现原理？和 HashMap 的关系？ 「🟢 校招/初级」 ​

HashSet 底层就是 HashMap ​

核心要点 ​

HashSet 和 HashMap 的关系 ​

为什么 HashSet 允许 null ​

LinkedHashSet 和 TreeSet ​

Set 去重原理 ​

Q9: LinkedHashMap 的原理和应用场景？ 「🟡 中级」 ​

基本概念 ​

两种顺序模式 ​

1. 插入顺序（默认） ​

Java 集合框架

Q1: Java 集合框架的整体结构？List/Set/Map 有什么区别？「🟢 校招/初级」

整体结构

Collection 三大子接口对比

Map 接口

List / Set / Map 核心区别

集合框架的设计特点

Q2: ArrayList 和 LinkedList 的区别？ArrayList 扩容机制？「🟢 校招/初级」

核心区别

ArrayList 详解

底层结构

扩容机制

优化建议

LinkedList 详解

底层结构

特点

实际性能对比

Q3: ArrayList 和 Vector 的区别？「🟢 校招/初级」

核心区别

线程安全的实现

扩容机制对比

为什么不推荐用 Vector

ArrayList 线程安全的替代方案

Q4: HashMap 的实现原理？JDK 1.7 和 1.8 有什么区别？「🟡 中级」

整体结构

JDK 1.7 vs JDK 1.8 对比

哈希计算与定位

Hash 计算（扰动函数）

桶定位

扩容机制

重要参数

扩容时机

扩容过程

红黑树相关

为什么用红黑树

为什么链表长度 > 8 且数组 > 64 才转树

Q5: HashMap 的 put 方法流程？「🟡 中级」

JDK 1.8 put 方法流程

核心代码解读（JDK 1.8）

几个关键点

get 方法流程（对比理解）

Q6: HashMap 为什么线程不安全？会有什么问题？「🟡 中级」

JDK 1.7 的问题 —— 扩容死循环

原因

过程简述

JDK 1.8 的问题

1. 数据丢失（并发 put 覆盖）

2. size 不准确

3. 并发 put 和 get 可能 get 到 null

4. 其他问题

总结

解决方案

Q7: ConcurrentHashMap 的实现原理？JDK 1.7 和 1.8 有什么区别？「🔴 高级」

JDK 1.7 —— 分段锁（Segment）

结构

并发原理

优缺点

JDK 1.8 —— CAS + synchronized 锁桶头

结构

并发原理

put 操作

get 操作

扩容（transfer）

size() 计算

为什么用 synchronized 而不是 ReentrantLock

JDK 1.7 vs 1.8 对比总结

其他重要问题

为什么不允许 null key / null value？

get 方法是否需要加锁？

Q8: HashSet 的实现原理？和 HashMap 的关系？「🟢 校招/初级」

HashSet 底层就是 HashMap

核心要点

HashSet 和 HashMap 的关系

为什么 HashSet 允许 null

LinkedHashSet 和 TreeSet

Set 去重原理

Q9: LinkedHashMap 的原理和应用场景？「🟡 中级」

基本概念

两种顺序模式

1. 插入顺序（默认）