文档章节

ConcurrentHashMap笔记

精神病的羽毛球
 精神病的羽毛球
发布于 2014/04/06 14:26
字数 1615
阅读 178
收藏 5

    ConcurrentHashMap是支持多线程并发操作的哈希表,与HashTable相似,不支持nullkeyvalue,方法声明上也遵循了HashTable的规范。总体数据结构与HashMap类似,都是数组,按链地址法哈希具体的值。但ConcurrentHashMap内部按来组织,每个段对应了一个或多个哈希entry。写操作(putremove等)都需要加排它锁,而读操作(get)不需要加锁,因此获取的值可能是读操作的中间状态,尤其对(putAllclear),读操作可能只能获取部分值。迭代器和enumeration返回的是哈希表某个状态,不抛出ConcurrentModificationException。迭代器同一时刻只允许一个线程使用。

ConcurrentHashMap的成员变量有:

static final int DEFAULT_INITIAL_CAPACITY = 16;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final int DEFAULT_CONCURRENCY_LEVEL = 16;

static final int MAXIMUM_CAPACITY = 1 << 30;

static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

static final int MAX_SEGMENTS = 1 << 16;

static final int RETRIES_BEFORE_LOCK = 2;

 

其中大部分与HashMap一致。DEFAULT_CONCURRENCY_LEVEL一定程度上衡量了可支持的并发线程数;MIN_SEGMENT_TABLE_CAPACITY是每个段最少的哈希entry,即每个段中HashEntry数组最小容量;MAX_SEGMENTS是最大允许的段数目(源码中注释说是不小于1<<24,但默认的值给的是1<<16,并且对该值注释说”slightly conservative”;RETRIES_BEFORE_LOCKsizecontainsValue方法加锁时重试的最大次数,如果在多次重试后仍没有获取锁,则线程进入中断状态在加锁队列中排队。

简单来说,ConcurrentHashMap是一个Segment<K,V>[]数组,每个Segment<K,V>又包含一个HashEntry<K,V>[]数组(即维护了一个小的hash表),HashEntry数组每个元素就是一个hash值对应的HashEntry链,具体的key-value对就放在这个链中。

先来说说Segment<K,V>。这是一个内部类,派生自ReentrantLock。主要的成员变量包括:

static final int MAX_SCAN_RETRIES =

            Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

transient volatile HashEntry<K,V>[] table;

transient int count;

transient int modCount;

transient int threshold;

final float loadFactor;

    其中,loadFactorthresholdHashMap中一致;table就是该段一个小的hash表;count是表中的元素个数;modCount是段中所有可变操作(putremoveclear等)的次数,在isEmptysize中用得到,如果值溢出可能会导致一些问题。

    段的主要操作是putremovereplaceclear。除了clear,每次操作都需要tryLock,如果未获得锁,则调用scanAndLockscanAndLockForPut,一方面继续请求获得独占锁,另一方面检索表以找到待操作的节点(The main benefit is to absorb cache misses (which are very common for hash tables) while obtaining locks so that traversal is faster once)。如果多次(最大为MAX_SCAN_RETRIES)请求都没能获得锁,则interrupt线程,进入队列等待直到获得锁。具体细节与ReentrantLock的实现有关。相比而言,clear操作就显得粗暴一点,直接调用lock加锁。此外,put可能导致rehash,也是以两倍的大小增长。

    再来看看ConcurrentHashMap自己的成员。ConcurrentHashMap最关键的构造函数:

    public ConcurrentHashMap(int initialCapacity,

                             float loadFactor, int concurrencyLevel)

    首先找到一个不小于concurrentcyLevel的数,这个数即ssize必须是2的幂,且2^sshift=ssize,由此得到segmentShiftsegmentMask

        int sshift = 0;

        int ssize = 1;

        while (ssize < concurrencyLevel) {

            ++sshift;

            ssize <<= 1;

        }

        this.segmentShift = 32 - sshift;

        this.segmentMask = ssize - 1;

    再看capcap是每个段中的表初始大小,cap也是2的幂,最小是2cap×sszie>=initialCapacity

    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;

    最后,创建段数组。s0好比一个段模板,初始化表大小为caprehashthresholdcap×loadFactor,根据s0创建段数组。

    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;

    因此,concurrentHashMapssize个段,即表示最多支持ssize个线程同时写。

    concurrentHashMap的方法中,很多都有一个recheck的过程。

isEmpty()方法,先检查每个段的count,如果有不为0直接返回false,否则累加modCount得到sum;接着再遍历一遍段,如果count有不为0则返回false,否则用之前的sum递减modCount,若最后sum不为0则返回false,否则为true。这样做是针对一个段进行检查的同时另一个段正在进行修改的情况,意义和作用我还不是特别能理解。isEmpty并不需要加锁。

Size()操作都需要对每个段进行加锁(也不一定,如果发现为空则直接返回0);

containsValuesize一样,在指定次数(RETRIES_BEFORE_LOCK)内没发现想要的值,则强制加锁进行排它性查找,如果找到则返回true;还有个contains,是为了保持与HashTable一致,实际调用的就是containsValue

getcontainsKey都不需要加锁,表面含义和代码都很容易理解,如果参数为null则抛出NullPointerException

put操作首先找到段数组中指定映射的段,没有则生成一个新的段,接着调用段的put方法插入数据,每次在链头部插入。

putIfAbsentput差不多,不同的是只有在不存在指定key时才会插入新的key-value值,如果已经有了这个key则不执行更新。

putAll调用put进行插入;

remove调用segmentremove

replace调用segmentreplace

clear依次调用每个段的clearclear并不会同时对所有段加锁,因此可能在执行clear操作时,有读操作发生会出现读取到clear操作的中间结果,putAll也有这种情况。

keySet返回一个keyset,该set有个弱一致性的迭代器,不抛出ConcurrentModificationException。迭代器的操作调用的是该concurrentHashMap相关的方法,包括removesizecontainsclearisEmpty等,不包括任何put操作。所有iterator上的改动都会直接反应到ConcurrentHashMap,反之亦然。

valuesentrySetkeySetelementskeys返回的是一个枚举集。

再说hash算法,HashMaphash算法已经够变态了,没想到一山还有一山高,ConcurrentHashMap也是特么的吓唬人啊。

// 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的实现比起HashMap复杂很多,还有很多概念我理解的还很不到位,例如volatile的用法,happen-before到底是什么意思?不加锁的读会出现什么可能意想不到的后果?等等。


© 著作权归作者所有

精神病的羽毛球
粉丝 2
博文 27
码字总数 20242
作品 0
成都
程序员
私信 提问
Java并发编程笔记之ConcurrentHashMap原理探究

在多线程环境下,使用进行操作时存在丢失数据的情况,为了避免这种bug的隐患,强烈建议使用代替 HashTable是一个线程安全的类,它使用synchronized来锁住整张Hash表来实现线程安全,即每次锁...

狂小白
2018/08/15
0
0
dubbo源码学习笔记----registry

注册工厂 核心方法就这一个。 注册抽象类 可以发现注册集合的操作通过ReentrantLock加锁实现,createRegistry注册实现则是交给对应实现方自己实现。 将所有url和backupurl全部放入集合,通过...

春哥大魔王的博客
2018/01/14
49
0
dubbo源码学习笔记----Provider和Consumer

provider consumer ProviderMethodModel持有所有服务提供者的方法信息 ProviderModel持有所有服务提供者信息 ApplicationModel持有服务的提供者和消费者信息 service注解 service信息通过Ser...

服务端技术杂谈
2018/01/13
73
0
8月15日云栖精选夜读 | 马云最新演讲:为什么要别人帮你?不帮你才是常态 | 超燃视频

If not now, when? If not me, who? 我去年来非洲的时候就感觉,有一些事情必须要做,很多事情可以去做。 我开始阿里巴巴创业的时候,我和团队说:If not now, when? If not me, who?...

yq传送门
2018/08/15
0
0
dubbo源码学习笔记----monitor

核心类 针对于每个注册进来的URL有个对应的Monitor状态跟踪类,每个Monitor状态跟踪类,通过一个Listener进行绑定。 将这个Listener交给一个线程池定时拉取Monitor信息。 Monitor使用 Monito...

春哥大魔王的博客
2018/01/14
222
0

没有更多内容

加载失败,请刷新页面

加载更多

EDI 电子数据交换全解指南

EDI(Electronic Data Interchange,电子数据交换)技术使得企业与企业(B2B)实现通信自动化,帮助交易伙伴和组织更快更好地完成更多工作,并消除了人工操作带来的错误。从零售商到制造商、物...

EDI知行软件
58分钟前
3
0
CentOS7的LVM动态扩容

# 问题 CentOS7上面的磁盘空间有点紧张,需要扩容。 解决 查询当前磁盘状态 [root@xxx ~]# lsblkNAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINTfd0 2:0 1 4K ...

亚林瓜子
今天
3
0
Kafka 0.8 Producer (0.9以前版本适用)

Kafka旧版本producer由scala编写,0.9以后已经废除 示例代码如下: import kafka.producer.KeyedMessage;import kafka.javaapi.producer.Producer;import kafka.producer.ProducerConfig;......

实时计算
今天
4
0
Giraph源码分析(八)—— 统计每个SuperStep中参与计算的顶点数目

作者|白松 目的:科研中,需要分析在每次迭代过程中参与计算的顶点数目,来进一步优化系统。比如,在SSSP的compute()方法最后一行,都会把当前顶点voteToHalt,即变为InActive状态。所以每次...

数澜科技
今天
6
0
Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部