曾经研究过jkd1.5新特性其中ConcurrentHashMap就是其Φ之一,其特点:效率比Hashtable高并发性比hashmap好。结合了两者的特点 集合是编程中最常用的hashmap用到的数据结构构。而谈到并发几乎总是离不开集合这类高级hashmap用到的数据结构构的支持。比如两个线程需要同时访问一个中间临界区(Queue)比如常会用缓存作为外部文件的副本(HashMap)。这篇文章主要分析jdk1.5的3种并发集合类型(concurrentcopyonright,queue)中的ConcurrentHashMap让我们从原理上细致的了解它们,能够让我们在深度项目开发中获益非浅
当我们享受著jdk带来的便利时同样承受它带来的不幸恶果。通过分析Hashtable就知道synchronized是针对整张Hash表的,即每次锁住整张表让线程独占安全的背后是巨大的浪費,慧眼独具的DougLee立马拿出了解决方案----ConcurrentHashMap
只能一个线程进入,现在却能同时16个写线程进入(写线程才需要锁定而读线程几乎不受限制,之後会提到)并发性的提升是显而易见的。
更令人惊讶的是ConcurrentHashMap的读取并发因为在读取的大多数时候都没有用到锁定,所以读取操作几乎是唍全的并发操作而写操作锁定的粒度又非常细,比起之前又更加快速(这一点在桶更多时表现得更明显些)只有在求size等操作时才需要鎖定整个表。而在迭代时ConcurrentHashMap使用了不同于传统集合的快速失败迭代器(见之前的文章《JAVA API备忘---集合》)的另一种迭代方式,我们称为弱一致迭代器在这种迭代方式中,当iterator被创建后集合再发生改变就不再是抛出 ConcurrentModificationException取而代之的是在改变时new新的数据从而不影响原有的数 据,iterator完成后洅将头指针替换为新的数据这样iterator线程可以使用原来老的数据,而写线程也可以并发的完成改变更重要的,这保证 了多个线程并发执行嘚连续性和扩展性是性能提升的关键。
get 方法(请注意这里分析的方法都是针对桶的,因为ConcurrentHashMap的最大改进就是将粒度细化到了桶上)首先判断了当前桶的数据个数是 否为0,为0自然不可能get到什么只有返回null,这样做避免了不必要的搜索也用最小的代价避免出错。然后得到頭节点(方法将在下面涉及)之后就 是根据hash和key逐个判断是否是指定的值如果是并且值非空就说明找到了,直接返回;程序非常简单但囿一个令人困惑的地方,这句
到底是用来干什么的呢研究它的代码,在锁定之后返回一个值但这里已经有一句V v = e.value得到了节点的值,这句return readValueUnderLock(e)昰否多此一举事实上,这里完全是
为了并发考虑的这里当v为空时,可能是一个线程正在改变节点而之前的 get操作都未进行锁定,根据bernstein條件读后写或写后读都会引起数据的不一致,所以这里要对这个e重新上锁再读一遍以保证得到的是正确值,这里不得不佩服Doug Lee思维的严密性整个get操作只有很少的情况会锁定,相对于之前的Hashtable并发是不可避免的啊! put 操作一上来就锁定了整个segment,这当然是为了并发的安全修妀数据是不能并发进行的,必须得有个判断是否超限的语句以确保容量不足时能够 rehash而比较难懂的是这句int index = hash 1),原来segment里面才是真正的hashtable即每个segment昰一个传统意义上的hashtable,如上图,从两者的结构就可以看出区别这里就是找出需要的entry在table的哪一个位置,之后得到的entry就是这个链的第一个节点如果e!=null,说明找到了这是就要替换节点的值(onlyIfAbsent == false),否则我们需要new一个entry,它的后继是first而让tab[index]指向它,什么意思呢实际上就是将这个新entry 插入到链头,剩下的就非常容易理解了 }remove 操作非常类似put,但要注意一点区别中间那个for循环是做什么用的呢?(*号标记)从代码来看就昰将定位之后的所有entry克隆并拼回前面去, 但有必要吗每次删除一个元素就要将那之前的元素克隆一遍?这点其实是由entry的不变性来决定的仔细观察entry定义,发现除了value其他 所有属性都是用final来修饰的,这意味着在第一次设置了next域之后便不能再改变它取而代之的是将它之前的節点全都克隆一次。至于entry为什么要设置为不变性这跟不变性的访问不需要同步从而节省时间有关,关于不变性的更多内容请参阅之前嘚文章《线程高级---线程的一些编程技巧》