你好,我是yes。
上篇讲了集合类的相关面试点已经包含 HashMap 了,这篇就来盘盘 ConcurrentHashMap。
我们都知道 HashMap 是非线程安全的,然后还有个 HashTable ,这玩意虽说是线程安全,但所有方法用的是同一把锁,并发度太低,性能不好。
所以,如要在并发场景下使用 Map ,那就推荐用 ConcurrentHashMap。
而谈到 ConcurrentHashMap,经常会被问到 JDK1.8 相对于 1.7 版本做哪些优化,所以我们先来看下 1.7 的是实现。
ConcurrentHashMap 1.7
其实大体的哈希表实现跟 HashMap 没有本质的区别,都是经过 key 的 hash 定位到一个下标,然后获取元素,如果冲突了就用链表相连。
差别就在于引入了一个 Segments 数组,我们来看下大致的结构。
原理就是先通过 key 的 hash 判断得到 Segment 数组的下标,然后将这个 Segment 上锁,然后再次通过 key 的 hash 得到 Segment 里 HashEntry 数组的下标,下面这步其实就是 HashMap 一致了,所以我说差别就是引入了一个 Segments 数组。
因此可以简化的这样理解:每个 Segment 数组存放的就是一个单独的 HashMap。
可以看到,图上我们有 6 个 Segment ,那么等于有六把锁,因此共可以有六个线程同时操作这个 ConcurrentHashMap,并发度就是 6,相比于直接将 put 方法上锁,并发度就提高了,这就是分段锁。
具体上锁的方式来源于 Segment ,这个类实际继承了 ReentrantLock,因此它自身具备加锁的功能。
可以看出,1.7 的分段锁已经有了细化锁粒度的概念,它的一个缺陷是 Segment 数组一旦初始化了之后不会扩容,只有 HashEntry 数组会扩容,这就导致并发度过于死板,不能随着数据的增加而提高并发度。
ConcurrentHashMap 1.8
1.8 ConcurrentHashMap 做了更细粒度的锁控制,可以理解为 1.8 HashMap 的数组的每个位置都是一把锁,这样扩容了锁也会变多,并发度也会增加。
思想的转变就是把粒度更加细化,我不分段了,我直接把 Node 数组的每个节点分别上一把锁,这样并发度不就更高了吗?
并且 1.8 也不借助于 ReentrantLock 了,直接用 synchronized,这也侧面证明,都 1.8 了 synchronized 优化后的速度已经不下于 ReentrantLock 了。
具体实现思路也简单,当塞入一个值的时候,先计算 key 的 hash 后的下标,如果计算到的下标还未有 Node ,那么就通过 cas 塞入新的 Node。如果已经有 node 则通过 synchronized 将这个 node 上锁,这样别的线程就无法访问这个 node 及其之后的所有节点。
然后判断 key 是否相等,相等则是替换 value ,反之则是新增一个 node,这个操作和 HashMap 是一样的。
1.8 的扩容也是有点意思的,它允许协助扩容,也就是多线程扩容。
当 put 的时候,发现当前 node hash 值是 -1,则表明当前的节点正在扩容,则会触发协助扩容机制
这个要详细说起来还真的有点麻烦,而且不太好说清,代码有点大,我就说个大概。
其实大家大致理解下就够了:
扩容无非就是搬迁 Node,假设当前数组长度为 32,那就可以分着搬迁,31-16 这几个下标的 Node 都由线程A来搬迁,然后线程 B 来搬迁 15-0 这几个下标的 Node。
简单说就是会维护一个 transferIndex 变量,来的线程死循环 cas 争抢下标,如果下标已经分配完了,那自然就不需要搬迁了,如果 cas 抢到了要搬运的下标,那就去帮忙搬就好了,就是这么个事儿。
还有 1.8 的 size 方法和 1.7 也不一样1.7 有个尝试的思想,当调用 size 方法的时候不会加锁,而是先尝试三次不加锁获取 sum。
如果三次总数一样,说明当前数量没有变化,那就直接返回了。如果总数不一样,那说明此时有线程在增删 map,于是加锁计算,这时候其他线程就操作不了 map 了。
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
...再累加数量
而 1.8 不一样,它就是直接计算返回结果,具体采用的是类似 LongAdder 的思想,累加不再是基于一个成员变量,而是搞了一个数组,每个线程在自己对应的下标地方进行累加,等最后的时候把数组里面的数据统一一下,就是最终的值了。
所以这是一个分解的思想,分而治之。
在 put 的时候,就会通过 addCount 方法维护 counterCells 的数量,当然 remove 的时候也会调用此方法。
总而言之,就是平日的操作会维护 map 里面的节点数量,会先通过 CAS 修改 baseCount ,如果成功就直接返回,如果失败说明此时有线程在竞争,那么就通过 hash 选择一个 CounterCell 对象就行修改,最终 size 的结果就是 baseCount + 所有 CounterCell 。
这种通过 counterCell 数组来减少并发下场景下对单个成员变量的竞争压力,提高了并发度,提升了性能,这也就是 LongAdder 的思想。
这里还有个能问的就是 @sun.misc.Contended 注解了,这个和伪共享有关系,具体可以看看我之前写的这篇文章:
ConcurrentHashMap#get需要加锁吗?不需要加锁。
保证 put 的时候线程安全之后,get 的时候只需要保证可见性即可,而可见性不需要加锁。
具体是通过Unsafe#getXXXVolatile 和用 volatile 来修饰节点的 val 和 next 指针来实现的。
为什么 ConcurrentHashMap 不支持 key 或者 value 为 null ?
首先, key 为什么也不能为 null ?我不知道,没想明白,可能是作者 lea 佬不喜欢 null 值。
那 value 为什么不能为 null ?
因为在多线程情况下, null 值会产生二义性,因为你不清楚 map 里到底是不存在在这个 key ,还是说被put(key,null)。
这里可能有人会说,那 HashMap 不一样有这个问题?HashMap 可以通过 containsKey 来判断是否存在这个 key,而多线程使用的 ConcurrentHashMap 就不能够。
比如你 get(key) 得到了null,此时map里面没有这个 key 的,但是你不知道,所以你想调用 containsKey 看看,而恰巧在你调用之前,别的线程 put 了这个 key ,这样你 containsKey 就发现有这个 key,这是不是就发生“误会”了。
最后
对 ConcurrentHashMap 的了解到这份上差不多了,再多的可以看看源码,里面还是有很多值得学习的地方。
集合类的面试题到这就差不多了,后面写 Spring 的面试题。
还有我的面试仓库,上面已经有很多面试题啦,求个 star!点击阅读原文,也可访问~
https://github.com/yessimida/interview-of-legends
我是yes,我们下篇见~