夜雨聆风写在前面
最近帮几个朋友复盘大厂面试，发现集合框架仍然是「翻车重灾区」。很多人停留在"ArrayList底层是数组，LinkedList底层是链表"这个层面，一到源码追问就卡壳。
我整理了10道2026年高频集合源码面试题，每道都配了核心源码解读。文末有完整面试话术，直接拿去用。
1. HashMap的put流程是怎样的？
这题必问。核心看 hash扰动 → 数组定位 → 链表/红黑树插入 → 扩容判断。
// HashMap.put() 简化版核心流程（JDK 17）
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){
Node<K,V>[]tab;Node<K,V>p;intn,i;
// ① table为空则初始化（延迟初始化）
if((tab=table)==null||(n=tab.length)==0)
n=(tab=resize()).length;
// ② 通过 (n-1)&hash 计算桶位，空则直接放入
if((p=tab[i=(n-1)&hash])==null)
tab[i]=newNode(hash,key,value,null);
else{
// ③ 桶位有元素——链表或红黑树
Node<K,V>e;Kk;
if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))
e=p;// key相同，覆盖 → ⑧
elseif(pinstanceofTreeNode)
e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);// 红黑树
else{
for(intbinCount=0;;++binCount){
if((e=p.next)==null){// ④ 尾插法追加
p.next=newNode(hash,key,value,null);
if(binCount>=TREEIFY_THRESHOLD-1)// ⑤ 链表≥8→转红黑树
treeifyBin(tab,hash);
break;
}
if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))
break;// key已存在
p=e;
}
}
if(e!=null){// ⑧ 覆盖旧值
VoldValue=e.value;
if(!onlyIfAbsent||oldValue==null)e.value=value;
returnoldValue;
}
}
if(++size>threshold)resize();// ⑥ 超过阈值，扩容
returnnull;
}
面试话术：先讲1.8以后改用尾插法解决死循环，再说链表≥8且数组≥64才转红黑树。追问为什么阈值是8——泊松分布下链表长度到8的概率不到千万分之一。
2. HashMap为什么用红黑树不用AVL树？
红黑树是弱平衡（最长路径≤最短路径2倍），AVL是严格平衡。HashMap选红黑树的原因：插入删除更快。
| 对比维度 | 红黑树 | AVL树 |
|---|---|---|
| 平衡度 | 弱平衡（≤2倍） | 严格平衡（≤1） |
| 插入旋转 | 最多2次 | 可能O(logn)次 |
| 查询速度 | 略慢（深度差2倍） | 略快 |
| 适用场景 | 频繁插入删除 | 频繁查询 |
HashMap要同时处理put（插入）和get（查询），红黑树在写多的场景下更优。
3. ConcurrentHashMap怎么保证线程安全？
JDK 7 → JDK 8 是这道题的亮点：
- JDK 7：分段锁（Segment extends ReentrantLock），默认16段，锁粒度粗
- JDK 8+：CAS + synchronized锁链表头节点，锁粒度到桶级
// JDK 17 ConcurrentHashMap.putVal 核心
finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent){
// ...省略初始化代码
for(Node<K,V>[]tab=table;;){
Node<K,V>f;intn,i,fh;
if(tab==null||(n=tab.length)==0)
tab=initTable();
elseif((f=tabAt(tab,i=(n-1)&hash))==null){
// ① 桶位为空 → CAS写入，无锁
if(casTabAt(tab,i,null,newNode<K,V>(hash,key,value,null)))
break;
}
elseif((fh=f.hash)==MOVED)// ② 正在扩容 → 帮助迁移
tab=helpTransfer(tab,f);
else{
// ③ 桶位有数据 → synchronized锁头节点
synchronized(f){/* ...写入逻辑... */}
}
}
}
亮点：① 初始化用了CAS+SIZECTL自旋（不用synchronized），② 扩容时其他线程帮助迁移数据，③ size()不锁全表用CounterCell累加。
4. ArrayList扩容机制
// JDK 17 ArrayList.grow()
privateObject[]grow(intminCapacity){
intoldCapacity=elementData.length;
// 新容量 = 旧 × 1.5
intnewCapacity=oldCapacity+(oldCapacity>>1);
if(newCapacity-minCapacity<=0)// 不够就用minCapacity
newCapacity=minCapacity;
returnelementData=Arrays.copyOf(elementData,newCapacity);
}
关键数字：默认容量10，扩容倍率1.5（>> 1）。追问为什么是1.5——经统计计算，1.5倍在空间浪费和扩容频率间最优。扩容用Arrays.copyOf是浅拷贝。
5. ArrayList vs LinkedList
| 维度 | ArrayList | LinkedList |
|---|---|---|
| 底层 | Object[] | 双向链表Node |
| 随机访问 | O(1) | O(n) |
| 头插 | O(n) | O(1) |
| 尾插(无扩容) | O(1) | O(1) |
| 内存占用 | 仅数据+数组尾部空隙 | 数据+prev/next指针 |
面试陷阱：「LinkedList插入删除总是O(1)」——错误。只有给定节点位置的插入才是O(1)。add(index, E)需要先O(n)遍历找到位置。
6. HashSet底层
HashSet就是HashMap的马甲：
publicHashSet(){map=newHashMap<>();}
publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;}
// PRESENT = new Object() // 静态Dummy对象当value
所以HashSet的add调用HashMap的put，元素当key，PRESENT当value。
7. TreeMap vs HashMap
| 维度 | HashMap | TreeMap |
|---|---|---|
| 底层 | 数组+链表+红黑树 | 红黑树 |
| 排序 | 无序 | 按key自然序或Comparator |
| 时间复杂度 | O(1) ~ O(logn) | O(logn) |
| null key | 允许1个 | 不允许 |
面试亮点：TreeMap实现NavigableMap接口，支持firstKey()、lastKey()、subMap()等范围查询。适合需要按key排序的场景。
8. LinkedHashMap实现LRU
// 构造时accessOrder=true → 按访问顺序排序
LinkedHashMap<K,V>cache=newLinkedHashMap<>(16,0.75f,true){
@Override
protectedbooleanremoveEldestEntry(Map.Entry<K,V>eldest){
returnsize()>100;// 超过100个移除最老
}
};
LinkedHashMap在HashMap基础上加了双向链表维护插入/访问顺序，LRU缓存是所有大厂的经典题。
9. CopyOnWriteArrayList
publicbooleanadd(Ee){
synchronized(lock){// 全局锁
Object[]es=getArray();
intlen=es.length;
es=Arrays.copyOf(es,len+1);// 拷贝新数组
es[len]=e;
setArray(es);
returntrue;
}
}
写时复制：写操作锁整个数组+拷贝全量数据；读操作完全无锁。适合读多写极少场景（如黑名单列表）。写频繁时不适用。
10. JDK 21 集合框架新特性
SequencedCollection 接口带来了有序集合的统一API：
interface SequencedCollection<E>extendsCollection<E>{
SequencedCollection<E>reversed();// 反转视图
voidaddFirst(E);voidaddLast(E);
EgetFirst();EgetLast();
EremoveFirst();EremoveLast();
}
List、LinkedHashSet、SortedSet、Deque都实现了这个接口。以前list.get(0)、deque.getFirst()风格不统一的问题彻底解决。
面试速答卡
| 题目 | 一句话答案 |
|---|---|
| HashMap结构 | 数组+链表+红黑树，1.8后尾插法 |
| 扩容触发 | size > capacity*0.75 |
| 链表转树条件 | 长度≥8 且 数组≥64 |
| ConcurrentHashMap锁 | JDK8+：CAS+synchronized锁头节点 |
| ArrayList扩容 | 1.5倍，Arrays.copyOf |
| HashSet | HashMap的key，value是PRESENT |
这10道题覆盖了集合框架80%的面试考点。理解源码比背答案更重要——面试官追问到细节时，看过源码的人优势明显。
参考：JDK 17/21 源码，HashMap/ConcurrentHashMap源码注释