前面几篇文章分析了并发HashMap的put方法及其相关方法,transfer方法,那么接下来本篇文章相对之前几篇难度会小一些。
本篇文章介绍ConcurrentHashMap
的get方
法和remove方法。
1、get方法
get
方法:获取元素,根据目标key所在桶的第一个元素的不同采用不同的方式获取元素,关键点在于find()方法的重写。
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:
// 如果元素所在的桶存在且里面有元素
// 条件一:(tab = table) != null
// true -> 表示已经put过数据,并且map内部的table也已经初始化完毕
// false -> 表示创建完map后,并没有put过数据,map内部的table是延迟初始化的,只有第一次写数据时会触发初始化创建table逻辑
// 条件二:(n = tab.length) > 0 如果为 true-> 表示table已经初始化
// 条件三:(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 // 如果第一个元素就是要找的元素,则直接返回
// 对比头结点hash与查询key的hash是否一致
// 条件成立:说明头结点与查询Key的hash值完全一致
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的不同子类有不同的实现方式:
// 情况一:eh=-1 是fwd结点 -> 说明当前table正在扩容,且当前查询的这个桶位的数据已经被迁移走了,需要借助fwd结点的内部方法find去查询
// 情况二: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 内部类(FWD结点)
在get
方法CASE2
中,eh < 0
会分2中情况:
情况一:eh=-1
是fwd结点 -> 说明当前table正在扩容,且当前查询的这个桶位的数据已经被迁移走了,需要借助fwd结点的内部方法find去查询。
情况二:eh = -2
是TreeBin节点 -> 需要使用TreeBin 提供的find方法查询。
下面就分析一下情况一,即当前桶位中是fwd结点。我们来分析一下FWD这个内部类,以及其内部的find方法:
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结点的find方法:
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
// tab 一定不为空:整个ConcurrentHashMap源码中,只有一个地方实例化ForwardingNode,就是在transfer迁移数据方法中执行了:ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);(当某个桶位数据处理完毕后,将此桶位设置为fwd节点,其它写线程或读线程看到后,会有不同逻辑)
Node<K,V>[] tab = nextTable;
java // ------------------------------------------------------------------------------
// 自旋1
outer: for (;;) {
// n 表示为扩容而创建的新表的长度
// e 表示在扩容而创建新表时,使用寻址算法得到的桶位头结点
Node<K,V> e; int n;
java // 条件一:永远不成立
// 条件二:永远不成立
// 条件三:永远不成立
// 条件四:在新扩容表中重新路由定位 hash 对应的头结点
// true -> 1.在oldTable中对应的桶位在迁移之前就是null
// false -> 2.扩容完成后,有其它写线程,将此桶位设置为了null
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
java // ---------------------------------------------------------------------------
// 自旋2
// 前置条件:扩容后的表对应hash的桶位一定不是null,e为此桶位的头结点
// e可能为哪些node类型?
// 1.node 类型
// 2.TreeBin 类型
// 3.FWD类型
for (;;) {
// eh 新扩容后表指定桶位的当前节点的hash
// ek 新扩容后表指定桶位的当前节点的key
int eh; K ek;
// CASE1条件成立:说明新扩容后的表,当前命中桶位中的数据,即为查询想要数据。
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
// 直接将e返回~
return e;
java // CASE2: eh < 0 时
// 1.TreeBin 类型
// 2.FWD类型(新扩容的表,在并发很大的情况下,可能在此方法再次拿到FWD类型),即可能又发生了扩容
if (eh < 0) {
// 判断是否是FWD结点
if (e instanceof ForwardingNode) {
// 是FWD结点
tab = ((ForwardingNode<K,V>)e).nextTable;
// 跳转到自旋1
continue outer;
}
else// 不是FWD结点
// 说明此桶位 为 TreeBin 节点,使用TreeBin.find 查找红黑树中相应节点。
return e.find(h, k);
}
java // 前置条件:当前桶位头结点 并没有命中查询,说明此桶位是链表
// 1.将当前元素指向链表的下一个元素
// 2.判断当前元素的下一个位置是否为空
// true -> 说明迭代到链表末尾,未找到对应的数据,返回Null
if ((e = e.next) == null)
return null;
}
}
}
}
小节:
(1)hash到元素所在的桶;
(2)如果桶中第一个元素就是该找的元素,直接返回;
(3)如果是树或者正在迁移元素,则调用各自Node子类的find()方法寻找元素;
(4)如果是链表,遍历整个链表寻找元素;
(5)获取元素没有加锁;
2、remove方法
remove方法:删除元素跟添加元素一样,都是先找到元素所在的桶,然后采用分段锁的思想锁住整个桶,再进行操作。
public V remove(Object key) {
// 调用替换节点方法
return replaceNode(key, null, null);
}
java
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:
// 条件一:tab == null
// true -> 表示当前map.table尚未初始化..
// false -> 表示当前map.table已经初始化
// 条件二:(n = tab.length) == 0
// true -> 表示当前map.table尚未初始化..
// false -> 已经初始化
// 条件三:(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
// 当前桶位是一个有数据的桶位,桶中可能是 "链表"也可能是"红黑树"TreeBin
else {
// 保留替换之前的数据引用
V oldVal = null;
// 校验标记,在下面的CASEn中的if判断使用:标记是否处理过
boolean validated = false;
// 加锁当前桶位头结点,加锁成功之后会进入代码块。
synchronized (f) {
// 判断sync加锁是否为当前桶位头节点,防止其它线程,在当前线程加锁成功之前,修改过桶位 的头结点,导致锁错对象!
java // --------------------------------------------------------------------
// CASE4: tabAt(tab, i) == f 再次验证当前桶第一个元素是否被修改过
// 条件成立:说明当前桶位头结点仍然为f,其它线程没修改过!
if (tabAt(tab, i) == f) {
// --------------------------------------------------------------------
// CASE5: fh >= 0
// 条件成立:说明桶位为链表或者单个node
if (fh >= 0) {
// 校验标记置为true
validated = true;
java // e 表示当前循环处理结点
// pred 表示当前循环节点的上一个节点
Node<K,V> e = f, pred = null;
// 遍历链表寻找目标节点
for (;;) {
// 表示当前节点key
K ek;
java // ------------------------------------------------------------
// CASE6:
// 条件一:e.hash == hash
// true->说明当前节点的hash与查找节点hash一致
// 条件二:((ek = e.key) == key || (ek != null && key.equals(ek)))
// CASE6的if条件成立,说明key 与查询的key完全一致。
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 找到了目标节点:当前节点的value,
V ev = e.val;
java // -----------------------------------------------------
// CASE7: 检查目标节点旧value是否等于cv
// 条件一:cv == null
// true -> 替换的值为null那么就是一个删除操作
// 条件二:cv == ev || (ev != null && cv.equals(ev))
// true -> 那么是一个替换操作
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
// 删除 或者 替换
// 将当前节点的值 赋值给 oldVal 后续返回会用到~
oldVal = ev;
java // 目标value不等于null
// 如果条件成立:说明当前是一个替换操作
if (value != null)
// 直接替换
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;
}
}
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 一致的node
TreeNode<K,V> r, p;
java // 遍历树找到了目标节点:
// 条件一:(r = t.root) != null 理论上是成立
// 条件二: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:
// 条件一:cv == null 成立:不必对比value,就做替换或者删除操作
// 条件二:cv == pv ||(pv != null && cv.equals(pv)) 成立:说明“对比值”与当前p节点的值 一致
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,说明当前是一次删除操作,oldVal !=null 成立,说明删除成功,更新当前元素个数计数器。
// 如果要替换的值为空,元素个数减1
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
java // 没找到元素返回空
return null;
}
小节:
(1)计算hash;
(2)如果所在的桶不存在,表示没有找到目标元素,返回;
(3)如果正在扩容,则协助扩容完成后再进行删除操作;
(4)如果是以链表形式存储的,则遍历整个链表查找元素,找到之后再删除;
(5)如果是以树形式存储的,则遍历树查找元素,找到之后再删除;
(6)如果是以树形式存储的,删除元素之后树较小,则退化成链表;
(7)如果确实删除了元素,则整个map元素个数减1,并返回旧值;
(8)如果没有删除元素,则返回null;
本篇文章结束,ConcurrentHashMap的大部分知识点分析完毕,下面一篇文章最后再分析一下TreeBin就收尾了!