很早就想研究ConcurrentHashMap ,不过一直拖拉,我也是个很容易被新奇好玩的技术吸引的人,这个呢有好也有坏。废话不多说上干货。
ConcurrentHashMap 最重要的就是引入了Segment 的概念,他在自己内部定义了这个Class来管理数据,这个Segment 类似于HashMap的定义,因为ConcurrentHashMap 会将对应的读写操作交给Segment。Segment 在ConcurrentHashMap 内部维护一个Segment 数组(默认16个),先将key值的hash值定位到Segment 数组中,取得对应的Segment 之后再利用Segment
的相应方法(对应HashMap里的方法)来读写数据,写操作会加锁。这样做的好处就是,如果有多个线程对ConcurrentHashMap 操作的时候,理想情况下如果key hash到的Segment 是不同的,那么写操作是可以并发执行的。当然像size(),isEmpty(),containsValue(Object value)这些操作涉及到跨Segment 的操作,需要一定的机制来保证,极端情况下需要锁定所有Segment 来做统计。
Segment 主要继承ReentrantLock,在Java5中,ReentrantLock的性能要远远高于内部锁。在Java6中,由于管理内部锁的算法采用了类似于 ReentrantLock使用的算法,因此内部锁和ReentrantLock之间的性能差别不大。
ReentrantLock的构造函数提供了两种公平性选择:创建非公平锁(默认)或者公平锁。在公平锁中,如果锁已被其它线程占有,那么请求线程会加入到等待队列中,并按顺序获得锁;在非公平锁中,当请求锁的时候,如果锁的状态是可用,那么请求线程可以直接获得锁,而不管等待队列中是否有线程已经在等待该锁。公平锁的代价是更多的挂起和重新开始线程的性能开销。在多数情况下,非公平锁的性能高于公平锁。Java内部锁也没有提供确定的公平性保证, Java语言规范也没有要求JVM公平地实现内部锁,因此ReentrantLock并没有减少锁的公平性。在中等或者更高负荷下,ReentrantLock有更好的性能,并且拥有可轮询和可定时的请求锁等高级功能。具体请参考:http://www.blogjava.net/killme2008/archive/2007/09/14/145195.html
有时间的话也研究下ReentrantLock的源码。
Segment源码分析:
可以看到真正存放数据的是HashEntry<K, V>[] table ,这里用到了自定义的class HashEntry ,因为ConcurrentHashMap完全允许多个读操作并发进行,读操作并不需要加锁。如果使用传统的技术,如HashMap中的实现,如果允许可以在hash链的中间删除元素,读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。HashEntry代表每个hash链中的一个节点,其结构如下所示:
可以看到除了value不是final的,其它值都是final的,这意味着不能从hash链的中间或尾部删除节点,因为这需要修改next引用值,所有的节点的修改只能从头部开始。对于put操作,可以一律添加到Hash链的头部。但是对于remove操作,可能需要从中间删除一个节点,这就需要将要删除节点的前面所有节点整个复制一遍,最后一个节点指向要删除结点的下一个结点。这在讲解删除操作时还会详述。为了确保读操作能够看到最新的值,将value设置成volatile,这避免了加锁。
这里读取采用了加锁的方式,注释里也提到了原因。关于逃逸分析可以参考http://blog.csdn.net/ykdsg/archive/2011/03/17/6255618.aspx
其他的操作像:containsKey,containsValue,clear基本上也是采用get这样的循环方式。这里就不具体分析了。接下来看下put方法,因为涉及到扩容操作。
其中关键的地方是rehash()方法和++modCount;这个操作,后面会讲到为什么要维护modCount(在改变元素个数的情况下++)。
可以看到rehash()方法就是把table数组扩容一倍,再把原来的引用计算出在新数组的位置e.hash & sizeMask ,然后放过去,原来旧的table数组就交给垃圾回收。
remove方法其实就是需要重新建立next链,所以需要复制。
基本上Segment特殊一点的方法就上面几个了。
接下来看ConcurrentHashMap是怎么使用的。因为ConcurrentHashMap做了二次hash,一些方法像entrySet()方法就要重写了。
其中HashIterator 的方法advance会循环Segment和其中的table数据,并分别记录下标,下次会在原来的下标继续循环。
构造函数
就是初始化一些基本的值,初始化好Segment数组,接下来的几个构造函数都是调用这个,只是提供了一些初始值,默认的Segment数组长度是16,装载因子是0.75f,初始容量是16。因为构造好Map之后,Segment数组是不会扩容的,如果要放的数据比较多的话,传入比较大的concurrencyLevel 可以支持比较好的并发性。
现在看下get方法的实现
很简单,就是先根据hash找到对应的segment ,然后再调用segment 的get方法。其他的像put ,containsKey,replace 等这些值涉及到单个segment 的操作都是类似的。
下面看下涉及到跨段操作的几个方法
可以看到跨Segment的操作中,先是是不锁表的,但是在多线程的情况下,就会造成数据的不一致,这里就用到了Segment中的modCount来做比较,如果modCount有变化就说明被其他线程污染了,就需要重新做统计,这个时候也是不带锁的。但是这样的循环不可能无限进行下去,所以做了限制,在不带锁的情况下允许进行2次尝试,如果还是受到其他线程的污染,那就要加锁统计了。注意要顺序的加锁再顺序的解锁,不然可能会出现死锁。containsValue的是实现与size相似。
本文基于java6 的源码分析,对一些英文的翻译不一定很到位,一些理解上也存在偏颇,欢迎大家指正。
分享到:
相关推荐
ConcurrentHashMap源码分析源码分析 代码解释非常详细!!!!
ConcurrentHashMap具体是怎么实现线程安全的呢,肯定不可能是每个方法加synchronized,那样就变成了HashTable。
源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556
ConcurrentHashMap源码分析(JDK8版本)注:本文源码是JDK8的版本,与之前的版本有较大差异ConcurrentHashMap是conccur
主要为大家详细分析了Java并发系列之ConcurrentHashMap源码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
程序员面试加薪必备_ConcurrentHashMap底层原理与源码分析深入详解
concurrenthashmap1.7的源码分析
ConcurrentHashMap理论概述,实现原理,简单的源码分析,put和get的简单学习
源码分析: ArrayList 源码+扩容机制分析 HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) ...
源码分析 : ArrayList 源码+扩容机制分析 HashMap(JDK1.8)源码+底层数据结构分析 ConcurrentHashMap 源码+底层数据结构分析 IO IO 基础知识总结 IO 设计模式总结 IO 模型详解 并发 知识点/面试题总结 : (必看 ) ...
Java并发包源码分析(JDK1.8):囊括了java.util.concurrent包中大部分类的源码分析,其中涉及automic包,locks包(AbstractQueuedSynchronizer、ReentrantLock、ReentrantReadWriteLock、LockSupport等),queue...
java8 源码 ...源码分析 : 、 、 、[ConcurrentHashMap 源码+底层数据结构分析](docs/java/collection/ConcurrentHashMap 源码+底层数据结构分析.md) 并发 并发这部分内容非常重要,还是面试中的重
集合源码分析 JAVA: 基本语法 static 修饰变量 方法 静态块(初始化块 构造函数 ) 静态内部类() 静态导包 final() transient() foreach循环原理() volatile底层实现() equals和hashcode(, ) string,stringbuffer和...
源码分析:ArrayList、Vector、LinkedList、HashMap、ConcurrentHashMap、HashSet、LinkedHashSet and LinkedHashMap 线程状态、线程机制、线程通信、J.U.C 组件、JMM、线程安全、锁优化 磁盘操作、字节操作、字符...
只是都是相通的,当我们了解了ConcurrentHashMap的实现原理以及各个方法的实现机制,我们对于其他的hash类型实现也能快速的理解,今天我们就来通过源码来一点一点的分析下ConcurrentHashMap的实现。 首先我们来看...
JDK1.8源码分析 相关的原始码分析结果会以注解的形式体现到原始码中 已完成部分: ReentrantLock CountDownLatch Semaphore HashMap TreeMap LinkedHashMap ConcurrentHashMap 执行器 ...
JUC集合框架的目录整理如下:1. 【JUC】JUC集合框架综述【JUC】JDK1.8源码分析之ConcurrentHashMap(一)【JUC】JDK1.8源
bitset源码Java源码分析 基础集合列表 ArrayList (done) Vector (done) LinkedList (done) Stack (done) ReferenceQueue (done) ArrayDeque (done) Set HashSet (done) TreeSet (done) LinkedHashSet (done) BitSet ...
高并发编程第三阶段11讲 AtomicXXXFieldUpdater源码分析及使用场景分析.mp4 高并发编程第三阶段12讲 sun.misc.Unsafe介绍以及几种Counter方案性能对比.mp4 高并发编程第三阶段13讲 一个JNI程序的编写,通过...