`
IXHONG
  • 浏览: 450159 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

为什么ConcurrentHashMap是弱一致的(jdk6)

阅读更多

本文将用到Java内存模型的happens-before偏序关系(下文将简称为hb)以及ConcurrentHashMap的底层模型相关的知识。本文将从ConcurrentHashMap的get,clear,iterator(entrySet、keySet、values方法)三个方法来分析它们的弱一致问题。

ConcurrentHashMap#get

get方法是弱一致的,是什么含义?可能你期望往ConcurrentHashMap底层数据结构中加入一个元素后,立马能对get可见,但ConcurrentHashMap并不能如你所愿。换句话说,put操作将一个元素加入到底层数据结构后,get可能在某段时间内还看不到这个元素,若不考虑内存模型,单从代码逻辑上来看,却是应该可以看得到的。

下面将结合代码和java内存模型相关内容来分析下put/get方法(本文中所有ConcurrentHashMap相关的代码均来自hotspot1.6.0_18)。put方法我们只需关注Segment#put,get方法只需关注Segment#get,在继续之前,先要说明一下Segment里有两个volatile变量:counttable;HashEntry里有一个volatile变量:value
Segment#put

V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock();
    try {
        int c = count;
        if (c++ > threshold) // ensure capacity
            rehash();
        HashEntry<K,V>[] tab = table;
        int index = hash & (tab.length - 1);
        HashEntry<K,V> first = tab[index];
        HashEntry<K,V> 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<K,V>(key, hash, first, value);
            count = c; // write-volatile
        }
        return oldValue;
    } finally {
        unlock();
    }
}

Segment#get

V get(Object key, int hash) {
    if (count != 0) { // read-volatile
        HashEntry<K,V> 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;
}

我们如何确定线程1放入某个变量的值是否对线程2可见?文章开头提到的JLS链接中有说到,当a hb c时,a对c可见,那么我们接下来我们只要寻找put和get之间所有可能的执行轨迹上的hb关系。要找出hb关系,我们需要先找出与hb相关的Action。为方便,这里将两段代码放到了一张图片上。

可以注意到,同一个Segment实例中的put操作是加了锁的,而对应的get却没有。根据hb关系中的线程间Action类别,可以从上图中找出这些Action,主要是volatile读写和加解锁,也就是图中画了横线的那些。

put操作可以分为两种情况,一是key已经存在,修改对应的value;二是key不存在,将一个新的Entry加入底层数据结构。

key已经存在的情况比较简单,即if (e != null)部分,前面已经说过HashEntry的value是个volatile变量,当线程1给value赋值后,会立马对执行get的线程2可见,而不用等到put方法结束。

key不存在的情况稍微复杂一些,新加一个Entry的逻辑在else中。那么将new HashEntry赋值给tab[index]是否能立刻对执行get的线程可见呢?我们只需分析写tab[index]与读取tab[index]之间是否有hb关系即可。

假设执行put的线程与执行get的线程的轨迹是这样的

执行put的线程 执行get的线程
⑧tab[index] = new HashEntry\<K,V>(key, hash, first, value)  
②count = c  
  ③if (count != 0)
  ⑨HashEntry e = getFirst(hash);

tab变量是一个普通的变量,虽然给它赋值的是volatile的table。另外,虽然引用类型(数组类型)的变量table是volatile的,但table中的元素不是volatile的,因此⑧只是一个普通的写操作;count变量是volatile的,因此②是一个volatile写;③很显然是一个volatile读;⑨中getFirst方法中读取了table,因此包含一个volatile读。

根据Synchronization Order,对同一个volatile变量,有volatile写 hb volatile读。在这个执行轨迹中,时间上②在③之前发生,且②是写count,③是读count,都是针对同一个volatile变量count,因此有② hb ③;又因为⑧和②是同一个线程中的,③和⑨是同一个线程中的,根据Program Order,有⑧ hb ②,③ hb ⑨。目前我们有了三组关系了⑧ hb ②,② hb ③,③ hb ⑨,再根据hb关系是可传递的(即若有x hb y且y hb z,可得出x hb z),可以得出⑧ hb ⑨。因此,如果按照上述执行轨迹,⑧中写入的数组元素对⑨中的读取操作是可见的。

再考虑这样一个执行轨迹:

|执行put的线程|执行get的线程|
|-|-|
|⑧tab[index] = new HashEntry\<K,V>(key, hash, first, value)||
||③if (count != 0)|
②count = c||
||⑨HashEntry e = getFirst(hash);|

这里只是变换了下执行顺序。每条语句的volatile读写含义同上,但它们之间的hb关系却改变了。Program Order是我们一直拥有的,即我们有⑧ hb ②,③ hb ⑨。但这次对volatile的count的读时间上发生在对count的写之前,我们无法得出② hb ⑨这层关系了。因此,通过count变量,在这个轨迹上是无法得出⑧ hb ⑨的。那么,存不存在其它可替换关系,让我们仍能得出⑧ hb ⑨呢?

我们要找的是,在⑧之后有一条语句或指令x,在⑨之前有一条语句或指令y,存在x hb y。这样我们可以有⑧ hb x,x hb y, y hb ⑨。就让我们来找一下是否存在这样的x和y。图中的⑤、⑥、⑦、①存在volatile读写,但是它们在⑧之前,因此对确立⑧ hb ⑨这个关系没有用处;同理,④在⑨之后,我们要找的是⑨之前的,因此也对这个问题无益。前面已经分析过了②,③之间没法确立hb关系。

在⑧之后,我们发现一个unlock操作,如果能在⑨之前找到一个lock操作,那么我们要找的x就是unlock,要找的y就是lock,因为Synchronization Order中有unlock hb lock的关系。但是,很不幸运,⑨之前没有lock操作。因此,对于这样的轨迹,是没有⑧ hb ⑨关系的,也就是说,如果某个Segment实例中的put将一个Entry加入到了table中,在未执行count赋值操作之前有另一个线程执行了同一个Segment实例中的get,来获取这个刚加入的Entry中的value,那么是有可能取不到的!

此外,如果getFirst(hash)先执行,tab[index] = new HashEntry\<K,V>(key, hash, first, value)后执行,那么,这个get操作也是看不到put的结果的。

正是因为get操作几乎所有时候都是一个无锁操作(get中有一个readValueUnderLock调用,不过这句执行到的几率极小),使得同一个Segment实例上的put和get可以同时进行,这就是get操作是弱一致的根本原因。Java API中对此有一句简单的描述:

Retrievals reflect the results of the most recently completed
update operations holding upon their onset.

也就是说API上保证get操作一定能看到已完成的put操作。已完成的put操作肯定在get读取count之前对count做了写入操作。因此,也就是我们第一个轨迹分析的情况。总之,get有可能读到过时的数据。

ConcurrentHashMap#clear

clear方法很简单,看下代码即知。

public void clear() {
    for (int i = 0; i < segments.length; ++i)
        segments[i].clear();
}

因为没有全局的锁,在清除完一个segments之后,正在清理下一个segments的时候,已经清理segments可能又被加入了数据,因此clear返回的时候,ConcurrentHashMap中是可能存在数据的。因此,clear方法是弱一致的。

ConcurrentHashMap中的迭代器

ConcurrentHashMap中的迭代器主要包括entrySet、keySet、values方法。它们大同小异,这里选择entrySet解释。当我们调用entrySet返回值的iterator方法时,返回的是EntryIterator,在EntryIterator上调用next方法时,最终实际调用到了HashIterator.advance()方法,看下这个方法:

final void advance() {
    if (nextEntry != null && (nextEntry = nextEntry.next) != null)
        return;

    while (nextTableIndex >= 0) {
        if ( (nextEntry = currentTable[nextTableIndex--]) != null)
            return;
    }

    while (nextSegmentIndex >= 0) {
        Segment<K,V> seg = segments[nextSegmentIndex--];
        if (seg.count != 0) {
            currentTable = seg.table;
            for (int j = currentTable.length - 1; j >= 0; --j) {
                if ( (nextEntry = currentTable[j]) != null) {
                    nextTableIndex = j - 1;
                    return;
                }
            }
        }
    }
}

这个方法在遍历底层数组。在遍历过程中,如果已经遍历的数组上的内容变化了,迭代器不会抛出ConcurrentModificationException异常。如果未遍历的数组上的内容发生了变化,则有可能反映到迭代过程中。这就是ConcurrentHashMap迭代器弱一致的表现。

总结

ConcurrentHashMap的弱一致性主要是为了提升效率,是一致性与效率之间的一种权衡。要成为强一致性,就得到处使用锁,甚至是全局锁,这就与Hashtable和同步的HashMap一样了。

0
0
分享到:
评论

相关推荐

    JDK-1.6u45-Windows 32位

    5. **动态语言支持**:JDK 6引入了JSR 292(即Dynamic Language Support),为Java平台提供了支持其他动态语言的基础。 6. **更好的内存管理**:JVM(Java虚拟机)在Java 6中进行了优化,包括垃圾回收算法的改进,...

    HashMap与ConcurrentHashMap面试要点.pdf

    ##### JDK8中为什么要使用红黑树? JDK8引入红黑树主要是为了解决HashMap在高哈希碰撞情况下的性能问题。当链表长度超过一定阈值(默认为8个元素)时,链表的查找效率会低于红黑树,因此将链表转换为红黑树以保证其...

    71-ConcurrentHashMap笔记1

    《并发编程:深入理解JDK1.8 ConcurrentHashMap》 ConcurrentHashMap是Java并发编程中不可或缺的一个数据结构,它在JDK1.8中进行了重大的优化,极大地提升了并发性能。相较于早期版本,JDK1.8的ConcurrentHashMap...

    jdk1.6安装文件-64位

    Java Development Kit(JDK)是Java编程语言的核心组件,它为开发者提供了编译、调试和运行Java应用程序所需的所有工具。JDK 1.6,也称为Java SE 6,是Oracle公司发布的一个早期版本,主要面向Windows操作系统。在这...

    JDK1.8自动脚本安装

    6. **JDK1.8的关键特性**: - Lambda表达式:引入函数式编程概念,简化多线程和事件驱动编程。 - Stream API:处理集合数据的新方式,支持并行计算。 - 方法引用和构造器引用:简化代码,与Lambda表达式结合使用...

    jdk中线程安全的集合类.docx

    ##### 2.1 为什么HashMap在多线程下不安全? `HashMap`之所以在多线程环境下出现问题,主要源于其内部实现机制。在`HashMap`中,数据是以键值对的形式存储在一个数组中,每个键值对对应一个链表或红黑树的节点。当...

    JDK.rar_jdk1.7

    在JDK 1.7之前,Java程序员需要为每种可能抛出的异常分别写一个catch块。1.7引入了多catch语句,允许开发者在一个catch块中处理多个不同类型的异常,提高了代码的可读性和简洁性。 ```java try { // 代码块 } ...

    hashmap_use_in_JDK7.zip

    7. **迭代器遍历**:HashMap的迭代器(`Iterator`)是弱一致性的,这意味着在遍历过程中,如果其他线程修改了HashMap(除了通过迭代器自身的`remove()`方法),则可能会看到不一致的结果。但不会抛出`...

    java jdk1.8中文版和英文版和jdk1.6中文说明文档 chm文档

    Java JDK是Java开发工具包,它是Java编程语言和平台的核心组成部分。JDK1.8和JDK1.6是两个不同版本的Java Development Kit,分别代表了Java在2014年和2006年的主要发布。这两个版本在功能、性能以及API支持上存在...

    JDK8中sun.misc下UnSafe类源代码 UnSafe.java

    《深入解析JDK8中的sun.misc.UnSafe类》 在Java编程中,sun.misc.UnSafe类是一个非常特殊的存在。这个类在JDK8中扮演着一个核心的角色,它提供了对Java语言规范中未公开的底层操作的访问。尽管UnSafe类并非设计为...

    集合常见面试题

    jdk1.8之前并发操作hashmap时为什么会有死循环的问题? hashmap扩容时每个entry需要再计算一次hash吗? hashmap的数组长度为什么要保证是2的幂? 如何用LinkedHashMap实现LRU? 如何用TreeMap实现一致性hash? ...

    多线程精品资源--java-study 是本人学习Java过程中记录的一些代码!从Java基础的数据类型、jdk1..zip

    6. **并发集合**:如ConcurrentHashMap、CopyOnWriteArrayList等,这些集合在多线程环境下提供了安全的读写操作,提高了并发性能。 7. **线程中断与异常处理**:如何通过interrupt()方法中断线程,以及如何处理...

    最新JDK教程(CHM版)

    - **线程模型的增强**:JDK 5.0之后引入了更高级的并发工具类,如`ConcurrentHashMap`等。 #### 三、集合框架 - **概述**:Java集合框架提供了一组接口和实现类,用于存储和操作对象集合。 - **Collection接口**:...

    jdk api 1.8.CHM 中文版

    《Java开发工具包(JDK)API 1.8中文版》是Java开发者的重要参考资料,它详尽地列出了Java 1.8版本中的各种类、接口、方法和异常等核心组件,为开发者提供了全面的编程指南。这个CHM文件不仅包含了中文版的API文档,...

    Java并发编程实践-03章-使用JDK并发包构建程序1

    原子量是JDK并发包中的重要组成部分,它们保证了在多线程环境下的操作是不可分割的,即使在高并发情况下也能确保数据的一致性。原子量主要由以下几部分组成: **3.2.1 锁同步法** 在Java中,传统的同步机制包括...

    Java面试题集合部分.docx

    7. **与(&)操作**:使用与(&)运算代替取模操作,是因为与运算在二进制层面更快,且能保证计算结果与取模一致,前提数组长度为2的n次幂。 8. **数组长度为2的n次幂**:这样的长度可以确保哈希计算的均匀性,避免因...

    HashMap与CorruntHashMap性能对比

    `ConcurrentHashMap`则是在JDK 5.0引入的,专为多线程环境设计。它采用了分段锁(Segment)的设计,将整个散列表分割成多个独立的段,每个段可以看作是一个小型的`HashMap`,并由各自的锁来保护。这种设计允许并发...

    javajdk8源码-concurrencyJava:基于JDK8源码学习并发编程知识

    此外,`java.util.stream`流API在JDK 8中引入,虽然不是专门为并发设计的,但通过`parallelStream()`方法,我们可以很容易地将串行操作转换为并行操作,从而利用多核优势进行并行计算。 `ConcurrentHashMap`是并发...

    Brian Goetz - 构造一个更好的hashmap

    这篇文章的标题为“构造一个更好的hashmap”,该文章主要讨论了ConcurrentHashMap的数据结构及其在java.util.concurrent包中的实现方式。该话题主要涉及并发编程领域,尤其是Java语言在并发控制方面的应用。下面是对...

Global site tag (gtag.js) - Google Analytics