- 正确答案：HashMap在JDK 8及以后的底层实现是数组 + 链表 + 红黑树的混合结构，采用拉链法解决哈希冲突；默认初始容量为16，负载因子0.75，当单个桶中链表长度≥8且数组长度≥64时，链表转为红黑树；扩容时触发rehash，新容量为原容量的2倍。ConcurrentHashMap在JDK 8中摒弃了分段锁（Segment），改用CAS + synchronized（细粒度锁）+ Node数组 + 链表/红黑树实现线程安全；其核心是将锁粒度从整个table降低到单个Node桶（即对首节点加synchronized），同时使用volatile修饰关键字段（如tab、nextTable、sizeCtl）保证可见性；扩容过程支持多线程协作推进，通过ForwardingNode标记正在迁移的桶，并利用sizeCtl控制扩容状态。 - 解答思路：先分别拆解两个类的演进脉络——HashMap从JDK 7（数组+链表+头插法+死循环风险）到JDK 8（尾插法+红黑树优化+避免链表过长导致O(n)查找）的关键改进；ConcurrentHashMap则需对比JDK 7（基于Segment分段锁，16段独立锁）与JDK 8（无Segment，CAS+synchronized on first node）的设计哲学转变。重点说明“为什么这样设计”：比如HashMap不直接全用红黑树是因为小规模数据下链表更轻量（无树节点开销、无旋转逻辑）；ConcurrentHashMap避免全局锁是为了提升并发吞吐，而选择synchronized而非ReentrantLock是因为JVM对synchronized做了大量优化（偏向锁→轻量级锁→重量级锁的自适应升级），且synchronized可精确作用于单个桶头节点，锁范围最小化。 - 深度知识讲解： 1. HashMap底层核心字段： - transient Node[] table：主哈希桶数组，延迟初始化（首次put时init），长度始终为2的幂次（便于用位运算替代取模：index = hash & (length-1)）； - static class Node implements Map.Entry：基础链表节点，含hash、key、value、next四个字段； - static final class TreeNode extends LinkedHashMap.Entry：红黑树节点，继承自LinkedHashMap.Entry（含before/after指针，支持遍历顺序），额外含parent、left、right、red等字段； - transient int size：实际键值对数量； - int threshold：扩容阈值 = capacity × loadFactor； - final float loadFactor：负载因子，默认0.75，权衡时间与空间——过高则哈希冲突加剧，过低则浪费内存； - transient int modCount：用于fail-fast机制，每次结构性修改（add/remove）递增，迭代器创建时记录该值，遍历时校验是否一致，不一致抛ConcurrentModificationException。 2. HashMap put流程（JDK 8）： - 计算key.hashCode() → 再散列（h ^ (h >>> 16)）增强低位随机性； - index = (n - 1) & hash（n为table.length，必须是2的幂，保证均匀分布）； - 若table[index]为空，直接CAS插入（无竞争时）； - 若为普通Node，则遍历链表：存在相同key（equals+hash相等）则覆盖value；否则尾插新Node； - 若为TreeNode，则调用putTreeVal()走红黑树插入逻辑； - 插入后检查：若链表长度≥8且table.length≥64，则treeifyBin()将该桶转为红黑树；若table.length < 64，则优先resize()扩容而非树化（因扩容本身能缓解冲突）； - 若size > threshold，触发resize()：新建2倍容量数组，遍历旧数组，每个桶内节点按hash & oldCap==0或1分为两组（因新容量为2倍，高位bit决定归属），保持相对顺序（尾插法保障），无需重新hash计算。 3. ConcurrentHashMap核心机制（JDK 8）： - 关键字段： - transient volatile Node[] table：同HashMap，但声明为volatile，保证多线程读可见； - private transient volatile Node[] nextTable：扩容时的新数组，仅在扩容期间非null； - private transient volatile long baseCount：基础计数器，CAS更新； - private transient volatile int sizeCtl：核心状态控制器，含义随阶段变化： * -1：table正在初始化； * -(1 + nThreads)：有n个线程正在扩容； * 0：未初始化，首次put时设为DEFAULT_CAPACITY（16）； * >0：下次扩容阈值（类似HashMap.threshold）； - static final class ForwardingNode extends Node：扩容专用节点，其nextTable指向newTable，find()方法会跳转到新表查找，确保扩容期间读操作不阻塞。 - put操作（核心是无锁读 + CAS写 + 必要时synchronized）： * 若table为空，先通过CAS初始化（compareAndSet(table, null, newTab)）； * 计算i = (n-1) & hash，定位桶； * 若table[i]为null，尝试CAS插入Node； * 若table[i]为ForwardingNode，说明该桶正在迁移，当前线程协助扩容（helpTransfer）； * 否则synchronized锁住table[i]（即桶首节点），在临界区内执行链表/树插入逻辑（与HashMap一致），插入后检查是否需树化或扩容； * 更新baseCount（CAS），并判断是否触发扩容（checkResize()：若sizeCtl < 0说明已在扩容中；否则若size > sizeCtl，则tryPresize()启动扩容）。 - 扩容机制（多线程协作）： * 调用transfer(tab, nextTab)，nextTab由当前线程创建（大小为2×tab.length）； * 每个线程分配一个「任务区间」（如从i=15到i=0），逆序遍历旧表； * 对每个桶，若为空，直接写入ForwardingNode； * 若为普通链表，按hash & oldCap拆分为低位链（留在原索引）和高位链（新索引 = 原索引 + oldCap）； * 若为红黑树，同样拆分为两棵子树，若某子树节点数≤6则退化为链表； * 每处理完一个桶，将table[i]设为ForwardingNode； * 所有线程完成各自区间后，更新sizeCtl为新阈值，并清空nextTable。 - 线程安全性保障点： * volatile字段（table、nextTable、sizeCtl）保证状态变更对其他线程立即可见； * CAS操作（如初始化table、更新baseCount、设置sizeCtl）保证原子性； * synchronized锁定粒度为单个桶头节点，避免全局锁，极大提升并发度； * ForwardingNode作为「迁移中」标记，使读操作可无缝转向新表，写操作可协助迁移，实现无停顿扩容（pauseless resize）。 4. 对比总结： - 安全性：HashMap完全不安全，多线程put可能造成数据丢失、死循环（JDK 7）、或覆盖；ConcurrentHashMap提供强线程安全，满足高并发读写场景； - 性能：HashMap单线程性能最优；ConcurrentHashMap在多线程下远优于Collections.synchronizedMap或Hashtable（后者全表锁）； - 内存：ConcurrentHashMap因ForwardingNode、额外volatile字段、树节点等略高；但相比Segment方案（JDK 7）已大幅节省； - 迭代器：HashMap迭代器弱一致性（fail-fast），ConcurrentHashMap迭代器弱一致性（weakly consistent），可容忍并发修改，不抛异常，但可能反映某一时刻的快照（不保证反映所有修改）。 - 伪代码示例（ConcurrentHashMap put核心逻辑简化）： ``` public V put(K key, V value) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); // 类似h ^ (h >>> 16) int binCount = 0; for (Node[] tab = table;;) { Node f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); // CAS初始化 else if ((f = tabAt(tab, i = (n-1)&hash)) == null) { if (casTabAt(tab, i, null, new Node(hash, key, value, null))) break; // 成功插入 } else if ((fh = f.hash) == MOVED) // ForwardingNode tab = helpTransfer(tab, f); // 协助扩容 else { V oldVal = null; synchronized (f) { // 锁定桶首节点 if (tabAt(tab, i) == f) { if (fh >= 0) { // 链表 binCount = 1; for (Node e = f;; ++binCount) { if (e.hash == hash && ((e.key == key) || (e.key != null && key.equals(e.key)))) { oldVal = e.val; e.val = value; break; } Node pred = e; if ((e = e.next) == null) { pred.next = new Node(hash, key, value, null); break; } } } else if (f instanceof TreeBin) // 红黑树 oldVal = ((TreeBin)f).putTreeVal(hash, key, value); } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); // 可能触发扩容 if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); // 更新计数，检查扩容 return null; } ```

腾讯混元后台一面面经

全站热榜

创作者周榜