Analysis of ConcurrentHashMap: get remove
- 2021-09-12 01:12:33
- OfStack
The previous articles analyzed the put method of concurrent HashMap and its related methods, transfer method, so the next article will be less difficult than the previous articles.
This article introduces
ConcurrentHashMap
Adj.
get方
Method and remove method.
1. get method
get
Method: Get the element, according to the target key bucket where the first element is different to get the element in different ways, the key point lies in the override of find () method.
public V get(Object key) {
// tab 引用map.table
// e 当前元素(用于循环遍历)
// p 目标节点
// n table数组长度
// eh 当前元素hash
// ek 当前元素key
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 根据key.hashCode()计算hash: 扰动运算后得到得到更散列的hash值
int h = spread(key.hashCode());
java // --------------------------------------------------------------------------------
// CASE1:
// 如果元素所在的桶存在且里面有元素
// 条件1：(tab = table) != null
// true -> 表示已经put过数据，并且map内部的table也已经初始化完毕
// false -> 表示创建完map后，并没有put过数据，map内部的table是延迟初始化的，只有第1次写数据时会触发初始化创建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) {
// 进入if代码块内部的前置条件：当前桶位有数据
java // 如果第1个元素就是要找的元素，则直接返回
// 对比头结点hash与查询key的hash是否1致
// 条件成立：说明头结点与查询Key的hash值完全1致
if ((eh = e.hash) == h) {
// 完全比对 查询key 和 头结点的key
// 条件成立：说明头结点就是查询数据
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
// 当e的hash值以及e对应的key都匹配目标元素时，则找到了，直接返回~
return e.val;
}
java // --------------------------------------------------------------------------------
// CASE2: eh < 0
// 条件成立：即，hash小于0 分2种情况，是树或者正在扩容,需要借助find方法寻找元素，find的寻找方式依据Node的不同子类有不同的实现方式:
// 情况1：eh=-1 是fwd结点 -> 说明当前table正在扩容，且当前查询的这个桶位的数据已经被迁移走了，需要借助fwd结点的内部方法find去查询
// 情况2：eh=-2 是TreeBin节点 -> 需要使用TreeBin 提供的find方法查询。
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
java // --------------------------------------------------------------------------------
// CASE3: 前提条件 -> CASE1和CASE2条件不满足！
// 说明是当前桶位已经形成链表的这种情况: 遍历整个链表寻找元素
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
java }
return null;
}
1.1 ForwardingNode Inner Class (FWD Node)
In
get
Method
CASE2
In,
eh < 0
Will be divided into two situations:
Situation 1:
eh=-1
It's the fwd node--
>
It shows that the current table is expanding, and the data of this bucket has been migrated, so it is necessary to query with the help of the internal method find of fwd node.
Situation 2:
eh = -2
Is the TreeBin node--
>
You need to use the find method provided by TreeBin to query.
Let's analyze case 1, that is, the fwd node is in the current bucket. Let's analyze the inner class FWD under 1 and its inner find method:
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;
}
java // fwd Nodal find Methods:
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
// tab 1 Definitely not empty: the whole ConcurrentHashMap In the source code, only 1 Local instantiation ForwardingNode , that is, in transfer In the Migrate Data method: ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); When the data of a bucket is processed, set the bucket to fwd Node, other writing threads or reading threads will have different logic after seeing it)
Node<K,V>[] tab = nextTable;
java // ------------------------------------------------------------------------------
// Spin 1
outer: for (;;) {
// n Represents the length of a new table created for expansion
// e Represents the bucket header node obtained by using addressing algorithm when creating a new table for expansion
Node<K,V> e; int n;
java // Condition 1 : Never hold water
// Condition 2 : Never hold water
// Condition 3 : Never hold water
// Condition 4 Rerouting in New Expansion Table hash Corresponding head node
// true -> 1. In oldTable Before migration, the corresponding bucket in is null
// false -> 2. After the expansion is completed, there are other write threads, and set this bucket bit to null
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
java // ---------------------------------------------------------------------------
// Spin 2
// Precondition: Table correspondence after expansion hash Barrel position of 1 Definitely not null , e Head node for this bucket
// e What might be node Type?
// 1.node Type
// 2.TreeBin Type
// 3.FWD Type
for (;;) {
// eh The of the current node of the specified bucket in the newly expanded table hash
// ek The of the current node of the specified bucket in the newly expanded table key
int eh; K ek;
// CASE1 Condition holds: Explain the data in the new expanded table and the current hit bucket position, that is, the desired data for query.
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
// Directly put e Return ~
return e;
java // CASE2: eh < 0 Hour
// 1.TreeBin Type
// 2.FWD Type (the newly expanded table, in the case of large concurrency, may be obtained again in this method FWD Type), that is, expansion may have occurred again
if (eh < 0) {
// Determine whether it is FWD Node
if (e instanceof ForwardingNode) {
// Yes FWD Node
tab = ((ForwardingNode<K,V>)e).nextTable;
// Jump to spin 1
continue outer;
}
else// No FWD Node
// Explain this bucket position For TreeBin Node, using the TreeBin.find Find the corresponding node in the red-black tree.
return e.find(h, k);
}
java // Precondition: Current bucket head node The query was not hit, indicating that this bucket is a linked list
// 1. Points the current element to the bottom of the linked list 1 Elements
// 2. Determines the following of the current element 1 Whether the positions are empty
// true -> Explain that iterating to the end of the linked list, no corresponding data is found, and return Null
if ((e = e.next) == null)
return null;
}
}
}
}
Subsection:
(1) hash to the bucket where the element is located;
(2) If the first element in the bucket is the element to be found, return directly;
(3) If it is a tree or an element is being migrated, call the find () method of each Node subclass to find the element;
(4) If it is a linked list, traverse the whole linked list to find elements;
(5) The fetched element is not locked;
2. remove method
remove method: Delete elements and add elements like 1, are to find the element in the bucket first, and then use the idea of segmented lock to lock the entire bucket, and then operate.
public V remove(Object key) {
// 调用替换节点方法
return replaceNode(key, null, null);
}
java/**
* 结点替换：
* 参数1：Object key -> 就表示当前结点的key
* 参数2：V value -> 要替换的目标值
* 参数3：Object cv（compare Value） ->
* 如果cv不为null，则需要既比对key，还要比对cv，这样个参数都1致，才能替换成目标值
*/
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;
java // ----------------------------------------------------------------------------
// CASE1：
// 条件1：tab == null
// true -> 表示当前map.table尚未初始化..
// false -> 表示当前map.table已经初始化
// 条件2：(n = tab.length) == 0
// true -> 表示当前map.table尚未初始化..
// false -> 已经初始化
// 条件3：(f = tabAt(tab, i = (n - 1) & hash)) == null
// true -> 表示命中桶位中为null，直接break
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
// 如果目标key所在的桶不存在，跳出循环返回null
break;
java // ----------------------------------------------------------------------------
// CASE2：
// 前置条件CASE2 ~ CASE3：当前桶位不是null
// 条件成立：fwd结点，说明当前table正在扩容中，当前是个写操作，所以当前线程需要协助table完成扩容。
else if ((fh = f.hash) == MOVED)
// 如果正在扩容中，则协助扩容
tab = helpTransfer(tab, f);
java // ----------------------------------------------------------------------------
// CASE3:
// 前置条件CASE2 ~ CASE3：当前桶位不是null
// 当前桶位是1个有数据的桶位，桶中可能是 "链表"也可能是"红黑树"TreeBin
else {
// 保留替换之前的数据引用
V oldVal = null;
// 校验标记,在下面的CASEn中的if判断使用：标记是否处理过
boolean validated = false;
// 加锁当前桶位头结点，加锁成功之后会进入代码块。
synchronized (f) {
// 判断sync加锁是否为当前桶位头节点，防止其它线程，在当前线程加锁成功之前，修改过桶位 的头结点，导致锁错对象！
java // --------------------------------------------------------------------
// CASE4: tabAt(tab, i) == f 再次验证当前桶第1个元素是否被修改过
// 条件成立：说明当前桶位头结点仍然为f，其它线程没修改过！
if (tabAt(tab, i) == f) {
// --------------------------------------------------------------------
// CASE5: fh >= 0
// 条件成立：说明桶位为链表或者单个node
if (fh >= 0) {
// 校验标记置为true
validated = true;
java // e 表示当前循环处理结点
// pred 表示当前循环节点的上1个节点
Node<K,V> e = f, pred = null;
// 遍历链表寻找目标节点
for (;;) {
// 表示当前节点key
K ek;
java // ------------------------------------------------------------
// CASE6:
// 条件1：e.hash == hash
// true->说明当前节点的hash与查找节点hash1致
// 条件2：((ek = e.key) == key || (ek != null && key.equals(ek)))
// CASE6的if条件成立，说明key 与查询的key完全1致。
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 找到了目标节点：当前节点的value，
V ev = e.val;
java // -----------------------------------------------------
// CASE7: 检查目标节点旧value是否等于cv
// 条件1：cv == null
// true -> 替换的值为null那么就是1个删除操作
// 条件2：cv == ev || (ev != null && cv.equals(ev))
// true -> 那么是1个替换操作
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
// 删除 或者 替换
// 将当前节点的值 赋值给 oldVal 后续返回会用到~
oldVal = ev;
java // 目标value不等于null
// 如果条件成立：说明当前是1个替换操作
if (value != null)
// 直接替换
e.val = value;
// 条件成立：说明当前节点非头结点
else if (pred != null)
// 如果前置节点不为空，删除当前节点：
// 让当前节点的上1个节点，指向当前节点的下1个节点。
pred.next = e.next;
// 条件成里：说明当前节点即为头结点
else
// 如果前置节点为空，说明是桶中第1个元素，删除之：
// 只需要将桶位设置为头结点的下1个节点。
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
// 遍历到链表尾部还没找到元素，跳出循环
if ((e = e.next) == null)
break;
}
}
java // --------------------------------------------------------------------
// CASE8: f instanceof TreeBin
// 条件成立：TreeBin节点。
else if (f instanceof TreeBin) {
// 校验标记置为true
validated = true;
java // 转换为实际类型 TreeBin t
TreeBin<K,V> t = (TreeBin<K,V>)f;
// r 表示 红黑树根节点
// p 表示 红黑树中查找到对应key 1致的node
TreeNode<K,V> r, p;
java // 遍历树找到了目标节点：
// 条件1：(r = t.root) != null 理论上是成立
// 条件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;
java // 检查目标节点旧value是否等于cv：
// 条件1：cv == null 成立：不必对比value，就做替换或者删除操作
// 条件2：cv == pv ||(pv != null && cv.equals(pv)) 成立：说明“对比值”与当前p节点的值 1致
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
// 替换或者删除操作
oldVal = pv;
java // 如果value不为空则替换旧值
// 条件成立：替换操作
if (value != null)
p.val = value;
java // 如果value为空则删除元素
// 删除操作
else if (t.removeTreeNode(p))
// 如果删除后树的元素个数较少则退化成链表
// t.removeTreeNode(p)这个方法返回true表示删除节点后树的元素个数较少
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// ----------------------------------------------------------------------------
// CASEn: 如果处理过，不管有没有找到元素都返回
// 当其他线程修改过桶位头结点时，当前线程 sync 头结点 锁错对象时，validated 为false，会进入下次for自旋:
if (validated) {
// 如果找到了元素，返回其旧值
if (oldVal != null) {
// 替换的值 为null，说明当前是1次删除操作，oldVal ！=null 成立，说明删除成功，更新当前元素个数计数器。
// 如果要替换的值为空，元素个数减1
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
java // 没找到元素返回空
return null;
}
Subsection:
(1) Calculate hash;
(2) If the bucket does not exist, it means that the target element has not been found and returns;
(3) If expansion is under way, assist in deleting after expansion is completed;
(4) If it is stored in the form of linked list, traverse the whole linked list to find elements and delete them after finding them;
(5) If it is stored in the form of a tree, traverse the tree to find elements and delete them after finding them;
(6) If it is stored in the form of a tree, the tree is smaller after deleting elements, and it degenerates into a linked list;
(7) If the element is deleted, the number of map elements is reduced by 1, and the old value is returned;
(8) If no element is deleted, null is returned;
At the end of this article, most of the knowledge points of ConcurrentHashMap are analyzed, and the following article finally analyzes TreeBin!