深入细节ThreadLocalMap
原创
前面一篇文章ThreadLocal浅析，让我们大概了解其内部运行方式，不熟悉ThreadLocal的同学，在指教下面文章前建议看下，或多或少有点帮助。
这篇文章，我这里重点是了解下ThreadLocalMap。看下get、set、remove等方法内部实现
一、set
private void set(ThreadLocal<?> key, Object value) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);//计算当前key的hash值，也就是数组下标
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) { //这就话就是不断向下寻找非null的Entry。
ThreadLocal<?> k = e.get();
--------------------- 步骤一 --------------------
if (k == key) {//如果当前Entry的key正好就是当前ThreadLocal，则替换value值就好
e.value = value;
return;
}
--------------------- 步骤二 --------------------
if (k == null) { //Entry中key，即ThreadLocal是弱引用，很容易被回收key=null。
replaceStaleEntry(key, value, i); //替换Entry，清理无效Entry，整理Entry数字
return;
}
}
--------------------- 步骤三 --------------------
//如果Entry数组里，没有相同的key或key=null的Entry，那就新增Entry到Entry数组里。
tab[i] = new Entry(key, value);
int sz = ++size;
//清理无效Entry后，在看下当前Entry容量是否超过阀值，超过的话就要扩容。
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}1.threadLocalHashCode
看下 int i = key.threadLocalHashCode &(len-1);这句代码，粗看，这个有点像HashMap中hashcode获得方式。具体我们来看看源码
private final int threadLocalHashCode = nextHashCode();
private static AtomicInteger nextHashCode = new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}这里定义了一个AtomicInteger类型，每次获取threadLocalHashCode，nextHashCode当前值都要加上HASH_INCREMENT，HASH_INCREMENT=0x61c88647，是一个神奇的数字，让哈希码能均匀的分布在2的N次方的数组里，他为啥用这个数？我们看下& (len - 1) 这个 ，这是取模的一种方式，对于2的幂作为模数取模，用此代替%(2^n)，这也就是为啥用0x61c88647了。这样的话，key.threadLocalHashCode &(len-1)得出的值，也就是数组下标，就在【0～数组长度-1】之间，肯定在Entry[] table 数组长度值内。
2.nextIndex
看下nextIndex源码
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}这段就是取下一个下标index，如果下一个下标就最后一个下标，则从0下标开始。就是一个正向环形移位操作。
3.replaceStaleEntry
当Entry中的key即ThreadLocal，（Entry中的ThreadLocal是弱引用），在即被回收或其他情况，导致当前Entry的key=null，这个时候调用replaceStaleEntry方法，清理、替换无效Entry、整理Entry数组。这是ThreadLocalMap核心内容。
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
int staleSlot) {
Entry[] tab = table;
int len = tab.length;
Entry e;
int slotToExpunge = staleSlot;//staleSlot就是当前下标
for (int i = prevIndex(staleSlot, len); //从staleSlot下标开始，不断向前遍历Entry数组，
//找到key=null最小下标
(e = tab[i]) != null;
i = prevIndex(i, len))
if (e.get() == null)
slotToExpunge = i;
for (int i = nextIndex(staleSlot, len);
(e = tab[i]) != null;
i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
---------------------步骤1------------------------
if (k == key) {//从staleSlot下标开始往后找Entry，如果当前key和位置i的Entry key一样，那就交换value
e.value = value;
tab[i] = tab[staleSlot];
tab[staleSlot] = e;
if (slotToExpunge == staleSlot)//如果上面prevIndex过程没有找到key=null的Entry，
//则清理位置i的Entry
slotToExpunge = i;
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); //清理数据
return;
}
---------------------步骤2------------------------
if (k == null && slotToExpunge == staleSlot)
slotToExpunge = i;
}
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);
if (slotToExpunge != staleSlot)
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}4.prevIndex
看下prevIndex源码
private static int prevIndex(int i, int len) {
return ((i - 1 >= 0) ? i - 1 : len - 1);
}这个和nextIndex效果类似，只不过移位方向和nextIndex相反。
5.cleanSomeSlots
看下cleanSomeSlots源码
private boolean cleanSomeSlots(int i, int n) {
boolean removed = false;
Entry[] tab = table;
int len = tab.length;
do {
i = nextIndex(i, len);
Entry e = tab[i];
if (e != null && e.get() == null) {
n = len;
removed = true;
i = expungeStaleEntry(i);
}
} while ( (n >>>= 1) != 0);
return removed;
}大致意思是 遍历Entry数组，e !=null&& e.get()==null条件的Entry即无效Entry的位置下标，然后调用expungeStaleEntry清理数据
6.expungeStaleEntry
看下expungeStaleEntry源码
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
//清空位置staleSlot的Entry
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) { //从位置staleSlot开始，往后遇到key=null的就清理对应的Entry
//这里设置为null ,方便让GC 回收
e.value = null;
tab[i] = null;
size--;
} else {
int h = k.threadLocalHashCode & (len - 1);
//计算出来的索引 h，与其现在所在位置的索引 i 不一致，置空当前的table[i]
if (h != i) {
tab[i] = null;
//从h下标开始往后，遇到null的情况，则把当前Entry放在h位置，把非null的Entry放在前面
while (tab[h] != null)
h = nextIndex(h, len);
tab[h] = e;
}
}
}
return i;
}expungeStaleEntry ，大概意思是
从下标staleSlot开始，往后遍历直到遇到Entry是null【这个staleSlot就是key=null的下标位置或者向前遍历key=null的最小下标位置】
1.清空staleSlot位置的数据.
2.遇到key=null的Entry，则清空该Entry
3.如果当前Entry的key不是null，说明Entry有数据，计算其key的hash值和当前对应数组下标比较，一样的话就当没事，如果不一样，就要把该下标的Entry设为null，同时计算该key的hash值即下标，在该下标后面遇到为null的Entry，把当前的Entry放在此处即null的位置。为何要这么做？？
7.rehash
private void rehash() {
expungeStaleEntries();
if (size >= threshold - threshold / 4)
resize();
}rehash主要是两个步骤
1.expungeStaleEntries
private void expungeStaleEntries() {
Entry[] tab = table;
int len = tab.length;
for (int j = 0; j < len; j++) {
Entry e = tab[j];
if (e != null && e.get() == null)
expungeStaleEntry(j);
}
}里面调用expungeStaleEntry，还是清理、整理Entry数组
2.resize
如果当前size>= threshold - threshold /4，就走resize过程，也就是扩容过程。
private void resize() {
Entry[] oldTab = table;
int oldLen = oldTab.length;
int newLen = oldLen * 2;
Entry[] newTab = new Entry[newLen];
int count = 0;
for (int j = 0; j < oldLen; ++j) {
Entry e = oldTab[j];
if (e != null) {
ThreadLocal<?> k = e.get();
if (k == null) {
e.value = null; // Help the GC
} else {
int h = k.threadLocalHashCode & (newLen - 1);
while (newTab[h] != null)
h = nextIndex(h, newLen);
newTab[h] = e;
count++;
}
}
}
setThreshold(newLen);
size = count;
table = newTab;
}整个过程不难理解。
扩容，容量是之前的2倍，遍历旧Entry数组，为每个Entry重新计算hash值作为key，把旧Entry放进新Entry数组里。
至此，set流程完毕，过程涉及到 替换Entry、清理无效Entry、整理Entry数组、和扩容
整个set过程差不多这样，但是感觉看懂又不懂，我们直接来个案例，加深理解。
这个画图，我先暂时用其他作者的图，后期换掉。
二、实例解读Set（重点）
场景一、
Entry数组里，起始下标后面没有相同的key或key=null的Entry。那就在首次遇到Entry=null的地方存放该数据。
我们准备表长为10的Entry数组，计算key哈希值 我们用函数f(key) = key mod l0，简单一些。现在我们有 4个树值{12,33,4,5}，都是没有冲突的散列地址，直接存入（蓝色代表为空的，可以存放数据）：
现在我们想set一个值，key=15，f(15)=5，也就是i=5
回看set方法,从下标5开始遍历，发现下标为6时Entry为null。此时f(15)=5，key=15和key=5不等，且f(15)=5不为null，不符合步骤一和二，我们走步骤三，此时i经过nextIndex移位，i=6。那就把key=15放在下标6的位置。
然后在判断是否要rehash，显然容量还没达到阀值，不需要扩容。
假如哈，假如。在添加key=15时，Entry数组容量正好满了，这个时候tab[11]存放key=15的Entry，需要扩容了。
场景二、
Entry数组里，起始下标后面，有key=null的Entry。
我们准备表长为10的Entry数组，计算key哈希值 我们用函数f(key) = key mod l0，简单一些。现在我们有 6个数值{12,33,4,5,15,25}，并且此时key=33,k=5 已经过期了（蓝色代表为空的，可以存放数据，红色代表key 过期，过期的key为null）
现在我们想set一个值，key=15，f(15)=5，也就是i=5
回看set方法,从下标5开始遍历，发现下标为5的key=null，按道理，我们应该走步骤二，即进入replaceStaleEntry方法
里面做啥呢？回看replaceStaleEntry方法，我们知道其中内幕。
1.记录当前位置，也就是i=5，slotToExpunge = staleSlot=5
2.从下标5开始往前移动，直到遇到Entry为null为止，也就是下标1的位置。找到下标最小key=null的位置。看图，很容易直到那这个位置就是3，slotToExpunge=3。
3.从下标5开始往后遍历，直到遇到Entry为null为止，也就是下标8的位置。
在步骤3这过程中：
如果发现有待插入Entry的key和遍历过程中Entry的key相同，那就把该Entry和下标为staleSlot的Entry交换位置。也就是下标5，f(15)的数据，下标6，key=null 的数据 交换，原本key=15的数据被f（15）替换。
这个过程主要是两部分，第一，替换旧数据，第二交换位置。交换后如图。
然后看下expungeStaleEntry流程。slotToExpunge=3和staleSlot=5不等，于是从下标3开始 所有key=null的Entry被清空。
这里我们看下为什么要交换数据和清空数据？
清空数据容易理解，数据过期了嘛，自然要清空，释放空间给对方百分点。
我们来看看为什么要交换，这里说交换，这里有点难理解。起始我们的想法是，ThreadLocalMap里面的数据，不能存在相同的key，也就是冲突的key，假如key=15的Entry和下标5的Entry不交换，如果此时，我想插入f（15）的数据，那这数据就存放在下标5的地方，ThreadLocalMap里面就存在两个key=15的Entry，这肯定不行。
下面我们会遍历到下标i=7，经过int h = k.threadLocalHashCode & (len - 1) (实际上对应我们的举例的函数int h= f(25))，得到的h=5,而25实际存放在index=7 的位置上，这个时候我们需要从h=5的位置上重新开始编列，直到遇到空的Entry 为止
expungeStaleEntry流程最后返回i=7；
最后还要执行cleanSomeSlots，清除过期无效的Entry，但是下标7及后面没有过期无效Entry，所以结束。
三、getEntry
private Entry getEntry(ThreadLocal<?> key) {
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
if (e != null && e.get() == key)
return e;
else
return getEntryAfterMiss(key, i, e);
}这里面没啥好讲的，我们来看下getEntryAfterMiss
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
while (e != null) {
ThreadLocal<?> k = e.get();
if (k == key)
return e;
if (k == null)
expungeStaleEntry(i);
else
i = nextIndex(i, len);
e = tab[i];
}
return null;
}其实有一种情况，不同的key hash值，但是可能他们key是一样的。上面代码主要功能就是遍历Entry数组，找到key一样的Entry，找到就返回此Entry，找不到就返回null。
四、remove
private void remove(ThreadLocal<?> key) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
if (e.get() == key) {
e.clear();
expungeStaleEntry(i);
return;
}
}
}这里面有了上面讲解基础，很好理解。根据当前key的hash值，也就是数组下标，找到对应的Entry，判断此时的Entry的key和当前ThreadLocal是不是同一个，是的话，就clear，然后expungeStaleEntry清理、整理Entry数组。
五、问题
HashMap和ThreadLocalMap区别,怕篇幅太长，为了减少阅读压力，这个留在后面一篇聊聊吧。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
