Java HashMap 与 ConcurrentHashMap 核心原理总结：从 Hash 冲突到 LongAdder

一、Hash 冲突是什么Hash 表的核心思想是通过hash算法把一个key映射到数组中的某个位置。例如int index hash(key) % table.length;但是不同的key经过 hash 计算之后可能得到相同的数组下标。这种情况就叫Hash 冲突比如key1 - index 3 key2 - index 3这两个不同的 key 都想放到数组下标 3 的位置这就发生了 Hash 冲突。二、Hash 冲突的解决方案常见的 Hash 冲突解决方案有几种。1. 链地址法链地址法也叫拉链法。数组的每个位置不只存一个元素而是存一个链表。数组下标 0 - null 数组下标 1 - A - B - C 数组下标 2 - null 数组下标 3 - D如果多个 key 都落到同一个桶里就把它们挂成链表。Java 的HashMap主要采用的就是这种方式。2. 开放地址法开放地址法的思路是当前位置被占了就继续找下一个空位置。常见方式有线性探测index 1, index 2 ... 二次探测index 1², index 2² ... 双重 hash使用另一个 hash 函数重新定位3. 再哈希如果冲突比较严重可以使用新的 hash 函数重新计算位置。4. 扩容当 HashMap 中元素越来越多时数组容量不够就会扩容。比如16 - 32 - 64 - 128扩容后元素会重新分布Hash 冲突可能会减少。5. 链表转红黑树JDK 1.8 之后HashMap在链表过长时会把链表转成红黑树。链表查询效率是O(n)红黑树查询效率是O(log n)所以当冲突严重时红黑树可以提高查询效率。三、HashMap 的扩容机制HashMap扩容主要由负载因子决定。默认负载因子是0.75扩容判断公式是元素数量 数组容量 * 负载因子比如默认数组容量是 1616 * 0.75 12当元素数量超过 12 时就会扩容16 - 32所以负载因子的作用就是决定 HashMap 什么时候扩容。四、为什么 HashMap 默认负载因子是 0.75负载因子太大数组利用率高但是 Hash 冲突变多查询变慢。负载因子太小Hash 冲突少查询快但是浪费空间。所以0.75是一个折中值既保证空间利用率又尽量减少 Hash 冲突。五、HashMap 为什么链表长度到 8 才转红黑树JDK 1.8 之后HashMap有几个重要阈值TREEIFY_THRESHOLD 8; UNTREEIFY_THRESHOLD 6; MIN_TREEIFY_CAPACITY 64;意思是链表长度 8并且数组长度 64才会转红黑树。为什么是 8因为正常情况下hash 分布应该是比较均匀的。如果一个桶里的链表长度都达到 8 了说明这个桶的 Hash 冲突已经比较严重了。继续用链表查询效率会变差。所以达到一定长度后就考虑转红黑树。六、为什么数组长度小于 64 时不转红黑树这是一个很重要的面试点。如果数组长度还很小比如16 或 32这时候发生链表过长不一定是 hash 算法太差也可能只是因为数组太小桶太少元素挤在一起了。所以这时候更好的方案不是转红黑树而是优先扩容。扩容后元素会重新分布原来一个桶里的链表可能会被拆散。所以规则是数组长度 64 优先扩容 数组长度 64 链表还很长才转红黑树注意64 不是扩容条件而是是否允许链表转红黑树的条件。HashMap 正常扩容还是看元素数量 数组容量 * 负载因子七、红黑树什么时候退回链表还有一个阈值UNTREEIFY_THRESHOLD 6;意思是当红黑树中的节点数量减少到 6 左右时可能会退回链表。为什么不是 8这是为了避免频繁转换。如果 8 转树8 又退回链表那么节点数量在 7、8 之间变化时就会频繁地链表和红黑树互相转换。所以设计成8链表转红黑树 6红黑树退回链表中间留了一个缓冲区。八、ConcurrentHashMap 是干什么的普通的HashMap是线程不安全的。在多线程环境下如果多个线程同时 put、remove可能会导致数据异常。所以 Java 提供了线程安全的 MapConcurrentHashMap它的作用是在多线程环境下安全地操作 Map同时尽量保证较高性能。九、JDK 1.7 的 ConcurrentHashMap 设计JDK 1.7 的ConcurrentHashMap使用的是Segment 分段锁整体结构大概是ConcurrentHashMap ├── Segment 0 ├── Segment 1 ├── Segment 2 ... └── Segment 15每个Segment都类似一个小型的 HashMap。结构可以理解成Segment HashEntry 数组 链表 ReentrantLock每个Segment自己有一把锁。写操作时1. 根据 key 的 hash 定位 Segment 2. 锁住这个 Segment 3. 在这个 Segment 里面进行 put 操作好处是不同 Segment 可以并发操作。比如线程 A 操作 Segment 1 线程 B 操作 Segment 7它们可以同时执行。但是问题是如果两个线程操作的是同一个 Segment即使它们操作的不是同一个桶也要竞争同一把锁。所以 JDK 1.7 的锁粒度还是比较大。十、ReentrantLock 是什么ReentrantLock是 Java 并发包里的可重入锁。包路径是java.util.concurrent.locks.ReentrantLock它的作用是保证同一时间只有一个线程进入某段代码。常见写法ReentrantLock lock new ReentrantLock(); lock.lock(); try { // 需要线程安全的代码 } finally { lock.unlock(); }为什么一定要写finally因为ReentrantLock需要手动释放锁。如果忘记unlock()其他线程可能永远拿不到锁。可重入是什么意思可重入的意思是同一个线程已经拿到这把锁后可以再次拿这把锁不会把自己卡死。比如public void methodA() { lock.lock(); try { methodB(); } finally { lock.unlock(); } } public void methodB() { lock.lock(); try { System.out.println(methodB); } finally { lock.unlock(); } }同一个线程进入methodA()后又进入methodB()可以再次获得同一把锁。十一、synchronized 是什么锁synchronized是 Java 自带的内置锁也叫对象锁 监视器锁 互斥锁 可重入锁它可以修饰方法也可以修饰代码块。普通同步方法public synchronized void test() { }锁的是当前对象 this静态同步方法public static synchronized void test() { }锁的是当前类的 Class 对象同步代码块synchronized (obj) { }锁的是括号里的 obj 对象synchronized也是可重入锁。十二、synchronized 和 ReentrantLock 的区别它们都可以保证线程安全也都是可重入锁。核心区别是synchronized 简单自动释放锁 ReentrantLock 灵活但是需要手动释放锁。对比synchronizedReentrantLock类型Java 关键字JUC 包下的类释放锁自动释放手动 unlock是否可重入是是公平锁不支持手动设置支持尝试加锁不支持支持 tryLock可中断等待不灵活支持 lockInterruptibly条件队列一个等待队列多个 Condition简单理解synchronized 是自动挡 ReentrantLock 是手动挡。普通场景用synchronized就够了。复杂并发控制比如需要公平锁、尝试加锁、可中断锁、多个条件队列时可以用ReentrantLock。十三、公平锁和非公平锁的区别公平锁谁先等待谁先获得锁。就像排队买东西先来先服务。非公平锁允许线程插队谁抢到算谁的。ReentrantLock默认是非公平锁ReentrantLock lock new ReentrantLock();等价于ReentrantLock lock new ReentrantLock(false);公平锁写法ReentrantLock lock new ReentrantLock(true);公平锁优点线程不容易饥饿。公平锁缺点性能相对低因为要维护排队顺序。非公平锁优点性能更高。非公平锁缺点可能导致某些线程等待很久。一句话总结公平锁讲顺序非公平锁讲效率。十四、JDK 1.8 的 ConcurrentHashMap 设计JDK 1.8 对ConcurrentHashMap做了很大改动。JDK 1.7 使用的是Segment 分段锁JDK 1.8 改成了CAS synchronized Node 数组 链表 红黑树底层结构大概是ConcurrentHashMap └── Node[] table ├── 桶 0 - 链表 / 红黑树 ├── 桶 1 - null ├── 桶 2 - 链表 / 红黑树 └── ...也就是说JDK 1.8 不再主要使用 Segment而是直接对数组桶进行并发控制。核心思想是能不加锁就不加锁 必须加锁时只锁当前桶。十五、JDK 1.8 的 put 流程执行map.put(张三, 18);大概流程是1. 根据 key 计算 hash 2. 根据 hash 找到数组下标 3. 如果桶为空用 CAS 插入 4. 如果桶不为空用 synchronized 锁住桶头节点 5. 如果链表过长转红黑树 6. 如果元素过多触发扩容1. 桶为空使用 CAS如果当前位置是空的table[i] null说明这个桶没有元素。这时候 JDK 1.8 会使用 CAS 直接插入。可以理解成如果 table[i] 还是 null就把新节点放进去 如果 table[i] 已经不是 null说明别的线程先插入了就重试。CAS 的好处是不需要加锁性能更高。2. 桶不为空使用 synchronized 锁桶头节点如果桶不为空table[i] - A - B - C说明发生了 Hash 冲突。这时候多个线程可能同时修改这个桶里的链表或红黑树所以必须加锁。JDK 1.8 锁的是当前桶的头节点synchronized (f) { // 操作当前桶 }这里的f就是桶的第一个节点。这不是锁整个 Map也不是锁整个数组而是只锁当前桶。所以叫桶级别加锁。这样如果两个线程操作不同桶就可以并发执行。十六、为什么 JDK 1.8 用 synchronized不用 ReentrantLock主要有三个原因。第一JDK 1.8 锁粒度变小了。JDK 1.7 锁的是 SegmentJDK 1.8 锁的是桶。锁的范围更小不需要给每个桶都单独维护一个ReentrantLock对象。第二synchronized已经被优化过了。JDK 1.6 之后synchronized做了很多优化比如偏向锁 轻量级锁 自旋锁 锁膨胀所以性能已经不错。第三使用更简单。直接锁桶头节点即可synchronized (f) { }不需要创建额外的锁对象也不需要手动释放锁。十七、JDK 1.8 的 get 为什么一般不加锁ConcurrentHashMap的get操作一般不加锁。因为 get 只是读操作1. 计算 hash 2. 找到桶 3. 遍历链表或红黑树 4. 返回 value它能不加锁是因为内部很多字段使用了volatile。例如 Node 中的volatile V val; volatile NodeK,V next;volatile可以保证可见性。简单理解一个线程 put 进去的数据另一个线程 get 的时候能够看到。所以 JDK 1.8 的ConcurrentHashMap是读操作基本无锁 写操作只锁当前桶。十八、JDK 1.8 的扩容机制ConcurrentHashMap是并发容器扩容时不能简单让所有线程都等待。所以 JDK 1.8 设计了多线程协助扩容。意思是线程 A 发现需要扩容开始迁移数据 线程 B 进来后发现正在扩容不是傻等而是一起帮忙迁移 线程 C 也可以帮忙。就像搬家一个人搬很慢多个人一起搬更快。扩容过程中如果某个桶已经迁移完成旧数组对应位置会放一个特殊节点ForwardingNode它的作用是告诉其他线程这个桶已经迁移到新数组了不要再操作旧桶。如果线程看到ForwardingNode就知道当前正在扩容可以去新数组查找或者帮助扩容。十九、ConcurrentHashMap 怎么统计 size普通HashMap可以简单使用size;但是ConcurrentHashMap不能这么做。因为在多线程环境下size不是原子操作。它大概分三步读取 size 加 1 写回 size多个线程同时执行时可能会丢失更新。所以 JDK 1.8 的ConcurrentHashMap使用类似LongAdder的思想baseCount CounterCell[]低并发时直接 CAS 修改 baseCount。高并发时如果多个线程同时修改 baseCount竞争很严重就把计数分散到 CounterCell[] 中。最后统计 size 时size baseCount 所有 CounterCell 的值比如baseCount 10 CounterCell[0] 3 CounterCell[1] 5 CounterCell[2] 2 size 10 3 5 2 20本质就是把一个热点计数变量拆成多个小计数器减少多线程竞争。你可以理解成人少时一个收银台就够了 人多时开多个收银台 最后把所有收银台的钱加起来。二十、LongAdder 是干什么的LongAdder是 JDK 1.8 提供的一个高并发计数器。它主要用来解决很多线程同时对一个数字做累加时AtomicLong 竞争太激烈的问题。比如统计访问次数LongAdder count new LongAdder(); count.increment(); count.add(5); long result count.sum();AtomicLong的问题是所有线程都抢同一个变量。高并发下会出现大量 CAS 失败和重试。而LongAdder的思想是把一个计数器拆成多个小计数器。它内部大概是base Cell[0] Cell[1] Cell[2] Cell[3]低并发时直接更新base。高并发时多个线程分散更新不同的Cell。最后调用sum()把它们加起来总数 base Cell[0] Cell[1] Cell[2] ...所以AtomicLong 是大家抢一个计数器 LongAdder 是把一个计数器拆成多个小计数器最后再求和。LongAdder 和 AtomicLong 的区别对比AtomicLongLongAdder底层思想一个变量 CASbase Cell 数组并发低性能很好也可以并发高CAS 竞争严重分散竞争性能更好获取值get()sum()适合场景精确更新高并发统计LongAdder的缺点是sum() 不是强一致的瞬间快照。因为调用sum()的时候其他线程可能还在修改 Cell。所以它更适合统计类场景比如访问量统计 点赞数统计 接口调用次数 QPS 统计二十一、JDK 1.7 和 JDK 1.8 ConcurrentHashMap 对比对比点JDK 1.7JDK 1.8核心结构Segment HashEntry 数组Node 数组锁机制ReentrantLockCAS synchronized锁粒度Segment 级别桶级别冲突处理链表链表 红黑树空桶插入锁 SegmentCAS 插入非空桶插入锁 Segmentsynchronized 锁桶头get 操作一般不加锁一般不加锁扩容Segment 内部扩容多线程协助扩容size 统计分段统计baseCount CounterCell[]二十二、面试总结版如果面试官问 HashMap可以这样回答HashMap 底层是数组 链表 红黑树。Hash 冲突时多个元素会放到同一个桶中形成链表。JDK 1.8 之后当链表长度达到 8并且数组长度达到 64 时会转成红黑树提高查询效率。如果数组长度小于 64会优先扩容因为此时冲突可能只是数组太小导致的。HashMap 的扩容由负载因子决定默认负载因子是 0.75当元素数量超过容量乘以负载因子时触发扩容。如果面试官问 ConcurrentHashMap可以这样回答JDK 1.7 的 ConcurrentHashMap 使用 Segment 分段锁。每个 Segment 继承 ReentrantLock内部维护 HashEntry 数组和链表。写操作时先定位 Segment然后锁住 Segment。不同 Segment 可以并发但是同一个 Segment 内部操作不同桶也会发生锁竞争所以锁粒度比较大。 JDK 1.8 之后取消了 Segment改成 Node 数组 链表 红黑树的结构并使用 CAS synchronized 实现线程安全。put 时如果桶为空使用 CAS 插入如果桶不为空使用 synchronized 锁住桶头节点所以锁粒度从 Segment 级别降低到了桶级别。get 操作一般不加锁依靠 volatile 保证可见性。扩容时支持多线程协助扩容迁移完成的桶会用 ForwardingNode 标记。如果面试官问 LongAdder可以这样回答LongAdder 是 JDK 1.8 提供的高并发计数器。AtomicLong 在高并发下多个线程竞争同一个变量CAS 失败重试较多性能会下降。LongAdder 使用分段计数思想内部维护 base 和 Cell 数组。低并发时直接更新 base高并发时把不同线程的更新分散到不同 Cell 中最后 sum() 时再累加。它适合访问量、点赞数、QPS 这类高并发统计场景。最核心的一句话HashMap 解决的是 Hash 冲突和查询效率问题 ConcurrentHashMap 解决的是多线程安全和并发性能问题 LongAdder 解决的是高并发计数时热点变量竞争问题。这几个知识点其实都围绕一个核心思想减少冲突降低竞争提高并发性能。