JUC ThreadLocal源码行级解析 JDK8

刺骨的言语ヽ痛彻心扉 2023-07-25 12:37 13阅读 0赞

# 前言 #

**源码面前,了无秘密。**

ThreadLocal看类名就是线程本地变量的意思。从使用上来说，如果定义了一个ThreadLocal，那么各个线程针对这个ThreadLocal进行get/set都是线程独立的，也就是说，是线程隔离的本地变量。

从实现上来说，每个线程在运行过程中都可以通过`Thread.currentThread()`获得与之对应的Thread对象，而每个Thread对象都有一个`ThreadLocalMap`类型的成员，`ThreadLocalMap`是一种hashmap，它以ThreadLocal作为key。所以，通过Thread对象和ThreadLocal对象二者，才可以唯一确定到一个value上去。线程隔离的关键，正是因为这种对应关系用到了Thread对象。

# 标准示例 #

这是来自API文档的标准示例。

import java.util.concurrent.atomic.AtomicInteger;
    
     public class ThreadId { 
         // Atomic integer containing the next thread ID to be assigned
         private static final AtomicInteger nextId = new AtomicInteger(0);
    
         // Thread local variable containing each thread's ID
         private static final ThreadLocal<Integer> threadId =
             new ThreadLocal<Integer>() { 
                 @Override 
                 protected Integer initialValue() { 
                     return nextId.getAndIncrement();
                 }
         };
    
         // Returns the current thread's unique ID, assigning it if necessary
         public static int get() { 
             return threadId.get();
         }
     }

*  `threadId`这个你定义的ThreadLocal对象，它是当作key使用的，而它的初始的value则在initialValue中给出。
 *  各个线程第一次get时会调用到重写的initialValue函数，由于AtomicInteger利用了volatile+CAS，所以各个线程调用get时不需要同步操作（调用get，最终会间接调用到initialValue）。即每个线程都能通过threadId这个ThreadLocal对象，获得一个唯一的线程ID。
 *  threadId这个ThreadLocal对象被设置为了一个静态对象，这就让整个内存中只有这一个对象。ThreadLocal给多个线程作为key来使用，自然只保持同一个对象才是正确的选择。

# 类定义 #

public class ThreadLocal<T> { ...}

泛型T规定了ThreadLocal对象的对应的value的类型。

# 成员变量 #

每个ThreadLocal对象是需要在ThreadLocalMaps里作为key，而ThreadLocalMaps也是一种hashmap，所以ThreadLocal对象需要有哈希值。

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);
        }

*  每个ThreadLocal对象都有一个int值的成员变量，作为它在ThreadLocalMaps里的哈希值。
 *  第一次构造ThreadLocal对象时，它的哈希值为0。此后，每个新构造出来的ThreadLocal对象都新增一个魔数`0x61c88647`。
 *  使用了AtomicInteger，就算两个线程同时构造了ThreadLocal对象，也能保证这个int成员变量各自线程的不同。
 *  魔数`0x61c88647`在2的幂为容量的哈希表上，能够完美散列，没有一个元素会哈希冲突。

import java.util.HashSet;
    import java.util.Set;
    
    public class MagicHashCode { 
        private static final int HASH_INCREMENT = 0x61c88647;
    
        public static void main(String[] args) { 
            hashCode(16);
            hashCode(32);
            hashCode(64);
        }
    
        private static void hashCode(Integer length){ 
            int hashCode = 0;
            Set<Integer> set = new HashSet<>();
            for(int i=0;i<length;i++){ 
                hashCode = i*HASH_INCREMENT;//第一次为0，每次递增HASH_INCREMENT
                System.out.print((hashCode & (length-1)) + " ");//哈希值取模，才能得到哈希表的数组下标。注意& (length-1)相当于% length
                set.add(hashCode & (length-1));
            }
            System.out.print("将取模后的数组下标 加入set后的大小："+set.size());
            System.out.println();
        }
    }

0 7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 将取模后的数组下标 加入set后的大小：16
    0 7 14 21 28 3 10 17 24 31 6 13 20 27 2 9 16 23 30 5 12 19 26 1 8 15 22 29 4 11 18 25 将取模后的数组下标 加入set后的大小：32
    0 7 14 21 28 35 42 49 56 63 6 13 20 27 34 41 48 55 62 5 12 19 26 33 40 47 54 61 4 11 18 25 32 39 46 53 60 3 10 17 24 31 38 45 52 59 2 9 16 23 30 37 44 51 58 1 8 15 22 29 36 43 50 57 将取模后的数组下标 加入set后的大小：64

从打印结果可以看出，按照魔数递增的哈希值真的实现了完美散列。注意，**取模下标分布十分均匀。**

# initialValue #

*  当线程第一次调用`get()`方法时，`initialValue`方法会被间接调用到；但如果线程之前调用了`set(T)`方法，那么第一次调用`get()`方法时，`initialValue`方法将不会被调用。
 *  一般情况下，一个线程只会调用到一次`initialValue`方法。
 *  调用完`get()`方法后，如果你调用了`remove()`方法，那么，`initialValue`方法才可能会被第二次调用。

以上几点先记下，之后对其他方法的讲解将进行解释。

protected T initialValue() { 
            return null;
        }

*  `initialValue`方法的默认实现是返回null。如果想给线程的初始值是具体的值，那么子类需要重写此方法。
 *  ThreadLocal的常用创建方法是，构造一个匿名内部类，类里重写 initialValue\`方法。

# withInitial与静态内部类SuppliedThreadLocal #

*  可以通过传给`withInitial`方法一个Supplier接口的子类，来构造得到一个SuppliedThreadLocal对象，它是ThreadLocal的子类。
 *  相比构造一个匿名内部类，其实这种方式就是把要重写的`initialValue`方法的逻辑，写在了Supplier接口的子类里。相同之处：你自己的匿名内部类和SuppliedThreadLocal，都是ThreadLocal的子类，只是SuppliedThreadLocal这个类有个名字而已。

public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) { 
            return new SuppliedThreadLocal<>(supplier);
        }
    	//ThreadLocal的静态内部类
        static final class SuppliedThreadLocal<T> extends ThreadLocal<T> { 
            //由于是? extends，只能使用supplier的泛型出口代码
            private final Supplier<? extends T> supplier;  
    
            SuppliedThreadLocal(Supplier<? extends T> supplier) { 
                this.supplier = Objects.requireNonNull(supplier);
            }
    
            @Override
            protected T initialValue() { 
                return supplier.get();  //调用supplier的泛型出口代码
            }
        }

*  注意方法签名为`<S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier)`，形参为泛型的通配符，所以可以写出下面这种代码。

//只要Supplier的实际泛型类型，是赋值过去的泛型类型的子类，就可以
    ThreadLocal<Number> localNumber = ThreadLocal.withInitial(new Supplier<Integer>() { 
        @Override
        public Integer get() { 
            return  null;
        };
    });

# get与setInitialValue与getMap #

//ThreadLocal
        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();
        }
    
        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;
        }
    
        ThreadLocalMap getMap(Thread t) { 
            return t.threadLocals;
        }
    //Thread
        ThreadLocal.ThreadLocalMap threadLocals = null;

*  刚开始就直接找到了调用当前函数的线程是哪个（`Thread t = Thread.currentThread();`），然后调用getMap，最后居然直接去取Thread对象的一个`ThreadLocal.ThreadLocalMap`类型的`threadLocals`成员.
 *  上面这点就直接解释了，为什么ThreadLocal可以实现线程隔离的线程私有变量。因为它把这个Map对象直接作为了Thread对象的成员，这样，每个运行的线程都对应到一个唯一的Thread对象，而每个Thread对象都保存着各自的`ThreadLocal.ThreadLocalMap`类型的成员变量。

如果当前线程的Thread对象还没有创建`ThreadLocal.ThreadLocalMap`类型的成员变量：

*  get函数中，调用getMap将会返回null。紧接着，会调用setInitialValue函数。
 *  setInitialValue函数里，通过initialValue获得初值。然后调用getMap又将会返回null，进else分支调用createMap：果然，创建了一个`ThreadLocal.ThreadLocalMap`对象赋值给了Thread对象的成员变量。

void createMap(Thread t, T firstValue) { 
            t.threadLocals = new ThreadLocalMap(this, firstValue);
        }

*  这个Map的第一个键值对：key为`this`即`ThreadLocal`对象，value为`T`对象。其实看到这里，就能理解到ThreadLocal的基本原理了：每个线程对应到一个Map对象上去，且key的类型为`ThreadLocal`。而且根据前面ThreadLocal的哈希值成员的讲解，可以得知，每个ThreadLocal对象的哈希值肯定不同，所以，**当不同线程想要根据同一个key来get/set value时，必须复用ThreadLocal对象（也就是为什么ThreadLocal对象一般设置为`static`的原因，比如那个来自API文档的标准示例。）**。

如果当前线程的Thread对象已经创建了`ThreadLocal.ThreadLocalMap`类型的成员变量：

*  直接调用`getEntry(ThreadLocal对象)`，通过key获得了key所在的entry（entry自然包含了key和key对应的value）。
 *  如果这个entry对象不为空，获得entry的value，返回value。
 *  如果这个entry对象为空，还是会调用到setInitialValue去。

# set与remove #

public void set(T value) { 
            Thread t = Thread.currentThread();
            ThreadLocalMap map = getMap(t);
            if (map != null)//如果map对象存在，直接set值
                map.set(this, value);
            else//如果map对象不存在，用第一对键值对，创建map
                createMap(t, value);
        }
    
         public void remove() { 
             ThreadLocalMap m = getMap(Thread.currentThread());
             if (m != null)//只需在map对象存在时，才删除键值对
                 m.remove(this);
         }

其实这块没啥好讲的，但从上面的分析，我们能看到，ThreadLocal的方法其实都在依靠ThreadLocalMap的方法。

# createInheritedMap与childValue #

/** * 工厂方法，当父线程创建子线程，通过此方法构造出一个ThreadLocalMap赋值给 * 子线程的inheritableThreadLocals成员。 * 这个方法是父线程通过new Thread间接调用到的。 * * @param parentMap 父线程（当前线程）的inheritableThreadLocals成员 * @return 父线程的inheritableThreadLocals成员，浅复制而来的一个ThreadLocalMap */
        static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) { 
            return new ThreadLocalMap(parentMap);
        }
    
        /** * 默认实现是抛异常，InheritableThreadLocal子类实现了此方法，逻辑可为： * 可根据父线程的value来设置子线程的value。 */
        T childValue(T parentValue) { 
            throw new UnsupportedOperationException();
        }

简单实用例子：

public class test3 { 
        public static void main(String[] args) { 
            InheritableThreadLocal<Number> localNumber = new InheritableThreadLocal<>();
            localNumber.set(1);
    
            new Thread(new Runnable(){ 
                @Override
                public void run() { 
                    System.out.println(Thread.currentThread().getName()+" "+localNumber.get());
                }
            }).start();
    
        }
    }/*打印结果： Thread-0 1

*  父线程（main线程）的inheritableThreadLocals成员里，有一个键值对的key是InheritableThreadLocal实例，即localNumber。

//Thread
    private void init(ThreadGroup g, Runnable target, String name,
                          long stackSize, AccessControlContext acc) { 
        ...
        Thread parent = currentThread();//父线程间接调用到init方法，来初始化线程
        if (parent.inheritableThreadLocals != null)//如果父线程的inheritableThreadLocals成员不为null
            this.inheritableThreadLocals =
                ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);  
            //调用工厂方法，返回map赋值给子线程的inheritableThreadLocals成员
        ...  
    }

*  子线程的inheritableThreadLocals成员里，有一个键值对的key也是同一个InheritableThreadLocal实例。具体看ThreadLocalMap的构造器。

# ThreadLocalMap静态内部类 #

这才是ThreadLocal的关键所在，ThreadLocal的很多操作都是在间接调用ThreadLocalMap的方法。

## Entry静态内部类 ##

static class Entry extends WeakReference<ThreadLocal<?>> { 
                /** The value associated with this ThreadLocal. */
                Object value;
    
                Entry(ThreadLocal<?> k, Object v) { 
                    super(k);
                    value = v;
                }
            }

*  继承了WeakReference，而尖括号里面的`ThreadLocal<?>`指定了父类的referent成员的类型。这里，把这个referent成员，作为了entry的key使用。

public class WeakReference<T> extends Reference<T> { 
    }
    
    public abstract class Reference<T> { 
    	private T referent; 
    }

*  自己新加了一个value成员，作为了entry的value使用。
 *  继承使用WeakReference的父类成员referent，当没有强引用指向referent这个对象时，可能这个referent会被回收。从下面测试类可以看到，当执行gc时，没有强引用的weak对象被回收。
 *  由于ThreadLocal对象一般设置为static，那么只有当这个静态变量赋值为null时，entry的父类成员referent才可能被回收。

import java.lang.ref.WeakReference;
    
    public class WeakReferenceDemo { 
        static class Entry extends WeakReference<String> { 
            String member;
    
            public Entry(String referent, String member) { 
                super(referent);
                this.member = member;
            }
        }
        static Entry entry;
    
        static void test () { 
            String Weak = new String("weak");
            String Member = new String("member");
            entry = new Entry(Weak,Member);
    
            System.gc();
            System.out.println("进行gc时，Reference类的referent成员有强引用，member有强引用：" + entry.get());
    
            Weak = null;
            System.gc();
            System.out.println("进行gc时，Reference类的referent成员没有强引用，member有强引用：" + entry.get());
        }
    
        public static void main(String[] args) { 
            test();
        }
    }/*打印结果： 进行gc时，Reference类的referent成员有强引用，member有强引用：weak 进行gc时，Reference类的referent成员没有强引用，member有强引用：null

*  如果一个entry的key为null，那么被称为stale entry。

## 成员 ##

/** * 初始容量16，必须为2的幂 */
            private static final int INITIAL_CAPACITY = 16;
    
            /** * 内部实现为Entry对象的数组 */
            private Entry[] table;
    
            /** * entry个数 */
            private int size = 0;
    
            /** * 阈值，到达时再哈希 */
            private int threshold; // Default to 0
    
            /** * 根据容量设置阈值 */
            private void setThreshold(int len) { 
                threshold = len * 2 / 3;
            }
    
            /** * 自增i，取模容量。用于开放寻址 */
            private static int nextIndex(int i, int len) { 
                return ((i + 1 < len) ? i + 1 : 0);
            }
    
            /** * 自减i，取模容量 */
            private static int prevIndex(int i, int len) { 
                return ((i - 1 >= 0) ? i - 1 : len - 1);
            }

*  最重要是nextIndex，它是key放入map中，如果发生了哈希冲突，寻找下一个可能位置时，将使用的函数。
 *  nextIndex和prevIndex的逻辑很简单，只是向后或向前移动索引，超出范围时，就取模容量。
 *  **由于开放寻址用的是nextIndex来寻找下一个可能位置，所以`Entry[] table`实际是一个环形数组**。在寻找位置过程中，如果到达了len，那么跳转到0。

## ThreadLocalMap构造器 ##

//使用第一对键值对，创建map。一般使用到这个构造器
            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);
            }
    
            /** * 根据父线程的inheritableThreadLocals字段构造子线程（this）的inheritableThreadLocals。 * 这个构造器只能被 静态工厂方法createInheritedMap调用 * * @param parentMap 父线程的inheritableThreadLocals字段 */
            private ThreadLocalMap(ThreadLocalMap parentMap) { 
                Entry[] parentTable = parentMap.table;
                int len = parentTable.length;  //容量
                setThreshold(len);  //设置阈值
                table = new Entry[len];  //初始化entry数组
    
                for (int j = 0; j < len; j++) { 
                    Entry e = parentTable[j];
                    if (e != null) { 
                        @SuppressWarnings("unchecked")
                        ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();  //获得key
                        if (key != null) {   //判断key，不为null，才说明这是个有效entry
                            //childValue的原实现抛异常，所以key的真正类型肯定是ThreadLocal的子类，以重写该方法
                            //并且重写方法实现，可以根据父线程的value，得到子线程的新value
                            //一般是InheritableThreadLocal的实现，直接返回父线程的value。
                            Object value = key.childValue(e.value);
                            Entry c = new Entry(key, value);
                            int h = key.threadLocalHashCode & (len - 1);  //获得数组下标
                            while (table[h] != null)
                                h = nextIndex(h, len);  //开发寻址法
                            //最终h为，哈希冲突后的最终位置。如果没有冲突，那么h == j
                            table[h] = c;
                            size++;
                        }
                    }
                }
            }

*  需要注意的是，父线程的inheritableThreadLocals字段和子线程的inheritableThreadLocals字段，如果直接使用InheritableThreadLocal的childValue方法，那么它们之间的value只是浅复制。要想解决这点，需要你继承InheritableThreadLocal并重写childValue方法，在方法内部new新对象出来。

## get操作 ##

getEntry会被ThreadLocal的get方法直接调用，用于返回key所在的entry（如果这样的entry存在的话），它可能会有后续调用。

/** * 根据key的hash值获得数组下标，但如果传入key和entry的key * 不是同一个对象，那么说明哈希冲突了。 * * @param key 用户传入的key * @return 与key关联的entry，如果没有返回空 */
            private Entry getEntry(ThreadLocal<?> key) { 
                int i = key.threadLocalHashCode & (table.length - 1);
                Entry e = table[i];  //根据下标获得的entry可能为null
                //只有当entry非null，且key为同一个对象时，才直接返回value
                if (e != null && e.get() == key)
                    return e;
                //取模下标无法直接得到，考虑哈希冲突。这里有两种情况：
                //1.e不为null，但e的key与传入key不同
                //2.e为null，调用下面函数将直接返回null。
                else
                    return getEntryAfterMiss(key, i, e);
            }

*  注意注释我写了，如果e（取模下标的entry）为null，调用下面getEntryAfterMiss函数将直接返回null。为啥这么自信呢，哈希值取模下标的entry没找到，就认为目标key肯定不在map里了。显然，ThreadLocalMap的函数逻辑是保证了这样一点：多个哈希值不同但取模下标相同的ThreadLocal，在你操作完毕后，或者说操作开始前，它们肯定从这个取模下标开始放置的（后面的由于冲突，会依次放在后面索引）。

常用操作解释：

*  一个数组元素为null，称为null entry
 *  一个数组元素虽不为null，但key为null，称为stale entry
 *  循环通常从一个索引向后搜索，直到遇到第一个null entry（一般是指循环处理前，就是null的entry），结束循环。将这个索引直到第一个null entry称为连续段。

/** * 当传入key的哈希值取模下标无法直接得到entry，调用此方法。 * 此方法考虑了传入key，因为哈希冲突，所以取模下标不是其实际所在下标。 * 通过循环往后移动，如果直到null的entry前，都没有 * 找到key，那么返回null。 * * @param key 用户传入的key * @param i 用户传入的key的取模下标 * @param e i对应的entry * @return */
            private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) { 
                Entry[] tab = table;
                int len = tab.length;
    
                //循环，不断寻址以找到那个哈希冲突的key。简而言之，向后搜索连续段
                while (e != null) { //当为null时，循环停止。因为当初因哈希冲突set值时，也是set到第一个不为null的位置
                    ThreadLocal<?> k = e.get();//获得当前entry的key
                    if (k == key)//第一次循环不可能进入此分支，此后可能。进入说明找到了哈希冲突的位置的entry
                        return e;
                    if (k == null)//寻址的过程中，不巧发现了包含null key的entry
                        expungeStaleEntry(i);//执行完此函数，i索引的entry不一定变成null
                    else//利用nextIndex，寻址到冲突后的实际位置
                        i = nextIndex(i, len);
                    e = tab[i];//将新下标所在entry赋值给e
                }
                //如果考虑了哈希冲突后，开放寻址还是不能找到entry，那么说明该key确实不在map中
                return null;
            }

*  如果进入`if (k == key)`分支，那说明虽然哈希冲突，但还是找到了key。
 *  如果进入`if (k == null)`分支，那说明遇到了stale entry，调用expungeStaleEntry函数，这里先简单说下expungeStaleEntry的作用：向后搜索连续段，如果遇到stale entry就清空（所以刚开始就会把i下标清空），如果遇到取模下标不等于实际下标的entry，为其再哈希，以使得它更靠近取模下标，甚至直接到取模下标上去。
    
     *  所以，如果之后的连续段中，有包含key的entry，那么一定移动使得其更加靠近取模下标。
     *  如果有包含key的entry，要么这个entry已经在i下标上了，要么i以及之后N个下标刚好是N+1个取模下标也等于i的entry分布在上面（当然，也有这几个entry没有一个是包含key的entry）。
     *  还有一点，进入这个分支，i 会保持不变（注意，本地循环不会执行`i = nextIndex(i, len);`）。如果后面没有一个取模下标也等于i的entry，那么由于expungeStaleEntry的行为，i 下标为null，再执行`e = tab[i]`，循环直接退出。这里也很自信，因为expungeStaleEntry也会向后搜索连续段，所以相当于将剩余搜索工作交给了expungeStaleEntry。
 *  如果这两个分支都没有进，那就是正常的向后搜索连续段。

/** * 此方法从staleSlot索引开始，一直到循环开始前就为null的entry为止。 * 过程中，如果遇到entry的key为null，执行清空操作； * 如果遇到entry的key因冲突而本不应该在当前位置，也清空当前位置，再从新为其找新位置 * （可能找到离取模下标更近的位置）。 * * @param staleSlot 当前已知的stale entry的索引 * @return 在staleSlot之后的，第一个为null的entry的索引。 * (staleSlot索引和返回值索引之间的entry都会收到expunge检查). */
            private int expungeStaleEntry(int staleSlot) { 
                Entry[] tab = table;
                int len = tab.length;
    
                // staleSlot所在的entry包含null的key，所以清空
                tab[staleSlot].value = null;
                tab[staleSlot] = null;
                size--;
    
                // Rehash until we encounter null
                Entry e;
                int i;
                //循环会一直进行，直到通过nextIndex找到了第一个为null的entry
                for (i = nextIndex(staleSlot, len) ; (e = tab[i]) != null ; i = nextIndex(i, len)) { 
                    ThreadLocal<?> k = e.get();
                    if (k == null) { //如果又是一个staleSlot，也执行清空操作
                        e.value = null;
                        tab[i] = null;
                        size--;
                    } else { //key不为null
                        int h = k.threadLocalHashCode & (len - 1);//得到k的取模下标
                        if (h != i) { //如果不相等，说明k是因为冲突，才会放到i位置。而且，不考虑环形数组的话，h肯定比i小
                            tab[i] = null;//先把i位置清空
    
                            // Unlike Knuth 6.4 Algorithm R, we must scan until
                            // null because multiple entries could have been stale.
                            while (tab[h] != null)//再从h出发（不冲突的话，k就应该放到h位置），找到不冲突的位置
                                h = nextIndex(h, len);
                            //当退出时，h位置是空的
                            tab[h] = e;//此时再把e赋值为h位置。当然也有可能，最终新的h还是等于i
                        }
                    }
                }
                //当循环退出，tab[i]) == null
                return i;
            }

expungeStaleEntry函数，看名字就知道是用来清理stale entry的。而且get、set、remove、resize都可能调用到它，实际上它也确实是用来处理stale entry的主要函数。

*  循环从来向后搜索连续段，当遇到null entry时（是指循环开始前就为null的entry），停止。
 *  每次循环中，遇到stale entry，清空它。
 *  每次循环中，遇到取模下标不是其实际下标的entry，为其rehash，以使得它移动到更靠近取模下标的位置上去。

## set操作 ##

set会被ThreadLocal的set方法直接调用，如果含有key的entry存在，那么更新value即可；否则新建一个entry即可。它可能会有后续调用。

private void set(ThreadLocal<?> key, Object value) { 
    
                Entry[] tab = table;
                int len = tab.length;
                int i = key.threadLocalHashCode & (len-1);//获得取模下标
                //循环开始，获得i位置的entry
                for (Entry e = tab[i];
                     e != null;//当循环停止时，i位置的entry肯定null
                     e = tab[i = nextIndex(i, len)]) { //每次循环后，i使用nextIndex移动i，并赋值e
                    ThreadLocal<?> k = e.get();
    
                    if (k == key) { //当前循环找到了key所在的entry
                        e.value = value;//设置新的value
                        return;
                    }
    
                    if (k == null) { //当前循环找到了一个stale entry
                        replaceStaleEntry(key, value, i);
                        return;
                    }
                }
                //循环结束，i为最终的插入位置
                tab[i] = new Entry(key, value);
                int sz = ++size;
                //cleanSomeSlots返回真说明有stale entry被清空了，size肯定减小了；
                //只有当 cleanSomeSlots返回假 且到达阈值时，才肯定需要rehash
                if (!cleanSomeSlots(i, sz) && sz >= threshold)
                    rehash();
            }

*  循环中，向后搜索连续段。
 *  如果进入`if (k == key)`分支，说明找到了含有key的entry，更新value即可。
 *  如果进入`if (k == null)`分支，说明只是遇到了一个stale entry，但之后的处理不能再交给自己的剩余循环了，因为自己的循环没有对stale entry进行处理。显然replaceStaleEntry做了足够的处理，以至于这里都直接返回了。
    
     *  传入参数i ，是为了让replaceStaleEntry，从剩余进度继续搜索下去。
     *  传入参数key和value，是为了replaceStaleEntry可以找到含有key的entry，并在找到的情况下进行value替换。
     *  replaceStaleEntry会对搜索过程中遇到的stale entry进行处理的，现在我们对replaceStaleEntry简单理解到这样即可。
 *  如果循环结束，那么说明确实没有一个 含有key的entry，那么新建一个entry即可。
 *  最后，如果cleanSomeSlots函数启发式搜索没有清理掉一个stale entry（注意，如果cleanSomeSlots函数清理掉至少一个，那么size也会变化），且size到达threshold时，需要扩容。

replaceStaleEntry函数中，无论怎样，都会把传入的key和value塞到staleSlot所在的下标上去，只不过有两种情况都会达到这个目标，具体看注释。另外，该函数会把staleSlot参数所在的run里的所有stale entry都给清理掉。  
术语定义：

*  run：一个run指给定索引前后延伸的连续段，注意，延伸是考虑到环形数组了的。

private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                           int staleSlot) { 
                Entry[] tab = table;
                int len = tab.length;
                Entry e;
    
                // 向前的连续段中，寻找最靠前的stale entry的索引
                int slotToExpunge = staleSlot;//slotToExpunge作为清理stale的起点
                for (int i = prevIndex(staleSlot, len);//向前寻找别的stale entry的索引
                     (e = tab[i]) != null;//直到向前到达了第一个为null的entry
                     i = prevIndex(i, len))
                    if (e.get() == null)
                        slotToExpunge = i;//这个索引可能多次被替换。
                        //即使向前找到了多个stale entry，只保留最靠前的那个的索引
                //循环结束，slotToExpunge要么不变，要么向前移动了
                        
    
                // 向后的连续段中，寻找最靠后的stale entry的索引。
                // 当连续段结束，或者找到相同key时，循环结束
                for (int i = nextIndex(staleSlot, len);//向后移动i
                     (e = tab[i]) != null;//直到向后到达了第一个为null的entry
                     i = nextIndex(i, len)) { 
                    ThreadLocal<?> k = e.get();
    
                    // 如果找到了key，循环会结束。
                    if (k == key) { 
                        e.value = value;//先将value，设置为找到的key所在的entry
    
                        tab[i] = tab[staleSlot];//交换staleSlot和i索引的entry
                        tab[staleSlot] = e;
    
                        // 如果相等，说明staleSlot之前的连续段中，没有stale entry。
                        // 这里有两种情况，如果不同，可能是slotToExpunge向前移动了，
                        // 此时i肯定在slotToExpunge后面，执行slotToExpunge = i，再
                        // 执行expungeStaleEntry将会漏掉stale entry。
                        // 
                        // 如果不同，还可能是slotToExpunge向后移动了，只能是for循环外
                        // 的if分支执行的，此时slotToExpunge已经停留在staleSlot之后的
                        // 第一个stale entry上了，而现在的i肯定比slotToExpunge小，所以
                        // 不能再往后移动，不然执行expungeStaleEntry将会漏掉stale entry。
                        if (slotToExpunge == staleSlot)
                            slotToExpunge = i;
                        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                        return;
                    }
    
                    // 分析同上
                    if (k == null && slotToExpunge == staleSlot)
                        slotToExpunge = i;
                    //总之，slotToExpunge要么停留之前的最靠前的stale entry上，
                    //要么停留在之后的第一个stale entry上。
                }
                //运行到这里，说明staleSlot向后的连续段中，没有找到key
    
                // 效果和上面其实一样，还是value设置在了staleSlot位置的entry里
                // 只不过上面先设置到别处，再交换过来
                tab[staleSlot].value = null;
                tab[staleSlot] = new Entry(key, value);
    
                // 正如上面分析，如果二者相等，说明向前向后的连续段中，都没有发现stale entry
                // 也就不需要执行清理操作了
                if (slotToExpunge != staleSlot)
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            }

*  定义了一个slotToExpunge，它代表需要从这个索引开始往后清理stale entry（当然，是通过expungeStaleEntry清理的）。初始值为staleSlot。
 *  slotToExpunge，它刚开始等于staleSlot。如果最终slotToExpunge不等于staleSlot，那么它的值为 staleSlot所在的run里，最前面的stale entry的所在索引。
 *  同时，关于slotToExpunge还有一个结论：以该函数执行前作为观察标准，staleSlot所在的run里，如果除了参数staleSlot索引以外，没有任何的stale entry，那么slotToExpunge肯定没有变化，还是等于初始值staleSlot。

理解到以上两点，就基本理解到replaceStaleEntry函数的逻辑了。对了，我们先把staleSlot所在的run分成两部分，staleSlot之前的部分，和staleSlot之后的部分。

*  在`for (int i = prevIndex(staleSlot, len);`循环里，遍历run里staleSlot之前的部分，并最终将slotToExpunge停留在最靠前的stale entry的索引。当然，如果遍历过程中，没有发现stale entry，slotToExpunge不变。
 *  在`for (int i = nextIndex(staleSlot, len);`循环里，遍历run里staleSlot之后的部分：
    
     *  如果当前循环没有发现key，那么执行`if (k == null && slotToExpunge == staleSlot)`分支，前者条件成立，说明当前循环的是个stale entry；后者条件成立，说明run里staleSlot之前的部分，没有发现stale entry，且说明之前的循环过程中也没有发现stale entry，所以slotToExpunge保持了不变。如果二者都成立，说明slotToExpunge可以往后移动，因为要保持“它的值为 staleSlot所在的run里，最前面的stale entry的所在索引”。
     *  显然，在这个循环里，slotToExpunge只能移动一次，因为要保持“它的值为 staleSlot所在的run里，最前面的stale entry的所在索引”。
     *  如果当前循环发现了key，先把key所在entry更新value，然后交换i下标和staleSlot下标的entry，所以，最终效果还是“传入的key和value塞到staleSlot所在的下标上去”。并且不用担心交换后i 下标的stale entry，因为slotToExpunge肯定比 当前的i 小，最后一定会清理到的。
        
         *  注意，这里同样有`slotToExpunge == staleSlot`，解释同上，总之slotToExpunge只能移动一次。
         *  最后，来一套`cleanSomeSlots(expungeStaleEntry(slotToExpunge), len)`操作。

如果第二个循环也正常退出，继续执行了，说明在staleSlot所在的run里确实没有这个key。那么先执行“传入的key和value塞到staleSlot所在的下标上去”。当slotToExpunge不等于staleSlot，说明这个run里确实有stale entry，然后来一套`cleanSomeSlots(expungeStaleEntry(slotToExpunge), len)`操作。

cleanSomeSlots函数启发式地扫描并清空stale entry，其实启发是指扫描次数不一定是多少次。当别的函数调用到该函数时，参数n要么为个数，要么为容量。

/** * 启发式地扫描stale entry,其实启发是指扫描次数。 * 扫描还是往后移动索引。 * * @param i 一个是有效entry的索引。所以扫描从i之后开始 * * @param n 用来控制扫描的次数。次数可为log2(n)次，但如果扫描到 * stale entry，那么不管已扫描次数，再扫描log2(容量)次。 * * @return 返回true如果扫描并清空到至少一个stale entry */
            private boolean cleanSomeSlots(int i, int n) { 
                boolean removed = false;
                Entry[] tab = table;
                int len = tab.length;
                do { 
                    i = nextIndex(i, len);//另i往后移动
                    Entry e = tab[i];
                    if (e != null && e.get() == null) { //检测到i位置的entry是一个stale entry
                        n = len;//更新n为容量，接下来至少又得循环log2(容量)次
                        removed = true;
                        i = expungeStaleEntry(i);//返回i之后第一个为null的entry的索引，使得i跳跃
                    }
                } while ( (n >>>= 1) != 0);//n无符号右移，只是用来控制循环次数
                //
                return removed;
            }

*  执行循环，如果循环中一次都没有发现stale entry，那么只会循环 l o g 2 n log\_2n log2n次，因为n一直在无符号右移。
 *  如果循环中发现了一次stale entry，那么不管之前执行了多少次循环，之后也至少执行 l o g 2 c a p a c i t y log\_2capacity log2capacity次循环（n会更新为容量）。由于expungeStaleEntry的执行，i 可能会跳跃到 i 之后连续段的第一个null entry，然后下一次循环i 再移动。

private void rehash() { 
                expungeStaleEntries();
    
                // 阈值本是2/3的容量，这里运算后，>=右边是等于1/2容量
                // 所以降低了阈值来判断是否需要resize
                if (size >= threshold - threshold / 4)
                    resize();
            }
    
            /** * 检查每个元素是否为stale entry */
            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)//发现stale entry
                        //或者你以为可以j = expungeStaleEntry(j),毕竟expungeStaleEntry会清理之后连续段的stale。
                        //但是这样可能使得j直接跳回0，或者0之后的附近索引，然后造成再一次的循环。
                        expungeStaleEntry(j);
                }
            }
    
            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) { //遇到了stale entry
                            e.value = null; //清空stale entry
                        } 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;
            }

当然还有rehash函数、expungeStaleEntries函数、resize函数，这几个比较简单。注意在expungeStaleEntries函数里，或许你以为可以`j = expungeStaleEntry(j)`,毕竟expungeStaleEntry会清理之后连续段的stale，但是这样可能使得j直接跳回0，或者0之后的附近索引，然后造成再一次的循环。

## 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();//父类Reference的方法，令父类成员referent置null
                        //使得e变成了stale entry
                        expungeStaleEntry(i);
                        return;
                    }
                }
            }