死磕 java集合之ConcurrentHashMap源码分析(三)——内含彩蛋
本章接着上两章,链接直达:
死磕 java集合之ConcurrentHashMap源码分析(一)
死磕 java集合之ConcurrentHashMap源码分析(二)
删除元素
删除元素跟添加元素一样,都是先找到元素所在的桶,然后采用分段锁的思想锁住整个桶,再进行操作。
public V remove(Object key) { // 调用替换节点方法 return replaceNode(key, null, null); } final V replaceNode(Object key, V value, Object cv) { // 计算hash int hash = spread(key.hashCode()); // 自旋 for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null) // 如果目标key所在的桶不存在,跳出循环返回null break; else if ((fh = f.hash) == MOVED) // 如果正在扩容中,协助扩容 tab = helpTransfer(tab, f); else { V oldVal = null; // 标记是否处理过 boolean validated = false; synchronized (f) { // 再次验证当前桶第一个元素是否被修改过 if (tabAt(tab, i) == f) { if (fh >= 0) { // fh>=0表示是链表节点 validated = true; // 遍历链表寻找目标节点 for (Node<K,V> e = f, pred = null;;) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { // 找到了目标节点 V ev = e.val; // 检查目标节点旧value是否等于cv if (cv == null || cv == ev || (ev != null && cv.equals(ev))) { oldVal = ev; if (value != null) // 如果value不为空则替换旧值 e.val = value; else if (pred != null) // 如果前置节点不为空 // 删除当前节点 pred.next = e.next; else // 如果前置节点为空 // 说明是桶中第一个元素,删除之 setTabAt(tab, i, e.next); } break; } pred = e; // 遍历到链表尾部还没找到元素,跳出循环 if ((e = e.next) == null) break; } } else if (f instanceof TreeBin) { // 如果是树节点 validated = true; TreeBin<K,V> t = (TreeBin<K,V>)f; TreeNode<K,V> r, p; // 遍历树找到了目标节点 if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) { V pv = p.val; // 检查目标节点旧value是否等于cv if (cv == null || cv == pv || (pv != null && cv.equals(pv))) { oldVal = pv; if (value != null) // 如果value不为空则替换旧值 p.val = value; else if (t.removeTreeNode(p)) // 如果value为空则删除元素 // 如果删除后树的元素个数较少则退化成链表 // t.removeTreeNode(p)这个方法返回true表示删除节点后树的元素个数较少 setTabAt(tab, i, untreeify(t.first)); } } } } } // 如果处理过,不管有没有找到元素都返回 if (validated) { // 如果找到了元素,返回其旧值 if (oldVal != null) { // 如果要替换的值为空,元素个数减1 if (value == null) addCount(-1L, -1); return oldVal; } break; } } } // 没找到元素返回空 return null; }
(1)计算hash;
(2)如果所在的桶不存在,表示没有找到目标元素,返回;
(3)如果正在扩容,则协助扩容完成后再进行删除操作;
(4)如果是以链表形式存储的,则遍历整个链表查找元素,找到之后再删除;
(5)如果是以树形式存储的,则遍历树查找元素,找到之后再删除;
(6)如果是以树形式存储的,删除元素之后树较小,则退化成链表;
(7)如果确实删除了元素,则整个map元素个数减1,并返回旧值;
(8)如果没有删除元素,则返回null;
获取元素
获取元素,根据目标key所在桶的第一个元素的不同采用不同的方式获取元素,关键点在于find()方法的重写。
public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // 计算hash int h = spread(key.hashCode()); // 如果元素所在的桶存在且里面有元素 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 如果第一个元素就是要找的元素,直接返回 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0) // hash小于0,说明是树或者正在扩容 // 使用find寻找元素,find的寻找方式依据Node的不同子类有不同的实现方式 return (p = e.find(h, key)) != null ? p.val : null; // 遍历整个链表寻找元素 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }
(1)hash到元素所在的桶;
(2)如果桶中第一个元素就是该找的元素,直接返回;
(3)如果是树或者正在迁移元素,则调用各自Node子类的find()方法寻找元素;
(4)如果是链表,遍历整个链表寻找元素;
(5)获取元素没有加锁;
获取元素个数
元素个数的存储也是采用分段的思想,获取元素个数时需要把所有段加起来。
public int size() { // 调用sumCount()计算元素个数 long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } final long sumCount() { // 计算CounterCell所有段及baseCount的数量之和 CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; }
(1)元素的个数依据不同的线程存在在不同的段里;(见addCounter()分析)
(2)计算CounterCell所有段及baseCount的数量之和;
(3)获取元素个数没有加锁;
总结
(1)ConcurrentHashMap是HashMap的线程安全版本;
(2)ConcurrentHashMap采用(数组 + 链表 + 红黑树)的结构存储元素;
(3)ConcurrentHashMap相比于同样线程安全的HashTable,效率要高很多;
(4)ConcurrentHashMap采用的锁有 synchronized,CAS,自旋锁,分段锁,volatile等;
(5)ConcurrentHashMap中没有threshold和loadFactor这两个字段,而是采用sizeCtl来控制;
(6)sizeCtl = -1,表示正在进行初始化;
(7)sizeCtl = 0,默认值,表示后续在真正初始化的时候使用默认容量;
(8)sizeCtl > 0,在初始化之前存储的是传入的容量,在初始化或扩容后存储的是下一次的扩容门槛;
(9)sizeCtl = (resizeStamp << 16) + (1 + nThreads),表示正在进行扩容,高位存储扩容邮戳,低位存储扩容线程数加1;
(10)更新操作时如果正在进行扩容,当前线程协助扩容;
(11)更新操作会采用synchronized锁住当前桶的第一个元素,这是分段锁的思想;
(12)整个扩容过程都是通过CAS控制sizeCtl这个字段来进行的,这很关键;
(13)迁移完元素的桶会放置一个ForwardingNode节点,以标识该桶迁移完毕;
(14)元素个数的存储也是采用的分段思想,类似于LongAdder的实现;
(15)元素个数的更新会把不同的线程hash到不同的段上,减少资源争用;
(16)元素个数的更新如果还是出现多个线程同时更新一个段,则会扩容段(CounterCell);
(17)获取元素个数是把所有的段(包括baseCount和CounterCell)相加起来得到的;
(18)查询操作是不会加锁的,所以ConcurrentHashMap不是强一致性的;
(19)ConcurrentHashMap中不能存储key或value为null的元素;
彩蛋——值得学习的技术
ConcurrentHashMap中有哪些值得学习的技术呢?
我认为有以下几点:
(1)CAS + 自旋,乐观锁的思想,减少线程上下文切换的时间;
(2)分段锁的思想,减少同一把锁争用带来的低效问题;
(3)CounterCell,分段存储元素个数,减少多线程同时更新一个字段带来的低效;
(4)@sun.misc.Contended(CounterCell上的注解),避免伪共享;(p.s.伪共享我们后面也会讲的^^)
(5)多线程协同进行扩容;
(6)你又学到了哪些呢?
彩蛋——不能解决的问题
ConcurrentHashMap不能解决什么问题呢?
请看下面的例子:
private static final Map<Integer, Integer> map = new ConcurrentHashMap<>(); public void unsafeUpdate(Integer key, Integer value) { Integer oldValue = map.get(key); if (oldValue == null) { map.put(key, value); } }
这里如果有多个线程同时调用unsafeUpdate()这个方法,ConcurrentHashMap还能保证线程安全吗?
答案是不能。因为get()之后if之前可能有其它线程已经put()了这个元素,这时候再put()就把那个线程put()的元素覆盖了。
那怎么修改呢?
答案也很简单,使用putIfAbsent()方法,它会保证元素不存在时才插入元素,如下:
public void safeUpdate(Integer key, Integer value) { map.putIfAbsent(key, value); }
那么,如果上面oldValue不是跟null比较,而是跟一个特定的值比如1进行比较怎么办?也就是下面这样:
public void unsafeUpdate(Integer key, Integer value) { Integer oldValue = map.get(key); if (oldValue == 1) { map.put(key, value); } }
这样的话就没办法使用putIfAbsent()方法了。
其实,ConcurrentHashMap还提供了另一个方法叫replace(K key, V oldValue, V newValue)可以解决这个问题。
replace(K key, V oldValue, V newValue)这个方法可不能乱用,如果传入的newValue是null,则会删除元素。
public void safeUpdate(Integer key, Integer value) { map.replace(key, 1, value); }
那么,如果if之后不是简单的put()操作,而是还有其它业务操作,之后才是put(),比如下面这样,这该怎么办呢?
public void unsafeUpdate(Integer key, Integer value) { Integer oldValue = map.get(key); if (oldValue == 1) { System.out.println(System.currentTimeMillis()); /** * 其它业务操作 */ System.out.println(System.currentTimeMillis()); map.put(key, value); } }
这时候就没办法使用ConcurrentHashMap提供的方法了,只能业务自己来保证线程安全了,比如下面这样:
public void safeUpdate(Integer key, Integer value) { synchronized (map) { Integer oldValue = map.get(key); if (oldValue == null) { System.out.println(System.currentTimeMillis()); /** * 其它业务操作 */ System.out.println(System.currentTimeMillis()); map.put(key, value); } } }
这样虽然不太友好,但是最起码能保证业务逻辑是正确的。
当然,这里使用ConcurrentHashMap的意义也就不大了,可以换成普通的HashMap了。
上面只是举一个简单的例子,我们不能听说ConcurrentHashMap是线程安全的,就认为它无论什么情况下都是线程安全的,还是那句话尽信书不如无书。
这也正是我们读源码的目的之一,了解其本质,才能在我们的实际工作中少挖坑,不论是挖给别人还是挖给自己^^。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
你为什么要使用前端框架Vue?
1.前端框架的根本意义 1.1 前端框架的好处 最开始学习前端框架的时候(我第一个框架是 React)并不理解框架能带来什么,只是因为大家都在用框架,最实际的一个用途就是所有企业几乎都在用框架,不用框架就 out 了. 随着使用的深入我逐渐理解到框架的好处: 1.组件化: 其中以 React 的组件化最为彻底,甚至可以到函数级别的原子组件,高度的组件化可以是我们的工程易于维护、易于组合拓展。 2.天然分层: JQuery 时代的代码大部分情况下是面条代码,耦合严重,现代框架不管是 MVC、MVP还是MVVM 模式都能帮助我们进行分层,代码解耦更易于读写。 3.生态: 现在主流前端框架都自带生态,不管是数据流管理架构还是 UI 库都有成熟的解决方案。 1.2 前端框架的根本意义 简单来说,前端框架的根本意义是解决了UI 与状态同步问题。 在 Vue 中我们如果要在todos中添加一条,只需要app4.todos.push({ text: '新项目' }),这时由于 Vue 内置的响应式系统会自动帮我们进行 UI 与状态的同步工作. <div id="app-4"> <o...
- 下一篇
kubernetes 使用NFS搭建动态存储卷(PV/SorageClass/PVC)
在日常学习测试kubernetes时,经常需要PersistentVolume把一些数据(例如:数据库、日志等)存储起来,不随着容器的删除而丢失;关于PV、PVC、StorageClass的关系参考PV/PVC/StorageClass;存储卷的实现有很多种,此处选择比较容易实现的NFS作为存储;参考了网上好多资料,但都是不太完整,按照资料上的说明操作都有问题,所以在参考了众多资料之后决定记录一下过程,以供各位参考。 环境: centos-7(3.10.0-957.5.1.el7.x86_64)(node1, node2) kubernetes v1.13.0 helm v2.12.0 安装环境 安装kubernetes、helm 参考资料,在node1、node2上安装kubernetes和helm; 安装NFS 在node1上安装NFS Server $ sudo yum -y install nfs-utils rpcbind 在服务端node1上配置共享目录 $ sudo mkdir /var/nfs $ sudo su //切换到root用户 $ echo "/var/nfs...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS8编译安装MySQL8.0.19
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS7,CentOS8安装Elasticsearch6.8.6
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库