集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据结构的支持。比如两个线程需要同时访问一个中间临界区(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底层原理与源码分析深入详解
Java并发编程中的ConcurrentHashMap是HashMap的一个线程安全版本,设计目标是在高并发场景下提供高效的数据访问。相比HashTable,ConcurrentHashMap通过采用锁分离技术和更细粒度的锁定策略来提升性能。HashTable...
ConcurrentHashMap源码分析源码分析 代码解释非常详细!!!!
源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556
在理解`ConcurrentHashMap`的实现原理之前,我们先来看看哈希表的基本概念。 哈希表是一种键值对存储的数据结构,通过键(key)进行索引,可以高效地查找、插入和删除数据。如果键是整数,我们可以直接用它作为数组...
Java并发系列之ConcurrentHashMap源码分析 ConcurrentHashMap是Java中一个高性能的哈希表实现,它解决了HashTable的同步问题,允许多线程同时操作哈希表,从而提高性能。 1. ConcurrentHashMap的成员变量: ...
ConcurrentHashMap 的实现原理 ConcurrentHashMap 是 Java 中一个高效的线程安全的哈希表实现,它的实现原理可以分为两部分:JDK1.7 中的实现和 JDK8 中的实现。 JDK1.7 中的实现 在 JDK1.7 中,...
在Java并发编程领域,`ConcurrentHashMap`是一个至关重要的类,它提供了线程安全的哈希映射功能,且性能优异。在JDK8中,`ConcurrentHashMap`的实现方式与之前的版本(如JDK6)有了显著变化,去除了Segment锁段的...
#### 六、`ConcurrentHashMap`的工作原理 1. **定位元素**:`ConcurrentHashMap`采用两次哈希来定位元素。第一次哈希定位到具体的`Segment`,第二次哈希则定位到该`Segment`内的`HashEntry`链表头部。 2. **写操作*...
java本地缓存ConcurrentHashMap
本文将深入探讨ConcurrentHashMap的内部结构、工作原理及其在实际场景中的应用。 #### 二、结构解析 **1. 锁分段技术** ConcurrentHashMap的核心思想是将一个大哈希表分割成多个小哈希表(称为段,Segment),每...
Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~
在本文中,我们将深入探索 ConcurrentHashMap 的高并发实现机制,并分析其在 Java 内存模型基础上的实现原理。了解 ConcurrentHashMap 的实现机制有助于我们更好地理解 Java 并发编程的原理和技术。 一、Java 内存...
通过以上分析,我们可以看到ConcurrentHashMap如何通过锁分段技术来解决HashMap在并发环境下的线程安全问题,并通过巧妙的设计减少线程间锁的竞争,从而提升性能。因此,在设计需要高并发性能的程序时,...
我们首先来理解`computeIfAbsent`方法的基本概念,然后再深入分析这个问题的成因及解决方案。 `computeIfAbsent`是JDK 1.8中新增的一个功能强大的方法,它的作用是在给定的键不存在于映射中时,通过提供的函数来...
分析JDK源代码,探索ConcurrentHashMap高并发的具体实现机制,包括其在JDK中的定义和结构、并发存取、重哈希和跨段操作,并着重剖析了ConcurrentHashMap读操作不需要加锁和分段锁机制的内在奥秘和原理。
通过以上分析可以看出,`ConcurrentHashMap`的设计非常巧妙,它利用锁分离技术和不可变性来实现高效的并发访问。这种设计不仅提高了多线程环境下的性能,同时也保持了良好的线程安全性。对于需要在多线程环境下高效...