理解Java8并发工具类ConcurrentHashMap的实现

前面的文章已经分析过List和Queue相关的接口与并发实现类,本篇我们来分析一下非常Java里面非常重要的一个数据结构HashMap。(注意Set类型在这里我们不在单独分析,因为Set本身并不能算一种数据结构,它可以借助任何其他数据结构如array或者map类来实现。)

我们先看下Java里面一些常见的Map类型:

线程不安全的Map:

HashMap (允许key和value都为null)
TreeMap (允许value为null)
LinkedHashMap (允许key和value都为null)

线程安全的Map:

ConcurrentHashMap (key和value都不允许为null)
Hashtable (key和value都不允许为null)
Collections.synchronizedMap(map) (key和value都不允许为null)

在有序性方面:

HashMap是无序的,底层实现是数组+单向链表

LinkedHashMap可以保持插入顺序,底层实现是数组+双向链表

TreeMap是基于比较器顺序的,可以自定义key的排序规则,底层实现是数组+红黑树结构

上面的三个Map都是线程不安全的,也就是说在多线程下使用是有问题的,所以如果需要多线程场景下使用,就必须使用线程安全的集合,这里面Hashtable 和Collections.synchronizedMap(map)是JDK里面出现比较早的线程安全的map类,虽然是线程安全,但因为并不高效,因为其内部完全用的简单的synchronized来保证同步,在多线程竞争激烈情况下,效率较低。

不安全的Map在多线程下使用肯定是会有问题的,这毋庸置疑,比如JDK8之前的HashMap在高并发下如果有多个线程同时采用头插法扩容链表操作,那么将会有很大几率导致链表闭链,从而引发死循环导致CPU占满。这里简单分析一下原因:

看JDK7里面HashMap扩容的核心代码:

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;            ---------------------(1)
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity); 
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } // while

        }
    }

为了方便理解,我们制造如下的代码:

Map<Integer> map = new HashMap<Integer>(2);

上面的代码现在我们只放置两个元素3和7,其中的threshold为1,所以当再次插入数据时候,map会进行扩容操作,扩容后的大小是原长度的2倍也就是4。

我们简化现在的存放策略是对table数组的长度取模,由于3和7模上2都等于1,所以都会放在table数组1的

[0]= null
[1]= 3->7

如果再增加一个元素时候会发生扩容,数组的长度会变成4,然后数据需要迁移,迁移的方式是头插法,新加入的节点会插入链表的头部。

假设有两个线程同时进行扩容操作,第一个线程刚执行到下面这一步

Entry<K,V> next = e.next;

第二个线程已经完成扩容,扩容后的格式如下:

[0]= null
[1]= 3->7
[2]= 7->3
[3]= null

然后第一个线程继续执行,第二个线程执行完会把数据刷新到主内存里面,注意JMM内存模型在这里没有可见性保证,因为第一个线程并不是在第二个线程关闭之后启动的,所以此时线程二的修改结果,对于线程一来说可能是可见的。如果是可见的。

在扩容时候,线程一table[1]的7后面的引用变成了3,在扩容后,table下标2的位置就会出现如下的情况:

[2]=3->7->3

这样就导致了基于头插法倒置的链表就出现了死循环。

在JDK8以来,对HashMap内部做了很大的改进,数据结构采用了数组+链表+红黑树的方法来存储元素,针对扩容操作,不在改变原来的table数组的数据结构,而是在基于复制的思想在新数组上进行改动,完成之后在切换引用,避免了死循环的问题,但其仍然不是线程安全的,比如在多线程put的时候会发生丢数据,对迭代器遍历的时候会发生fail-fast,所以针对这种情况才有了ConcurrentHashMap这种高效安全的并发工具类。

在JDK7中的ConcurrentHashMap采用了分段锁的技术,每个段类似一个独立的数组+链表结构,并发粒度控制在Segment级别,如下图:

不难发现采用这种方式,并发粒度还是太粗了,对于同一个Segment下面不同的数组链表数,如果有多个线程访问仍然要等待,所以在jdk8中取消了分段锁的思想,改用基于CAS自旋+synchronized控制并发操作,实现了更粒度的锁控制。JDK8的源码里仍然保留了Segment类,仅仅是为了兼容旧的版本,不做其他的用途。

前面说过JDK8的ConcurrentHashMap用了数组+链表+红黑树的数据结构,如下图:

重要的成员字段:

// 核心数组存储
 transient volatile Node<K,V>[] table;
// 扩容时用到的数组
private transient volatile Node<K,V>[] nextTable;

/*用来控制table的初始化和扩容操作
#0:默认值
#-1:代表哈希表正在进行初始化
#大于0:相当于 HashMap 中的 threshold,表示阈值
#小于-1:代表有多个线程正在进行扩容
*/
private transient volatile int sizeCtl;
// 默认初始化table容量
private static final intDEFAULT_CAPACITY = 16;
// 默认的负载因子
private static final float LOAD_FACTOR = 0.75f;
// 链表转树的阀值,如果table[i]下面的链表长度大于8时就转化为红黑树
static final int TREEIFY_THRESHOLD = 8;
//树转链表的阀值,小于等于6是转为链表,仅在扩容tranfer时才可能树转链表
static final int UNTREEIFY_THRESHOLD = 6;

核心的链表Node类:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        //.......其他省略
        }

链表转树时,并不会直接转,只是把这些节点包装成TreeNode放到TreeBin中, 再由TreeBin来转化红黑树

static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        //.......
        }

TreeBin封装了TreeNode,当链表转树时,用于封装TreeNode,也就是说,ConcurrentHashMap的红黑树存放的时TreeBin,而不是treeNode。

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
        //......
        }

特殊的Node节点ForwardingNode类: 作用:在扩容的时候插在链表的头部,用来标识状态

static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    }

`

put(k,v)方法分析

(1)先判断key和value是否为null,为null扔出异常

(2)判断table是否初始化,如果没有则进行初始化

(3)计算key的hash值,并得到插入的数组索引。

(4)找到table[i]的位置,如果为null直接插入,如果不为null判断此key是否存在,如果存在直接覆盖,如果不存在进行判断如果head节点是树节点,按照红黑树的方式插入新的节点,如果不是则按照链表的方式插入,同时会判断当前的链表长度是否大于8,如果大于则转为红黑树再插入,否则直接插入,插入采用的CAS自旋的方式。

(5)最后判断table的size是否需要扩容,如果需要则扩容,否则就结束。在扩容的时候会在链表头部插入forward,如果其他线程检测到需要插入的位置被forward节点占有,就帮助进行扩容。

get方法分析:

get方法比较简单,因为不涉及并发问题,直接就根据key的hash值定位到链表,然后遍历查询即可。

size方法分析:

计算节点数量,计算baseCount和CounterCell.value的总和

entrySet方法分析:

通过EntrySetView类提供了当前的map的视图,在当前视图上的remove操作可以直接映射到Map上,反之亦然,这个视图提供了弱一致性的保证,在遍历删除的时候不会出现 Fail-fast的并发修改异常。

总结:

本文主要介绍了Java8里面HashMap的相关内容并着重介绍了ConcurrentHashMap的实现和核心方法分析,HashMap是我们日常开发中使用频率最高的类之一,而ConcurrentHashMap则是在并发编程中的高效工具类,理解其实核心设计,则对我们的工作和学习有很大帮助。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-09-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SDNLAB

Open vSwitch系列之数据结构解析深入分析ofpbuf

上一篇我们分析了hmap,hamp可以说是Open vSwitch中基石结构,很多Open vSwitch中数据结构都依赖hmap。本篇我们来分析一下ofpbu...

38880
来自专栏Redis源码学习系列

Redis源码学习之字典

在字典结构体中,包含了一组字典函数(dictType),通过封装的方法处理对应的操作,通常在字典初始化的时候对其进行配置。

35610
来自专栏夏时

PHP 常用函数大全

62320
来自专栏数据结构与算法

cf444E. DZY Loves Planting(并查集)

然后cf正解居然是网络流??出给NOIP模拟赛T1???¥%……&((……%&((

13430
来自专栏逍遥剑客的游戏开发

C++的反射和序列化

17720
来自专栏猿人谷

面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别

HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

19410
来自专栏用户2442861的专栏

怎么有效的防止内存泄漏

http://blog.csdn.net/couhujia/article/details/8474905

18920
来自专栏Laoqi's Linux运维专列

正则三剑客-awk

awk与前两个不同之处是支持分段处理; #mkdir awk; cp /etc/passwd awk/passwd         //前期准备,创建一个awk...

29150
来自专栏对角另一面

lodash源码分析之数组的差集

本文为读 lodash 源码的第十七篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

13940
来自专栏ACM算法日常

POJ-3641:Pseudoprime numbers(快速幂)

Fermat's theorem states that for any prime number p and for any integer a > 1, a...

11710

扫码关注云+社区

领取腾讯云代金券