HashMap中解决冲突的方法是在数组上构造一个链表结构,冲突的数据挂载到链表上,如果链表长度超过一定数量则会转化成红黑树。
而ThreadLocalMap中并没有链表结构,所以这里不能适用HashMap解决冲突的方式了。
Ynzr5D.png如上图所示,如果我们插入一个value=27的数据,通过hash计算后应该落入第4个槽位中,而槽位4已经有了Entry数据。
此时就会线性向后查找,一直找到Entry为null的槽位才会停止查找,将当前元素放入此槽位中。当然迭代过程中还有其他的情况,比如遇到了Entry不为null且key值相等的情况,还有Entry中的key值为null的情况等等都会有不同的处理,后面会一一详细讲解。
这里还画了一个Entry中的key为null的数据(Entry=2的灰色块数据),因为key值是弱引用类型,所以会有这种数据存在。在set过程中,如果遇到了key过期的Entry数据,实际上是会进行一轮探测式清理操作的,具体操作方式后面会讲到。
ThreadLocalMap.set()详解 ThreadLocalMap.set()原理图解看完了ThreadLocal hash算法后,我们再来看set是如何实现的。
往ThreadLocalMap中set数据(新增或者更新数据)分为好几种情况,针对不同的情况我们画图来说说明。
第一种情况: 通过hash计算后的槽位对应的Entry数据为空:
YuSniD.png这里直接将数据放到该槽位即可。
第二种情况: 槽位数据不为空,key值与当前ThreadLocal通过hash计算获取的key值一致:
image.png这里直接更新该槽位的数据。
第三种情况: 槽位数据不为空,往后遍历过程中,在找到Entry为null的槽位之前,没有遇到key过期的Entry:
image.png遍历散列数组,线性往后查找,如果找到Entry为null的槽位,则将数据放入该槽位中,或者往后遍历过程中,遇到了key值相等的数据,直接更新即可。
第四种情况: 槽位数据不为空,往后遍历过程中,在找到Entry为null的槽位之前,遇到key过期的Entry,如下图,往后遍历过程中,一到了index=7的槽位数据Entry的key=null:
Yu77qg.png散列数组下标为7位置对应的Entry数据key为null,表明此数据key值已经被垃圾回收掉了,此时就会执行replaceStaleEntry()方法,该方法含义是替换过期数据的逻辑,以index=7位起点开始遍历,进行探测式数据清理工作。
初始化探测式清理过期数据扫描的开始位置:slotToExpunge = staleSlot = 7
以当前staleSlot开始 向前迭代查找,找其他过期的数据,然后更新过期数据起始扫描下标slotToExpunge。for循环迭代,直到碰到Entry为null结束。
如果找到了过期的数据,继续向前迭代,直到遇到Entry=null的槽位才停止迭代,如下图所示,slotToExpunge被更新为0:
YuHSMT.png以当前节点(index=7)向前迭代,检测是否有过期的Entry数据,如果有则更新slotToExpunge值。碰到null则结束探测。以上图为例slotToExpunge被更新为0。
上面向前迭代的操作是为了更新探测清理过期数据的起始下标slotToExpunge的值,这个值在后面会讲解,它是用来判断当前过期槽位staleSlot之前是否还有过期元素。
接着开始以staleSlot位置(index=7)向后迭代,如果找到了相同key值的Entry数据:
YuHEJ1.png