-
ConcurrentHashMap源码解析 5.get() & remove() 方法
ConcurrentHashMap—get() & remove() 方法
get()
get()方法：获取元素，根据目标 key 所在桶的第一个元素的不同采用不同的方式获取元素，关键点在于find()方法的重写。
流程总结
- 计算 key 的 hash 值寻址到指定桶位。
- 当前桶位没有元素直接返回 null。
- 当前桶位如果是 fwd 节点或者是红黑树节点，则调用各自的
find()方法。 - 当前桶位不是 fwd 节点也不是红黑树节点，则说明当前为链表，遍历桶位，进行查找。
- 查找元素
没有任何的加锁操作。
源码解析
/* * 根据key进行查找获取value值 */ public V get(Object key) { /* * tab 引用table * e 当前元素 * p 目标元素 * n table数组长度 * eh 当前元素hash * ek 当前元素key */ Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // 扰动运算后得到 更散列的hash值 int h = spread(key.hashCode()); /* * 进入if语句内部的条件： * 条件1：(tab = table) != null * true->表示已经put过数据，并且map内部的table也已经初始化完毕 * false->表示创建完map后，并没有put过数据，map内部的table是延迟初始化的，只有第一次写数据时会触发创建逻辑 * 条件2：(n = tab.length) > 0 true->表示table已经初始化 * 条件3：(e = tabAt(tab, (n - 1) & h)) != null * true->当前key寻址的桶位 有值 * false->当前key寻址的桶位中是null，是null直接返回null */ if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 前置条件：当前桶位有数据 /* * 对比与头结点的key是否完全一致 * 1.比较key的hash值是否一致8 * 2.比较key的内存地址是否一致 或 进行equals的返回true * 同时满足这两个条件才能认为key完全一致 */ if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) // 完全一致 直接返回value return e.val; } /* * hash值小于0，有两种情况： * 1.hash = -1，表示当前桶位是FWD节点，表示当前桶位中的节点已经被迁移了 * 2.hash = -2, 表示当前桶位是TreeBin节点 * 如果是FWD节点的话，会进入对应的FWD中定义的find方法进行查找 * 如果是红黑树会进入TreeNode内部的find方法进行查找(多态) */ else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; // 当前桶位是一个链表，直接遍历每一个节点找到一个key完全相同的节点 返回value即可 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
ForwardingNode 的 find() 方法
上面在调用 get() 方法进行查找的时候，如果查找到当前桶位的节点的 hash 值为 -1，说明当前桶位的可能是 fwd 节点或者是红黑树节点，就要到指定的结构中去查找，这里我们分析一下当 hash 值为 -1 时，去 ForwardingNode 节点查找的方法，关于去红黑树中查找的源码解析，放到后续的 TreeBin 的源码解析中讲解。
流程总结
- 直接去 nextTable 中查询数据，经过寻址算法后发现当前桶位没有元素。
- 可能原桶位中的元素都是经过扩容后都是高 (低) 位，而当前寻址得到的桶位刚好相反。
- 如果发现当前桶位还是 fwd 节点 (可能高并发下又发生了扩容) 那么继续去新表查询。
- 如果发现当前桶位是红黑树，那么调用红黑树的 find 方法去查询。
- 否则当前是链表，遍历链表查询即可。
find()方法没有加锁过程。
Node<K,V> find(int h, Object k) { // 自旋 // outer：最外层的循环标签 /* * tab一定不为null * 整个ConcurrentHashMap源码中，只有一个地方实例化ForwardingNode， * 就是在transfer迁移数据方法中执行了：ForwardingNode- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
remove()
流程总结
- remove 底层调用的是 replaceNode 方法，传入的后两个参数都是 null，表示当前的替换操作是删除。
- 计算 hash 值，自旋去尝试删除。
- 寻址后桶位上没有元素，返回 null。
- 桶位上是链表，则遍历链表查找元素进行删除。
- 桶位上是 fwd 节点，表示正在扩容，先尝试帮助扩容，然后继续循环尝试删除。
- 桶位上形成了红黑树，遍历树查找元素，然后删除，删除后树中元素节点数较少，则
退化为链表。 - 如果确实删除了元素 (非value替换)，调用 addCount() 将元素个数 -1。
- 如果没有删除元素，则返回 null。
- 删除过程加锁
(sycnhronized)锁定当前桶位的头结点。
源码解析
public V remove(Object key) { //调用了替换节点的方法 return replaceNode(key, null, null); } || || \/ /* * @param Object key -> 表示要替换的key * @param V value -> 要替换的目标值(从remove方法调用的value为null，即将值替换为null，就是删除该节点) * @param Object cv(compare value) -> 如果cv不为null，则需要既对比key还要对比cv，这两个参数都一致，才能替换目标值 */ final V replaceNode(Object key, V value, Object cv) { // 计算key经过扰动运算的hash int hash = spread(key.hashCode()); // 自旋 for (Node<K,V>[] tab = table;;) { /* * f 表示桶位头节点 * n 表示table长度 * i 表示hash寻址后命中的下标 * fh 表示桶位头节点的hash值 */ Node<K,V> f; int n, i, fh; /* * CASE1： * 如果table为null，或者当前寻址后命中的桶位没有元素，直接break循环 */ if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null) break; /* * CASE2： * 前置条件：当前桶位不是null * 当前桶位是fwd节点，说明当前table正在扩容中，由于当前是写操作，需要尝试帮助table扩容 */ else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); /* * CASE3： * 前置条件：当前桶位不是null * 当前桶位是链表或者红黑树 */ else { // 保留替换之前的value V oldVal = null; // 校验标记：用于判断是否锁错对象，从而进入下一次的自旋 boolean validated = false; // 锁定当前桶位的头结点(分段锁思想) synchronized (f) { // 判断sync锁定的对象是否是当前桶位头节点，防止当前线程加锁之前，其他线程修改过桶位的头节点 if (tabAt(tab, i) == f) { // 哈希值大于0，说明桶位为正常的Node节点(或者Node链表) if (fh >= 0) { // validated赋值为true validated = true; // 自旋 /* * e 表示当前循环的元素 * pred 表示上一个元素 */ for (Node<K,V> e = f, pred = null;;) { // 当前桶位的key K ek; // 找到了指定key if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { // 将找到的指定节点的val赋值给ev V ev = e.val; /* * cv == null -> true 表示这是一个删除操作 * cv == ev -> true 表示这是一个替换操作 */ if (cv == null || cv == ev || (ev != null && cv.equals(ev))) { // 进行删除 或者 替换操作 // 将当前节点的值 赋值给 oldVal 后续返回会用到 oldVal = ev; // 条件成立：说明当前是一个替换操作 if (value != null) // 直接将value替换 e.val = value; // 当前节点不是头结点，并且这是一次删除操作 else if (pred != null) // 直接在链表中将e删除即可 pred.next = e.next; // 说明e是头结点 else // 调用setTab方法将当前桶位设置为头结点的下一个节点(e.next)即可，变向的将e删除 setTabAt(tab, i, e.next); } break; } // 向后遍历 pred = e; // 遍历到链表尾部还没找到元素，跳出循环 if ((e = e.next) == null) break; } } // 这里是红黑树TreeBin节点 else if (f instanceof TreeBin) { // 修改标志位 validated = true; // 转换为指定的TreeBin节点 TreeBin<K,V> t = (TreeBin<K,V>)f; /* * r 表示红黑树根节点 * p 表示红黑树中查找到的对应的key一致的node */ TreeNode<K,V> r, p; /* * 条件1：(r = t.root) != null 理论上是成立 * (TreeBin一共有两个引用：1.root 引用红黑树结构 2.first 引用链表结构) * 条件2：TreeNode.findTreeNode 以当前节点为入口，向下查找key（包括本身节点） * true->说明查找到相应key 对应的node节点，会赋值给p */ if ((r = t.root) != null && // 在红黑树中找到了指定的节点 (p = r.findTreeNode(hash, key, null)) != null) { // 保存p.val到pv V pv = p.val; // 条件1：cv == null 成立：不比对value，就做替换或者删除操作 // 条件2：cv == pv ||(pv != null && cv.equals(pv)) 成立：说明“对比值”与当前p节点的值 一致 if (cv == null || cv == pv || (pv != null && cv.equals(pv))) { // 替换或删除操作 // 原值赋给oldVal oldVal = pv; // value不为null，替换 if (value != null) p.val = value; // 删除 else if (t.removeTreeNode(p)) /* * t.removeTreeNode(p)这个方法返回true表示删除节点后树的元素个数是否较少(boolean) * 如果删除后树的元素个数较少则退化成链表 */ setTabAt(tab, i, untreeify(t.first)); } } } } } /* * 当其他线程修改过桶位的头节点时，说明当前线程锁错了对象 * 此时validated为false，不会进入到下面的if的逻辑中终止，则会进入下次自旋 * * 如果此时validated为true，说明进入过锁的逻辑，并执行过删除/替换操作 * 然后判断是否真正的删除了节点，是的话则调用addCount()将元素数量-1，然后结束方法 */ if (validated) { // oldVal不为null，说明操作成功 if (oldVal != null) { // value == null 说明这是一次删除操作，更新节点个数(-1) if (value == null) addCount(-1L, -1); // 返回旧值 return oldVal; } break; } } } return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
参考
-
相关阅读:
小程序与uniapp如何进行传参
vvic API接口接入说明：解锁新一代数据可视化的无限可能
git 对比两个分支差异
面试中常问到的C++11的题目和答案
基于ssm阳光心理健康网站的设计与实现-计算机毕业设计源码+LW文档
Python怎么实现动态的方法调用？比如Ruby就有元编程
Qt学习总结之QTextEdit
四入进博会，优衣库围绕科技可持续演绎“服装进化论”
MAC地址、IP地址以及ARP协议详细讲解
【Python】Python 中实现数据序列化
- 原文地址：https://blog.csdn.net/weixin_53407527/article/details/127747924
