ConcurrentHashmap 解析

Stella981
• 阅读 315

ConcurrentHashmap(JDK1.7) 

总体描述:

  concurrentHashmap是为了高并发而实现,内部采用分离锁的设计,有效地避开了热点访问。而对于每个分段,ConcurrentHashmap采用final和内存可见修饰符volatile关键字(内存立即可见:Java 的内存模型可以保证:某个写线程对 value 域的写入马上可以被后续的某个读线程“看”到。注:并不能保证对volatile变量状态有依赖的其他操作的原子性)

借用某博客对concurrentHashmap对结构图:

ConcurrentHashmap 解析

ConcurrentHashmap 解析

不难看出,concurrenthashmap采用了二次hash的方式,第一次hash将key映射到对应的segment,而第二次hash则是映射到segment的不同桶中。

为什么要用二次hash,主要原因是为了构造分离锁,使得对于map的修改不会锁住整个容器,提高并发能力。当然,没有一种东西是绝对完美的,二次hash带来的问题是整个hash的过程比hashmap单次hash要长,所以,如果不是并发情形,不要使用concurrentHashmap。

代码实现:

该数据结构中,最核心的部分是两个内部类,HashEntry和Segment

concurrentHashmap维护一个segment数组,将元素分成若干段(第一次hash)

/**
* The segments, each of which is a specialized hash table.
*/
final Segment<K,V>[] segments;

segments的每一个segment维护一个链表数组

代码:

再来看看构造方法

public ConcurrentHashMap(int initialCapacity,
    float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
    throw new IllegalArgumentException();
    if (concurrencyLevel > MAX_SEGMENTS)
    concurrencyLevel = MAX_SEGMENTS;
    // Find power-of-two sizes best matching arguments
    int sshift = 0;
    int ssize = 1;
    while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
    }
    this.segmentShift = 32 - sshift;
    this.segmentMask = ssize - 1;
    if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
    int c = initialCapacity / ssize;
    if (c * ssize < initialCapacity)
    ++c;
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    while (cap < c)
    cap <<= 1;
    // create segments and segments[0]
    Segment<K,V> s0 =
    new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
    (HashEntry<K,V>[])new HashEntry[cap]);
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}

代码28行,一旦指定了concurrencyLevel(segments数组大小)便不能改变,这样,一旦threshold超标,rehash真不会影响segments数组,这样,在大并发的情况下,只会影响某一个segment的rehash而其他segment不会受到影响

(put方法都要上锁)

HashEntry

与hashmap类似,concurrentHashmap也采用了链表作为每个hash桶中的元素,不过concurrentHashmap又有些不同

static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;
     
    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
    }
     
    /**
    * Sets next field with volatile write semantics. (See above
    * about use of putOrderedObject.)
    */
    final void setNext(HashEntry<K,V> n) {
    UNSAFE.putOrderedObject(this, nextOffset, n);
    }
     
    // Unsafe mechanics
    static final sun.misc.Unsafe UNSAFE;
    static final long nextOffset;
    static {
    try {
    UNSAFE = sun.misc.Unsafe.getUnsafe();
    Class k = HashEntry.class;
    nextOffset = UNSAFE.objectFieldOffset
    (k.getDeclaredField("next"));
    } catch (Exception e) {
    throw new Error(e);
    }
    }
}

HashEntry的key,hash采用final,可以避免并发修改问题,HashEntry链的尾部是不能修改的,而next和value采用volatile,可以避免使用同步造成的并发性能灾难,新版(jdk1.7)的concurrentHashmap大量使用java Unsafe类提供的原子操作,直接调用底层操作系统,提高性能(这块我也不是特别清楚)

get方法(1.6 vs 1.7)

1.6

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.6的jdk采用了乐观锁的方式处理了get方法,在get的时候put方法正在new对象,而此时value并未赋值,这时判断为空则加锁访问

1.7

public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
    (tab = s.table) != null) {
    for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
    (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
    e != null; e = e.next) {
    K k;
    if ((k = e.key) == key || (e.hash == h && key.equals(k)))
    return e.value;
    }
    }
    return null;
}

1.7并没有判断value=null的情况,不知为何

跟同事沟通过,无论是1.6还是1.7的实现,实际上都是一种乐观的方式,而乐观的方式带来的是性能上的提升,但同时也带来数据的弱一致性,如果你的业务是强一致性的业务,可能就要考虑另外的解决办法(用Collections包装或者像jdk6中一样二次加锁获取)

http://ifeve.com/concurrenthashmap-weakly-consistent/

这篇文章可以很好地解释弱一致性问题

put方法

public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key);
        int j = (hash >>> segmentShift) & segmentMask;
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        return s.put(key, hash, value, false);
    }

对于put,concurrentHashmap采用自旋锁的方式,不同于1.6的直接获取锁

注:个人理解,这里采用自旋锁可能作者是觉得在分段锁的状态下,并发的可能本来就比较小,并且锁占用时间又并不是特别长,因此自旋锁可以减小线程唤醒和切换的开销

关于hash

private int hash(Object k) {
        int h = hashSeed;
        if ((0 != h) && (k instanceof String)) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

concurrentHashMap采用本身hashcode的同时,采用Wang/Jenkins算法对每位都做了处理,使得发生hash冲突的可能性大大减小(否则效率会很差)

而对于concurrentHashMap,segments的大小在初始时确定,此后不变,而元素所在segments桶序列由hash的高位决定

public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key);
        int j = (hash >>> segmentShift) & segmentMask;
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        return s.put(key, hash, value, false);
    }

segmentShift为(32-segments大小的二进制长度)

总结

concurrentHashmap主要是为并发设计,与Collections的包装不同,他不是采用全同步的方式,而是采用非锁get方式,通过数据的弱一致性带来性能上的大幅提升,同时采用分段锁的策略,提高并发能力

参考:

http://www.jb51.net/article/49699.htm

http://my.oschina.net/chihz/blog/58035

http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/

http://www.ibm.com/developerworks/cn/java/j-jtp06197.html

点赞
收藏
评论区
推荐文章
光头强的博客 光头强的博客
2个月前
Java面向对象试题
1、 请创建一个Animal动物类,要求有方法eat()方法,方法输出一条语句“吃东西”。 创建一个接口A,接口里有一个抽象方法fly()。创建一个Bird类继承Animal类并实现 接口A里的方法输出一条有语句“鸟儿飞翔”,重写eat()方法输出一条语句“鸟儿 吃虫”。在Test类中向上转型创建b对象,调用eat方法。然后向下转型调用eat()方
刚刚好 刚刚好
2个月前
css问题
1、 在IOS中图片不显示(给图片加了圆角或者img没有父级) <div<img src""/</div div {width: 20px; height: 20px; borderradius: 20px; overflow: h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
小森森 小森森
2个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本 欢迎添加左边的微信一起探讨!项目地址:](https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n) \2. Bug修复更新日历 2. 情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意), \ \ 和 注意
晴空闲云 晴空闲云
2个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。 盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
> MemFire Cloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序 select * from table_name order id desc; 2.按照指定(多个)字段排序 select * from table_name order id desc,status desc; 3.按照指定字段和规则排序 selec
Stella981 Stella981
1年前
Angular material mat
Icon Icon Name mat-icon code _add\_comment_ add comment icon <mat-icon> add\_comment</mat-icon> _attach\_file_ attach file icon <mat-icon> attach\_file</mat-icon> _attach\
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
#### 背景描述 # Time: 2019-01-24T00:08:14.705724+08:00 # User@Host: **[**] @ [**] Id: ** # Schema: sentrymeta Last_errno: 0 Killed: 0 # Query_time: 0.315758 Lock_
helloworld_34035044 helloworld_34035044
4个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。 uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid() 或 uuid(sep)参数说明:sep 布尔值,生成的uuid中是否包含分隔符'',缺省为
helloworld_28799839 helloworld_28799839
2个月前
常用知识整理
# Javascript ## 判断对象是否为空 ```js Object.keys(myObject).length === 0 ``` ## 经常使用的三元运算 > 我们经常遇到处理表格列状态字段如 `status` 的时候可以用到 ``` vue