最后判断除了staleSlot以外,还发现了其他过期的slot数据,就要开启清理数据的逻辑:
if (slotToExpunge != staleSlot)cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
ThreadLocalMap过期key的探测式清理流程
上面我们有提及ThreadLocalMap的两种过期key数据清理方式:探测式清理和启发式清理。
我们先讲下探测式清理,也就是expungeStaleEntry方法,遍历散列数组,从开始位置向后探测清理过期数据,将过期数据的Entry设置为null,沿途中碰到未过期的数据则将此数据rehash后重新在table数组中定位,如果定位的位置已经有了数据,则会将未过期的数据放到最靠近此位置的Entry=null的桶中,使rehash后的Entry数据距离正确的桶的位置更近一些。操作逻辑如下:
YuH2OU.png如上图,set(27) 经过hash计算后应该落到index=4的桶中,由于index=4桶已经有了数据,所以往后迭代最终数据放入到index=7的桶中,放入后一段时间后index=5中的Entry数据key变为了null
YuHb6K.png如果再有其他数据set到map中,就会触发探测式清理操作。
如上图,执行探测式清理后,index=5的数据被清理掉,继续往后迭代,到index=7的元素时,经过rehash后发现该元素正确的index=4,而此位置已经已经有了数据,往后查找离index=4最近的Entry=null的节点(刚被探测式清理掉的数据:index=5),找到后移动index= 7的数据到index=5中,此时桶的位置离正确的位置index=4更近了。
经过一轮探测式清理后,key过期的数据会被清理掉,没过期的数据经过rehash重定位后所处的桶位置理论上更接近i= key.hashCode & (tab.len - 1)的位置。这种优化会提高整个散列表查询性能。
接着看下expungeStaleEntry()具体流程,我们还是以先原理图后源码讲解的方式来一步步梳理:
Yuf301.png我们假设expungeStaleEntry(3) 来调用此方法,如上图所示,我们可以看到ThreadLocalMap中table的数据情况,接着执行清理操作:
YufupF.png第一步是清空当前staleSlot位置的数据,index=3位置的Entry变成了null。然后接着往后探测:
YufAwq.png执行完第二步后,index=4的元素挪到index=3的槽位中。
继续往后迭代检查,碰到正常数据,计算该数据位置是否偏移,如果被偏移,则重新计算slot位置,目的是让正常数据尽可能存放在正确位置或离正确位置更近的位置
YuWjTP.png在往后迭代的过程中碰到空的槽位,终止探测,这样一轮探测式清理工作就完成了,接着我们继续看看具体实现源代码:
private int expungeStaleEntry(int staleSlot) {Entry[] tab = table;
int len = tab.length;
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;
Entry e;
int i;
for (i = nextIndex(staleSlot, len);
(e = tab[i]) != null;
i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
if (k == null) {
e.value = null;
tab[i] = null;
size--;
} else {
int h = k.threadLocalHashCode & (len - 1);
if (h != i) {
tab[i] = null;
while (tab[h] != null)
h = nextIndex(h, len);
tab[h] = e;
}
}
}
return i;
}