ThreadLocal 学习笔记

学习目标

读懂 ThreadLocal 源码，理解其内部实现原理。根据 ThreadLocal 特点，总结出使用场景。

过程记录

第一次阅读 ThreadLocal 源码，在 IDE 中打开ThreadLocal.java 源文件，算上注释这个类下一共才 800 行不到的代码。之前没有阅读过相关文章，我们可以一点一点看起。
先粗略了看了一下类的内部，包含两个静态内部类 SuppliedThreadLocal 和 ThreadLocalMap、三个成员变量和若干个方法（没有数）。

ThreadLocal 的成员

// 当前的 HashCode 值
private final int threadLocalHashCode = nextHashCode();
// AtomicInteger 提供了原子性的操作
private static AtomicInteger nextHashCode = new AutomicInteger();
// 魔法值
private static final int HASH_INCREMENT = 0x61c88647;
// 每当创建 ThreadLocal 实例，这个值都会累加魔数
private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

为什么是 0x61c88647 ？ 为了让哈希码能均匀的分布在2的N次方的数组里，0x61c88647 可以有效的降低碰撞概率；

ThreadLocal 的 get 与 set

get()
get() 方法，首先通过 Thread.currentThread() 获取当前线程
getMap 返回了当前 Thread 中的 threadLocals成员变量

public T get() {
    // 获取当前线程
    Thread t = Thread.currentThread();
    // 获取 ThreadLocalMap
    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 为空，则会调用 setInitialValue()
setInitialValue()方法第一行会调用 initialValue()
然后再在当前线程中获取一次 ThreadLocalMap 如果不此时不为空，就把 initialValue 返回的值通过 ThreadLocalMap 的 set() 方法设置进去。如果 ThreadLocalMap 为空，则调用 createMap 方法。

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

createMap 方法内调用了 ThreadLocalMap(ThreadLocal<?> firstKey``, ``Object firstValue)构造方法

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

ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
    // 初始化 Entry[]
    // Default INITIAL_CAPACITY = 16 必须是2的倍数
    table = new Entry[INITIAL_CAPACITY];
    // 开放地址法 - 位运算，结果与取模相同，计算出需要存放的位置
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    // 将数据复制到对应位置
    table[i] = new Entry(firstKey, firstValue);
    // 设置 ENTRY 中的元素个数
    size = 1;
    // 设置扩容条件 超过2/3 即扩容
    setThreshold(INITIAL_CAPACITY);
}

Entry 通过弱引用的方式继承了 ThreadLocal，实现了 Key - Value 的形式

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

ThreadLocalMap

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)]) {
        // 顺序遍历 tab 上的位置数据
        ThreadLocal<?> k = e.get();
        if (k == key) {
            // 设置值
            e.value = value;
            return;
        }
        // 如果 k 为 null时，说明弱引用已经失效了
        if (k == null) {
            // 替换掉过时的 value
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    tab[i] = new Entry(key, value);
    int sz = ++size;
    // 调用 cleanSomeSlots 清楚无效的 entry
    // 如果满足条件测触发 rehash()
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                       int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;
            Entry e;
            // 这里采用从当前的 staleSlot 位置向前遍历
            // 是为了把前面所有的已经被回收的也一起释放空间出来
            int slotToExpunge = staleSlot;
            for (int i = prevIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = prevIndex(i, len))
                if (e.get() == null)
                    // 记录当前左手边第一个空的 entry 到staleSlot 之间key过期最小的index
                    slotToExpunge = i;
            // 获取 staleSlot 右边第一个空的 entry 
            for (int i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();
                // 说明之前已经存在相同的key, 要替换旧值并和前面的
                // 过期对象进行位置交换
                if (k == key) {
                    e.value = value;
                    tab[i] = tab[staleSlot];
                    tab[staleSlot] = e;
                    // 如果之前向前找, 没有找到过期的
                    // 前面已经把向后找的放到了[i]上
                    // 所以清理位置 i
                    if (slotToExpunge == staleSlot)
                        slotToExpunge = i;
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    // 清理了之后就会退出
                    return;
                }
                // 如果向前找没有找到过期对象
                // 那么就向后找, 如果向后找也没有找到
                // 那么整个数据组都没有过期的 key , 那就把该 key 设置到 staleSlot 位置上
                // staleSlot 位置总是存放的有效值
                if (k == null && slotToExpunge == staleSlot)
                    slotToExpunge = i;
            }
            // 如果 key 不存在, 新建一个新的 entry 放进去
            tab[staleSlot].value = null;
            tab[staleSlot] = new Entry(key, value);
            // 清理其他过期对象
            if (slotToExpunge != staleSlot)
                // 清理
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }

// 删除过期 entry, 帮助垃圾回收
private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    // 当前statleSlot 传入的是无效 entry 的 index
    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) {
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            // 因为是采用的是开放地址法, 所以删除的元素是多个冲突元素转给你的一个
            // 需要对后面元素往前移动, 如果不移动的话,后面的元素就永远访问不到了
            int h = k.threadLocalHashCode & (len - 1);
            // 不相等,说明是有冲突的
            if (h != i) {
                tab[i] = null;
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    return i;
}

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

rehash()

private void rehash() {
    // 清除过期 entry 
    expungeStaleEntries();
    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}
// 再扩充一倍 table
private void resize() {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    int count = 0;
    // 把旧数据重新 hash 一遍放到新数组里
    for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if (e != null) {
            ThreadLocal<?> k = e.get();
            if (k == null) {
                // 如果 key 已经失效了,则把 value 也置为空
                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. 使用 ThreadLocal 记录线程本地变量时， 会将ThreadLocalMap 绑定到本地线程上
2. Hash 使用的是开放地址法， 每次增加 0x61c88647 是为了减少碰撞次数，使得能够更均匀的分布在2的N次方数组里
3. ThreadLocalMap 并不是一个 Map 结构，内部的 Entry 而是使用了弱引用 LocalThread 为 Key，内部对象 Object value 作为 value 的一个 Key - Value 实现。
4. 默认的桶的数量为 16 ，初始化应该为 2 的倍数， 满足了resize() 条件后， 则会扩充2倍
5. 通过复写 initialValue() 实现默认值的返回
6. 调用 get() 和 set() 方法时，都可能会触发调用 expungeStaleEntry() 对过期 key 的清除，避免内存泄露
7. 如果set值时，index 冲突了，则会向后找位置， 在向后找位置的过程中如果遇到过期的Key 值则会触发 replaceStaleEntry 方法清除过期 entry ，replaceStaleEntry 接收三个参数，Key -> 要设置的 ThreadLocal ，Value -> Object ,以及当前过期的位置 i，方法先在 index（i） 查找左边过期的 entry 的 index 最小值，然后再获取右边过期的 key， 如果左边有过期的key，查看是否与有要设置的 key 是相同的，如果有的话先把新的Value 值设置到有效的 entry 上，并把当前 statleSlot 和 有效的 i 的entry 交换（此时 index：i 上的 entry 就是过期的 entry）， 接下来判断之前向左是否获取到了无效的key，如果有的话就调用 expungeStaleEntry 清除在左边获取的key的index，否则的话就清除当前当前 statleSlot 的值。然后调用 cleanSomeSlots 清除过期对象
8. 如果说会出现内存泄漏，那只有在出现了 key 为 null 的记录后，没有手动调用 remove() 方法，并且之后也不再调用 get()、set()、remove() 方法的情况下。

   使用场景

• 每个线程有自己的单独实例
• 实例需要在多个方法中共享，但不希望被多线程共享

  使用 ThreadLocal 来存储 Hibernate 中 Session

  解决Java7中SimpleDateFormat 线程安全问题

  附： 1.8 ThreadLocal.java 代码

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

/**

• This class provides thread-local variables. These variables differ from
• their normal counterparts in that each thread that accesses one (via its
• {@code get} or {@code set} method) has its own, independently initialized
• copy of the variable. {@code ThreadLocal} instances are typically private
• static fields in classes that wish to associate state with a thread (e.g.,
• a user ID or Transaction ID). *

• For example, the class below generates unique identifiers local to each

• thread.
• A thread’s id is assigned the first time it invokes {@code ThreadId.get()}
• and remains unchanged on subsequent calls.
• 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();
• }
• }

• Each thread holds an implicit reference to its copy of a thread-local

• variable as long as the thread is alive and the {@code ThreadLocal}
• instance is accessible; after a thread goes away, all of its copies of
• thread-local instances are subject to garbage collection (unless other
• references to these copies exist). *
• @author Josh Bloch and Doug Lea

• @since 1.2 / public class ThreadLocal { /*

  • ThreadLocals rely on per-thread linear-probe hash maps attached
  • to each thread (Thread.threadLocals and
  • inheritableThreadLocals). The ThreadLocal objects act as keys,
  • searched via threadLocalHashCode. This is a custom hash code
  • (useful only within ThreadLocalMaps) that eliminates collisions
  • in the common case where consecutively constructed ThreadLocals
  • are used by the same threads, while remaining well-behaved in

  • less common cases. */ private final int threadLocalHashCode = nextHashCode();

    /**

  • The next hash code to be given out. Updated atomically. Starts at

  • zero. */ private static AtomicInteger nextHashCode = new AtomicInteger();

    /**

  • The difference between successively generated hash codes - turns
  • implicit sequential thread-local IDs into near-optimally spread

  • multiplicative hash values for power-of-two-sized tables. */ private static final int HASH_INCREMENT = 0x61c88647;

    /**

  • Returns the next hash code. */ private static int nextHashCode() { return nextHashCode.getAndAdd(HASH_INCREMENT); }

    /**

  • Returns the current thread’s “initial value” for this
  • thread-local variable. This method will be invoked the first
  • time a thread accesses the variable with the {@link #get}
  • method, unless the thread previously invoked the {@link #set}
  • method, in which case the {@code initialValue} method will not
  • be invoked for the thread. Normally, this method is invoked at
  • most once per thread, but it may be invoked again in case of
  • subsequent invocations of {@link #remove} followed by {@link #get}. *

  • This implementation simply returns {@code null}; if the

  • programmer desires thread-local variables to have an initial
  • value other than {@code null}, {@code ThreadLocal} must be
  • subclassed, and this method overridden. Typically, an
  • anonymous inner class will be used. *

  • @return the initial value for this thread-local */ protected T initialValue() { return null; }

    /**

  • Creates a thread local variable. The initial value of the variable is
  • determined by invoking the {@code get} method on the {@code Supplier}. *
  • @param the type of the thread local’s value
  • @param supplier the supplier to be used to determine the initial value
  • @return a new thread local variable
  • @throws NullPointerException if the specified supplier is null

  • @since 1.8 */ public static ThreadLocal withInitial(Supplier<? extends S> supplier) { return new SuppliedThreadLocal<>(supplier); }

    /**

  • Creates a thread local variable.

  • @see #withInitial(java.util.function.Supplier) */ public ThreadLocal() { }

    /**

  • Returns the value in the current thread’s copy of this
  • thread-local variable. If the variable has no value for the
  • current thread, it is first initialized to the value returned
  • by an invocation of the {@link #initialValue} method. *

  • @return the current thread’s value of this thread-local */ 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(); }

    /**

  • Variant of set() to establish initialValue. Used instead
  • of set() in case user has overridden the set() method. *

  • @return the initial value */ 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; }

    /**

  • Sets the current thread’s copy of this thread-local variable
  • to the specified value. Most subclasses will have no need to
  • override this method, relying solely on the {@link #initialValue}
  • method to set the values of thread-locals. *
  • @param value the value to be stored in the current thread’s copy of

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

    /**

  • Removes the current thread’s value for this thread-local
  • variable. If this thread-local variable is subsequently
  • {@linkplain #get read} by the current thread, its value will be
  • reinitialized by invoking its {@link #initialValue} method,
  • unless its value is {@linkplain #set set} by the current thread
  • in the interim. This may result in multiple invocations of the
  • {@code initialValue} method in the current thread. *

  • @since 1.5 */ public void remove() { ThreadLocalMap m = getMap(Thread.currentThread()); if (m != null)

      m.remove(this);

    }

    /**

  • Get the map associated with a ThreadLocal. Overridden in
  • InheritableThreadLocal. *
  • @param t the current thread

  • @return the map */ ThreadLocalMap getMap(Thread t) { return t.threadLocals; }

    /**

  • Create the map associated with a ThreadLocal. Overridden in
  • InheritableThreadLocal. *
  • @param t the current thread

  • @param firstValue value for the initial entry of the map */ void createMap(Thread t, T firstValue) { t.threadLocals = new ThreadLocalMap(this, firstValue); }

    /**

  • Factory method to create map of inherited thread locals.
  • Designed to be called only from Thread constructor. *
  • @param parentMap the map associated with parent thread

  • @return a map containing the parent’s inheritable bindings */ 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 extends ThreadLocal {

    private final Supplier<? extends T> supplier;

    SuppliedThreadLocal(Supplier<? extends T> supplier) {

     this.supplier = Objects.requireNonNull(supplier);

    }

    @Override protected T initialValue() {

     return supplier.get();

    } }

    /**

  • ThreadLocalMap is a customized hash map suitable only for
  • maintaining thread local values. No operations are exported
  • outside of the ThreadLocal class. The class is package private to
  • allow declaration of fields in class Thread. To help deal with
  • very large and long-lived usages, the hash table entries use
  • WeakReferences for keys. However, since reference queues are not
  • used, stale entries are guaranteed to be removed only when

  • the table starts running out of space. */ static class ThreadLocalMap {

    /**

    • The entries in this hash map extend WeakReference, using
    • its main ref field as the key (which is always a
    • ThreadLocal object). Note that null keys (i.e. entry.get()
    • == null) mean that the key is no longer referenced, so the
    • entry can be expunged from table. Such entries are referred to

    • as “stale entries” in the code that follows. / static class Entry extends WeakReference> { /** The value associated with this ThreadLocal. / Object value;

      Entry(ThreadLocal<?> k, Object v) {

       super(k);
       value = v;

      } }

      /**

    • The initial capacity — MUST be a power of two. */ private static final int INITIAL_CAPACITY = 16;

      /**

    • The table, resized as necessary.

    • table.length MUST always be a power of two. */ private Entry[] table;

      /**

    • The number of entries in the table. */ private int size = 0;

      /**

    • The next size value at which to resize. */ private int threshold; // Default to 0

      /**

    • Set the resize threshold to maintain at worst a 2/3 load factor. / private void setThreshold(int len) { threshold = len 2 / 3; }

      /**

    • Increment i modulo len. */ private static int nextIndex(int i, int len) { return ((i + 1 < len) ? i + 1 : 0); }

      /**

    • Decrement i modulo len. */ private static int prevIndex(int i, int len) { return ((i - 1 >= 0) ? i - 1 : len - 1); }

      /**

    • Construct a new map initially containing (firstKey, firstValue).
    • ThreadLocalMaps are constructed lazily, so we only create

    • one when we have at least one entry to put in it. */ 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); }

      /**

    • Construct a new map including all Inheritable ThreadLocals
    • from given parent map. Called only by createInheritedMap. *

    • @param parentMap the map associated with parent thread. */ private ThreadLocalMap(ThreadLocalMap parentMap) { Entry[] parentTable = parentMap.table; int len = parentTable.length; setThreshold(len); 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++;
           }
       }

      } }

      /**

    • Get the entry associated with key. This method
    • itself handles only the fast path: a direct hit of existing
    • key. It otherwise relays to getEntryAfterMiss. This is
    • designed to maximize performance for direct hits, in part
    • by making this method readily inlinable. *
    • @param key the thread local object

    • @return the entry associated with key, or null if no such */ 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);

      }

      /**

    • Version of getEntry method for use when key is not found in
    • its direct hash slot. *
    • @param key the thread local object
    • @param i the table index for key’s hash code
    • @param e the entry at table[i]

    • @return the entry associated with key, or null if no such */ 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; }

      /**

    • Set the value associated with key. *
    • @param key the thread local object

    • @param value the value to be set */ private void set(ThreadLocal<?> key, Object value) {

      // We don’t use a fast path as with get() because it is at // least as common to use set() to create new entries as // it is to replace existing ones, in which case, a fast // path would fail more often than not.

      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); int sz = ++size; if (!cleanSomeSlots(i, sz) && sz >= threshold)

       rehash();

      }

      /**

    • Remove the entry for key. */ 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;
       }

      } }

      /**

    • Replace a stale entry encountered during a set operation
    • with an entry for the specified key. The value passed in
    • the value parameter is stored in the entry, whether or not
    • an entry already exists for the specified key. *
    • As a side effect, this method expunges all stale entries in the
    • “run” containing the stale entry. (A run is a sequence of entries
    • between two null slots.) *
    • @param key the key
    • @param value the value to be associated with key
    • @param staleSlot index of the first stale entry encountered while

    • searching for key. */ 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); }

      /**

    • Expunge a stale entry by rehashing any possibly colliding entries
    • lying between staleSlot and the next null slot. This also expunges
    • any other stale entries encountered before the trailing null. See
    • Knuth, Section 6.4 *
    • @param staleSlot index of slot known to have null key
    • @return the index of the next null slot after staleSlot
    • (all between staleSlot and this slot will have been checked

    • for expunging). */ 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; }

      /**

    • Heuristically scan some cells looking for stale entries.
    • This is invoked when either a new element is added, or
    • another stale one has been expunged. It performs a
    • logarithmic number of scans, as a balance between no
    • scanning (fast but retains garbage) and a number of scans
    • proportional to number of elements, that would find all
    • garbage but would cause some insertions to take O(n) time. *
    • @param i a position known NOT to hold a stale entry. The
    • scan starts at the element after i. *
    • @param n scan control: {@code log2(n)} cells are scanned,
    • unless a stale entry is found, in which case
    • {@code log2(table.length)-1} additional cells are scanned.
    • When called from insertions, this parameter is the number
    • of elements, but when from replaceStaleEntry, it is the
    • table length. (Note: all this could be changed to be either
    • more or less aggressive by weighting n instead of just
    • using straight log n. But this version is simple, fast, and
    • seems to work well.) *

    • @return true if any stale entries have been removed. */ 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; }

      /**

    • Re-pack and/or re-size the table. First scan the entire
    • table removing stale entries. If this doesn’t sufficiently

    • shrink the size of the table, double the table size. */ private void rehash() { expungeStaleEntries();

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

       resize();

      }

      /**

    • Double the capacity of the table. / 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; }

      /**

    • Expunge all stale entries in the table. */ 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);

      } } } } ```