ConcurrentHashMap源码解析,多线程扩容

put、get 等等核心方法在多线程情况下,都会出现修改的覆盖,数据不一致等等问题。比如多个线程 put 先后的问题,会导致结果覆盖,如果一个 put 一个get,也可能会因为调度问题获取到错误的结果;

多线程操作有读有写的时候,可能会出现一个典型异常:ConcurrentModificationException

另外扩容的时候,hashmap1.7 的实现还有可能出现死循环的问题。

关于线程安全的哈希映射的选择有三种:

Hashtable;

SynchronizedMap对HashMap包装;

ConcurrentHashMap

其中,Hashtable 的效率比较低,因为他的每一个方法都是用了锁,synchronized 修饰的;

用 SynchronizedMap 对 HashMap 包装的实质也是额外加入一个对象叫做 mutex,是一个 Object,然后给对应的方法上都加上 synchronized(mutex),当然比 Hashtable 是要好一些的,因为锁对象粒度要小一些。Hashtable 采用的 synchronized 锁上方法锁定的是整个 this。

ConcurrentHashMap则是最好的选择,这里我们来看看他的源码原理。

一、ConcurrentHashMap 数据结构

其实可以想见,一个功能完全一致的容器,和原来的 HashMap 相比,肯定结构不会差到哪里去,实际上也是这样。jdk8之后 HashMap 引入红黑树的优化,ConcurrentHashMap 也有,所以我们还是分 7 和 8 来说:

1.1 jdk 7 的 ConcurrentHashMap

ConcurrentHashMap源码解析,多线程扩容

由 Segment 片段,HashEntry组成,和HashMap一样,仍然是枚举链表。

很简单,就是 Segment 数组又分成了 HashEntry 类型的数组。

那 Segment 类型是什么呢?这个内部类维护的就是HashEntry 类型的数组。

HashEntry 是什么呢?就是链表。

所以其实首先在容器存储的核心结构上,把当时对应的 HashMap 分成了更细的粒度。

与此同时,Segment 数组是继承了 ReentrantLock 的,再往下层 HashEntry 类型的数组 table 和 HashEntry 这个链表节点都是用 volatile 修饰的。

1.2 jdk 8 的 ConcurrentHashMap

显然是因为 jdk 8 的 HashMap 更新了结构,所以对应的 ConcurrentHashMap 也在这方面跟着改变了。

ConcurrentHashMap源码解析,多线程扩容

jdk 8 的实现已经摒弃了 Segment 的概念,而是直接用Node数组+链表+红黑树,和 HashMap 一模一样的数据结构来实现,虽然源码里还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。

对应的,不再是 Entry 而是 Node 节点,就是因为要转树,对应的方法操作,最重要的就是没有显式的再使用 ReentrantLock,用到了 synchronized 和 CAS 操作,Node 节点也是 volatile 修饰的。

二、ConcurrentHashMap 的内部方法 2.1 jdk7 的 put ,get ,扩容方法

这里没有源码的截图,但是过程是清晰的。

put 方法(加锁):

将当前 Segment 中的表通过 key 的哈希码定位到HashEntry。这一步会尝试获取锁,如果获取失败肯定存在其他线程存在竞争,则利用 scanAndLockForPut() 方法去获取锁。

遍历该 HashEntry,如果不为空则判断预定的 key 和当前遍历的 key 是否替代,替代则覆盖旧的值。

不为空则需要新建一个 HashEntry 并加入到 Segment 中,同时会先判断是否需要扩容。

最后会解除在 1 中所获取当前Segment的锁。

可以看到,整体就是获取锁的中间进行 put 操作,put 操作的流程也和 HashMap 的 put 是类似的。

get 方法(不加锁)

ConcurrentHashMap 的 get 操作跟 HashMap 类似,只是ConcurrentHashMap 第一次需要经过一次 hash 定位到 Segment 的位置,然后再 hash 定位到指定的 HashEntry,遍历该 HashEntry 下的链表进行对比,成功就返回,不成功就返回 null。

并且 get 的过程调用的是 Unsafe 包的 getObjectVolatile 方法,因为具体的对象是 volatile 修饰的,不用加锁,读取也可以直接读到最新的值。

rehash 方法(加锁)

ConcurrentHashMap 的扩容方法和 HashMap 也是类似的,因为外部已经对 Segment 加锁,内部的操作就是重新计算 hash 值,然后重新移动元素。

这里可以看出来,因为有 Segment 的一个粒度缩小的优化,加上一个读写分离的普遍思想,jdk 7 实现的方法比较容易理解。

下来的 jdk 8 做出的优化非常多,因此几个方法分开来讲

2.2 jdk 8 的初始化

构造方法和 HashMap 一样,是不会初始化的,而是在第一次调用 put 方法之后才会进行初始化。构造方法调用的时候只是进行了一些参数的确定。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpswjs.html