取index值

上面代码中，用取得的hash值，与ThreadLocalMap实例中数组长度减一的与操作，计算出了index值
这个很重要的，因为大于长度的高位hash值是不需要的

此处会将传入的ThreadLocal实例计算出一个hash值，怎么计算的后面再说，这地方有个位与的操作，这地方是和长度减一的与操作，这个很重要的，因为大于长度的高位hash值是不需要的

假设hash值为：010110011101
长度（此处选择默认值：16-1）：01111
看下图可知，这个与操作，可去掉高位无用的hash值，取到的index值可限制在数组长度中

hash值低位与操作

塞值

看下塞值进入ThreadLocalMap数组的操作
- 关于Key：因为Entry是继承的WeakReference类，get()方法是获取其内部弱引用对象，所以可以通过get()拿到当前ThreadLocal实例
- 关于value：直接 .value 就OK了

private void set(ThreadLocal<?> key, Object value) {

    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)]) {

        ThreadLocal<?> k = e.get();

if (k == key) {

            e.value = value;
return;

        }

if (k == null) {

            replaceStaleEntry(key, value, i);
return;

        }

    }


    tab[i] = new Entry(key, value);

    ...

}

分析下塞值流程

实际上面的循环还值得去思考，来思考下这循环处理的事情
循环中获取当前index值，从Entry数组取到当前index位置的Entry对象

如果获取的这Entry是null，则直接结束这个循环体
- 在Entry数组的index塞入一个新生成的节点
如果获取的这Entry不为null
1. key值相等，说明Entry对象存在，覆盖其value值即可
2. key为null，说明该节点可被替换（替换算法后面讲），new一个Entry对象，在此节点存储数据
3. 如果key不相等且不为null，循环获取下一节点的Entry对象，并重复上述逻辑

整体的逻辑比较清晰，如果key已存在，则覆盖；不存在，index位置是否可用，可用则使用该节点，不可用，往后寻找可用节点：线性探测法

替换旧节点的逻辑，实在有点绕，下面单独提出来说明

map.set流程

替换算法

在上述set方法中，当生成的index节点，已被占用，会向后探测可用节点

探测的节点为null，则会直接使用该节点
探测的节点key值相同，则会覆盖value值
探测的节点key值不相同，继续向后探测
探测的节点key值为null，会执行一个替换旧节点的操作，逻辑有点绕，下面来分析下

private void set(ThreadLocal<?> key, Object value) {

    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)]) {

        ThreadLocal<?> k = e.get();

		...
if (k == null) {

            replaceStaleEntry(key, value, i);
return;

        }

    }

    ...

}

来看下replaceStaleEntry方法中的逻辑

private static int prevIndex(int i, int len) {
return ((i - 1 >= 0) ? i - 1 : len - 1);

}

private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {

    Entry[] tab = table;
int len = tab.length;

    Entry e;

// Back up to check for prior stale entry in current run.
// We clean out whole runs at a time to avoid continual
// incremental rehashing due to garbage collector freeing
// up refs in bunches (i.e., whenever the collector runs).
int slotToExpunge = staleSlot;
for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len))
if (e.get() == null)

            slotToExpunge = i;

// Find either the key or trailing null slot of run, whichever
// occurs first
for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {

        ThreadLocal<?> k = e.get();

// If we find key, then we need to swap it
// with the stale entry to maintain hash table order.
// The newly stale slot, or any other stale slot
// encountered above it, can then be sent to expungeStaleEntry
// to remove or rehash all of the other entries in run.
if (k == key) {

            e.value = value;


            tab[i] = tab[staleSlot];

            tab[staleSlot] = e;

// Start expunge at preceding stale entry if it exists
if (slotToExpunge == staleSlot)

                slotToExpunge = i;

            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
return;

        }

// If we didn't find stale entry on backward scan, the
// first stale entry seen while scanning for key is the
// first still present in the run.
if (k == null && slotToExpunge == staleSlot)

            slotToExpunge = i;

    }

// If key not found, put new entry in stale slot

    tab[staleSlot].value = null;

    tab[staleSlot] = new Entry(key, value);

// If there are any other stale entries in run, expunge them
if (slotToExpunge != staleSlot)

        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);

}

上面的代码，很明显俩个循环是重点逻辑，这里面有俩个很重要的字段：slotToExpunge和staleSlot
- staleSlot：记录传进来节点key为null的位置
- slotToExpunge：标定是否需要执行最后的清理方法
第一个循环：很明显是往前列表头结点方向探测，是否还有key为null的节点，有的话将其下标赋值给slotToExpunge；这个探测是一个连续的不为null的节点链范围，有空节点，立马结束循环

替换算法-前探测

第二个循环：很明显主要是向后探测，探测整个数组，这里有很重要逻辑
- 这地方已经开始有点绕了，我giao，大家要好好想想
- 当探测的key和传入的需要设值的key相同时，会复写探测到Entry的value，然后将探测到位置和传入位置，俩者相互调换
为什么会出现探测到Entry和传入key相同？
- 相同是因为，存在到数组的时候，产生了hash冲突，会自动向后探测合适的位置存储
- 当你第二次用ThreadLocal存值的时候，hash产生的index，比较俩者key，肯定是不可能相同，因为产生了hash冲突，真正储存Entry，在往后的位置；所以需要向后探测
- 假设探测的时候，一直没有遇到key为null的Entry：正常循环的话，肯定是能探测到key相同的Entry，然后进行复写value的操作
- 但是在探测的时候，遇到key为null的Entry的呢？此时就进入了替换旧Entry算法，所以替换算法就也有了一个向后探测的逻辑
- 探测到相同key值的Entry，就说明了找到了我们需要复写value的Entry实例
为什么要调换俩者位置呢？
- 这个问题，大家可以好好想想，我们时候往后探测，而这key为null的Entry实例，属于较快的探测到Entry
- 而这个Entry实例的key又为null，说明这个Entry可以被回收了，此时正处于占着茅坑不拉屎的位置
- 此时就可以把我需要复写Entry实例和这个key为null的Entry调换位置
- 可以使得我们需要被操作的Entry实例，在下次被操作时候，可以尽快被找到
调换了位置之后，就会执行擦除旧节点算法

替换算法-后探测（需复写）

上面是探查连续的Entry节点，未碰到null节点的情况；如果碰到null节点，会直接结束探测
- 请注意，如果数组中，有需要复写value的节点；在计算的hash值处，向后探测的过程，一定不会碰到null节点
- 毕竟，第一次向后探测可用节点是，碰到第一个null节点，就停下来使用了

替换算法-后探测（null节点）

在第二个循环中，还有一段代码，比较有意思，这判断逻辑的作用是
- 以key为null的Entry，以它为界限
- 向前探测的时候，未碰到key为null的Entry
- 而向后探测的时候，碰到的key为null的Entry
- 然后改变slotToExpunge的值，使其和staleSlot不相等

private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {

   	...
for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {

        ...
if (k == null && slotToExpunge == staleSlot)

            slotToExpunge = i;

    }

	...

}

替换算法-后探测（寻找key为null）

可以看出来这俩个循环的操作，是有关联性，对此，我表示

为什么这俩个循环都这么执着的，想改变slotToExpunge的数值呢？

来看下关于slotToExpunge的关键代码

private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {

    ...
int slotToExpunge = staleSlot;

    ...
if (slotToExpunge != staleSlot)

        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);

}

明白了吧！都是为了替换方法里面的最后一段逻辑：为了判断是否需要执行擦除算法

总结

双向探测流程
- 替换算法会以传入的key为null的Entry节点为界限，在一个连续的Entry范围往俩边探测
  - 什么是连续的Entry范围？这边数组的节点都不能为null，碰到为null节点会结束探测
- 先向前探测：如果碰到key为null的Entry，会将其下标赋值给slotToExpunge
- 向后探测使：如果向前探测没有碰到key的节点，只要向后探测的时候碰到为null的节点，会将其下标赋值给slotToExpunge
- 上面向俩边探测的逻辑，是为了：遇到key为null的节点，能确保slotToExpunge不等于staleSlot
在向后探测的时候，如果遇到key值对比相同的Entry，说明遇到我们需要复写value的Entry
- 此时复写value的Entry，用我们传入的value数值将其原来的value数值覆盖
- 然后将传入key为null的Entry（通过传入的下标得知Entry）和需要复写value的Entry交换位置
- 最后执行擦除算法
如果在向后探测的时候，没有遇到遇到key值对比相同的Entry
- 传入key为null的Entry，将其value赋值为null，断开引用
- 创建一个新节点，放到此位置，key为传入当前ThreadLocal实例，value为传入的value数据
- 然后根据lotToExpunge和staleSlot是否相等，来判断是否要执行擦除算法

总结

来总结下

再来看下总流程

set总流程

上面分析完了替换旧节点方法逻辑，终于可以把map.set的那块替换算法操作流程补起来了
- 不管后续遇到null，还是遇到需要被复写value的Entry，这个key为null的Entry都将被替换掉

map.set流程（完善）

这俩个图示，大概描述了ThreadLocal进行set操作的整个流程；现在，进入下一个栏目吧，来看看ThreadLocal的get操作！

get

get流程，总体要比set流程简单很多，可以轻松一下了

总流程

来看下代码
- 总体流程非常简单，将自身作为key，传入map.getEntry方法，获取符合实例的Entry，然后拿到value，返回就行了

public T get() {

    Thread t = Thread.currentThread();

    ThreadLocalMap map = getMap(t);
if (map != null) {

        ThreadLocalMap.Entry e = map.getEntry(this);
if (e != null) {
@SuppressWarnings("unchecked")

            T result = (T)e.value;
return result;

        }

    }
return setInitialValue();

}

如果通过map.getEntry获取的Entry为null，会返回setInitialValue()，来看下这个方法是干嘛的
- 从这个方法可知，如果我们没有进行set操作，直接进行get操作，他会给ThreadLocal的threadLocals方法赋初值
- setInitialValue() 方法，返回的是initialValue() 方法的数据，可知默认为null
- 所以通过key没查到对应的Entry，get方法会返回null

private T setInitialValue() {

    T value = initialValue();

    Thread t = Thread.currentThread();

    ThreadLocalMap map = getMap(t);
if (map != null)

        map.set(this, value);
else

        createMap(t, value);
return value;

}

protected T initialValue() {
return null;

}

void createMap(Thread t, T firstValue) {

    t.threadLocals = new ThreadLocalMap(this, firstValue);

}

map.getEntry

从上面的代码可以看出来，getEntry方法是获取符合条件的节点
- 这里逻辑很简单，通过当前ThreadLocal实例获取HashCode，然后算出index值
- 直接获取当前index下标的Entry，将其key和当前ThreadLocal实例对比，看是否一样
- 相同：说明没有发生Hash碰撞，可以直接使用
- 不相同：说明发生了Hash碰撞，需要向后探测寻找，执行getEntryAfterMiss()方法
- 此时，就需要来看看getEntryAfterMiss()方法逻辑了

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;

}

整体逻辑还是很清晰了，通过while循环，不断获取Entry数组中的下一个节点，循环中有三个逻辑走向

当前节点的key等于当前ThreadLocal实例：直接返回这个节点的Entry
当前节点的key为null：执行擦除旧节点算法，继续循环
当前节点的可以不等于当前ThreadLocal实例且不为null：获取下一节点的下标，然后继续上面的逻辑

如果没有获取到符合条件的Entry节点，会直接返回null

get流程-getEntryAfterMiss

总结

ThreadLocal的流程，总体上比较简单

将当前ThreadLocal实例当为key，查找Entry数组当前节点（使用ThreadLocal中的魔术值算出的index）是否符合条件
不符合条件将返回null
- 从未进行过set操作
- 未查到符合条件的key
符合条件就直接返回当前节点
- 如果遇到哈希冲突，算出的index值的Entry数组上存在Entry，但是key不相等，就向后查找
- 如果遇到key为null的Entry，就执行擦除算法，然后继续往后寻找
- 如果遇到key相当的Entry，就直接结束寻找，返回这个Entry节点
这里大家一定要明确一个概念：在set的流程，发生了hash冲突，是在冲突节点向后的连续节点上，找到符合条件的节点存储，所以查询的时候，只需要在连续的节点上查找，如果碰到为null的节点，就可以直接结束查找

get流程

擦除算法

在set流程和get流程都使用了这个擦除旧节点的逻辑，它可以及时清除掉Entry数组中，那些key为null的Entry，如果key为null，说明这些这节点，已经没地方使用了，所以就需要清除掉

来看看这个方法代码

private int expungeStaleEntry(int staleSlot) {

    Entry[] tab = table;
int len = tab.length;

// expunge entry at staleSlot

    tab[staleSlot].value = null;

    tab[staleSlot] = null;

    size--;

// Rehash until we encounter null

    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;

// Unlike Knuth 6.4 Algorithm R, we must scan until
// null because multiple entries could have been stale.
while (tab[h] != null)

                    h = nextIndex(h, len);

                tab[h] = e;

            }

        }

    }
return i;

}

前置操作

从上面的代码，可以发现，再进行主要的循环体，有个前置操作

private int expungeStaleEntry(int staleSlot) {

    Entry[] tab = table;
int len = tab.length;

// expunge entry at staleSlot

    tab[staleSlot].value = null;

    tab[staleSlot] = null;

    size--;


    ...

}

这地方做了很简单的置空操作，如果Entry节点的key为空，说明这个节点可以被清除，value置空，和数组的链接断开

擦除算法-前置操作

主体逻辑

很明显，循环体里面的逻辑是最重要，而且循环体里面做了一个相当有趣的操作！

private int expungeStaleEntry(int staleSlot) {

    Entry[] tab = table;
int len = tab.length;

	...
// Rehash until we encounter null

    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;

// Unlike Knuth 6.4 Algorithm R, we must scan until
// null because multiple entries could have been stale.
while (tab[h] != null)

                    h = nextIndex(h, len);

                tab[h] = e;

            }

        }

    }
return i;

}

上面的循环体里面，就是不断的获取下一节点的Entry实例，然后判断key值进行相关处理
key为null：中规中矩的，将value置空，断开与数组的链接
key不为null：这时候就有意思了
- 首先，会获取当前ThreadLocal实例的hash值，然后取得index值
- 判断h(idnex值)和i是否相等，不相等进行下述操作，因为Entry数组是环形结构，是完成存在相等的情况
  1. 会将当前循环到节点置空，该节点的Entry记为e
  2. 从通过hreadLocal实例的hash值获取到index处，开始进行循环
  3. 循环到节点Entry为null，则结束循环
  4. 将e赋值给为null的节点
- 这里面的逻辑就是关键了
大家可能对这个文字的描述，感觉比较抽象，来个图，来体会下这短短几行代码的妙处

擦除算法-主体逻辑

总结

代码很少，但是实现的功能却并不少

擦除旧节点的方法，在Entry上探测的时候
- 遇到key为空的节点，会将该节点置空
- 遇到key不为空的节点，会将该节点移到靠前位置（具体移动逻辑，请参考上述说明）
交互到靠前节点位置，可以看出，主要的目的，是为了：
- ThreadLocal实例计算出的index节点位置往后的位置，能让节点保持连续性
- 也能让交换的节点，更快的被操作

扩容

在进行set操作的时候，会进行相关的扩容操作

来看下扩容代码入口：resize方法便是扩容方法

public void set(T value) {

    ...
if (map != null)

        map.set(this, value);
else

        createMap(t, value);

}

private void set(ThreadLocal<?> key, Object value) {

	...

    tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold)

        rehash();

}

private void rehash() {

    expungeStaleEntries();

// Use lower threshold for doubling to avoid hysteresis
if (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;

}

触发条件

先来看下扩容的触发条件吧

整体代码

public void set(T value) {

    ...
if (map != null)

        map.set(this, value);
else

        createMap(t, value);

}

private void set(ThreadLocal<?> key, Object value) {

	...

    tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold)

        rehash();

}

private void rehash() {

    expungeStaleEntries();

// Use lower threshold for doubling to avoid hysteresis
if (size >= threshold - threshold / 4)

        resize();

}

上面主要的代码就是：!cleanSomeSlots(i, sz) && sz >= threshold

来看下threshold是什么
- 只要Entry数组含有Entry实例大于等于数组的长度的三分之二，便能满足后一段判定

ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {

    table = new Entry[INITIAL_CAPACITY];
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);

    table[i] = new Entry(firstKey, firstValue);

    size = 1;

    setThreshold(INITIAL_CAPACITY);

}

private void setThreshold(int len) {

    threshold = len * 2 / 3;

}

来看看前一段的判定，看下cleanSomeSlots，只要返回false，就能触发扩容方法了

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;

}

n >>>= 1：表达是无符号右移一位，正数高位补0，负数高位补1
举例：0011 ---> 0001

在上面的cleanSomeSlots方法中，只要在探测节点的时候，没有遇到Entry的key为null的节点，该方法就会返回false

rehash方法就非常简单了
- 执行擦除方法
- 只要size(含有Entry实例数)长度大于等于3/4 threshold，就执行扩容操作

private void rehash() {

    expungeStaleEntries();

// Use lower threshold for doubling to avoid hysteresis
if (size >= threshold - threshold / 4)

        resize();

}

总结

满足下面俩个条件即可

Entry数组中不含key为null的Entry实例
数组中含有是实例数大于等于threshold的四分之三（threshold为数组长度的三分之二）

扩容逻辑

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;

}

从上面的逻辑，可以看出来，将旧数组的数据赋值到扩容数组，并不是全盘赋值到扩容数组的对应位置
遍历旧数组，取出其中的Entry实例
- key为null：需要将该节点value置空，等待GC处理（Help the GC，hhhh）
  - 这里你可能有个疑问，不是说数组的节点key不为null，才会触发扩容机制吗？
  - 在多线程的环境里，执行扩容的时候，key的强引用断开，导致key被回收，从而key为null，这是完全存在的
- key不为null：算出index值，向扩容数组中存储，如果该节点冲突，向后找到为null的节点，然后存储
这里的扩容存储和ArrayList之类是有区别

扩容机制

总结

可以发现

set，替换，擦除，扩容，基本无时无刻，都是为了使hash冲突节点，向冲突的节点靠近
这是为了提高读写节点的效率

remove

remove方法是非常简单的，ThreadLocal拥有三个api：set、get、remove；虽然非常简单，但是还有一些必要，来稍微了解下

remove代码

public void remove() {

    ThreadLocalMap m = getMap(Thread.currentThread());
if (m != null)

        m.remove(this);

}

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;

        }

    }

}

逻辑非常的清晰，通过ThreadLocal实例，获取当前的index，然后从此开始查找符合条件Entry，找到后，会将其key值清掉，然后执行擦除算法

e.clear就是，弱引用的清理弱引用的方法，很简单，将弱引用referent变量置空就行了，这个变量就是持有弱引用对象的变量

remove流程

最后

文章写到这里，基本上到了尾声了，写了差不多万余字，希望大家看完后，对ThreadLocal能有个更加深入的认识

ThreadLocal的源码虽然并不多，但是其中有很多奇思妙想，有种萝卜雕花的感觉，这就是高手写的代码吗？

系列文章

源码篇：Handler那些事（万字图文）

源码篇：ThreadLocal的奇思妙想（万字图文）（二）