搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > java进阶笔记 > CurrentHashMap原理与应用

CurrentHashMap原理与应用

java进阶笔记 2019-02-13
举报

结构

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对;Segment 用来充当锁的角色,每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

HashEntry 类

HashEntry 用来封装散列映射表中的键值对。在 HashEntry 类中,key,hash 和 next 域都被声明为 final 型,value 域被声明为 volatile 型。

Segment 类

Segment 类继承于 ReentrantLock 类,从而使得 Segment 对象能充当锁的角色。每个 Segment 对象用来守护其(成员对象 table 中)包含的若干个桶。 table 是一个由 HashEntry 对象组成的数组。table 数组的每一个数组成员就是散列映射表的一个桶。

ConcurrentHashMap 类

ConcurrentHashMap 在默认并发级别会创建包含 16 个 Segment 对象的数组。每个 Segment 的成员对象 table 包含若干个散列表的桶。每个桶是由 HashEntry 链接起来的一个链表。如果键能均匀散列,每个 Segment 大约守护整个散列表中桶总数的 1/16。

结构示意图

put实现

  1. 首先,根据 key 计算出对应的 hash 值:

  2. 然后,根据 hash 值找到对应的Segment 对象:

  3. 最后,在这个 Segment 中执行具体的 put 操作:

    注意:这里的加锁操作是针对(键的 hash 值对应的)某个具体的 Segment,锁定的是该 Segment 而不是整个 ConcurrentHashMap。 同时,所有读线程几乎不会因本线程的加锁而阻塞(除非读线程刚好读到这个 Segment 中某个 HashEntry 的 value 域的值为 null,此时需要加锁后重新读取该值)。

remove实现

和 get 操作一样,首先根据散列码找到具体的链表;然后遍历这个链表找到要删除的节点;最后把待删除节点之后的所有节点原样保留在新链表中,把待删除节点之前的每个节点克隆到新链表中。(删除c节点)在执行 remove 操作时,原始链表并没有被修改,也就是说:读线程不会受同时执行 remove 操作的并发写线程的干扰。

get实现

ConcurrentHashMap 中,每个 Segment 都有一个变量 count。它用来统计 Segment 中的 HashEntry 的个数。这个变量被声明为 volatile。 所有不加锁读方法,在进入读方法时,首先都会去读这个 count 变量。比如下面的 get 方法:

 
   
   
 
  1. V get(Object key, int hash) {

  2.           if(count != 0) {       // 首先读 count 变量

  3.               HashEntry<K,V> e = getFirst(hash);

  4.               while(e != null) {

  5.                   if(e.hash == hash && key.equals(e.key)) {

  6.                       V v = e.value;

  7.                       if(v != null)            

  8.                           return v;

  9.                       // 如果读到 value 域为 null,说明发生了重排序,加锁后重新读取

  10.                       return readValueUnderLock(e);

  11.                   }

  12.                   e = e.next;

  13.               }

  14.           }

  15.           return null;

  16.       }

在 ConcurrentHashMap 中,所有执行写操作的方法(put, remove, clear),在对链表做结构性修改之后,在退出写方法前都会去写这个 count 变量。所有未加锁的读操作(get, contains, containsKey)在读方法中,都会首先去读取这个 count 变量。 根据 Java 内存模型,对 同一个 volatile 变量的写 / 读操作可以确保:写线程写入的值,能够被之后未加锁的读线程“看到”。


欢迎加入java交流群:



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《CurrentHashMap原理与应用》的版权归原作者「java进阶笔记」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注java进阶笔记微信公众号

java进阶笔记微信公众号:tangshandxs

java进阶笔记

手机扫描上方二维码即可关注java进阶笔记微信公众号

java进阶笔记最新文章

精品公众号随机推荐

举报