ThreadLocal初衷是在线程并发时，解决共享问题，但是由于过度设计，比如弱引用和哈希碰撞，导致理解难度增大，使用成本高，反而成为故障高发点，容易出现内存泄漏，脏数据，共享对象更新等问题。

关于引用类型

在垃圾回收GC里已经介绍过

  • 强引用 Strong Reference
  • 软引用 Soft Reference
  • 弱引用 Weak Reference
  • 虚引用 Phantom Reference

ThreadLocal 引入了WeakReference. 原意是ThreadLocal对象消失后，占用内存被GC掉，但是实际使用中，不当操作会出现内存泄漏风险。

应用

普通场景

在使用SpringBoot编写Web后端时，有时候需要手动创建一个应用上下文(Context)来在一个进程里传递数据
如

  1. public class UserContext {
  2.     private static final ThreadLocal<String> user = new ThreadLocal<String>();
  4.     public static void add(String userName) {
  5.         user.set(userName);
  6.     }
  8.     public static void remove() {
  9.         user.remove();
  10.     }
  12.     public static String getCurrentUserName() {
  13.         return user.get();
  14.     }
  15. }

然后在拦截器里注册

  1. @Component
  2. public class LoginInterceptor extends HandlerInterceptorAdapter {
  4.     @Override
  5.     public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler) throws Exception {
  7.         HandlerMethod handlerMethod=(HandlerMethod)handler;
  8.         Method method=handlerMethod.getMethod();
  10.         // 。。。。
  11.         if (claims != null) {
  12.             // 将我们之前放到token中的userName给存到上下文对象中
  13.             UserContext.add(claims.getSubject());
  14.             return true;
  15.         }
  17.         return false;
  18.     }
  20.     @Override
  21.     public void afterCompletion(HttpServletRequest request, HttpServletResponse response, Object handler, Exception ex) throws Exception {
  22.         // 请求结束后要从上下文对象删除数据，如果不删除则可能会导致内存泄露
  23.         UserContext.remove();
  24.         super.afterCompletion(request, response, handler, ex);
  25.     }
  26. }

这样可以在Service里使用

  1. String username = UserContext.getCurrentUserName();

Spring

Spring采用Threadlocal的方式，来保证单个线程中的数据库操作使用的是同一个数据库连接，同时，采用这种方式可以使业务层使用事务时不需要感知并管理connection对象，通过传播级别，巧妙地管理多个事务配置之间的切换，挂起和恢复。
Spring框架里面就是用的ThreadLocal来实现这种隔离，主要是在TransactionSynchronizationManager这个类里面，代码如下所示:

  1. private static final Log logger = LogFactory.getLog(TransactionSynchronizationManager.class);
  3.  private static final ThreadLocal<Map<Object, Object>> resources =
  4.    new NamedThreadLocal<>("Transactional resources");
  6.  private static final ThreadLocal<Set<TransactionSynchronization>> synchronizations =
  7.    new NamedThreadLocal<>("Transaction synchronizations");
  9.  private static final ThreadLocal<String> currentTransactionName =
  10.    new NamedThreadLocal<>("Current transaction name");

Spring的事务主要是ThreadLocal和AOP去做实现的

源码

ThreadLocal可以实现线程之间数据的隔离，使用时只要先set，用的时候get，最后remove
线程使用ThreadLocal有三个重要的方法

  • set() 如果没有set操作的ThreadLocal，容易引起脏数据问题
  • get() 始终没有get操作的ThreadLocal对象是没有意义的
  • remove() 如果没有remove操作，容易引起内存泄漏。

    set()

    1.   public void set(T value) {
    2.       //获取当前线程
    3.       Thread t = Thread.currentThread();
    4.       //获取ThreadLocalMap对象
    5.       ThreadLocalMap map = getMap(t);
    6.       if (map != null)
    7.           map.set(this, value);
    8.       else
    9.           createMap(t, value);
    10.   }
    对于获取ThreadLocalMap对象的getMap（）
    1. ThreadLocalMap getMap(Thread t) {
    2.       return t.threadLocals;
    3. }
    4. //而Thraed中
    5. public class Thread implements Runnable {
    6.   ThreadLocal.ThreadLocalMap threadLocals = null;
    7.   ThreadLocal.ThreadLocalMap inheritableThreadLocals = null;
    8. }
    即每个Thread维护了自己的ThreadLocals变量，实现了数据隔离

    对于ThreadLocalMap底层

  1. static class ThreadLocalMap {
  3.         static class Entry extends WeakReference<ThreadLocal<?>> {
  4.             /** The value associated with this ThreadLocal. */
  5.             Object value;
  7.             Entry(ThreadLocal<?> k, Object v) {
  8.                 super(k);
  9.                 value = v;
  10.             }
  11.         }
  13.         /**
  14.          * The initial capacity -- MUST be a power of two.
  15.          */
  16.         private static final int INITIAL_CAPACITY = 16;
  18.         /**
  19.          * The table, resized as necessary.
  20.          * table.length MUST always be a power of two.
  21.          */
  22.         private Entry[] table;
  23.         //。。。。
  24. }

ThreadLocalMap并未实现Map接口，而Entry是弱引用。底层使用了一个数组来存每个Entry
image.png

  • 一个Thread有且仅有1个ThreadLocalMap对象
  • 一个Entry对象的Key弱引用指向一个ThreadLocal对象
  • 1个ThreadLocal对象可以存储多个Entry对象
  • 一个ThreadLocal对象可以被多个对象共享
  • ThreadLocal对象不持有Value，Value由Entry对象持有

ThreadLocalMap中数组的存储

ThreadLocalMap在存储的时候会给每一个ThreadLocal对象一个threadLocalHashCode，在插入过程中，根据ThreadLocal对象的hash值，定位到table中的位置i，
int i = key.threadLocalHashCode & (len-1)。

  1. private void set(ThreadLocal<?> key, Object value) {
  2.            Entry[] tab = table;
  3.             int len = tab.length;
  4.             int i = key.threadLocalHashCode & (len-1);
  5.             for (Entry e = tab[i];
  6.                  e != null;
  7.                  e = tab[i = nextIndex(i, len)]) {
  8.                 ThreadLocal<?> k = e.get();
  9.                 //如果位置i不为空，如果这个Entry对象的key正好是即将设置的key，那么就刷新Entry中的value；
  10.                 if (k == key) {
  11.                     e.value = value;
  12.                     return;
  13.                 }
  14.                 //如果当前位置是空的，就初始化一个Entry对象放在位置i上
  15.                 if (k == null) {
  16.                     replaceStaleEntry(key, value, i);
  17.                     return;
  18.                 }
  19.             }
  20.             tab[i] = new Entry(key, value);
  21.             int sz = ++size;
  22.             if (!cleanSomeSlots(i, sz) && sz >= threshold)
  23.                 rehash();
  24.         }

如果位置i的不为空，而且key不等于entry，那就找下一个空位置，直到为空为止

image.png

get()

  1.  private Entry getEntry(ThreadLocal<?> key) {
  2.             int i = key.threadLocalHashCode & (table.length - 1);
  3.             Entry e = table[i];
  4.             if (e != null && e.get() == key)
  5.                 return e;
  6.             else
  7.                 return getEntryAfterMiss(key, i, e);
  8.         }
  10.  private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
  11.             Entry[] tab = table;
  12.             int len = tab.length;
  13. // get的时候一样是根据ThreadLocal获取到table的i值，然后查找数据拿到后会对比key是否相等  if (e != null && e.get() == key)。
  14.             while (e != null) {
  15.                 ThreadLocal<?> k = e.get();
  16.               // 相等就直接返回，不相等就继续查找，找到相等位置。
  17.                 if (k == key)
  18.                     return e;
  19.                 if (k == null)
  20.                     expungeStaleEntry(i);
  21.                 else
  22.                     i = nextIndex(i, len);
  23.                 e = tab[i];
  24.             }
  25.             return null;
  26.         }

内存存放

在Java中，栈内存归属于单个线程，每个线程都会有一个栈内存，其存储的变量只能在其所属线程中可见，即栈内存可以理解成线程的私有内存，而堆内存中的对象对所有线程可见，堆内存中的对象可以被所有线程访问。
ThreadLocal实例实际上也是被其创建的类持有（更顶端应该是被线程持有），而ThreadLocal的值其实也是被线程实例持有，它们都是位于堆上，只是通过一些技巧将可见性修改成了线程可见。

共享线程ThreadLocal数据

使用InheritableThreadLocal可以实现多个线程访问ThreadLocal的值，我们在主线程中创建一个InheritableThreadLocal的实例，然后在子线程中得到这个InheritableThreadLocal实例设置的值。
这样
ThreadLocal threadLocal = new InheritableThreadLocal(); 

  1. public class Thread implements Runnable {
  2.   ……
  3.    if (inheritThreadLocals && parent.inheritableThreadLocals != null)
  4.       this.inheritableThreadLocals=ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);
  5.   ……
  6. }

如果线程的inheritThreadLocals变量不为空，比如我们上面的例子，而且父线程的inheritThreadLocals也存在，那么我就把父线程的inheritThreadLocals给当前线程的inheritThreadLocals。

createInheritedMap()其实是调用ThreadLocalMap的私有构造方法来产生一个实例对象，把父线程的不为null的变量的线程变量拷贝过来。

ThreadLocal副作用

对于ThreadLocal的弱引用，即使线程正在执行中，只要ThreadLocal对象引用被置为null，Entry的Key就会自动在下一次YGC时被回收，而在ThreadLocal使用Get() 和 Set() 时，又会自动地将那些key=null的value置为null，使value能够被垃圾回收，避免内存泄漏。但是事实并不如意。。。
正如ThreadLocal源码注释所述
ThreadLocal instances are typically private static fields in classess.
ThreadLocal对象通常作为私有静态变量使用，那么其生命周期至少不会随着线程的结束。
ThreadLocal会产生脏数据和内存泄漏，因为ThreadLocal有线程复用和内存常驻

脏数据

线程复用会产生脏数据。由于线程池会重用Thread对象，那么Thread绑定的类的静态属性ThreadLocal变量也会被重用。如果在实现的线程run() 方法体不显式地调用remove()清理与线程相关的ThreadLocal信息，那么如果下一线程不调用set()设置初始值，可能会get() 到重用信息

内存泄露

源码中使用static关键字修饰ThreadLocal ThreadLocal失去引用后，如果不进行remove()，那么这个线程执行后，通过ThraedLocal对象持有的String对象是不会被释放的。

贴一下ThreadLocal源代码（JDK8）：

  1. /*
  2.  * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
  3.  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4.  *
  5.  * This code is free software; you can redistribute it and/or modify it
  6.  * under the terms of the GNU General Public License version 2 only, as
  7.  * published by the Free Software Foundation.  Oracle designates this
  8.  * particular file as subject to the "Classpath" exception as provided
  9.  * by Oracle in the LICENSE file that accompanied this code.
  10.  *
  11.  * This code is distributed in the hope that it will be useful, but WITHOUT
  12.  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13.  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14.  * version 2 for more details (a copy is included in the LICENSE file that
  15.  * accompanied this code).
  16.  *
  17.  * You should have received a copy of the GNU General Public License version
  18.  * 2 along with this work; if not, write to the Free Software Foundation,
  19.  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20.  *
  21.  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22.  * or visit www.oracle.com if you need additional information or have any
  23.  * questions.
  24.  */
  26. package java.lang;
  27. import java.lang.ref.*;
  28. import java.util.Objects;
  29. import java.util.concurrent.atomic.AtomicInteger;
  30. import java.util.function.Supplier;
  32. /**
  33.  * This class provides thread-local variables.  These variables differ from
  34.  * their normal counterparts in that each thread that accesses one (via its
  35.  * {@code get} or {@code set} method) has its own, independently initialized
  36.  * copy of the variable.  {@code ThreadLocal} instances are typically private
  37.  * static fields in classes that wish to associate state with a thread (e.g.,
  38.  * a user ID or Transaction ID).
  39.  *
  40.  * <p>For example, the class below generates unique identifiers local to each
  41.  * thread.
  42.  * A thread's id is assigned the first time it invokes {@code ThreadId.get()}
  43.  * and remains unchanged on subsequent calls.
  44.  * <pre>
  45.  * import java.util.concurrent.atomic.AtomicInteger;
  46.  *
  47.  * public class ThreadId {
  48.  *     // Atomic integer containing the next thread ID to be assigned
  49.  *     private static final AtomicInteger nextId = new AtomicInteger(0);
  50.  *
  51.  *     // Thread local variable containing each thread's ID
  52.  *     private static final ThreadLocal&lt;Integer&gt; threadId =
  53.  *         new ThreadLocal&lt;Integer&gt;() {
  54.  *             &#64;Override protected Integer initialValue() {
  55.  *                 return nextId.getAndIncrement();
  56.  *         }
  57.  *     };
  58.  *
  59.  *     // Returns the current thread's unique ID, assigning it if necessary
  60.  *     public static int get() {
  61.  *         return threadId.get();
  62.  *     }
  63.  * }
  64.  * </pre>
  65.  * <p>Each thread holds an implicit reference to its copy of a thread-local
  66.  * variable as long as the thread is alive and the {@code ThreadLocal}
  67.  * instance is accessible; after a thread goes away, all of its copies of
  68.  * thread-local instances are subject to garbage collection (unless other
  69.  * references to these copies exist).
  70.  *
  71.  * @author  Josh Bloch and Doug Lea
  72.  * @since   1.2
  73.  */
  74. public class ThreadLocal<T> {
  75.     /**
  76.      * ThreadLocals rely on per-thread linear-probe hash maps attached
  77.      * to each thread (Thread.threadLocals and
  78.      * inheritableThreadLocals).  The ThreadLocal objects act as keys,
  79.      * searched via threadLocalHashCode.  This is a custom hash code
  80.      * (useful only within ThreadLocalMaps) that eliminates collisions
  81.      * in the common case where consecutively constructed ThreadLocals
  82.      * are used by the same threads, while remaining well-behaved in
  83.      * less common cases.
  84.      */
  85.     private final int threadLocalHashCode = nextHashCode();
  87.     /**
  88.      * The next hash code to be given out. Updated atomically. Starts at
  89.      * zero.
  90.      */
  91.     private static AtomicInteger nextHashCode =
  92.         new AtomicInteger();
  94.     /**
  95.      * The difference between successively generated hash codes - turns
  96.      * implicit sequential thread-local IDs into near-optimally spread
  97.      * multiplicative hash values for power-of-two-sized tables.
  98.      */
  99.     private static final int HASH_INCREMENT = 0x61c88647;
  101.     /**
  102.      * Returns the next hash code.
  103.      */
  104.     private static int nextHashCode() {
  105.         return nextHashCode.getAndAdd(HASH_INCREMENT);
  106.     }
  108.     /**
  109.      * Returns the current thread's "initial value" for this
  110.      * thread-local variable.  This method will be invoked the first
  111.      * time a thread accesses the variable with the {@link #get}
  112.      * method, unless the thread previously invoked the {@link #set}
  113.      * method, in which case the {@code initialValue} method will not
  114.      * be invoked for the thread.  Normally, this method is invoked at
  115.      * most once per thread, but it may be invoked again in case of
  116.      * subsequent invocations of {@link #remove} followed by {@link #get}.
  117.      *
  118.      * <p>This implementation simply returns {@code null}; if the
  119.      * programmer desires thread-local variables to have an initial
  120.      * value other than {@code null}, {@code ThreadLocal} must be
  121.      * subclassed, and this method overridden.  Typically, an
  122.      * anonymous inner class will be used.
  123.      *
  124.      * @return the initial value for this thread-local
  125.      */
  126.     protected T initialValue() {
  127.         return null;
  128.     }
  130.     /**
  131.      * Creates a thread local variable. The initial value of the variable is
  132.      * determined by invoking the {@code get} method on the {@code Supplier}.
  133.      *
  134.      * @param <S> the type of the thread local's value
  135.      * @param supplier the supplier to be used to determine the initial value
  136.      * @return a new thread local variable
  137.      * @throws NullPointerException if the specified supplier is null
  138.      * @since 1.8
  139.      */
  140.     public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
  141.         return new SuppliedThreadLocal<>(supplier);
  142.     }
  144.     /**
  145.      * Creates a thread local variable.
  146.      * @see #withInitial(java.util.function.Supplier)
  147.      */
  148.     public ThreadLocal() {
  149.     }
  151.     /**
  152.      * Returns the value in the current thread's copy of this
  153.      * thread-local variable.  If the variable has no value for the
  154.      * current thread, it is first initialized to the value returned
  155.      * by an invocation of the {@link #initialValue} method.
  156.      *
  157.      * @return the current thread's value of this thread-local
  158.      */
  159.     public T get() {
  160.         Thread t = Thread.currentThread();
  161.         ThreadLocalMap map = getMap(t);
  162.         if (map != null) {
  163.             ThreadLocalMap.Entry e = map.getEntry(this);
  164.             if (e != null) {
  165.                 @SuppressWarnings("unchecked")
  166.                 T result = (T)e.value;
  167.                 return result;
  168.             }
  169.         }
  170.         return setInitialValue();
  171.     }
  173.     /**
  174.      * Variant of set() to establish initialValue. Used instead
  175.      * of set() in case user has overridden the set() method.
  176.      *
  177.      * @return the initial value
  178.      */
  179.     private T setInitialValue() {
  180.         T value = initialValue();
  181.         Thread t = Thread.currentThread();
  182.         ThreadLocalMap map = getMap(t);
  183.         if (map != null)
  184.             map.set(this, value);
  185.         else
  186.             createMap(t, value);
  187.         return value;
  188.     }
  190.     /**
  191.      * Sets the current thread's copy of this thread-local variable
  192.      * to the specified value.  Most subclasses will have no need to
  193.      * override this method, relying solely on the {@link #initialValue}
  194.      * method to set the values of thread-locals.
  195.      *
  196.      * @param value the value to be stored in the current thread's copy of
  197.      *        this thread-local.
  198.      */
  199.     public void set(T value) {
  200.         Thread t = Thread.currentThread();
  201.         ThreadLocalMap map = getMap(t);
  202.         if (map != null)
  203.             map.set(this, value);
  204.         else
  205.             createMap(t, value);
  206.     }
  208.     /**
  209.      * Removes the current thread's value for this thread-local
  210.      * variable.  If this thread-local variable is subsequently
  211.      * {@linkplain #get read} by the current thread, its value will be
  212.      * reinitialized by invoking its {@link #initialValue} method,
  213.      * unless its value is {@linkplain #set set} by the current thread
  214.      * in the interim.  This may result in multiple invocations of the
  215.      * {@code initialValue} method in the current thread.
  216.      *
  217.      * @since 1.5
  218.      */
  219.      public void remove() {
  220.          ThreadLocalMap m = getMap(Thread.currentThread());
  221.          if (m != null)
  222.              m.remove(this);
  223.      }
  225.     /**
  226.      * Get the map associated with a ThreadLocal. Overridden in
  227.      * InheritableThreadLocal.
  228.      *
  229.      * @param  t the current thread
  230.      * @return the map
  231.      */
  232.     ThreadLocalMap getMap(Thread t) {
  233.         return t.threadLocals;
  234.     }
  236.     /**
  237.      * Create the map associated with a ThreadLocal. Overridden in
  238.      * InheritableThreadLocal.
  239.      *
  240.      * @param t the current thread
  241.      * @param firstValue value for the initial entry of the map
  242.      */
  243.     void createMap(Thread t, T firstValue) {
  244.         t.threadLocals = new ThreadLocalMap(this, firstValue);
  245.     }
  247.     /**
  248.      * Factory method to create map of inherited thread locals.
  249.      * Designed to be called only from Thread constructor.
  250.      *
  251.      * @param  parentMap the map associated with parent thread
  252.      * @return a map containing the parent's inheritable bindings
  253.      */
  254.     static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
  255.         return new ThreadLocalMap(parentMap);
  256.     }
  258.     /**
  259.      * Method childValue is visibly defined in subclass
  260.      * InheritableThreadLocal, but is internally defined here for the
  261.      * sake of providing createInheritedMap factory method without
  262.      * needing to subclass the map class in InheritableThreadLocal.
  263.      * This technique is preferable to the alternative of embedding
  264.      * instanceof tests in methods.
  265.      */
  266.     T childValue(T parentValue) {
  267.         throw new UnsupportedOperationException();
  268.     }
  270.     /**
  271.      * An extension of ThreadLocal that obtains its initial value from
  272.      * the specified {@code Supplier}.
  273.      */
  274.     static final class SuppliedThreadLocal<T> extends ThreadLocal<T> {
  276.         private final Supplier<? extends T> supplier;
  278.         SuppliedThreadLocal(Supplier<? extends T> supplier) {
  279.             this.supplier = Objects.requireNonNull(supplier);
  280.         }
  282.         @Override
  283.         protected T initialValue() {
  284.             return supplier.get();
  285.         }
  286.     }
  288.     /**
  289.      * ThreadLocalMap is a customized hash map suitable only for
  290.      * maintaining thread local values. No operations are exported
  291.      * outside of the ThreadLocal class. The class is package private to
  292.      * allow declaration of fields in class Thread.  To help deal with
  293.      * very large and long-lived usages, the hash table entries use
  294.      * WeakReferences for keys. However, since reference queues are not
  295.      * used, stale entries are guaranteed to be removed only when
  296.      * the table starts running out of space.
  297.      */
  298.     static class ThreadLocalMap {
  300.         /**
  301.          * The entries in this hash map extend WeakReference, using
  302.          * its main ref field as the key (which is always a
  303.          * ThreadLocal object).  Note that null keys (i.e. entry.get()
  304.          * == null) mean that the key is no longer referenced, so the
  305.          * entry can be expunged from table.  Such entries are referred to
  306.          * as "stale entries" in the code that follows.
  307.          */
  308.         static class Entry extends WeakReference<ThreadLocal<?>> {
  309.             /** The value associated with this ThreadLocal. */
  310.             Object value;
  312.             Entry(ThreadLocal<?> k, Object v) {
  313.                 super(k);
  314.                 value = v;
  315.             }
  316.         }
  318.         /**
  319.          * The initial capacity -- MUST be a power of two.
  320.          */
  321.         private static final int INITIAL_CAPACITY = 16;
  323.         /**
  324.          * The table, resized as necessary.
  325.          * table.length MUST always be a power of two.
  326.          */
  327.         private Entry[] table;
  329.         /**
  330.          * The number of entries in the table.
  331.          */
  332.         private int size = 0;
  334.         /**
  335.          * The next size value at which to resize.
  336.          */
  337.         private int threshold; // Default to 0
  339.         /**
  340.          * Set the resize threshold to maintain at worst a 2/3 load factor.
  341.          */
  342.         private void setThreshold(int len) {
  343.             threshold = len * 2 / 3;
  344.         }
  346.         /**
  347.          * Increment i modulo len.
  348.          */
  349.         private static int nextIndex(int i, int len) {
  350.             return ((i + 1 < len) ? i + 1 : 0);
  351.         }
  353.         /**
  354.          * Decrement i modulo len.
  355.          */
  356.         private static int prevIndex(int i, int len) {
  357.             return ((i - 1 >= 0) ? i - 1 : len - 1);
  358.         }
  360.         /**
  361.          * Construct a new map initially containing (firstKey, firstValue).
  362.          * ThreadLocalMaps are constructed lazily, so we only create
  363.          * one when we have at least one entry to put in it.
  364.          */
  365.         ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
  366.             table = new Entry[INITIAL_CAPACITY];
  367.             int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
  368.             table[i] = new Entry(firstKey, firstValue);
  369.             size = 1;
  370.             setThreshold(INITIAL_CAPACITY);
  371.         }
  373.         /**
  374.          * Construct a new map including all Inheritable ThreadLocals
  375.          * from given parent map. Called only by createInheritedMap.
  376.          *
  377.          * @param parentMap the map associated with parent thread.
  378.          */
  379.         private ThreadLocalMap(ThreadLocalMap parentMap) {
  380.             Entry[] parentTable = parentMap.table;
  381.             int len = parentTable.length;
  382.             setThreshold(len);
  383.             table = new Entry[len];
  385.             for (int j = 0; j < len; j++) {
  386.                 Entry e = parentTable[j];
  387.                 if (e != null) {
  388.                     @SuppressWarnings("unchecked")
  389.                     ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
  390.                     if (key != null) {
  391.                         Object value = key.childValue(e.value);
  392.                         Entry c = new Entry(key, value);
  393.                         int h = key.threadLocalHashCode & (len - 1);
  394.                         while (table[h] != null)
  395.                             h = nextIndex(h, len);
  396.                         table[h] = c;
  397.                         size++;
  398.                     }
  399.                 }
  400.             }
  401.         }
  403.         /**
  404.          * Get the entry associated with key.  This method
  405.          * itself handles only the fast path: a direct hit of existing
  406.          * key. It otherwise relays to getEntryAfterMiss.  This is
  407.          * designed to maximize performance for direct hits, in part
  408.          * by making this method readily inlinable.
  409.          *
  410.          * @param  key the thread local object
  411.          * @return the entry associated with key, or null if no such
  412.          */
  413.         private Entry getEntry(ThreadLocal<?> key) {
  414.             int i = key.threadLocalHashCode & (table.length - 1);
  415.             Entry e = table[i];
  416.             if (e != null && e.get() == key)
  417.                 return e;
  418.             else
  419.                 return getEntryAfterMiss(key, i, e);
  420.         }
  422.         /**
  423.          * Version of getEntry method for use when key is not found in
  424.          * its direct hash slot.
  425.          *
  426.          * @param  key the thread local object
  427.          * @param  i the table index for key's hash code
  428.          * @param  e the entry at table[i]
  429.          * @return the entry associated with key, or null if no such
  430.          */
  431.         private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
  432.             Entry[] tab = table;
  433.             int len = tab.length;
  435.             while (e != null) {
  436.                 ThreadLocal<?> k = e.get();
  437.                 if (k == key)
  438.                     return e;
  439.                 if (k == null)
  440.                     expungeStaleEntry(i);
  441.                 else
  442.                     i = nextIndex(i, len);
  443.                 e = tab[i];
  444.             }
  445.             return null;
  446.         }
  448.         /**
  449.          * Set the value associated with key.
  450.          *
  451.          * @param key the thread local object
  452.          * @param value the value to be set
  453.          */
  454.         private void set(ThreadLocal<?> key, Object value) {
  456.             // We don't use a fast path as with get() because it is at
  457.             // least as common to use set() to create new entries as
  458.             // it is to replace existing ones, in which case, a fast
  459.             // path would fail more often than not.
  461.             Entry[] tab = table;
  462.             int len = tab.length;
  463.             int i = key.threadLocalHashCode & (len-1);
  465.             for (Entry e = tab[i];
  466.                  e != null;
  467.                  e = tab[i = nextIndex(i, len)]) {
  468.                 ThreadLocal<?> k = e.get();
  470.                 if (k == key) {
  471.                     e.value = value;
  472.                     return;
  473.                 }
  475.                 if (k == null) {
  476.                     replaceStaleEntry(key, value, i);
  477.                     return;
  478.                 }
  479.             }
  481.             tab[i] = new Entry(key, value);
  482.             int sz = ++size;
  483.             if (!cleanSomeSlots(i, sz) && sz >= threshold)
  484.                 rehash();
  485.         }
  487.         /**
  488.          * Remove the entry for key.
  489.          */
  490.         private void remove(ThreadLocal<?> key) {
  491.             Entry[] tab = table;
  492.             int len = tab.length;
  493.             int i = key.threadLocalHashCode & (len-1);
  494.             for (Entry e = tab[i];
  495.                  e != null;
  496.                  e = tab[i = nextIndex(i, len)]) {
  497.                 if (e.get() == key) {
  498.                     e.clear();
  499.                     expungeStaleEntry(i);
  500.                     return;
  501.                 }
  502.             }
  503.         }
  505.         /**
  506.          * Replace a stale entry encountered during a set operation
  507.          * with an entry for the specified key.  The value passed in
  508.          * the value parameter is stored in the entry, whether or not
  509.          * an entry already exists for the specified key.
  510.          *
  511.          * As a side effect, this method expunges all stale entries in the
  512.          * "run" containing the stale entry.  (A run is a sequence of entries
  513.          * between two null slots.)
  514.          *
  515.          * @param  key the key
  516.          * @param  value the value to be associated with key
  517.          * @param  staleSlot index of the first stale entry encountered while
  518.          *         searching for key.
  519.          */
  520.         private void replaceStaleEntry(ThreadLocal<?> key, Object value,
  521.                                        int staleSlot) {
  522.             Entry[] tab = table;
  523.             int len = tab.length;
  524.             Entry e;
  526.             // Back up to check for prior stale entry in current run.
  527.             // We clean out whole runs at a time to avoid continual
  528.             // incremental rehashing due to garbage collector freeing
  529.             // up refs in bunches (i.e., whenever the collector runs).
  530.             int slotToExpunge = staleSlot;
  531.             for (int i = prevIndex(staleSlot, len);
  532.                  (e = tab[i]) != null;
  533.                  i = prevIndex(i, len))
  534.                 if (e.get() == null)
  535.                     slotToExpunge = i;
  537.             // Find either the key or trailing null slot of run, whichever
  538.             // occurs first
  539.             for (int i = nextIndex(staleSlot, len);
  540.                  (e = tab[i]) != null;
  541.                  i = nextIndex(i, len)) {
  542.                 ThreadLocal<?> k = e.get();
  544.                 // If we find key, then we need to swap it
  545.                 // with the stale entry to maintain hash table order.
  546.                 // The newly stale slot, or any other stale slot
  547.                 // encountered above it, can then be sent to expungeStaleEntry
  548.                 // to remove or rehash all of the other entries in run.
  549.                 if (k == key) {
  550.                     e.value = value;
  552.                     tab[i] = tab[staleSlot];
  553.                     tab[staleSlot] = e;
  555.                     // Start expunge at preceding stale entry if it exists
  556.                     if (slotToExpunge == staleSlot)
  557.                         slotToExpunge = i;
  558.                     cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
  559.                     return;
  560.                 }
  562.                 // If we didn't find stale entry on backward scan, the
  563.                 // first stale entry seen while scanning for key is the
  564.                 // first still present in the run.
  565.                 if (k == null && slotToExpunge == staleSlot)
  566.                     slotToExpunge = i;
  567.             }
  569.             // If key not found, put new entry in stale slot
  570.             tab[staleSlot].value = null;
  571.             tab[staleSlot] = new Entry(key, value);
  573.             // If there are any other stale entries in run, expunge them
  574.             if (slotToExpunge != staleSlot)
  575.                 cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
  576.         }
  578.         /**
  579.          * Expunge a stale entry by rehashing any possibly colliding entries
  580.          * lying between staleSlot and the next null slot.  This also expunges
  581.          * any other stale entries encountered before the trailing null.  See
  582.          * Knuth, Section 6.4
  583.          *
  584.          * @param staleSlot index of slot known to have null key
  585.          * @return the index of the next null slot after staleSlot
  586.          * (all between staleSlot and this slot will have been checked
  587.          * for expunging).
  588.          */
  589.         private int expungeStaleEntry(int staleSlot) {
  590.             Entry[] tab = table;
  591.             int len = tab.length;
  593.             // expunge entry at staleSlot
  594.             tab[staleSlot].value = null;
  595.             tab[staleSlot] = null;
  596.             size--;
  598.             // Rehash until we encounter null
  599.             Entry e;
  600.             int i;
  601.             for (i = nextIndex(staleSlot, len);
  602.                  (e = tab[i]) != null;
  603.                  i = nextIndex(i, len)) {
  604.                 ThreadLocal<?> k = e.get();
  605.                 if (k == null) {
  606.                     e.value = null;
  607.                     tab[i] = null;
  608.                     size--;
  609.                 } else {
  610.                     int h = k.threadLocalHashCode & (len - 1);
  611.                     if (h != i) {
  612.                         tab[i] = null;
  614.                         // Unlike Knuth 6.4 Algorithm R, we must scan until
  615.                         // null because multiple entries could have been stale.
  616.                         while (tab[h] != null)
  617.                             h = nextIndex(h, len);
  618.                         tab[h] = e;
  619.                     }
  620.                 }
  621.             }
  622.             return i;
  623.         }
  625.         /**
  626.          * Heuristically scan some cells looking for stale entries.
  627.          * This is invoked when either a new element is added, or
  628.          * another stale one has been expunged. It performs a
  629.          * logarithmic number of scans, as a balance between no
  630.          * scanning (fast but retains garbage) and a number of scans
  631.          * proportional to number of elements, that would find all
  632.          * garbage but would cause some insertions to take O(n) time.
  633.          *
  634.          * @param i a position known NOT to hold a stale entry. The
  635.          * scan starts at the element after i.
  636.          *
  637.          * @param n scan control: {@code log2(n)} cells are scanned,
  638.          * unless a stale entry is found, in which case
  639.          * {@code log2(table.length)-1} additional cells are scanned.
  640.          * When called from insertions, this parameter is the number
  641.          * of elements, but when from replaceStaleEntry, it is the
  642.          * table length. (Note: all this could be changed to be either
  643.          * more or less aggressive by weighting n instead of just
  644.          * using straight log n. But this version is simple, fast, and
  645.          * seems to work well.)
  646.          *
  647.          * @return true if any stale entries have been removed.
  648.          */
  649.         private boolean cleanSomeSlots(int i, int n) {
  650.             boolean removed = false;
  651.             Entry[] tab = table;
  652.             int len = tab.length;
  653.             do {
  654.                 i = nextIndex(i, len);
  655.                 Entry e = tab[i];
  656.                 if (e != null && e.get() == null) {
  657.                     n = len;
  658.                     removed = true;
  659.                     i = expungeStaleEntry(i);
  660.                 }
  661.             } while ( (n >>>= 1) != 0);
  662.             return removed;
  663.         }
  665.         /**
  666.          * Re-pack and/or re-size the table. First scan the entire
  667.          * table removing stale entries. If this doesn't sufficiently
  668.          * shrink the size of the table, double the table size.
  669.          */
  670.         private void rehash() {
  671.             expungeStaleEntries();
  673.             // Use lower threshold for doubling to avoid hysteresis
  674.             if (size >= threshold - threshold / 4)
  675.                 resize();
  676.         }
  678.         /**
  679.          * Double the capacity of the table.
  680.          */
  681.         private void resize() {
  682.             Entry[] oldTab = table;
  683.             int oldLen = oldTab.length;
  684.             int newLen = oldLen * 2;
  685.             Entry[] newTab = new Entry[newLen];
  686.             int count = 0;
  688.             for (int j = 0; j < oldLen; ++j) {
  689.                 Entry e = oldTab[j];
  690.                 if (e != null) {
  691.                     ThreadLocal<?> k = e.get();
  692.                     if (k == null) {
  693.                         e.value = null; // Help the GC
  694.                     } else {
  695.                         int h = k.threadLocalHashCode & (newLen - 1);
  696.                         while (newTab[h] != null)
  697.                             h = nextIndex(h, newLen);
  698.                         newTab[h] = e;
  699.                         count++;
  700.                     }
  701.                 }
  702.             }
  704.             setThreshold(newLen);
  705.             size = count;
  706.             table = newTab;
  707.         }
  709.         /**
  710.          * Expunge all stale entries in the table.
  711.          */
  712.         private void expungeStaleEntries() {
  713.             Entry[] tab = table;
  714.             int len = tab.length;
  715.             for (int j = 0; j < len; j++) {
  716.                 Entry e = tab[j];
  717.                 if (e != null && e.get() == null)
  718.                     expungeStaleEntry(j);
  719.             }
  720.         }
  721.     }
  722. }