Java8 ThreadLocal源码阅读

ThreadLocal 原理

每个线程内部维护着一个 ThreadLocalMap，这个 Map 的底层是由一个 Entry 数组实现的。Entry 中的 key 为弱引用类型，指向 ThreadLocal 本身，value 则是实际存储的变量 Object。

概述

ThreadLocal 的作用在于提供了「线程内的局部变量」，该变量在线程的生命周期内起作用，减少同一个线程内多个函数或者组件之间一些公共变量的传递的复杂度。

其他线程无法访问 ThreadLocal 内的变量，这样就隔离了多个线程间的资源，也不会出现线程安全问题。

Get 策略

public T get() {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null)
            return (T)e.value;
    }
    return setInitialValue();
}

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

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

1. 获取当前线程。
2. 获取当前线程的 ThreadLocalMap。
3. 如果 ThreadLocalMap 不为空，以 ThreadLocal 的引用作为 key 来在 ThreadLocalMap 中获取对应的value e。
4. if (e != null && e.get() == key)，返回 e。
5. ThreadLocalMap 为 null 或 value 为 null，则调用 setInitialValue() 方法返回初始值。

Set 策略

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

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

1. 获取当前线程。
2. 获取当前线程的 ThreadLocalMap。
3. ThreadLocalMap 不为 null，将 value 放入 key 为当前 ThreadLocal 的槽位中。
4. 如果ThreadLocalMap 为 null，则新建一个 ThreadLocalMap 并将 value 放入 key 为当前 ThreadLocal 的槽位中。

Remove 策略

public void remove() {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if (m != null)
        m.remove(this);
}

ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

1. 获取当前线程的 ThreadLocalMap。
2. 如果 ThreadLocalMap 不为 null，则清除。
3. 注意这里的成员变量 threadLocals 其实就是 ThreadLocalMap。

扩容策略

// threshold是数组长度的2/3
private void setThreshold(int len) {
    threshold = len * 2 / 3;
}

// 判断是否需要扩容
if (!cleanSomeSlots(i, sz) && sz >= threshold){
    rehash();
}

private void rehash() {
    // 全量清除stale entry，会导致size变化
    expungeStaleEntries();
   // size大于等于3/4扩容阈值才会扩容
    if (size >= threshold - threshold / 4)
        resize();

private void resize() {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    // 新建一个数组，按照原来容量的2倍扩容
    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();
            // 其实这里也有一个判断key是否为null并将value设为null的操作
            // 都是为了避免内存泄漏
            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;
}
}

1. 判断是否需要扩容，主要是 !cleanSomeSlots(i, sz) 比较难理解，cleanSomeSlots() 会从当前插入元素的位置往后扫描 table 中的元素并判断是否是 stale entry(即key 为 null 的 entry)，如果找到则调用 expungeStaleEntry() 方法清理。如果找到 stale entry 则返回 true，否则返回 false。在expungeStaleEntry() 方法中，如果清除了 stale entry 就会导致 size—，这样情况下，set 新的 entry 时就可能不用扩容啦，所以才需要在这里判断一下。
2. 调用 rehash() 方法，此时还未真正扩容，先全量清除stale entry，再判断size是否大于等于3/4扩容阈值才会真正扩容。
3. 调用 resize() 扩容，不同于 ArrayList 中的 1.5 倍扩容，这里是按照 2倍 扩容，值得注意的是扩容的过程中也同时清理了 key 为 null 的 stale entry。

简单来说：

1. 当数组元素数量达到了扩容阈值threshold(即数组容量的2/3)且找不到stale entry后，进入下一步。
2. 执行全量清理 stale entry，如果清理后的元素数量大于3/4扩容阈值(即数组容量的1/2)，进入下一步。
3. 按照 2 倍容量执行真正的扩容。

哈希冲突问题

不同于 HashMap 中的链表法，ThreadLocalMap 采用的是开放地址法(线性探测)来解决哈希冲突问题。同时，不同于 HashMap 中的链表或红黑树，ThreadLocalMap 仅仅采用了数组来维护 Map。

注意到 ThreadLocal 中的一个魔数 HASH_INCREMENT = 0x61c88647，ThreadLocalMap 就是通过这个魔数来提高散列性以减少哈希碰撞的概率。

0x61c88647可以理解为黄金分割数(0.618)乘以2的32次方，它可以保证 nextHashCode 生成的哈希值，均匀的分布在2的N次方的数组里，且小于2的32次方。

但是尽管该方法可以有效减少哈希冲突的概率，但并不能完全避免哈希冲突，如果哈希冲突出现， ThreadLocal 会通过线性探测(步长加1或减1，寻找下一个相邻的位置)来查找下一个可用的槽位存放新的 entry。

这里的细节是如果槽位的 key 存放的是同一个对象，则覆盖 value，如果槽位存放的 key 为 null，则会替换它的位置。

不采用线程 id 来作为 ThreadLocalMap key的原因

因为一个线程中可以有多个 ThreadLocal 对象，所以 ThreadLocalMap 中可以有多个键值对，而如果使用线程 id 作为 key，就只有一个键值对。

Entry 采用 WeakReference 的原因

作者在注释中说道：

To help deal with very large and long-lived usages, the hash table entries use WeakReferences for keys.
为了保证在大量生命周期长对象存在时Map的高效可利用性，使用了WeakReferences来作为key。

如果 key 使用的是强引用，当引用 ThreadLocal 的对象被 GC 回收时，如果 ThreadLocalMap 还持有 ThreadLocal 的强引用且没有被手动删除，ThreadLocal 就永远不会被回收，导致 Entry 内存泄漏。

而如果 key 使用的是弱引用的话，当引用 ThreadLocal 的对象被 GC 回收时，由于 ThreadLocalMap 的 key 为弱引用类型，即使没有手动删，key 也会被 GC 回收。这样 value 在下一次 ThreadLocalMap 调用set()，get()，remove() 方法时就会被清除。

ThreadLocal 的内存泄漏问题

内存泄漏(Memory leak)和内存溢出(Out of memory)的区别：

• 内存溢出是指程序在申请新的内存时，没有足够的内存空间供其使用。
• 内存泄漏是指程序申请完内存后，无法释放已申请的内存空间，不再使用的对象或者变量仍占内存空间。
• Memory leak会最终会导致Out of memory！

导致 ThreadLocal 内存泄漏的原因：

ThreadLocalMap 中使用 ThreadLocal 的弱引用作为 key，在没有外部对象强引用时，弱引用的 key 在 GC 中会被回收，而 value 不会回收，从而导致内存泄漏。

这种情况下，key 为 null 的 Entry 的 value 会一直存在一条强引用链：

ThreadLocal Ref -> Thread -> ThreaLocalMap -> Entry -> value

即内存泄漏的根源在于没有及时删除 key 对应的 value，而不是采用了 WeakReference。

实际上作者已经在源码中做出了优化来避免该问题，在源码中处处可见删除 stale entry 的操作。

在 ThreadLocal的 get()、set()、remove() 方法调用时都会有额外的操作来清除 ThreadLocalMap 中的 stale entry。但如果一直没有执行 get()、set()、remove() 这些方法，还是避免不了内存泄漏，所以 remove() 方法就变得十分重要了。

如何避免内存泄漏：

1. 调用 remove() 方法，将 Entry 和 Map 的引用关系移除，这样整个 Entry 对象在 GC Roots 分析后就变成不可达了，下次 GC 的时候就可以被回收。

2. 手动将 value 设为 null，让 JVM 进行回收。

源码阅读

package java.lang;
import java.lang.ref.*;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Supplier;

/**
 * 这个类提供了一个线程本地的变量（thread-local variables）
 * 这些变量在被共享访问的情况下在【不同的线程】里是【独立】的。在多线程条件下，每一个线程通过get和set方法来访问该变量，并独立地初始化变量副本(各个线程里的变量相对独立于其他线程内的变量)
 * 在类中的ThreadLocal实例通常来说都是private static类型类型，目的是为了将状态与线程关联(例如用户ID或事务ID)
 *
 * @author  Josh Bloch and Doug Lea
 * @since   1.2
 */
public class ThreadLocal<T> {
    /**
     * ThreadLocals基于每个线程的线性探测的Hash Maps（ThreadLocalMap类型），将Thread类的threadLocals属性与线程关联
     * 在该Hash Map中，key为ThreadLocal，但实质上通过threadLocalHashCode作为哈希值查找
     * 这个哈希值只对ThreadLocalMaps有用，用于排除在相同的线程中构造ThreadLocals引起的冲突
     */
    private final int threadLocalHashCode = nextHashCode();

    /**
     * 下一个Hash Code，原子性更新，起始于0
     */
    private static AtomicInteger nextHashCode =
        new AtomicInteger();

    /**
     * 每个ThreadLocal key的hashCode累加值
     * 为了让HashCode能均匀的分布在2的N次方的数组里，减少哈希碰撞概率
     */
    private static final int HASH_INCREMENT = 0x61c88647;

    /**
     * 返回下一个Hash Code，注意是先get再add
     */
    private static int nextHashCode() {
        return nextHashCode.getAndAdd(HASH_INCREMENT);
    }

    /**
     * 返回当前线程的ThreadLocal初始值(null)
     * 当线程第一次调用get方法访问该变量时将会调用该方法(若get前调用了set方法则不会调用initialValue()方法)
     * 通常每个线程最多调用一次该方法，但如果remove后调用get方法，则会再次调用该方法
     * 可用于被子类重写
     */
    protected T initialValue() {
        return null;
    }

    /**
     * 创建一个ThreadLocal变量（JDK1.8中新增的方法）
     * 提供一个Supplier的lamda表达式用来当做初始值
     */
    public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
        return new SuppliedThreadLocal<>(supplier);
    }

    /**
     * 无参构造方法
     */
    public ThreadLocal() {
    }

    /**
     * 返回当前线程的线程ThreadLocal值
     * 如果当前线程的ThreadLocal为空，则会先初始化该线程的ThreadLocal
     */
    public T get() {
        // 获取当前线程
        Thread t = Thread.currentThread();
        // 获取当前线程的ThreadLocalMap
        ThreadLocalMap map = getMap(t);
        // 如果ThreadLocalMap不为空
        if (map != null) {
            ThreadLocalMap.Entry e = map.getEntry(this);
            if (e != null) {
                @SuppressWarnings("unchecked")
                T result = (T)e.value;
                // 返回对应变量值
                return result;
            }
        }
        // 为空，则调用setInitialValue()方法返回初始值
        return setInitialValue();
    }

    /**
     * 调用set()方法用于初始化值
     * 如果重写了该set()方法，则会使用重写的方法
     */
    private T setInitialValue() {
        // 获取初始化值
        T value = initialValue();
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        // 如果ThreadLocalMap不为空
        if (map != null)
            map.set(this, value);
        // 否则，调用createMap()创建ThreadLocalMap
        else
            createMap(t, value);
        // 返回初始值
        return value;
    }

    /**
     * 设置当前线程的ThreadLocal的拷贝为特定值
     * 大多数的子类不需要重写此方法，只需要单独重写initialValue()就足以设置ThreadLocal值
     */
    public void set(T value) {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null)
            map.set(this, value);
        else
            createMap(t, value);
    }

    /**
     * 删除当前线程的ThreadLocal变量值
     * 如果调用该方法后该ThreadLoca变量被当前线程访问，则会调用initialValue()进行初始化(除非这期间内，当前线程调用了set()方法)
     * 可能会导致当前线程多次调用initialValue()方法
     */
     public void remove() {
         ThreadLocalMap m = getMap(Thread.currentThread());
         if (m != null)
             m.remove(this);
     }

    /**
     * 获取与ThreadLocal关联的ThreadLocalMap，可在InheritableThreadLocal中被重写
     */
    ThreadLocalMap getMap(Thread t) {
        return t.threadLocals;
    }

    /**
     * 创建与ThreadLocal关联的ThreadLocalMap，可在InheritableThreadLocal中被重写
     */
    void createMap(Thread t, T firstValue) {
        t.threadLocals = new ThreadLocalMap(this, firstValue);
    }

    /**
     * 用于创建可继承的ThreadLocalMap的工厂方法
     */
    static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
        return new ThreadLocalMap(parentMap);
    }

    /**
     * Method childValue is visibly defined in subclass
     * InheritableThreadLocal, but is internally defined here for the
     * sake of providing createInheritedMap factory method without
     * needing to subclass the map class in InheritableThreadLocal.
     * This technique is preferable to the alternative of embedding
     * instanceof tests in methods.
     */
    T childValue(T parentValue) {
        throw new UnsupportedOperationException();
    }

    /**
     * An extension of ThreadLocal that obtains its initial value from
     * the specified {@code Supplier}.
     */
    static final class SuppliedThreadLocal<T> extends ThreadLocal<T> {

        private final Supplier<? extends T> supplier;

        SuppliedThreadLocal(Supplier<? extends T> supplier) {
            this.supplier = Objects.requireNonNull(supplier);
        }

        @Override
        protected T initialValue() {
            return supplier.get();
        }
    }

    /**
     *  ThreadLocalMap是用于维护ThreadLocal变量的定制HashMap
     *  没有暴露任何操作给外部的ThreadLocal
     *  ThreadLocalMap是内部私有类，允许在Thread中声明为fields
     *  为了保证在大量生命周期长对象存在时Map的高效可利用性，使用了WeakReferences来作为key
     *  如果hash table空间不足，key为null的entry就会被清理掉
     */
    static class ThreadLocalMap {

        /**
         * ThreadLocalMap内的Entry继承自WeakReference(弱引用，会导致内存泄漏)
         * 如果key为空(entry.get() == null)，意味着key不再被引用，会从table中删去
         * 这样的entry也被称为"stale entries"
         */
        static class Entry extends WeakReference<ThreadLocal<?>> {
            // ThreadLocal的值
            Object value;

            Entry(ThreadLocal<?> k, Object v) {
                super(k);
                value = v;
            }
        }

        /**
         * 初始化容量为16
         */
        private static final int INITIAL_CAPACITY = 16;

        /**
         * 存放entry的table，会在必要时扩容
         * 由于一个线程可以持有多个ThreadLocal，所以是数组
         */
        private Entry[] table;

        /**
         * table中的Enrty数量
         */
        private int size = 0;

        /**
         * 扩容阈值，默认为0
         */
        private int threshold; // Default to 0

        /**
         * 设置扩容阈值为临界条件的2/3
         * 注意：ThreadLocalMap没有负载因子，扩容策略采用的是 len * 2 / 3
         */
        private void setThreshold(int len) {
            threshold = len * 2 / 3;
        }

        /**
         * 获取索引i的下一个table索引 
         */
        private static int nextIndex(int i, int len) {
            return ((i + 1 < len) ? i + 1 : 0);
        }

        /**
         * 获取索引i的前一个table索引
         */
        private static int prevIndex(int i, int len) {
            return ((i - 1 >= 0) ? i - 1 : len - 1);
        }

        /**
         *  构建一个ThreadLocalMap，并将Entry(firstKey, firstValue)放入到hashMap中
         *  构建的过程是lazily的，即我们只会在至少有一个entry被put进map时才会构建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);
        }

        /**
         * 构建一个新的包含父类中所有ThreadLocals的map，该方法只会被createInheritedMap()调用
         * (即将父线程中的ThreadLocal实例都复制到子线程中)
         */
        private ThreadLocalMap(ThreadLocalMap parentMap) {
            // 获取父线程的table
            Entry[] parentTable = parentMap.table;
            int len = parentTable.length;
            setThreshold(len);
            // 子线程的map长度和父线程map长度一致
            table = new Entry[len];
            // 拷贝
            for (int j = 0; j < len; j++) {
                Entry e = parentTable[j];
                if (e != null) {
                    @SuppressWarnings("unchecked")
                    ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
                    if (key != null) {
                        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);
                        table[h] = c;
                        size++;
                    }
                }
            }
        }

        /**
         * 通过key获取Entry
         * 
         * 由于ThreadLocalMap采用开放定址法(线性探测)，所以当前key的HashCode和元素在数组中的索引并不一定完全对应，这里采取了一个快捷方式(先直接通过索引拿到entry)
         * 若索引没有命中，则调用getEntryAfterMiss继续查找
         * 这样处理是为了最大限度直接命中entry
         */
        private Entry getEntry(ThreadLocal<?> key) {
            int i = key.threadLocalHashCode & (table.length - 1);
            // 先从tabel直接找entry
            Entry e = table[i];
            // 找到则返回
            if (e != null && e.get() == key)
                return e;
            // 否则调用getEntryAfterMiss()方法
            else
                return getEntryAfterMiss(key, i, e);
        }

        /**
         * 通过HashCode作为索引查找没命中时调用的entry查找方法
         */
        private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
            Entry[] tab = table;
            int len = tab.length;
            // 从i开始，一直往下找，直至找到为止
            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;
        }

        /**
         * 设置ThreadLocal的变量值
         * 由于entry是弱引用，所以其引用的ThreadLocal可能会被GC回收，因此在插入元素时，从hash函数计算的索引i开始查找
         * (1) 若tab[i]为空，表明位置可用，则直接放入该位置
         * (2) 若tab[i]的key等于插入的key，则更新该位置处的value
         *（3) 若tab[i]的key为null，说明key已被GC回收，则调用replaceStaleEntry将元素放入该位置
         */
        private void set(ThreadLocal<?> key, Object value) {

            // 在set中没有使用像get中的快捷方式
            // 原因是set中覆盖entry的操作与新建entry一样常见
            // 在这种情况下，直接通过索引查找的快捷方式查找失败的概率会大得多

            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) {
                    // 则覆盖value
                    e.value = value;
                    return;
                }
                // 如果key为null
                if (k == null) {
                    // 调用replaceStaleEntry()替换该位置的元素
                    replaceStaleEntry(key, value, i);
                    return;
                }
                // 继续向后一个位置查找，直到找到空的位置
            }

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

        /**
         * 删除entry
         */
        private void remove(ThreadLocal<?> key) {
            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode & (len-1);
            // 遍历table
            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                // 如果key相等，则移除该entry
                if (e.get() == key) {
                    e.clear();
                    expungeStaleEntry(i);
                    return;
                }
            }
        }

        /**
         * 在set操作中，使用特定的key替换陈旧的entry(stale entry，即为null的entry)
         * 副作用是，该方法会清除所有在stale entry之间的"run"("run"指的是两个stale entry之间的空槽位)
         */
        private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                       int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;
            Entry e;

            // 往前查找第一个key为null的stale entry
            int slotToExpunge = staleSlot;
            for (int i = prevIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = prevIndex(i, len))
                // 如果entry的key及value为null
                if (e.get() == null)
                    // 记下该索引
                    slotToExpunge = i;

            // 找到传进来的key
            // 或者是在传进来的staleSlot后面第一个stale entry
            for (int i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();

                // 如果找到了key，则需要用stale entry与其交换以维护hash table的顺序
                // 然后可以将较新的stale slot或其他在上面循环中遇到的其他stale slot 
                // 传给expungeStaleEntry()方法以清除或rehash这个“run”中的其他所有entry
                if (k == key) {
                    e.value = value;

                    tab[i] = tab[staleSlot];
                    tab[staleSlot] = e;

                    // 如果存在，则开始清除前面陈旧的entry
                    if (slotToExpunge == staleSlot)
                        slotToExpunge = i;
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    return;
                }

                // 如果我们没在向后扫描过程中找到stale entry
                // 那么slotToExpunge就是第一个stale entry的下标
                if (k == null && slotToExpunge == staleSlot)
                    slotToExpunge = i;
            }

            // 如果key在table中不存在，则在staleSlot中新建一个stale entry
            tab[staleSlot].value = null;
            tab[staleSlot] = new Entry(key, value);

            // 如果还有其他stale entry存在于"run"中，则清除
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }

        /**
         * 通过rehash来清除所有可能发生冲突的位于staleSlot与下一个null slot间的stale entry
         */
        private int expungeStaleEntry(int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;

            // 清除位于staleSlot的entry
            tab[staleSlot].value = null;
            tab[staleSlot] = null;
            size--;

            // Rehash直到遇到为null的slot
            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;
        }

        /**
         * 启发式地搜索一些位置以查找清除stale entry
         * 当添加新元素或删除另一个stale entry时，将调用此方法
         * 这是对数级(log2n)级的扫描，是一种基于不扫描(快速但保留垃圾)和所有元素扫描之间的平衡
         * 这种方式会发现所有垃圾，但会导致一些插入操作需要O(n)的时间
         *
         * @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);
                Entry e = tab[i];
                if (e != null && e.get() == null) {
                    n = len;
                    removed = true;
                    i = expungeStaleEntry(i);
                }
            } while ( (n >>>= 1) != 0);
            return removed;
        }

        /**
         * 对table进行rehash
         * 首先扫描整个table并清理所有stale entry
         * 然后可能会缩小size并扩容
         */
        private void rehash() {
            //全量清除stale entry
            expungeStaleEntries();

            // 使用较小的扩容阈值(约threshold的3/4)防止rehash滞后
            if (size >= threshold - threshold / 4)
                resize();
        }

        /**
         * 翻倍table的容量(x2)
         */
        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;
        }

        /**
         * 清除table中的所有stale entry
         */
        private void expungeStaleEntries() {
            Entry[] tab = table;
            int len = tab.length;
            // 调用expungeStaleEntry循环清除
            for (int j = 0; j < len; j++) {
                Entry e = tab[j];
                if (e != null && e.get() == null)
                    expungeStaleEntry(j);
            }
        }
    }
}