文档章节

ConcurrentHashMap原理分析

phacks
 phacks
发布于 2015/08/19 08:29
字数 1971
阅读 9
收藏 0
点赞 0
评论 0

集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区(Queue),比如常会用缓存作为外部文件的副本(HashMap)。这篇文章主要分析jdk1.5的3种并发集合类型(concurrent,copyonright,queue)中的ConcurrentHashMap,让我们从原理上细致的了解它们,能够让我们在深度项目开发中获益非浅。

    在tiger之前,我们使用得最多的数据结构之一就是HashMap和Hashtable。大家都知道,HashMap中未进行同步考虑,而Hashtable则使用了synchronized,带来的直接影响就是可选择,我们可以在单线程时使用HashMap提高效率,而多线程时用Hashtable来保证安全。

    当我们享受着jdk带来的便利时同样承受它带来的不幸恶果。通过分析Hashtable就知道,synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,安全的背后是巨大的浪费,慧眼独具的Doug Lee立马拿出了解决方案----ConcurrentHashMap。

    ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁。如图


左边便是Hashtable的实现方式---锁整个hash表;而右边则是ConcurrentHashMap的实现方式---锁桶(或段)。ConcurrentHashMap将hash表分为16个桶(默认值),诸如get,put,remove等常用操作只锁当前需要用到的桶。试想,原来只能一个线程进入,现在却能同时16个写线程进入(写线程才需要锁定,而读线程几乎不受限制,之后会提到),并发性的提升是显而易见的。

    更令人惊讶的是ConcurrentHashMap的读取并发,因为在读取的大多数时候都没有用到锁定,所以读取操作几乎是完全的并发操作,而写操作锁定的粒度又非常细,比起之前又更加快速(这一点在桶更多时表现得更明显些)。只有在求size等操作时才需要锁定整个表。而在迭代时,ConcurrentHashMap使用了不同于传统集合的快速失败迭代器(见之前的文章《JAVA API备忘---集合》)的另一种迭代方式,我们称为弱一致迭代器。在这种迭代方式中,当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException,取而代之的是在改变时new新的数据从而不影响原有的数据,iterator完成后再将头指针替换为新的数据,这样iterator线程可以使用原来老的数据,而写线程也可以并发的完成改变,更重要的,这保证了多个线程并发执行的连续性和扩展性,是性能提升的关键。

    接下来,让我们看看ConcurrentHashMap中的几个重要方法,心里知道了实现机制后,使用起来就更加有底气。

    ConcurrentHashMap中主要实体类就是三个:ConcurrentHashMap(整个Hash表),Segment(桶),HashEntry(节点),对应上面的图可以看出之间的关系。

    get方法(请注意,这里分析的方法都是针对桶的,因为ConcurrentHashMap的最大改进就是将粒度细化到了桶上),首先判断了当前桶的数据个数是否为0,为0自然不可能get到什么,只有返回null,这样做避免了不必要的搜索,也用最小的代价避免出错。然后得到头节点(方法将在下面涉及)之后就是根据hash和key逐个判断是否是指定的值,如果是并且值非空就说明找到了,直接返回;程序非常简单,但有一个令人困惑的地方,这句return readValueUnderLock(e)到底是用来干什么的呢?研究它的代码,在锁定之后返回一个值。但这里已经有一句V v = e.value得到了节点的值,这句return readValueUnderLock(e)是否多此一举?事实上,这里完全是为了并发考虑的,这里当v为空时,可能是一个线程正在改变节点,而之前的get操作都未进行锁定,根据bernstein条件,读后写或写后读都会引起数据的不一致,所以这里要对这个e重新上锁再读一遍,以保证得到的是正确值,这里不得不佩服Doug Lee思维的严密性。整个get操作只有很少的情况会锁定,相对于之前的Hashtable,并发是不可避免的啊!

 

V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry 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 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[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry first = (HashEntry) tab[index];
                HashEntry 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(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[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry first = (HashEntry)tab[index];
                HashEntry 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 newFirst = e.next;
                    *    for (HashEntry p = first; p != e; p = p.next)
                    *        newFirst = new HashEntry(p.key, p.hash, 
                                                          newFirst, p.value);
                        tab[index] = newFirst;
                        count = c; // write-volatile
                    }
                }
                return oldValue;
            } finally {
                unlock();
            }
        }


static final class HashEntry {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry next;

        HashEntry(K key, int hash, HashEntry next, V value) {
            this.key = key;
            this.hash = hash;
            this.next = next;
            this.value = value;
        }
    }

 以上,分析了几个最简单的操作,限于篇幅,这里不再对rehash或iterator等实现进行讨论,有兴趣可以参考src。

    接下来实际上还有一个疑问,ConcurrentHashMap跟HashMap相比较性能到底如何。这在Brian Goetz的文章中已经有过评测http://www.ibm.com/developerworks/cn/java/j-jtp07233/




© 著作权归作者所有

共有 人打赏支持
phacks
粉丝 5
博文 99
码字总数 105354
作品 0
高级程序员
ConcurrentHashMap源码分析

前言 JDK中的Hashtable是一个线程安全的K-V形式的容器,它实现线程安全的原理十分简单,就是在所有涉及对该哈希表操作的方法上都加上了synchronized关键字,进行加锁操作。这么做实现了线程安...

Justlearn ⋅ 2017/04/13 ⋅ 0

探究Java的ConcurrentHashMap实现机制

原文地址: http://blog.csdn.net/u011080472/article/details/51392712 在学习ConcurrentHashMap的高并发时,找到了一些高质量的博客,就没有重复转载了。分别列出了JDK6中的Segment分段加锁...

Gavin__Zhou ⋅ 2017/08/06 ⋅ 0

ConcurrentHashMap能完全替代HashTable吗?

关于ConcurrentHashMap在之前的ConcurrentHashMap原理分析中已经解释了原理,而HashTable其实大抵上只是对HashMap的线程安全的封装,在JDK7与JDK8中HashMap的实现中解释了HashMap的原理。 至...

Hosee ⋅ 2016/05/15 ⋅ 2

ConcurrentHashMap原理分析

曾经在 [高并发Java 五] JDK并发包1 中提到过ConcurrentHashMap,只是简单的提到了下ConcurrentHashMap的优点,以及大概的实现原理。 而本文则重点介绍ConcurrentHashMap实现的细节。 HashMa...

Hosee ⋅ 2016/03/17 ⋅ 2

Java集合--ConcurrentHashMap原理

1.1 ConcurrentHashMap源码理解 上篇,介绍了ConcurrentHashMap的结构。本节中,我们来从源码的角度出发,来看下ConcurrentHashMap原理。 1.2 ConcurrentHashMap初始化 我们首先,来看下Con...

贾博岩 ⋅ 2017/11/12 ⋅ 0

Java并发学习(十九)-Java8中ConcurrentHashMap分析

断断续续看了那么些天,趁着周末把知识记下来。 在平常编程时,HashMap是用的很频繁的一个类,但是,当在并发情况下,却不推荐使用它,因为它没有做任何的并发控制,不安全,是个隐患。 当然...

anLA_ ⋅ 2017/12/19 ⋅ 0

HashMap-你可能需要知道这些

HashMap是Android程序员(当然也包括Java程序员)经常使用的映射数据类型,伴随着JDK的版本更新,JDK1.8相比1.7对HashMap的底层实现了一些优化,尤其是红黑树这个点(现在面试的时候基本都会问...

24K男 ⋅ 2017/10/09 ⋅ 0

聊聊并发系列_Index

聊聊并发系列 聊聊并发(一)深入分析Volatile的实现原理 聊聊并发(二)Java SE1.6中的Synchronized 聊聊并发(三)Java线程池的分析和使用 聊聊并发(四)深入分析ConcurrentHashMap 聊聊并...

陶邦仁 ⋅ 2016/01/04 ⋅ 0

ConcurrentHashMap源码分析

最近,在写一个数据监控项目,涉及到ConcurrentHashMap,之前只是用,虽然没出问题,但是并不是特别清楚里面的原理,所以,这一次,需要把原理弄明白再开始动手。 ==========================...

强子哥哥 ⋅ 2016/12/26 ⋅ 0

ConcurrentHashMap深入分析

![Map类图][1]Hashtable是JDK 5之前Map唯一线程安全的内置实现(Collections.synchronizedMap不算)。Hashtable继承的是Dictionary(Hashtable是其唯一公开的子类),并不继承AbstractMap或者...

陶邦仁 ⋅ 2014/03/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mahout推荐算法API详解

前言 用Mahout来构建推荐系统,是一件既简单又困难的事情。简单是因为Mahout完整地封装了“协同过滤”算法,并实现了并行化,提供非常简单的API接口;困难是因为我们不了解算法细节,很难去根...

xiaomin0322 ⋅ 21分钟前 ⋅ 0

WampServer默认web服务器根目录位置

安装WampServer之后的web服务器根目录默认位置在WampServer安装目录下的www:

临江仙卜算子 ⋅ 22分钟前 ⋅ 0

Redux的一些手法记录

Redux Redux的基本概念见另一篇文。 这里记录一下Redux在项目中的实际操作的手法。 actions 首先定义action.js,actions的type,可以另起一个action-type.js文件。 action-type.js用来存...

LinearLaw ⋅ 23分钟前 ⋅ 0

android 手势检测(左右滑动、上下滑动)

GestureDetector类可以让我们快速的处理手势事件,如点击,滑动等。 使用GestureDetector分三步: 1. 定义GestureDetector类 2. 初始化手势类,同时设置手势监听 3. 将touch事件交给gesture...

王先森oO ⋅ 38分钟前 ⋅ 0

java 方法的执行时间监控 设置超时(Future 接口)

java 方法的执行时间监控 设置超时(Future 接口) import java.util.concurrent.Callable; import java.util.concurrent.ExecutionException; import java.util.concurrent.Executor......

青峰Jun19er ⋅ 42分钟前 ⋅ 0

一名开源小白的Apache成长自述

今天收到了来自Apache Vote我成为Serviceomb项目Committer的邮件,代表自己的贡献得到了充分的肯定;除了感谢团队的给力支持,我更希望将自己的成长经历——如何践行Apache Way的心得介绍给大...

微服务框架 ⋅ 44分钟前 ⋅ 0

vim介绍、颜色显示和移动光标、一般模式下复制、剪切和粘贴

1.vim 是 vi 的升级版 vim 是带有颜色显示的 mini安装的系统,一般都不带有vim [root@aminglinux-128 ~]# yum install -y vim-enhanced已加载插件:fastestmirror, langpacksLoading mir...

oschina130111 ⋅ 45分钟前 ⋅ 0

Deepin 操作系统四面楚歌

作为国内做的最好的 Linux 发行版,源自 Debian sid 的 Deepin 目前正面临重重困境,新版本不断延期,开发人员离职,bug 长期得不到修复,和 Debian/Ubuntu 的兼容性问题也面临越来越严重的挑...

六库科技 ⋅ 45分钟前 ⋅ 0

MyBatis之动态sql

我们需要知道的是,使用mybatis重点是对sql的灵活解析和处理。在原先的UserMappser.xml中,我们这样查询表中满足条件的记录 : 123 <select id="findUserList" parameterType="userQuery...

瑟青豆 ⋅ 45分钟前 ⋅ 0

这届俄罗斯世界杯的冷门那么多怎么办?

最纯粹的世界杯,最神奇的大冷门。 德国0比1被墨西哥摩擦了。 日本历史性的赢了哥伦比亚。 C罗也挑平了西班牙。 梅西被冰岛狮吼吼愣神了。 就连11次进世界杯4强的巴西也被瑞士逼平了。 天台已...

开源中国众包平台 ⋅ 46分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部