HashMap → ConcurrentHashMap → 并发集合追问链#

追问路径#

Q: HashMap底层数据结构是什么？
→ 数组 + 链表 + 红黑树（JDK8+）
  Q: 链表转红黑树的阈值为什么是8？
  → 泊松分布下，链表长度达到8的概率小于千万分之一，是空间与时间的平衡点
    Q: HashMap的扩容机制？
    → 容量翻倍，rehash时利用高位bit判断新位置（原位或原位+oldCap）
      ├─ Q: 多线程同时put会怎样？
      │  → JDK7环形链表死循环；JDK8数据覆盖丢失
      │    Q: ConcurrentHashMap怎么解决线程安全？
      │    → JDK7分段锁(Segment)；JDK8 CAS+synchronized锁单个Node
      │      Q: ConcurrentHashMap的size()怎么保证准确？
      │      → baseCount + CounterCell数组，类似LongAdder分散竞争
      │        Q: 和LongAdder是什么关系？
      │        → 同源设计，Doug Lea实现，都用@Contended避免伪共享
      └─ Q: equals和hashCode有什么约定？
         → 重写equals必须重写hashCode，否则HashMap无法正确定位
           Q: hash冲突严重怎么优化？
           → 扰动函数：(h = key.hashCode()) ^ (h >>> 16)，高低位混合减少冲突

plaintext

涉及知识点#

HashMap底层原理 — 数组+链表+红黑树结构
HashMap扩容机制 — 2倍扩容与rehash优化
ConcurrentHashMap原理 — JDK7分段锁 vs JDK8 CAS+synchronized
equals与hashCode — Object契约与HashMap正确性
CAS原理与ABA问题 — ConcurrentHashMap的无锁写入基础
synchronized原理与锁升级 — 偏向锁→轻量级→重量级
AQS原理 — JUC锁的底层框架
伪共享与缓存行 — @Contended与CounterCell优化

核心串联逻辑#

HashMap结构：数组存Node，hash冲突用链表，链表长度≥8且数组长度≥64时转红黑树（O(n)→O(logn)）
扩容：负载因子0.75触发，容量翻倍；JDK8利用(e.hash & oldCap) == 0判断新位置，无需重算hash
线程不安全：JDK7头插法并发扩容导致环形链表；JDK8尾插法解决了环但仍有数据覆盖
ConcurrentHashMap演进：
- JDK7：16个Segment，每个Segment是一个小HashMap，并发度=Segment数
- JDK8：锁粒度细化到Node级别，CAS写baseCount，竞争激烈时用CounterCell分散

代码示例：

// ConcurrentHashMap JDK8 put核心逻辑
if (tab[i] == null)
    casTabAt(tab, i, null, new Node<>(hash, key, value)); // CAS写空槽
else
    synchronized (f) { /* 锁住链表头/树根 */ }

java

面试回答串联#

30秒速答#

“HashMap底层是数组+链表+红黑树，链表长度≥8转树。多线程不安全，JDK7会死循环。ConcurrentHashMap在JDK8用CAS+synchronized锁单个Node解决并发，size()用CounterCell分散竞争类似LongAdder。“

2分钟展开答#

“HashMap用数组存储Node节点，通过hash值定位数组下标。hash冲突时JDK8用尾插法链表，链表长度≥8且数组≥64时转红黑树，将O(n)查找优化到O(logn)。扩容时容量翻倍，利用高位bit直接判断新位置避免重算hash。多线程下JDK7的头插法扩容会形成环形链表导致死循环，JDK8虽然改用尾插法但仍存在数据覆盖问题。ConcurrentHashMap在JDK8弃用了分段锁，改为对链表头Node加synchronized锁+CAS写空槽，锁粒度从Segment级别细化到Node级别。它的size()方法借鉴LongAdder思想，用baseCount+CounterCell数组分散CAS竞争，还用@Contended注解避免伪共享。“

HashMap → ConcurrentHashMap → 并发集合 追问链#

追问路径#

涉及知识点#

核心串联逻辑#

面试回答串联#

30秒速答#

2分钟展开答#

相关追问链#

HashMap → ConcurrentHashMap → 并发集合追问链#