← 返回学习路线

SYSTEM

集合

八股三、集合system
src/content/notes/system/集合.md

三、集合

3.1 HashMap

HashMap 基于哈希表实现,1.8 是数组 + 链表 + 红黑树。

put 流程:

  1. 对 key 求 hash = (h = key.hashCode()) ^ (h >>> 16)——扰动让高位也参与桶定位,减少碰撞。
  2. 桶下标 index = (n-1) & hash,数组长度为 2 的幂保证等价取模且散列均匀。
  3. 桶为空直接放;桶有元素,比较 key:相同则覆盖,不同尾插链表。
  4. 链表长度 ≥8 且数组 ≥64 转红黑树(查找 O(log n));树节点 ≤6 退化为链表。
  5. 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