ConcurrentHashMap实现原理

ConcurrentHashMap是Java1.5中引用的一个线程安全的支持高并发的HashMap集合类。这篇文章总结了ConcurrentHashMap的内部实现原理,是对于自己理解后的一些整理。


1.HashTable与ConcurrentHashMap的对比

HashTable本身是线程安全的,写过Java程序的都知道通过加Synchronized关键字实现线程安全,这样对整张表加锁实现同步的一个缺陷就在于使程序的效率变得很低。这就是为什么Java中会在1.5后引入ConcurrentHashMap的原因。

从图中可以看出,HashTable的锁加在整个Hash表上,而ConcurrentHashMap将锁加在segment上(每个段上),这样我们在对segment1操作的时候,同时也可以对segment2中的数据操作,这样效率就会高很多。

2.ConcurrentHashMap的内部结构

ConcurrentHashMap主要有三大结构:整个Hash表,segment(段),HashEntry(节点)。每个segment就相当于一个HashTable。

(1)HashEntry类

每个HashEntry代表Hash表中的一个节点,在其定义的结构中可以看到,除了value值没有定义final,其余的都定义为final类型,我们知道Java中关键词final修饰的域成为最终域。用关键词final修饰的变量一旦赋值,就不能改变,也称为修饰的标识为常量。这就意味着我们删除或者增加一个节点的时候,就必须从头开始重新建立Hash链,因为next引用值需要改变。

由于这样的特性,所以插入Hash链中的数据都是从头开始插入的。例如将A,B,C插入空桶中,插入后的结构为:

(2)segment类

Segment 类继承于 ReentrantLock 类,从而使得 Segment 对象能充当锁的角色。每个 Segment 对象用来守护其(成员对象 table 中)包含的若干个桶。

table 是一个由 HashEntry 对象组成的数组。table 数组的每一个数组成员就是散列映射表的一个桶。

count 变量是一个计数器,它表示每个 Segment 对象管理的 table 数组(若干个 HashEntry 组成的链表)包含的 HashEntry 对象的个数。每一个 Segment 对象都有一个 count 对象来表示本 Segment 中包含的 HashEntry 对象的总数。注意,之所以在每个 Segment 对象中包含一个计数器,而不是在 ConcurrentHashMap 中使用全局的计数器,是为了避免出现“热点域”而影响 ConcurrentHashMap 的并发性。

ConcurrentHashMap 类

默认的情况下,每个ConcurrentHashMap 类会创建16个并发的segment,每个segment里面包含多个Hash表,每个Hash链都是有HashEntry节点组成的。

3.用分离锁实现多个线程间的并发写操作

(1)Put方法的实现

整个代码通过注释很好理解了,稍微要注意的是这里的加锁是针对具体的segment,而不是对整个ConcurrentHashMap。Put方法从源码上可以看出是从链表的头部插入新的数据的。

(2)Get方法的实现

ConcurrentHashMap中的读方法不需要加锁,所有的修改操作在进行结构修改时都会在最后一步写count 变量,通过这种机制保证get操作能够得到几乎最新的结构更新。

(3)Remove方法的实现

整个操作是在持有段锁的情况下执行的,空白行之前的行主要是定位到要删除的节点e。接下来,如果不存在这个节点就直接返回null,否则就要将e前面的结点复制一遍,尾结点指向e的下一个结点。e后面的结点不需要复制,它们可以重用。

中间那个for循环是做什么用的呢?从代码来看,就是将定位之后的所有entry克隆并拼回前面去,但有必要吗?每次删除一个元素就要将那之前的元素克隆一遍?这点其实是由entry的不变性来决定的,仔细观察entry定义,发现除了value,其他所有属性都是用final来修饰的,这意味着在第一次设置了next域之后便不能再改变它,取而代之的是将它之前的节点全都克隆一次。至于entry为什么要设置为不变性,这跟不变性的访问不需要同步从而节省时间有关。

执行删除之前的原链表:

执行删除之后的新链表

注意:新链表在clone的时候。顺序发生反转,A->B变为B->A。

(4)containsKey方法的实现

containsKey方法操作相对简单,因为它不需要读取值。

4.总结

在使用锁来协调多线程间并发访问的模式下,减小对锁的竞争可以有效提高并发性。有两种方式可以减小对锁的竞争:

  • 减小请求同一个锁的频率。
  • 减少持有锁的时间。

ConcurrentHashMap 的高并发性主要来自于三个方面:

  • 用分离锁实现多个线程间的更深层次的共享访问。
  • 用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求。
  • 通过对同一个 Volatile 变量的写 / 读访问,协调不同线程间读 / 写操作的内存可见性。

使用分离锁,减小了请求同一个锁的频率。

concurrentHashMap在jdk1.8中主要做了2方面的改进

改进一:取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存数据,采用table数组元素作为锁,从而实现了对每一行数据进行加锁,进一步减少并发冲突的概率。

改进二:将原先table数组+单向链表的数据结构,变更为table数组+单向链表+红黑树的结构。对于hash表来说,最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀,那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想,虽然ConcurrentHashMap类默认的加载因子为0.75,但是在数据量过大或者运气不佳的情况下,还是会存在一些队列长度过长的情况,如果还是采用单向列表方式,那么查询某个节点的时间复杂度为O(n);因此,对于个数超过8(默认值)的列表,jdk1.8中采用了红黑树的结构,那么查询的时间复杂度可以降低到O(logN),可以改进性能。

本文综合参考与网络,参考链接如下:

https://www.cnblogs.com/everSeeker/p/5601861.html

http://www.cnblogs.com/ITtangtang/p/3948786.html

原文发布于微信公众号 - Spark学习技巧(bigdatatip)

原文发表时间:2018-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Spark生态圈

[spark] 调度模式(FIFO&FAIR)

spark应用程序的调度体现在两个地方,第一个是Yarn对spark应用间的调度,第二个是spark应用内(同一个SparkContext)的多个TaskSet...

652
来自专栏恰同学骚年

数据结构基础温故-7.排序

排序(Sorting)是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序,特别是高效率地进行排序时计算...

661
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 aggregate和treeAggregate从原理到应用

由于treeAggregate是在aggregate基础上的优化版本,因此先来看看aggregate是什么.

780
来自专栏noteless

[零]java8 函数式编程入门官方文档中文版 java.util.stream 中文版 流处理的相关概念

https://docs.oracle.com/javase/8/docs/api/

671
来自专栏noteless

[三] java虚拟机 JVM字节码 指令集 bytecode 操作码 指令分类用法 助记符

计算机指令就是指挥机器工作的指示和命令,程序就是一系列按一定顺序排列的指令,执行程序的过程就是计算机的工作过程。

972
来自专栏Ryan Miao

java并发编程读书笔记(1)-- 对象的共享

1. 一些原则 RIM(Remote Method Invocation):远程方法调用 Race Condition:竞态条件 Servlet要满足多个线程的...

3428
来自专栏海纳周报

新生代的垃圾回收:Copy GC之基本原理

据我所能查到的资料,基于复制的GC算法最早是Marvin Minsky提出来的。 这个算法的思路很简单,总的来说,就是把空间分成两部分,一个叫分配空间(Allo...

4158
来自专栏数据库

记一次排查DB死锁的分析

文章摘要 在线上环境遇到数据库死锁问题该如何分析并解决问题呢? 虽然很多童鞋在学数据库课程时都了解数据库隔离级别、死锁和事务等概念,但在测试/线上环境遇到死锁却...

1868
来自专栏有趣的Python

算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队...

3545
来自专栏微信公众号:Java团长

初学者应该了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

642

扫码关注云+社区