ConcurrentHashMap 源码分析

可以参考的资料：

• ConcurrentHashMap源码分析(1.8) - Ouka傅 - 博客园
• Map相关常见知识(重)#ConcurrentHashMap的底层实现 (和 Hashtable 的区别)

JDK 1.7

//1.7 我觉得只需要稍微了解一下构成即可，不必详细了解

JDK 1.8

基本结构：

• Node 数组：ConcurrentHashMap 内部使用一个 Node[] 数组来存储键值对。每个 Node 代表一个键值对。
• 链表：当发生哈希冲突时，即多个键映射到同一个数组位置，这些键值对会以链表的形式存储。
• 红黑树：当链表的长度超过一定阈值（TREEIFY_THRESHOLD，默认为 8）时，链表会转换成红黑树，以提高搜索效率。

初始化：

ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl （sizeControl 的缩写），它的值决定着当前的初始化状态。

• -1 说明正在初始化，其他线程需要自旋等待
• -N 说明 table 正在进行扩容，高 16 位表示扩容的标识戳，低 16 位减 1 为正在进行扩容的线程数
• 0 表示 table 初始化大小，如果 table 没有初始化
• >0 表示 table 扩容的阈值，如果 table 已经初始化。

put

• 根据 key 计算出 hashcode 。
• 判断是否需要进行初始化。
• 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
• 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
• 如果都不满足，则利用 synchronized 锁写入数据。
• 如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法，在 treeifyBin 中会首先判断当前数组长度 ≥64 时才会将链表转换为红黑树。

get

总结一下 get 过程：

• 根据 hash 值计算位置。
• 查找到指定位置，如果头节点就是要找的，直接返回它的 value.
• 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
• 如果是链表，遍历查找之。

总结：总的来说 ConcurrentHashMap 在 Java 8 中相对于 Java 7 来说变化还是挺大的

总结

Java 7 中 ConcurrentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作，每一个 Segment 都是一个类似 HashMap 数组的结构，它可以扩容，它的冲突会转化为链表。但是 Segment 的个数一但初始化就不能改变。

Java 8 中的 ConcurrentHashMap 使用的 Synchronized 锁加 CAS 的机制。结构也由 Java 7 进化成了 Node 数组 + 链表 / 红黑树，Node 是类似于一个 HashEntry 的结构。它的冲突再达到一定大小时会转化成红黑树，在冲突小于一定数量时又退回链表。