- 浏览: 422042 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (269)
- 原创 (7)
- Java (51)
- Java Concurrency (2)
- IDE (16)
- Linux (46)
- Database (23)
- NoSQL (35)
- Web服务器 (23)
- Log日志 (11)
- HTTP (11)
- HTML (2)
- XML (1)
- Test (7)
- Mina (0)
- Amoeba (4)
- Cobar (1)
- 序列化 (2)
- Python (5)
- PHP (1)
- Socket通信 (1)
- Network (3)
- Struts (2)
- Web前端 (10)
- Maven (6)
- SVN (15)
- Json (1)
- XMPP (2)
- Go (1)
- Other (4)
- 未整理 (5)
最新评论
-
u012374672:
[color=darkred][/color][flash=2 ...
Mongo的ORM框架的学习Morphia(annotations) -
b_l_east:
很有问题啊
利用redis的transaction功能,实现分布式下加锁
曾经研究过jkd1.5新特性,其中ConcurrentHashMap就是其中之一,其特点:效率比Hashtable高,并发性比hashmap好。结合了两者的特点。
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区(Queue),比如常会用缓存作为外部文件的副本(HashMap)。这篇文章主要分析jdk1.5的3种并发集合类型(concurrent,copyonright,queue)中的ConcurrentHashMap,让我们从原理上细致的了解它们,能够让我们在深度项目开发中获益非浅。
左边便是Hashtable的实现方式---锁整个hash表;而右边则是ConcurrentHashMap的实现方式---锁桶(或段)。 ConcurrentHashMap将hash表分为16个桶(默认值),诸如get,put,remove等常用操作只锁当前需要用到的桶。试想,原来 只能一个线程进入,现在却能同时16个写线程进入(写线程才需要锁定,而读线程几乎不受限制,之后会提到),并发性的提升是显而易见的。
- V get(Object key, int hash) {
- if (count != 0 ) { // read-volatile
- HashEntry<K,V> e = getFirst(hash);
- while (e != null ) {
- if (e.hash == hash && key.equals(e.key)) {
- V v = e.value;
- if (v != null )
- return v;
- return readValueUnderLock(e); // recheck
- }
- e = e.next;
- }
- }
- return null ;
- }
- V readValueUnderLock(HashEntry<K,V> e) {
- lock();
- try {
- return e.value;
- } finally {
- unlock();
- }
- }
put 操作一上来就锁定了整个segment,这当然是为了并发的安全,修改数据是不能并发进行的 ,必须得有个判断是否超限的语句以确保容量不足时能够 rehash,而比较难懂的是这句int index = hash & (tab.length - 1),原来segment里面才是真正的hashtable,即每个segment是一个传统意义上的hashtable ,如上图,从两者的结构就可以看出区别,这里就是找出需要的entry在table的哪一个位置,之后得到的entry就是这个链的第一个节点,如果e!=null,说明找到了,这是就要替换节点的值(onlyIfAbsent == false),否则,我们需要new一个entry,它的后继是first,而让tab[index]指向它,什么意思呢?实际上就是将这个新entry 插入到链头,剩下的就非常容易理解了。
- V put(K key, int hash, V value, boolean onlyIfAbsent) {
- lock();
- try {
- int c = count;
- if (c++ > threshold) // ensure capacity
- rehash();
- HashEntry<K,V>[] tab = table;
- int index = hash & (tab.length - 1 );
- HashEntry<K,V> first = tab[index];
- HashEntry<K,V> e = first;
- while (e != null && (e.hash != hash || !key.equals(e.key)))
- e = e.next;
- V oldValue;
- if (e != null ) {
- oldValue = e.value;
- if (!onlyIfAbsent)
- e.value = value;
- }
- else {
- oldValue = null ;
- ++modCount;
- tab[index] = new HashEntry<K,V>(key, hash, first, value);
- count = c; // write-volatile
- }
- return oldValue;
- } finally {
- unlock();
- }
- }
remove 操作非常类似put,但要注意一点区别,中间那个for循环是做什么用的呢?(*号标记)从代码来看,就是将定位之后的所有entry克隆并拼回前面去, 但有必要吗?每次删除一个元素就要将那之前的元素克隆一遍?这点其实是由entry的不变性来决定的,仔细观察entry定义,发现除了value,其他 所有属性都是用final来修饰的,这意味着在第一次设置了next域之后便不能再改变它,取而代之的是将它之前的节点全都克隆一次。至于entry为什么要设置为不变性,这跟不变性的访问不需要同步从而节省时间有关,关于不变性的更多内容,请参阅之前的文章《线程高级---线程的一些编程技巧》
- V remove(Object key, int hash, Object value) {
- lock();
- try {
- int c = count - 1 ;
- HashEntry<K,V>[] tab = table;
- int index = hash & (tab.length - 1 );
- HashEntry<K,V> first = tab[index];
- HashEntry<K,V> e = first;
- while (e != null && (e.hash != hash || !key.equals(e.key)))
- e = e.next;
- V oldValue = null ;
- if (e != null ) {
- V v = e.value;
- if (value == null || value.equals(v)) {
- oldValue = v;
- // All entries following removed node can stay
- // in list, but all preceding ones need to be
- // cloned.
- ++modCount;
- HashEntry<K,V> newFirst = e.next;
- for (HashEntry<K,V> p = first; p != e; p = p.next)
- newFirst = new HashEntry<K,V>(p.key, p.hash,
- newFirst, p.value);
- tab[index] = newFirst;
- count = c; // write-volatile
- }
- }
- return oldValue;
- } finally {
- unlock();
- }
- }
- static final class HashEntry<K,V> {
- final K key;
- final int hash;
- volatile V value;
- final HashEntry<K,V> next;
- HashEntry(K key, int hash, HashEntry<K,V> next, V value) {
- this .key = key;
- this .hash = hash;
- this .next = next;
- this .value = value;
- }
- @SuppressWarnings ( "unchecked" )
- static final <K,V> HashEntry<K,V>[] newArray( int i) {
- return new HashEntry[i];
- }
- }
Java并发编程之ConcurrentHashMap
ConcurrentHashMap
ConcurrentHashMap是一个线程安全的Hash Table,它的主要功能是提供了一组和HashTable功能相同但是线程安全的方法。ConcurrentHashMap可以做到读取数据不加锁,并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持地尽量地小,不用对整个ConcurrentHashMap加锁。
ConcurrentHashMap的内部结构
ConcurrentHashMap为了提高本身的并发能力,在内部采用了一个叫做Segment的结构,一个Segment其实就是一个类Hash Table的结构,Segment内部维护了一个链表数组,我们用下面这一幅图来看下ConcurrentHashMap的内部结构:
从上面的结构我们可以了解到,ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作,第一次Hash定位到Segment,第二次Hash定位到元素所在的链表的头部,因此,这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长,但是带来的好处是写操作的时候可以只对元素所在的Segment进行加锁即可,不会影响到其他的Segment,这样,在最理想的情况下,ConcurrentHashMap可以最高同时支持Segment数量大小的写操作(刚好这些写操作都非常平均地分布在所有的Segment上),所以,通过这一种结构,ConcurrentHashMap的并发能力可以大大的提高。
Segment
我们再来具体了解一下Segment的数据结构:
- static final class Segment<K,V> extends ReentrantLock implements Serializable {
- transient volatile int count;
- transient int modCount;
- transient int threshold;
- transient volatile HashEntry<K,V>[] table;
- final float loadFactor;
- }
详细解释一下Segment里面的成员变量的意义:
- count:Segment中元素的数量
- modCount:对table的大小造成影响的操作的数量(比如put或者remove操作)
- threshold:阈值,Segment里面元素的数量超过这个值依旧就会对Segment进行扩容
- table:链表数组,数组中的每一个元素代表了一个链表的头部
- loadFactor:负载因子,用于确定threshold
HashEntry
Segment中的元素是以HashEntry的形式存放在链表数组中的,看一下HashEntry的结构:
- static final class HashEntry<K,V> {
- final K key;
- final int hash;
- volatile V value;
- final HashEntry<K,V> next;
- }
可以看到HashEntry的一个特点,除了value以外,其他的几个变量都是final的,这样做是为了防止链表结构被破坏,出现ConcurrentModification的情况。
ConcurrentHashMap的初始化
下面我们来结合源代码来具体分析一下ConcurrentHashMap的实现,先看下初始化方法:
- public ConcurrentHashMap( int initialCapacity,
- float loadFactor, int concurrencyLevel) {
- if (!(loadFactor > 0 ) || initialCapacity < 0 || concurrencyLevel <= 0 )
- throw new IllegalArgumentException();
- if (concurrencyLevel > MAX_SEGMENTS)
- concurrencyLevel = MAX_SEGMENTS;
- // Find power-of-two sizes best matching arguments
- int sshift = 0 ;
- int ssize = 1 ;
- while (ssize < concurrencyLevel) {
- ++sshift;
- ssize <<= 1 ;
- }
- segmentShift = 32 - sshift;
- segmentMask = ssize - 1 ;
- this .segments = Segment.newArray(ssize);
- if (initialCapacity > MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- int c = initialCapacity / ssize;
- if (c * ssize < initialCapacity)
- ++c;
- int cap = 1 ;
- while (cap < c)
- cap <<= 1 ;
- for ( int i = 0 ; i < this .segments.length; ++i)
- this .segments[i] = new Segment<K,V>(cap, loadFactor);
- }
CurrentHashMap的初始化一共有三个参数,一个initialCapacity,表示初始的容量,一个loadFactor,表示负载参数,最后一个是concurrentLevel,代表ConcurrentHashMap内部的Segment的数量,ConcurrentLevel一经指定,不可改变,后续如果ConcurrentHashMap的元素数量增加导致ConrruentHashMap需要扩容,ConcurrentHashMap不会增加Segment的数量,而只会增加Segment中链表数组的容量大小,这样的好处是扩容过程不需要对整个ConcurrentHashMap做rehash,而只需要对Segment里面的元素做一次rehash就可以了。
整个ConcurrentHashMap的初始化方法还是非常简单的,先是根据concurrentLevel来new出Segment,这里Segment的数量是不大于concurrentLevel的最大的2的指数,就是说Segment的数量永远是2的指数个,这样的好处是方便采用移位操作来进行hash,加快hash的过程。接下来就是根据intialCapacity确定Segment的容量的大小,每一个Segment的容量大小也是2的指数,同样使为了加快hash的过程。
这边需要特别注意一下两个变量,分别是segmentShift和segmentMask,这两个变量在后面将会起到很大的作用,假设构造函数确定了Segment的数量是2的n次方,那么segmentShift就等于32减去n,而segmentMask就等于2的n次方减一。
ConcurrentHashMap的get操作
前面提到过ConcurrentHashMap的get操作是不用加锁的,我们这里看一下其实现:
- public V get(Object key) {
- int hash = hash(key.hashCode());
- return segmentFor(hash).get(key, hash);
- }
看第三行,segmentFor这个函数用于确定操作应该在哪一个segment中进行,几乎对ConcurrentHashMap的所有操作都需要用到这个函数,我们看下这个函数的实现:
- final Segment<K,V> segmentFor( int hash) {
- return segments[(hash >>> segmentShift) & segmentMask];
- }
这个函数用了位操作来确定Segment,根据传入的hash值向右无符号右移segmentShift位,然后和segmentMask进行与操作,结合我们之前说的segmentShift和segmentMask的值,就可以得出以下结论:假设Segment的数量是2的n次方,根据元素的hash值的高n位就可以确定元素到底在哪一个Segment中。
在确定了需要在哪一个segment中进行操作以后,接下来的事情就是调用对应的Segment的get方法:
- V get(Object key, int hash) {
- if (count != 0 ) { // read-volatile
- HashEntry<K,V> e = getFirst(hash);
- while (e != null ) {
- if (e.hash == hash && key.equals(e.key)) {
- V v = e.value;
- if (v != null )
- return v;
- return readValueUnderLock(e); // recheck
- }
- e = e.next;
- }
- }
- return null ;
- }
先看第二行代码,这里对count进行了一次判断,其中count表示Segment中元素的数量,我们可以来看一下count的定义:
可以看到count是volatile的,实际上这里里面利用了volatile的语义:
因为实际上put、remove等操作也会更新count的值,所以当竞争发生的时候,volatile的语义可以保证写操作在读操作之前,也就保证了写操作对后续的读操作都是可见的,这样后面get的后续操作就可以拿到完整的元素内容。
然后,在第三行,调用了getFirst()来取得链表的头部:
- HashEntry<K,V> getFirst( int hash) {
- HashEntry<K,V>[] tab = table;
- return tab[hash & (tab.length - 1 )];
- }
同样,这里也是用位操作来确定链表的头部,hash值和HashTable的长度减一做与操作,最后的结果就是hash值的低n位,其中n是HashTable的长度以2为底的结果。
在确定了链表的头部以后,就可以对整个链表进行遍历,看第4行,取出key对应的value的值,如果拿出的value的值是null,则可能这个key,value对正在put的过程中,如果出现这种情况,那么就加锁来保证取出的value是完整的,如果不是null,则直接返回value。
ConcurrentHashMap的put操作
看完了get操作,再看下put操作,put操作的前面也是确定Segment的过程,这里不再赘述,直接看关键的segment的put方法:
- V put(K key, int hash, V value, boolean onlyIfAbsent) {
- lock();
- try {
- int c = count;
- if (c++ > threshold) // ensure capacity
- rehash();
- HashEntry<K,V>[] tab = table;
- int index = hash & (tab.length - 1 );
- HashEntry<K,V> first = tab[index];
- HashEntry<K,V> e = first;
- while (e != null && (e.hash != hash || !key.equals(e.key)))
- e = e.next;
- V oldValue;
- if (e != null ) {
- oldValue = e.value;
- if (!onlyIfAbsent)
- e.value = value;
- }
- else {
- oldValue = null ;
- ++modCount;
- tab[index] = new HashEntry<K,V>(key, hash, first, value);
- count = c; // write-volatile
- }
- return oldValue;
- } finally {
- unlock();
- }
- }
首先对Segment的put操作是加锁完成的,然后在第五行,如果Segment中元素的数量超过了阈值(由构造函数中的loadFactor算出)这需要进行对Segment扩容,并且要进行rehash,关于rehash的过程大家可以自己去了解,这里不详细讲了。
第8和第9行的操作就是getFirst的过程,确定链表头部的位置。
第11行这里的这个while循环是在链表中寻找和要put的元素相同key的元素,如果找到,就直接更新更新key的value,如果没有找到,则进入21行这里,生成一个新的HashEntry并且把它加到整个Segment的头部,然后再更新count的值。
ConcurrentHashMap的remove操作
Remove操作的前面一部分和前面的get和put操作一样,都是定位Segment的过程,然后再调用Segment的remove方法:
- V remove(Object key, int hash, Object value) {
- lock();
- try {
- int c = count - 1 ;
- HashEntry<K,V>[] tab = table;
- int index = hash & (tab.length - 1 );
- HashEntry<K,V> first = tab[index];
- HashEntry<K,V> e = first;
- while (e != null && (e.hash != hash || !key.equals(e.key)))
- e = e.next;
- V oldValue = null ;
- if (e != null ) {
- V v = e.value;
- if (value == null || value.equals(v)) {
- oldValue = v;
- // All entries following removed node can stay
- // in list, but all preceding ones need to be
- // cloned.
- ++modCount;
- HashEntry<K,V> newFirst = e.next;
- for (HashEntry<K,V> p = first; p != e; p = p.next)
- newFirst = new HashEntry<K,V>(p.key, p.hash,
- newFirst, p.value);
- tab[index] = newFirst;
- count = c; // write-volatile
- }
- }
- return oldValue;
- } finally {
- unlock();
- }
- }
首先remove操作也是确定需要删除的元素的位置,不过这里删除元素的方法不是简单地把待删除元素的前面的一个元素的next指向后面一个就完事了,我们之前已经说过HashEntry中的next是final的,一经赋值以后就不可修改,在定位到待删除元素的位置以后,程序就将待删除元素前面的那一些元素全部复制一遍,然后再一个一个重新接到链表上去,看一下下面这一幅图来了解这个过程:
假设链表中原来的元素如上图所示,现在要删除元素3,那么删除元素3以后的链表就如下图所示:
ConcurrentHashMap的size操作
在前面的章节中,我们涉及到的操作都是在单个Segment中进行的,但是ConcurrentHashMap有一些操作是在多个Segment中进行,比如size操作,ConcurrentHashMap的size操作也采用了一种比较巧的方式,来尽量避免对所有的Segment都加锁。
前面我们提到了一个Segment中的有一个modCount变量,代表的是对Segment中元素的数量造成影响的操作的次数,这个值只增不减,size操作就是遍历了两次Segment,每次记录Segment的modCount值,然后将两次的modCount进行比较,如果相同,则表示期间没有发生过写入操作,就将原先遍历的结果返回,如果不相同,则把这个过程再重复做一次,如果再不相同,则就需要将所有的Segment都锁住,然后一个一个遍历了,具体的实现大家可以看ConcurrentHashMap的源码,这里就不贴了。
PS. 原文在:Java并发编程之ConcurrentHashMap
PS:本篇文章的也提供了PDF下载:concurrentHashMap.pdf
发表评论
-
MyBatis-generator使用,为Example添加分页
2017-11-01 16:10 4960数据库为MySQL。1. 在Example类里,加入两个变 ... -
使用Spring MVC统一异常处理实战
2017-08-22 14:26 3361 描述 在J2EE项目的开 ... -
日志组件的关系梳理:如何正确使用它们
2017-08-07 14:25 731背景 由于现在开源框架日益丰富,好多开源框架使用的 ... -
Java中“引用”的几种类型
2017-07-18 17:09 611一. 概述: 强引用(S ... -
Spring和Mybatis整合时无法读取properties的处理方案
2016-11-29 11:39 1741config.properties配置文件信息 ... -
Protobuf使用
2016-07-12 11:49 2191ProtoBuf的官方下载包并不包含jar文件,需要用户自 ... -
jmeter读取外部配置文件
2016-06-06 10:30 0配置文件有两类: 一、路径相关配置文件,只需要了解清楚jm ... -
@SuppressWarnings抑制警告的关键字
2016-05-16 15:45 1962关键字 用途 all to suppress a ... -
Apache的DbUtils框架学习
2016-04-01 19:47 758一、commons-dbutils简介 co ... -
Dubbo与Zookeeper、SpringMVC整合和使用(负载均衡、容错)
2016-03-30 20:13 705互联网的发展,网站 ... -
Java GC 详解
2016-03-30 19:54 7371、基本回收算法 (1) 引用计数(Reference ... -
JVM(Java虚拟机)优化大全和案例实战
2016-03-30 19:53 500堆内存设置 原理 JVM堆内存分为2块:Perman ... -
Spring事务的传播行为和隔离级别
2016-02-20 22:32 910http://blog.csdn.net/paincupi ... -
java中什么是bridge method(桥接方法)
2016-01-31 19:19 558在看spring-mvc的源码的时候,看到在解析handle ... -
@SuppressWarnings的使用、作用、用法
2016-01-06 16:45 1522在java编译过程中会出现很多警告,有很多是安全的,但是每次 ... -
fastjson遇到的无限递归的问题
2015-09-13 18:09 3983fastjson是用反射的,如果在实体类里 ... -
当spring 容器初始化完成后执行某个方法
2015-08-11 14:56 2262在做web项目开发中,尤其是企业级应用开发的时候,往往会在工 ... -
javac命令初窥
2015-07-30 14:05 1952注:以下红色标记的参数在下文中有所讲解。 用法: ja ... -
JDK各版本地址下载
2015-07-17 13:09 13431. 总地址:http://www.oracle.com/ ... -
jdk1.5-1.9新特性
2015-07-17 13:02 17981.51.自动装箱与拆箱:2.枚举(常用来设计单例模式)3. ...
相关推荐
解析concurrenthashmap的源码,学习多线程的思想
java7-8中的 HashMap和ConcurrentHashMap全解析
java7-8中的 HashMap和ConcurrentHashMap全解析 如果你想了解底层的逻辑就来看看吧
ConcurrentHashMap具体是怎么实现线程安全的呢,肯定不可能是每个方法加synchronized,那样就变成了HashTable。
HashMap& ConcurrentHashMap 深度解析
ConcurrentHashMap源码级别的面试解析,适合0~2年的人员,附源码解读,下载即可拿到md的源文档
今天小编就为大家分享一篇关于Java源码解析ConcurrentHashMap的初始化,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
下面小编就为大家带来一篇基于Java并发容器ConcurrentHashMap#put方法解析。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
线程安全的 Map – ConcurrentHashMap,让我们一起研究和 HashMap 相比有何差异,为何能保证线程安全呢. 1 继承体系 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gkf7KyhC-...
上图中,每个绿色的实体是嵌套类 Entry 的实例,Entry 包含四个属性:key, value, hash 值和用于单向链表的capacity:当前数组容量
Java并发编程学习宝典(漫画版),Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习...
Java并发编程学习宝典(漫画版),Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习宝典(漫画版)Java并发编程学习...
HashMap、ConcurrentHashMap源码级解读,并且对比了JDK7和8实现的不同,进行了大量的解释,结合了多个学习视频
java所有集合类底层源码解析汇总,包括ArrayList、HashMap、HashSet、LinkedList、TreeMap、HashSet、ConcurrentHashMap等集合框架的底层实现源码大白话解读。
并发容器ConcurrentHashMap原理与使用.mp4 线程池的原理与使用.mp4 Executor框架详解.mp4 实战:简易web服务器(一).mp4 实战:简易web服务器(二).mp4 JDK8的新增原子操作类LongAddr原理与使用.mp4 JDK8新增锁...
其中服务端为解决多线程操作共享资源,确保线程安全摒弃资源消耗大的Synchronized使用ConcurrentHashMap存放Socket对象。 服务端: (1)连接客户端:实现与客户端的Socket通信。 (2)管理客户端:实现通过线程池...
08HashMap与ConcurrenthashMap源码解读 09MySQL深度原理解析 10Netty深度源码解读 11SpringCloud微服务框架源码解读 12彻底搞懂分布式锁架构设计原理 13分布式数据一致性设计原理 14分布式消息中间件 15实战新零售...
包含了摩根面试的技术要点,涉及JVM架构,内存回收,Classloader等JDK底层技术,也包括像HashMap,ConcurrentHashMap,Object线程同步等API的解读,还涉及了Spring AOP原理解析等框架技术。
第51节并发容器ConcurrentHashMap原理与使用00:38:22分钟 | 第52节线程池的原理与使用00:42:49分钟 | 第53节Executor框架详解00:36:54分钟 | 第54节实战:简易web服务器(一)00:55:34分钟 | 第55节实战:简易...