侵权投诉
订阅
纠错
加入自媒体

ConcurrentHashMap#概述

2020-10-08 10:49
java达人
关注

数据结构

jdk1.7

jdk1.8  

如果头节点是Node类型,其后就是一个普通的链表;如果头节点是TreeNode类型,它的后面就是一颗红黑树,TreeNode是Node的子类。链表和红黑树之间可以相互转换:初始的时候是链表,当链表中的元素超过某个阈值时,把链表转换成红黑树;反之,当红黑树中的元素个数小于某个阈值时,再转换为链表。

历史版本对比

从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。代码量从原来的1000多行变成了 6000多 行,实现上也和原来的分段式存储有很大的区别。

1.数据结构

取消了Segment分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。使用红黑树,当一个槽里有很多元素时,查询时间复杂度从原来的遍历链表O(n),变成遍历红黑树O(logN),Hash冲突的问题也会得到较好的解决

2.锁的粒度:

JDK1.7采用segment的分段锁机制实现线程安全,其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。原来是对需要进行数据操作的Segment加锁,现调整为对每个头节点分别加锁,其并发度,就是Node数组的长度,初始长度为16,这降低了锁的粒度。

3.并发的扩容:

在JDK 7中,一旦Segment的个数在初始化的时候确立,不能再更改,并发度被固定。之后只是在每个Segment内部扩容,这意味着每个Segment独立扩容,互不影响,不存在并发扩容的问题。但在JDK 8中,相当于只有1个Segment,当一个线程要扩容Node数组的时候,其他线程还要读写,因此处理过会更复杂。

4.代码实现上的区别:

sizeCtl:

多个线程的共享变量,是操作的控制标识符,它的作用不仅包括threshold的作用,在不同的地方有不同的值也有不同的用途。

-1代表正在初始化

-N 表示正在进行扩容操作。此时sizeCtl的高16位代表的是当前的容量(并不是数值等于容量大小) 低16位代表线程数 容量16的话计算rs = 32795 也就是 1000 0000 0001 1011 可以看出不同的容量对应不同rs值, rs << 16 的值为 11111111111111111111111111111111 10000000000110110000000000000000, 0-15位用于统计参与扩容的线程数, 16-31位用于代表扩容时容器的大小。

正数或0代表hash表还没有被初始化,这个数值表示初始化或下一次进行扩容的大小,这一点类似于扩容阈值的概念。后面可以看到,它的值始终是当前ConcurrentHashMap容量的0.75倍,这与loadfactor是对应的。

MOVED,TREEBIN,RESERVED :

MOVED,TREEBIN,RESERVED是用来表示特殊节点的哈希值。该类特殊节点均不含实际元素,且其哈希值被设置为负数和普通节点区分。


//    ForwardingNode标记节点的hash值(表示正在扩容)

static final int MOVED     = -1; // hash for forwarding nodes

// TreeBin节点的hash值,它是对应桶的根节点

static final int TREEBIN   = -2; // hash for roots of trees

static final int RESERVED  = -3; // hash for transient reservations

声明: 本文由入驻维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。

发表评论

0条评论,0人参与

请输入评论内容...

请输入评论/评论长度6~500个字

您提交的评论过于频繁,请输入验证码继续

暂无评论

暂无评论

文章纠错
x
*文字标题:
*纠错内容:
联系邮箱:
*验 证 码:

粤公网安备 44030502002758号