Java面试秋招集合框架源码剖析
第4章 集合框架源码剖析
面试重要程度：⭐⭐⭐⭐⭐常见提问方式：HashMap底层实现、ConcurrentHashMap线程安全预计阅读时间：35分钟
开场白
兄弟，集合框架绝对是Java面试的重头戏！我敢说，90%的Java面试都会问到HashMap，80%会问到ConcurrentHashMap。这些不仅是基础知识，更能体现你对Java底层原理的理解深度。
今天我们就把这些核心集合类的源码彻底剖析一遍，让你在面试中游刃有余。
🎯 字节真题：手写LRU缓存实现
面试场景：
面试官："请手写一个LRU缓存，要求O(1)时间复杂度的get和put操作"
标准实现：
public class LRUCache {
private final int capacity;
private final Map<Integer, Node> cache;
private final Node head, tail;
class Node {
int key, value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
// 创建虚拟头尾节点
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) return -1;
// 移动到头部（最近使用）
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
// 更新值并移到头部
node.value = value;
moveToHead(node);
} else {
// 新节点
Node newNode = new Node(key, value);
if (cache.size() >= capacity) {
// 删除尾部节点
Node last = removeTail();
cache.remove(last.key);
}
cache.put(key, newNode);
addToHead(newNode);
}
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node last = tail.prev;
removeNode(last);
return last;
}
}
🔥 腾讯真题：HashMap死循环问题分析
面试场景：
面试官："JDK 7的HashMap在并发环境下可能出现死循环，能分析一下原因吗？"
问题分析：
// JDK 7的扩容代码（简化版）
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; // 1. 保存下一个节点
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); // 2. 计算新位置
e.next = newTable[i]; // 3. 头插法
newTable[i] = e; // 4. 放入新位置
e = next; // 5. 处理下一个节点
}
}
}
// 死循环场景：
// 线程1和线程2同时扩容，头插法导致链表环形
// 原链表：A -> B -> null
// 线程1执行到步骤1后被挂起：e=A, next=B
// 线程2完成扩容：B -> A -> null
// 线程1继续执行：A -> B -> A（形成环）
JDK 8的解决方案：
// JDK 8使用尾插法，避免了死循环 // 扩容时保持原有顺序 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; // ... 尾插法实现
🗺️ 4.1 HashMap源码深度分析
HashMap的基本结构
面试必问：
面试官："说说HashMap的底层数据结构是什么？"
标准回答：
// HashMap的核心数据结构
public class HashMap<K,V> {
// 底层数组，存储Node节点
transient Node<K,V>[] table;
// 链表节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 哈希值
final K key; // 键
V value; // 值
Node<K,V> next; // 下一个节点
}
// 红黑树节点（JDK 8+）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 前一个节点
boolean red; // 红黑树颜色
}
}
数据结构演进：
JDK 7及以前：数组 + 链表 JDK 8及以后：数组 + 链表 + 红黑树
哈希算法实现
面试重点：
面试官："HashMap是如何计算哈希值的？为什么要这样设计？"
源码分析：
// 计算哈希值的方法
static final int hash(Object key) {
int h;
// 1. 获取key的hashCode
// 2. 高16位与低16位异或，减少哈希冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 根据哈希值计算数组索引
// 等价于 hash % table.length，但位运算更快
int index = (table.length - 1) & hash;
为什么要异或运算？
// 示例说明 int hashCode = "java".hashCode(); // 假设为 0x12345678 int h = hashCode >>> 16; // 高16位：0x00001234 int finalHash = hashCode ^ h; // 0x12345678 ^ 0x00001234 = 0x1234564C // 这样做的好处： // 1. 让高位也参与运算，减少冲突 // 2. 保持低位的随机性 // 3. 运算速度快
put方法源码解析
面试高频：
面试官："说说HashMap的put方法执行流程"
源码分析：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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. 如果table为空，进行初始化
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);
// 链表长度>=8，转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到相同key，准备覆盖
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 6. 覆盖旧值
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;
}
扩容机制详解
面试重点：
面试官："HashMap什么时候扩容？扩容过程是怎样的？"
扩容触发条件：
// 当元素个数超过阈值时扩容
// threshold = capacity * loadFactor
// 默认loadFactor = 0.75
if (++size > threshold)
resize();
扩容过程：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 已达到最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 容量翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 阈值也翻倍
}
// 创建新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 重新分布元素
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
Java面试圣经 文章被收录于专栏
Java面试圣经，带你练透java圣经
