本章接着上两章, 链接直达:
死磕 java 集合之 ConcurrentHashMap 源码分析(一) https://mp.weixin.qq.com/s/rlyoQp4ngTX8mjGDJgJIRA
死磕 java 集合之 ConcurrentHashMap 源码分析(二) https://mp.weixin.qq.com/s/_Bf6XcH51lssC0mdF_oW9A
删除元素
删除元素跟添加元素一样, 都是先找到元素所在的桶, 然后采用分段锁的思想锁住整个桶, 再进行操作.
- 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 是线程安全的, 就认为它无论什么情况下都是线程安全的, 还是那句话尽信书不如无书.
这也正是我们读源码的目的之一, 了解其本质, 才能在我们的实际工作中少挖坑, 不论是挖给别人还是挖给自己 ^^.
死磕 java 集合之 ConcurrentHashMap 源码分析(三)
来源: http://www.bubuko.com/infodetail-3019086.html