`
zl198751
  • 浏览: 272091 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Map的并发处理(ConcurrentHashMap)

阅读更多

推荐相关文章:

http://blog.csdn.net/waitforcher/archive/2009/05/24/4211896.aspx

 

 

ConcurrentModificationException

在这种迭代方式中,当iterator被创建后集合再发生改变就不再是抛出ConcurrentModificationException, 取而代之的是在改变时new新的数据从而不影响原有的数据iterator完成后再将头指针替换为新的数据 ,这样iterator线程可以使用原来老的数据,而写线程也可以并发的完成改变。

 

ConcurrentHashMap 原理:

集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区 (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;
        }
    }
 

 

 

 

 

ConcurrentHashMap 和 HashTable 的速度比较:

util.concurrent 包中的 ConcurrentHashMap 类(也将出现在JDK 1.5中的 java.util.concurrent 包中)是对 Map 的线程安全的实现,比起 synchronizedMap 来,它提供了好得多的并发性。多个读操作几乎总可以并发地执行,同时进行的读和写操作通常也能并发地执行,而同时进行的写操作仍然可以不时地并发进行(相关的类也提供了类似的多个读线程的并发性,但是,只允许有一个活动的写线程) 。ConcurrentHashMap 被设计用来优化检索操作;实际上,成功的 get() 操作完成之后通常根本不会有锁着的资源。要在不使用锁的情况下取得线程安全性需要一定的技巧性,并且需要对Java内存模型(Java Memory Model)的细节有深入的理解。 ConcurrentHashMap 实现,加上 util.concurrent 包的其他部分,已经被研究正确性和线程安全性的并发专家所正视。在下个月的文章中,我们将看看 ConcurrentHashMap 的实现的细节。

ConcurrentHashMap 通过稍微地松弛它对调用者的承诺而获得了更高的并发性。检索操作将可以返回由最近完成的插入操作所插入的值,也可以返回在步调上是并发的插入操作所添加的值(但是决不会返回一个没有意义的结果)。由 ConcurrentHashMap.iterator() 返回的 Iterators 将每次最多返回一个元素,并且决不会抛出 ConcurrentModificationException 异常,但是可能会也可能不会反映在该迭代器被构建之后发生的插入操作或者移除操作。在对 集合进行迭代时,不需要表范围的锁就能提供线程安全性。在任何不依赖于锁整个表来防止更新的应用程序中,可以使用 ConcurrentHashMap 来替代 synchronizedMapHashtable

上述改进使得 ConcurrentHashMap 能够提供比 Hashtable 高得多的可伸缩性,而且,对于很多类型的公用案例(比如共享的cache)来说,还不用损失其效率。

好了多少?

表 1对 Hashtable ConcurrentHashMap 的可伸缩性进行了粗略的比较。在每次运行过程中, n 个线程并发地执行一个死循环,在这个死循环中这些线程从一个 Hashtable 或者 ConcurrentHashMap 中检索随机的key value,发现在执行 put() 操作时有80%的检索失败率,在执行操作时有1%的检索成功率。测试所在的平台是一个双处理器的Xeon系统,操作系统是Linux。数据显示了10,000,000次迭代以毫秒计的运行时间,这个数据是在将对 ConcurrentHashMap的 操作标准化为一个线程的情况下进行统计的。您可以看到,当线程增加到多个时, ConcurrentHashMap 的性能仍然保持上升趋势,而 Hashtable 的性能则随着争用锁的情况的出现而立即降了下来。

比起通常情况下的服务器应用,这次测试中线程的数量看上去有点少。然而,因为每个线程都在不停地对表进行操作,所以这与实际环境下使用这个表的更多数量的线程的争用情况基本等同。

表 1.Hashtable 与 ConcurrentHashMap在可伸缩性方面的比较

线程数 ConcurrentHashMap Hashtable
1 1.00 1.03
2 2.59 32.40
4 5.58 78.23
8 13.21 163.48
16 27.58 341.21
32 57.27 778.41
  • 大小: 25.8 KB
分享到:
评论

相关推荐

    Java并发编程之ConcurrentHashMap

    ConcurrentHashMap为了提高本身的并发能力,在内部采用了一个叫做Segment的结构,一个Segment其实就是一个类HashTable的结构,Segment内部维护了一个链表数组,我们用下面这一幅图来看下ConcurrentHashMap的内部结构...

    java_各个Map的区别

    java_各个Map的区别 ConcurrentHashMap 支持检索的完全并发和更新的所期望可调整并发的哈希表。(线程安全)此类遵守与 Hashtable 相同的功能规范,并且包括对应于 Hashtable 的每个方法的方法版本。不过,尽管所有...

    【面试系列】并发容器之ConcurrentHashMap

    微信公众号:放开我我还能学 ...这就导致了所有并发操作都要竞争同一把锁,一个线程在进行同步操作时,其他线程只能等待,大大降低了并发操作的效率。 Collections#SynchronizedMap 同步包装器 SynchronizedMap

    Java并发编程实战

    1.2.3 异步事件的简化处理 1.2.4 响应更灵敏的用户界面 1.3 线程带来的风险 1.3.1 安全性问题 1.3.2 活跃性问题 1.3.3 性能问题 1.4 线程无处不在 第一部分 基础知识 第2章 线程安全性 2.1 什么是线程安全...

    一文让你彻底理解JavaHashMap和ConcurrentHashMap

    本篇主要想讨论ConcurrentHashMap这样一个并发容器,在正式开始之前我觉得有必要谈谈HashMap,没有它就不会有后面的ConcurrentHashMap。众所周知HashMap底层是基于数组+链表组成的,不过在jdk1.7和1.8中具体实现稍有...

    Java 并发编程实战

    1.2.3 异步事件的简化处理 1.2.4 响应更灵敏的用户界面 1.3 线程带来的风险 1.3.1 安全性问题 1.3.2 活跃性问题 1.3.3 性能问题 1.4 线程无处不在 第一部分 基础知识 第2章 线程安全性 2.1 什么是线程安全...

    Java并发编程(学习笔记).xmind

    用于替代同步且基于散列的Map CopyOnWriteArrayList 用于在遍历操作为主要操作的情况下替代同步的List Queue ConcurrentLinkedQueue *BlockingQueue 提供了可阻塞的put和take方法...

    Java 常见并发容器总结

    - **`ConcurrentHashMap`** : 线程安全的 `HashMap` - **`CopyOnWriteArrayList`** : 线程安全的 `List`,在读多写少的场合性能非常好,远远好于 `Vector`。 - **`ConcurrentLinkedQueue`** : 高效的并发队列,使用...

    通过面试题带你了解java的Map

    该资源主要针对后端程序员,由在大厂工作7年的Java程序员经验,血泪整理,由面试题带你深入理解java的map。 内容概要: map的扩容、1.7、1.8之间的区别 ...3、concurrenthashmap怎么做到并发安全的

    Java开发常见问题总结.docx

    对于并发环境,使用线程安全的集合类如ConcurrentHashMap、CopyOnWriteArrayList等。 避免在循环中修改集合,可能导致ConcurrentModificationException。 异常处理: 不要忽视异常,合理捕获并处理它们。 不要过度...

    大厂真题之蚂蚁金服-Java高级.zip

    jdk1.7 到 jdk1.8 Map 发生了什么变化(底层)? 1.8 之后 hashMap 的数据结构发生了变化,从之前的单纯的数组+链表结构变成...解决方案是 jdk 的 ConcurrentHashMap,位于 java.util.concurrent 下,专门 解决并发问题。

    weak-lock-free:具有弱键和分离线程本地存储的并发映射的实现

    这是具有弱键的并发,... 如果许多线程同时写入映射,则写入映射可能会导致阻塞(这由ConcurrentHashMap和ReferenceQueue支持的映射暗示),但是,映射的性能明显优于在弱哈希映射周围使用同步包装器。 该库托管在M

    sesvc.exe 阿萨德

    本篇主要想讨论 ConcurrentHashMap 这样一个并发容器,在正式开始之前我觉得有必要谈谈 HashMap,没有它就不会有后面的 ConcurrentHashMap。 HashMap 众所周知 HashMap 底层是基于 数组 + 链表 组成的,不过在 jdk...

    JAVA面试常见问题整理

    JAVA面试常见问题整理 本文主要概述了Java面试中常见...同时,还涉及了事务处理的并发问题、Spring事务的实现方式和隔离级别等相关知识。 总之,本文为读者提供了一个关于Java面试常见问题及内容的概述,帮助读者更好

    triemap:Scala集合库中并发trie哈希映射实现的Java端口

    关于这是Scala集合库中并发的trie哈希映射实现的Java端口。 它曾经是从Scala到Java的几乎逐行转换。 如今,它已经被重构为对Java 8友好,并且无法通过重构来进行一些原始的断言。 在Aleksandar Prokopec撰写的这些...

    java8源码-JavaRobot:Java学习笔记,JavaLearningNote

    ConcurrentHashMap TreeMap Hashtable Set源码系列 HashSet LinkedHashSet TreeSet HashSet Concurrent源码系列 待完善 JVM(Java虚拟机) 类加载 垃圾回收算法 JavaConcurrent(Java并发系列) 【Java并发系列】

    java7hashmap源码-to-be-architect:成为Java架构师,你应该学习这些

    java7 hashmap源码 to-be-architect to be a Java ...Map:ConcurrentHashMap、HashMap、HashTable 并发List Set:CopyOnWriteArrayList、CopyOnWriteArraySet、 ArrayList、 LinkedList Concurrent

    写给大忙人看的JAVA SE 8

    6.2 ConcurrentHashMap改进 131 6.2.1 更新值 132 6.2.2 批量数据操作 134 6.2.3 Set视图 136 6.3 并行数组操作 137 6.4 可完成的Future 138 6.4.1 Future 138 6.4.2 编写Future 139 6.4.3 Future流水线 139 6.4.4 ...

Global site tag (gtag.js) - Google Analytics