SYSTEM
集合
src/content/notes/system/集合.md 三、集合
3.1 HashMap
HashMap 基于哈希表实现,1.8 是数组 + 链表 + 红黑树。
put 流程:
- 对 key 求
hash = (h = key.hashCode()) ^ (h >>> 16)——扰动让高位也参与桶定位,减少碰撞。 - 桶下标
index = (n-1) & hash,数组长度为 2 的幂保证等价取模且散列均匀。 - 桶为空直接放;桶有元素,比较 key:相同则覆盖,不同尾插链表。
- 链表长度 ≥8 且数组 ≥64 转红黑树(查找 O(log n));树节点 ≤6 退化为链表。
- size 超阈值(
capacity * 0.75)触发扩容,2 倍扩容后 rehash。
// HashMap 关键源码逻辑(简化)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent) {
Node<K,V>[] tab = table;
int n = tab.length;
int i = (n - 1) & hash; // 桶下标
Node<K,V> p = tab[i];
if (p == null) {
tab[i] = newNode(hash, key, value, null); // 空桶直接放
} else {
// 桶非空:链表/树查找或尾插
for (int binCount = 0; ; binCount++) {
if (p.next == null) { // 链表尾部
p.next = newNode(hash, key, value, null); // 1.8 尾插
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash); // 转红黑树
break;
}
if (p.hash == hash && eq(key, p.key)) break; // 找到相同 key
p = p.next;
}
}
// ... 覆盖旧值、检查扩容
return null;
}
1.7 头插法死循环:扩容时链表迁移用头插,并发下两线程同时 rehash,迁移过程链表节点互相指向形成环形链表,后续 get 死循环 CPU 100%。
1.8 改进:尾插法保持链表原顺序,避免环形链表;引入红黑树解决哈希碰撞极端情况退化为 O(n)。但 1.8 仍非线程安全,并发下可能丢数据,需用 ConcurrentHashMap。
面试题:HashMap 的 put 流程?
先对 key 扰动求 hash,按
(n-1)&hash定位桶。空桶直接放;非空遍历链表/树,key 相同覆盖、不同尾插。链表长度≥8 且数组≥64 转红黑树。size 超阈值(0.75 × 容量)触发 2 倍扩容并 rehash。
面试题:HashMap 1.7 和 1.8 有什么区别?
三点:1.7 纯数组+链表,1.8 增加红黑树,链表≥8 转 tree 解决碰撞退化;1.7 头插法,并发扩容会形成环形链表导致 get 死循环,1.8 改尾插法保持原顺序避免环;1.7 扩容 rehash 重新计算位置,1.8 利用高位 bit 判断位置(原位置或原位置+旧容量)优化迁移。
3.2 ConcurrentHashMap
1.7 结构:Segment[] + HashEntry[],Segment 继承 ReentrantLock,默认 16 段,并发度 16。每个段是一把独立锁,不同段操作不互斥。
1.8 结构:去掉 Segment,用 Node[] + CAS + synchronized。空桶用 CAS 写入;非空桶 synchronized 锁住桶头节点,粒度从段降到桶,并发度大幅提升。
// 1.8 ConcurrentHashMap put 核心(简化)
final V putVal(K key, V value, boolean onlyIfAbsent) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
int i = (n - 1) & hash;
Node<K,V> f = tab[i];
if (f == null) {
if (casTabAt(tab, i, null, new Node<>(hash, key, value)))
break; // 空桶 CAS 写入,无锁
} else if ((fh = f.hash) == MOVED) {
tab = helpTransfer(tab, f); // 协助扩容
} else {
synchronized (f) { // 锁桶头节点
// 链表/树插入
}
}
}
}
sizeCtl 是并发扩容控制核心:-1 表示初始化,-(N+1) 表示 N 个线程在扩容,正数表示阈值。扩容时多线程协助迁移,迁移完的桶放 ForwardingNode,get 时转发到新表。
面试题:ConcurrentHashMap 1.7 和 1.8 的区别?
1.7 用 Segment 分段锁,每段是 ReentrantLock+HashEntry 数组,并发度等于段数(默认16),锁粒度在段。1.8 去掉 Segment,改用 Node 数组+CAS+synchronized,空桶 CAS 无锁写入,非空桶 synchronized 锁桶头节点,锁粒度降到桶级,并发度等于桶数。1.8 还引入红黑树、多线程协助扩容(ForwardingNode+sizeCtl),数据结构与并发度都优于 1.7。1.7 分段锁的原因是 CAS 普及前分段是降低锁竞争的折中,1.8 在 CAS 成熟后直接桶级加锁更高效。
3.3 ArrayList vs LinkedList
| 维度 | ArrayList | LinkedList |
|---|---|---|
| 底层结构 | 动态数组 | 双向链表 |
| 随机访问 | O(1) | O(n) |
| 头部插入 | O(n)(数组拷贝) | O(1)(指针修改) |
| 尾部插入 | 均摊 O(1)(扩容摊销) | O(1) |
| 中间插入 | O(n) | 查找 O(n)+插入 O(1) |
| 内存 | 连续、紧凑 | 每节点多两个指针 |
| 实现 | List+RandomAccess |
List+Deque |
| 场景 | 读多写少、随机访问 | 频繁头尾增删、作队列 |
ArrayList 扩容 1.5 倍,用 System.arraycopy 拷贝。LinkedList 实现了 Deque,可当栈/队列用,但随机访问慢。
// ArrayList 尾插与扩容核心
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 容量不足则扩容 1.5 倍
elementData[size++] = e;
return true;
}
private void grow(int minCapacity) {
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍
elementData = Arrays.copyOf(elementData, newCapacity); // 数组拷贝
}
实际项目几乎不选 LinkedList 作 List:它的中间插入需要先 O(n) 查找节点,所谓”插入快”优势不存在;内存占用还高。需要队列用 ArrayDeque 更好。
3.4 CopyOnWriteArrayList
写时复制(Copy-On-Write)策略:写操作用 ReentrantLock 加锁,复制出新数组写完再替换引用;读操作完全无锁,直接读 volatile 数组引用。
// CopyOnWriteArrayList 写核心
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray(); // 读旧数组
Object[] newElements = Arrays.copyOf(elements, elements.length + 1); // 复制
newElements[elements.length] = e; // 写新数组
setArray(newElements); // volatile 引用切换
return true;
} finally { lock.unlock(); }
}
// 读无锁
public E get(int index) {
return get(getArray(), index); // 直接读 volatile 数组快照
}
弱一致性:读线程读到的是读时刻的数组快照,写线程提交后读未必立刻看到新值,但最终一致。适合读多写少、可容忍短暂不一致的场景:配置列表、白名单、监听器列表。缺点:写时复制内存翻倍,不适合写频繁场景。
3.5 BlockingQueue
| 实现 | 底层 | 容量 | 锁 | 特点 |
|---|---|---|---|---|
| ArrayBlockingQueue | 数组 | 有界(构造指定) | 一把 ReentrantLock | 公平可选、有界防 OOM |
| LinkedBlockingQueue | 链表 | 默认 Integer.MAX_VALUE |
两把锁(入/出分离) | 吞吐高、默认无界有 OOM 风险 |
| SynchronousQueue | 无存储 | 0 | CAS 传递 | 直接交付,put 阻塞到有 take |
| PriorityBlockingQueue | 堆 | 无界 | 单锁 | 按优先级出队 |
| DelayQueue | 优先级堆 | 无界 | 单锁 | 延时出队,定时任务用 |
为什么 LinkedBlockingQueue 用两把锁? 入队和出队操作的是链表不同端,分离锁后可同时进行,吞吐量高于 ArrayBlockingQueue 的单锁。但默认容量 Integer.MAX_VALUE 等同无界,任务堆积易 OOM——这正是 Executors.newFixedThreadPool 用它的隐患。
线程池选择队列的依据:FixedPool/SinglePool 用 LinkedBQ(缓存任务);CachedPool 用 SynchronousQ(无缓存,直接交付给新线程);需有界防 OOM 手动构造时显式设容量。
// BlockingQueue 阻塞语义
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(100);
// 生产者:满则阻塞
queue.put(new Task()); // 满了阻塞等待
// 消费者:空则阻塞
Task task = queue.take(); // 空了阻塞等待
// 非阻塞尝试
queue.offer(new Task(), 3, TimeUnit.SECONDS); // 3秒内未入队返回 false
Task t = queue.poll(3, TimeUnit.SECONDS); // 3秒内无任务返回 null