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

ConcurrentHashMap原理分析

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

分享到:
评论

相关推荐

    程序员面试加薪必备:ConcurrentHashMap底层原理与源码分析深入详解

    程序员面试加薪必备_ConcurrentHashMap底层原理与源码分析深入详解

    ConcurrentHashmap源码

    源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556

    ConcurrentHashMap底层实现机制的分析1

    在本文中,我们将深入探索 ConcurrentHashMap 的高并发实现机制,并分析其在 Java 内存模型基础上的实现原理。了解 ConcurrentHashMap 的实现机制有助于我们更好地理解 Java 并发编程的原理和技术。 一、Java 内存...

    ConcurrentHashMap思维导图完整版

    分析JDK源代码,探索ConcurrentHashMap高并发的具体实现机制,包括其在JDK中的定义和结构、并发存取、重哈希和跨段操作,并着重剖析了ConcurrentHashMap读操作不需要加锁和分段锁机制的内在奥秘和原理。

    ConcurrentHashMap之实现细节

    通过以上分析可以看出,`ConcurrentHashMap`的设计非常巧妙,它利用锁分离技术和不可变性来实现高效的并发访问。这种设计不仅提高了多线程环境下的性能,同时也保持了良好的线程安全性。对于需要在多线程环境下高效...

    高薪程序员面试题精讲系列49之说说ConcurrentHashMap#put方法的源码及数。。。.pdf,这是一份不错的文件

    本文将对ConcurrentHashMap#put方法的源码进行详细分析,从而帮助读者更好地理解ConcurrentHashMap的工作机理。 一、ConcurrentHashMap的底层原理 ConcurrentHashMap是基于哈希表实现的,可以存储大量的数据。其...

    ConcurrentHashMap共18页.pdf.zip

    综上所述,"ConcurrentHashMap共18页.pdf.zip"这份文档很可能是深入分析 ConcurrentHashMap 的详细指南,涵盖了其设计原理、实现机制以及最佳实践。如果你对并发编程或者Java集合框架有深入需求,这份资料将是一份...

    24 经典并发容器,多线程面试必备。—深入解析ConcurrentHashMap.pdf

    【源码分析】深入理解`ConcurrentHashMap`的工作原理,需要查看其源码,特别是`put`、`get`、`resize`等关键操作,以及在不同版本中的变化,例如Java 8引入的红黑树优化。 总结,`ConcurrentHashMap`是Java并发编程...

    java ConcurrentHashMap锁分段技术及原理详解

    在`ConcurrentHashMap`的源码分析中,可以看到它通过`volatile`关键字保证了`HashEntry`中`value`字段的可见性,确保了读操作的正确性,而其他字段如`key`、`hash`和`next`都是`final`的,防止在链表中进行中间插入...

    JDK1.8 ConcurrentHashMap的一点理解

    只是都是相通的,当我们了解了ConcurrentHashMap的实现原理以及各个方法的实现机制,我们对于其他的hash类型实现也能快速的理解,今天我们就来通过源码来一点一点的分析下ConcurrentHashMap的实现。 首先我们来看...

    详谈HashMap和ConcurrentHashMap的区别(HashMap的底层源码)

    在HashMap源码分析中,我们可以看到HashMap类中的一些关键属性,如transient Entry[] table;、transient int size;、int threshold;、final float loadFactor;、transient int modCount;等等,这些属性都是HashMap...

    聊聊并发(4)深入分析ConcurrentHashMapJ

    本文将深入分析`ConcurrentHashMap`的设计原理、性能特点以及常见使用场景,帮助你提升Java并发编程的技能。 `ConcurrentHashMap`是`java.util.concurrent`包下的一个类,它在`HashMap`的基础上进行了优化,以适应...

    java中HashMap的原理分析

    现在我们来详细分析HashMap的工作机制: 1. **存储操作**:当我们调用`put()`方法插入键值对时,HashMap首先计算键的哈希码,然后模上数组的大小,得到一个索引位置。如果该位置的链表为空,就直接创建一个新的链表...

    并发编程atomic&collections-课上笔记1

    本文主要讲述了 Java 中的并发编程,包括 atomic 包的介绍、CAS 算法的原理、ABA 问题的解决方案,以及 collections 中的 HashMap、HashTable 和 ConcurrentHashMap 的源码分析。 Atomic 包的介绍 ----------------...

    并发编程以及计算机底层原理

    6. **阻塞队列BlockingQueue**:`14-阻塞队列BlockingQueue实战及其原理分析二-fox`讲解了阻塞队列的概念。 BlockingQueue是一种特殊的队列,当队列满时,生产者线程会被阻塞;队列空时,消费者线程会被阻塞。这种...

    Java并发容器,底层原理深入分析

    ConcurrentHashMapConcurrentHashMap底层具体实现JDK1.7底层实现将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap...

    Dubbo基本原理机制

    6. 客户端 socket 连接上专门监听消息的线程收到消息,分析结果,取到 ID,再从前面的 ConcurrentHashMap 里面 get(ID),从而找到 callback,将方法调用结果设置到 callback 对象里。 客户端获取结果 7. 监听线程...

    ConcurrentHashmaq源码分析.txt

    ConcurrentHashMap理论概述,实现原理,简单的源码分析,put和get的简单学习

    图灵Java高级互联网架构师第6期并发编程专题笔记.zip

    03-并发List、Set、 ConcurrentHashMap底层原理剖析-monkey 04-Java并发线程池底层原理详解与源码分析-monkey 05-并发编程之深入理解Java线程-fox 06-并发编程之CAS&Atomic原子操作详解-fox 07-并发锁机制之深入理解...

Global site tag (gtag.js) - Google Analytics