ConcurrentHashMap（jdk1.7）之构造方法和 put 方法过程分析

Segment[1]

否

该方法首要目标是获取锁。该方法返回，说明获取锁成功。除此之外，该方法还会干点“副业”：查找链表中，是否存在相同 key 的 HashEntry 节点，若不存在，帮助创建封装了 key，value 键值对的 HashEntry 对象（speculatively create node），后续插入链表将使用到。① 根据 hash 值，计算数组索引，返回这个索引上的 HashEntry 对象作为链表头；② 遍历链表，查询相同 key 的 HashEntry 对象，若找到，则链表结束遍历，否则，生成一个新的 HashEntry 对象（用作后续返回值）；③ 尝试获取锁次数没有达到上限（MAX_SCAN_RETRIES），则在下次循环继续尝试获取锁，否则，调用 lock 以阻塞方式获取；④ 判断链表头是否发生变化，若是，重设相关变量，重新遍历链表。

table[2]

Segment[0]

true

遍历这个链表

构造方法结束

该方法用于返回一个 seg.table 数组元素，数组元素坐标通过哈希值 h 计算出。(table.length -1) & h：用于定位 seg.table 数组的索引 index。UNSAFE.getObjectVolatile 方法：表示获取 table[index] 这个 HashEntry 元素。也许有人质疑，直接table[index]不可以么，为什么要这么复杂？在java内存模型中，每个线程都有一个工作内存，里面存储着table的副本，虽然table是volatile修饰的，但不能保证线程每次都拿到table中的最新元素，Unsafe.getObjectVolatile可以直接获取指定内存的数据，保证了每次拿到数据都是最新的。

HashEntry node = null

构造方法

替换这个 HashEntry 节点的原有值

e == null 表示：1、seg.table[index] 这个数组元素为 空，这里初始化一个 HashEntry 对象，后续用于添加到数组这个位置。2、或者遍历到末尾，也没找到 key 值和添加的key 相同的 HashEntry 对象，此时也初始化一个，用于后续插入到链表中。

④ 将 node 和其之后的 节点构成的链表，放入到新数组的 lastIdx 位置。对下图来说，就是将 n4，n5，n6 节点构成的链表，一起放入到 新数组的 4 位置

n6

tryLock() == true?

遍历下一个

构造 ConcurrentHashap 对象

HashEntry node = scanAndLockForPut

计算索引

false

table[3]

返回之前 key 关联的值

falseSegment s = segment[i]

index = (tab.length -1) & hash计算用于存放这个键值对的  Segment.table 数组索引

Segment[2]

table[0]

Segment 数组其他元素，参照第一个数组元素进行初始化

释放锁

retries < 0 ?

扩容

默认参数值

只初始化了 Segment 数组的第一个元素，其他元素，在用到的时候，参照这个元素执行初始化。

是

循环遍历

node = new HashEntry

初始化

s.put

方法结束

new ConcurrentHashMap()

table[1]

n4

e = e.next

最大尝试获取锁 的处理逻辑

④ 构造一个 Segment对象 s0 和 Segment 数组 ss，并填充 ss[0] = s0

将键值对，添加到 Segment 底层的 HashEntry 链表上。① 在这个 Segment 上尝试获取锁，若获取不到，再调用 scanAndLockForPut 获取；② 定位到底层 HashEntry 链表；entryAt 方法和 entryForHash 方法效果一样。③ 遍历链表，查找是否存在相同 key 的元素，若存在，替换其 value 值；④ 链表为空，或遍历结束没找到相同 key 的元素，则插入新的，并维护链表及相关信息。⑤ 释放 Segment 锁。

① 扩容底层数组为原来的 2 倍

Segment.put 方法详解

tryLock()?

返回 key 原来绑定的值

① 参数合法性检查

② 计算并发级别。并发级别就是 Segment 数组大小。必须是 2 的幂。

和 HashMap 不同，CHM 的 key和 value 都不能为 null

返回 key 之前关联的 value

无参

返回 Segment 对象 s

并发级别不能大于 65536

到末尾了？

需要扩容？

只有一个 HashEntry 节点？

key.equals(e.key)

② 直接将这个节点添加到新数组的链表中

sgements[j] 是否为 null？

int j = (hash >>> segmentShift) & segmentMask

③ 计算单个 Segment 的 table 数组大小。也是 2 的幂。

获取到锁

retries = 0

node == null?

oldTabe[i] == null

根据 key，计算 哈希值：hash = hash(key)

底层数组需要扩容时的插入逻辑。

(retries & 1) == 0且链表首节点发生变化？

添加元素

rehash(node)执行扩容逻辑

⑤ 遍历从表头到 node（不包含）的节点，将其放入新数组对应位置

++retries > MAX_SCAN_RETRIES

链表为空？

false 循环遍历

ConcurrentHashMap （简称 CHM）

e == null ?

n1

scanAndLockForPut 方法详解

左边是扩容前的数组，右边是扩容后的。假如扩容前数组大小为 m，扩容前某个元素在旧数组位置为 i，则扩容后在新数组的位置，只会是 i，或 i + m。如图：n1，n3 扩容后在新数组的索引位置是 0，n2，n4，n5，n6 在新数组的索引位置是 0 + 4 = 4 

⑥ 将新节点，插入扩容后的数组

n5

retries = -1表示重新遍历节点

判断当前 HashEntry 节点的 key，是否和插入的 key 相同

构造方法详解

遍历数组

根据哈希值，计算 Segment 数组索引： j

进入下次循环

Sgement[3]

注意：扩容是针对单个 Segment 的底层数组，而非整个 ConcurrentHashMap

CHM.put 方法详解

n2

链表为空，也可能扩容，因为扩容条件是：font color=\"#ff3333\

头插法，插入节点到链表

first = entryForHashe = firstnode = nullretires = -1

执行 Segment 对象初始化：ensureSegment(j)

return node

达到最大尝试次数，再以阻塞方式获取锁：lock()

false 遍历下一个链表

指定参数值

添加元素时，segments[k] 尚未初始化，调用该方法执行初始化。1、基于 segments[0] 构建 segments[k]2、使用 UNSAFE 保证原子性和多线程同步。

n3

true

为何加 retries & 1 == 0 限制？猜测可能为了减少【检测链表头是否发生变化的次数】：MAX_SCAN_RETRIES 值只能等于 1 或 64，当 retires 为 1 或 64 时，下次循环将以阻塞方式获取锁，而 retries 为 1 或 64 时，正好满足 retries & 1 == 0，所以可以保证在进入阻塞方法之前，会至少检测一次链表头是否发生变化。

③ 从链表中查找这样一个节点 node：该节点之后的所有节点，都是放到新数组中的同一个位置。比如，对右图来说，就是查找 n4 节点

所有链表都遍历完成了？