[toc]
實(shí)際上案怯，在分析整個(gè)Reference包源碼之前，重點(diǎn)關(guān)注的問題就是ThreadLocal的源碼澎办。這也是學(xué)習(xí)Reference這個(gè)系列的初衷嘲碱。一開始的想法就是將ThreadLocal源碼好好理解一遍。畢竟這這也是目前大多數(shù)大廠面試的高頻考點(diǎn)局蚀。但是在打開ThreadLocal之后麦锯，發(fā)現(xiàn)最關(guān)鍵的是巧妙應(yīng)用了WeakReference。雖然ThreadLocal的其他代碼的巧妙程度也讓人印象深刻至会。但是ThreadLocal絕對(duì)稱得上WeakReference的經(jīng)典應(yīng)用离咐，沒有之一。面試必問奉件。要想搞明白ThreadLocal必須弄清楚WeakReference宵蛀。這也是這個(gè)Reference的動(dòng)機(jī)之一。學(xué)習(xí)就是如此县貌，從一個(gè)點(diǎn)逐漸衍生到一個(gè)面术陶。那么看了weakReference，就會(huì)自然的看Reference的各個(gè)子類煤痕。包括在上一篇梧宫，對(duì)FinalReference的分析，這都是之前沒有重點(diǎn)關(guān)注的冷門知識(shí)點(diǎn)摆碉。那么現(xiàn)在能放到一個(gè)整體去分析塘匣，也是一個(gè)值得高興的事情。

1.ThreadLocal的使用

1.1 threadlocal 運(yùn)行示例

看如下示例代碼巷帝，我們有兩個(gè)線程忌卤，a和b,線程a啟動(dòng)之后，sleep 2秒楞泼，從threadlocal t1中取獲取person實(shí)例 p驰徊，線程b，啟動(dòng)之后堕阔，sleep 1秒棍厂，然后set Person的實(shí)例p到threadlocal t1中去。

    volatile static Person p = new  Person();

    static ThreadLocal<Person> t1 = new ThreadLocal<>();


    public static void main(String[] args) {
        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println(" thread a "+t1.get());
        }).start();

        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            t1.set(new Person());
            System.out.println(" thread b "+t1.get());
        }).start();
    }

    static class Person {
        String name;
    }

運(yùn)行代碼結(jié)果如下：

 thread b com.dhb.test.ThreadLocal1$Person@5058a2e0
 thread a null

Process finished with exit code 0

可以看到超陆，thread b能獲取到p,而thread a不能牺弹。這就證明了threadlocal的主要功能。threadlocal提供了一個(gè)對(duì)線程隔離的局部變量載體。

1.2 threadlocal的主要功能

可以看一下threadlocal中源碼的注釋：

/**
 * 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).
 *
 * <p>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.
 * <pre>
 * 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&lt;Integer&gt; threadId =
 *         new ThreadLocal&lt;Integer&gt;() {
 *             &#64;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();
 *     }
 * }
 * </pre>
 * <p>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
 */

大意為例驹，在jdk1.2版本之后捐韩，jdk提供了一個(gè)基于線程隔離的線程本地變量。每個(gè)訪問的get和set方法的線程都有自己獨(dú)立的變量副本鹃锈。threadlocal的實(shí)例通常會(huì)設(shè)置為private static 類型荤胁，以便將一些狀態(tài)和某個(gè)線程關(guān)聯(lián)。（如用戶編號(hào)和事務(wù)ID）屎债。
然后提供了一個(gè)基于AtomicInteger 的demo仅政。
對(duì)于一個(gè)threadlocal對(duì)象，每個(gè)線程在存活的周期內(nèi)都保留了一個(gè)對(duì)該對(duì)象的隱式引用盆驹，這個(gè)ThreadLocal可以進(jìn)行數(shù)據(jù)存取圆丹。當(dāng)線程死亡的時(shí)候，線程中的所有threadLocal對(duì)象都會(huì)被GC回收（除非有其他對(duì)ThreadLocal的引用任然存在）躯喇。
這就是threadlocal的主要功能辫封。這個(gè)功能主要用在什么地方呢？實(shí)際上廉丽，可能我們每天都在用倦微，但是你并沒有關(guān)注到而已。在spring中正压，基于數(shù)據(jù)庫事務(wù)的的調(diào)用欣福，spring使用連接池連接數(shù)據(jù)庫，又需要在CRUD操作中把多個(gè)代碼中的操作放到一個(gè)事務(wù)中的話焦履，那么最好的辦法就是拓劝，讓連接與spring的線程綁定，這個(gè)線程的所有crud操作最終都在一個(gè)connection上commit嘉裤。這自然可以實(shí)現(xiàn)這些需求郑临，這也是spring面試的高頻考點(diǎn)。

1.3 threadlocal提供的主要api

threadLocal的public方法表如下：

image.png

可以看到屑宠，除了構(gòu)造函數(shù)之外牧抵，ThreadLocal的主要方法有，get侨把、set、remove和基于lambda的withInitial方法妹孙。

1.3.1 get

    /**
     * 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();
    }
    
        /**
     * 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;
    }

可以看到秋柄，ThreadLocal內(nèi)部維護(hù)了一個(gè)特殊的HashMap,這個(gè)Map存在當(dāng)前線程（Thread.currentThread()）的threadLocals參數(shù)中，以當(dāng)前的ThreadLocal為key蠢正。通過當(dāng)前threadLocal去Map中獲取Entry骇笔。這個(gè)特殊的Map就是ThreadLocalMap。通過getmap方法可以知道，這個(gè)Map實(shí)際上就維護(hù)在Thread對(duì)象中笨触。屬性為threadLocals懦傍。

1.3.2 set

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

通過set方法的源碼，我們可以看到芦劣，在set的時(shí)候粗俱，首先判斷map是否為null，如果為null則調(diào)用creatMap方法虚吟，以當(dāng)前傳入的value創(chuàng)建一個(gè)以當(dāng)前ThreadLocal為key的新的map寸认。這個(gè)把當(dāng)前線程的threadLocals 指向這個(gè)map。
而InheritableThreadLocal串慰，則會(huì)對(duì)createMap重寫偏塞，以實(shí)現(xiàn)可繼承的在子類中共享的ThreadLocal。
因此可以知道邦鲫，每個(gè)線程都有一個(gè)固定的threadLocals屬性灸叼，這個(gè)屬性指向一個(gè)ThreadLocalMap。

1.3.3 remove

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

remove方法主要是從當(dāng)前線程的ThreadLocalMap中將ThreadLocal為key的Entry移除庆捺。對(duì)于Threadlocal,如果使用完畢古今，則務(wù)必調(diào)用remove方法移除，以避免引起內(nèi)存泄漏或者OOM疼燥。后面會(huì)對(duì)這個(gè)問題做詳細(xì)分析沧卢。

1.3.4 withInitial

    /**
     * Creates a thread local variable. The initial value of the variable is
     * determined by invoking the {@code get} method on the {@code Supplier}.
     *
     * @param <S> 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 <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
        return new SuppliedThreadLocal<>(supplier);
    }

這個(gè)withInitial方法是jdk1.8之后專門給lambda方式使用的的構(gòu)造方法。這個(gè)方法采用Lambda方式傳入實(shí)現(xiàn)了 Supplier 函數(shù)接口的參數(shù)醉者。如下：

ThreadLocal<Integer> balance = ThreadLocal.withInitial(() -> 1000);

這樣即可用lambda的方式進(jìn)行調(diào)用但狭。

2.ThreadLocal核心源碼及其與Weakreference的關(guān)系

2.1 ThreadLocalMap結(jié)構(gòu)

ThreadLocal的核心部分就是ThreadLocalMap。

    /**
     * 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<ThreadLocal<?>> {
            /** The value associated with this ThreadLocal. */
            Object value;

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

可以看到撬即，注釋中說得非常明白立磁，ThreadLocalMap是一個(gè)特定的hashMap,只適用于ThreadLocal，private修飾剥槐，做為threadLocal的內(nèi)部類唱歧，無法在其他地方訪問到。這個(gè)ThreadLocalMap的Entry繼承了WeakReference粒竖，用以實(shí)現(xiàn)對(duì)value對(duì)象的長期緩存颅崩。但是，由于用戶不能直接操作ReferenceQueue,而WeakReference與Key的綁定蕊苗，key是ThreadLocal自身沿后，那么Entry到Key之間就是弱引用的關(guān)系，因此朽砰，只有GC的時(shí)候這些過期不用的entry才會(huì)被刪除尖滚。當(dāng)entry.get()方法為null的時(shí)候喉刘，表示這個(gè)entry是過時(shí)的。

2.2 ThreadLocalMap與WeakReference的關(guān)系

從上文中可以看到漆弄，ThreadLocalMap的Entry是WeakReference的睦裳，那么，當(dāng)對(duì)這個(gè)Entry中的強(qiáng)引用消失之后撼唾，weakReference就會(huì)被GC回收廉邑。

ThreadLocal a = new ThreadLocal();
a.set(new byte[1024*1024*10]);

以上述代碼為例，其內(nèi)存布局如下：

image.png

如上圖所示券坞，如果定義了一個(gè)ThreadLocal鬓催，那么在Stack上就會(huì)有兩個(gè)指針，分別指向ThreadLocal和當(dāng)前線程在堆上的內(nèi)存地址恨锚。之后宇驾，當(dāng)前的線程中的threadLocals指向這個(gè)ThreadLocalMap,而Map中的Entry，包括Key和Value猴伶，Key又通過WeakReference的方式指向了ThreadLocal课舍。Value即是當(dāng)前需要放在ThreadLocal中的值∷妫可能是一個(gè)大的對(duì)象筝尾，以供線程內(nèi)部共享。因此value強(qiáng)引用指向了這個(gè)value內(nèi)容办桨。
此時(shí)不難發(fā)現(xiàn)一個(gè)問題筹淫，就是當(dāng)ThreadLocal的強(qiáng)引用一旦消失之后，如申明一個(gè)threadLocal變量a,此時(shí)令a=null,那么之前的threadlocal就會(huì)被GC回收呢撞。

ThreadLocal a = new ThreadLocal();
a.set(new byte[1024*1024*10]);
a = null;

此時(shí)损姜，如果a=null,那么后面如果執(zhí)行GC，會(huì)導(dǎo)致a被回收殊霞，而ThreadLocalMap中摧阅，這個(gè)a對(duì)應(yīng)的Entry的key就會(huì)變成null，而value為10MB,并不會(huì)在這次GC中回收绷蹲。這也是threadLocal可能會(huì)造成內(nèi)存泄漏的原因棒卷。因此，如果有threadlocal不需要使用之后祝钢，最好的辦法是使用remove將其從ThreadLocalMap中移除比规。

2.3 ThreadLocalMap的核心源碼

我們?cè)賮碓敿?xì)看看ThreadLocalMap，這個(gè)關(guān)鍵的類拦英，使用了很多腦洞大開的設(shè)計(jì)蜒什，值得我們?cè)谝院蟮木幋a中進(jìn)行借鑒。

2.3.1 基本組成元素 Entry

    /**
         * 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<ThreadLocal<?>> {
            /** The value associated with this ThreadLocal. */
            Object value;

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

Entry是ThreadLocalMap的核心龄章，也是應(yīng)用WeakReference的地方吃谣。Entry本身繼承了WeakReference。之后將傳入的ThreadLocal也就是key做裙，放在了WeakReference中岗憋，這樣構(gòu)成了對(duì)key的WeakReference,而value則是Entry的屬性，對(duì)value的指針是強(qiáng)引用锚贱。
其結(jié)構(gòu)如下圖：

image.png

引用關(guān)系如下：

image.png

2.3.2 構(gòu)造函數(shù)

ThreadLocal有兩個(gè)主要的構(gòu)造函數(shù)仔戈，分別是創(chuàng)建的時(shí)候插入一個(gè)Entry和批量插入Entry構(gòu)造。

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

這個(gè)構(gòu)造函數(shù)在使用的時(shí)候需要傳入第一個(gè)key和value拧廊。ThreadLoccalMap底層的hash表的長度初始為INITIAL_CAPACITY = 16监徘。
這個(gè)構(gòu)造函數(shù)的作用域在protected。

     /**
         * The initial capacity -- MUST be a power of two.
         */
        private static final int INITIAL_CAPACITY = 16;
 /**
         * 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) {
            //初始hash表吧碾，長度為16
            table = new Entry[INITIAL_CAPACITY];
            //Hash取模運(yùn)算凰盔，計(jì)算index
            int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
            //根據(jù)hash取模得到索引位置，然后構(gòu)建Entry
            table[i] = new Entry(firstKey, firstValue);
            //維護(hù)長度變量倦春，初始為1
            size = 1;
            //設(shè)置負(fù)載因子
            setThreshold(INITIAL_CAPACITY);
        }

該方法主要配合ThreadLocal中的createMap方法使用户敬。ThreadLocal是采用懶加載的方式，在需要的時(shí)候才會(huì)創(chuàng)建ThreadLocalMap,由于每個(gè)thread都有一個(gè)threadlocals來存儲(chǔ)對(duì)應(yīng)的ThreadLocalMap,不存在共享問題睁本，因此是線程安全的尿庐，不需要加鎖。
首先創(chuàng)建INITIAL_CAPACITY大小的Entry數(shù)組呢堰。之后將firstKey的threadLocalHashCode和(INITIAL_CAPACITY - 1)取模抄瑟。之后構(gòu)造一個(gè)Entry傳入這個(gè)hash表計(jì)算的index處。然后對(duì)于hash表的長度枉疼，size是動(dòng)態(tài)計(jì)算的皮假，初始為1，后續(xù)每次增減會(huì)用維護(hù)的這個(gè)size變量增減往衷。如下圖：

image.png

另外還維護(hù)的負(fù)載因子threshold钞翔，是len的2/3，當(dāng)size大于這個(gè)值就開始擴(kuò)容席舍。

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

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

批量構(gòu)造布轿，這種情況發(fā)生在InheritableThreadLocal的時(shí)候，一個(gè)子類要將父類全部的ThreadLocalMap繼承来颤，則會(huì)使用這個(gè)構(gòu)造函數(shù)汰扭。除此之外ThreadLocal種不會(huì)用到這個(gè)構(gòu)造函數(shù)。另外這個(gè)構(gòu)造函數(shù)也是private的福铅。不提供給用戶訪問萝毛。僅僅在createInheritedMap方法中調(diào)用。

        /**
         * 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) {
            //拿到父類種的table及其長度
            Entry[] parentTable = parentMap.table;
            int len = parentTable.length;
            //根據(jù)父類長度設(shè)置負(fù)載因子
            setThreshold(len);
            //根據(jù)父類長度創(chuàng)建相同大小的hash表
            table = new Entry[len];
            //遍歷賦值
            for (int j = 0; j < len; j++) {
               //通過entry判斷是否為空滑黔，不為空則構(gòu)造一個(gè)新的Entry
                Entry e = parentTable[j];
                if (e != null) {
                    @SuppressWarnings("unchecked")
                    //拿到key
                    ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
                    if (key != null) {
                        Object value = key.childValue(e.value);
                        Entry c = new Entry(key, value);
                        //重新根據(jù)hash計(jì)算index位置
                        int h = key.threadLocalHashCode & (len - 1);
                        //如果不為空則hash沖突笆包，此時(shí)采用開放定址法重新計(jì)算
                        while (table[h] != null)
                            h = nextIndex(h, len);
                        table[h] = c;
                        //長度加1
                        size++;
                    }
                }
            }
        }

childValue方法在InheritableThreadLocal實(shí)現(xiàn)环揽，而ThreadLocal不支持。這個(gè)在后面InheritableThreadLocal的源碼中進(jìn)行討論庵佣。

   /**
     * 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();
    }

上面過程如下圖：

image.png

對(duì)于hash碰撞之后使用的開放定址法使用的nextIndex將在后面進(jìn)行討論歉胶。

2.3.3 Hash及hash碰撞的處理方法

在討論后面的set、get巴粪、remove之前通今，有兩個(gè)基本的內(nèi)容需要先理解清楚，第一個(gè)內(nèi)容就是ThreadLocalMap的hash及hash碰撞的解決方法肛根。

2.3.3.1 threadLocalHashCode的計(jì)算過程

ThreadLocalMap的hash算法主要依賴于threadLocalHashCode辫塌。其主要過程如下：

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

可以看到，主要的hashcode是采用0x61c88647這個(gè)魔術(shù)生成的派哲，而不是常規(guī)的hash算法臼氨。0x61c88647這是一個(gè)特殊的數(shù)字。每次增加0x61c88647狮辽，之后取模能將碰撞的概率降到最低一也。這個(gè)魔數(shù)使用斐波拉契數(shù)列來實(shí)現(xiàn)hash算法。具體的數(shù)學(xué)原理本文無法討論喉脖。通過如下代碼進(jìn)行測(cè)試：

public class MagicHashCodeTest {

    private static final int HASH_INCREMENT = 0x61c88647;


    public static void main(String[] args) {
        hashCode(16);
        hashCode(32);
        hashCode(64);
    }

    private static void hashCode(Integer length){
        int hashCode = 0;
        for(int i=0; i< length; i++){
            hashCode = i * HASH_INCREMENT+HASH_INCREMENT;
            System.out.print(hashCode & (length-1));
            System.out.print(" ");
        }
        System.out.println();
    }
}

可以看到椰苟，其結(jié)果真的很均勻：

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

將hash碰撞的概率降到了最低。

2.3.3.2 hash碰撞的解決辦法--開放定址法

雖然使用魔數(shù)將hash碰撞的概率降低了很多树叽，但是舆蝴，hash碰撞的可能性還是存在的。那么出現(xiàn)之后該如何處理呢题诵？
參考前文：
解決哈希沖突的常用方法分析
ThreadLocalMap使用了開放定址法洁仗，即從發(fā)生沖突的那個(gè)單元起，按照一定的次序性锭，從哈希表中找到一個(gè)空閑的單元赠潦。然后把發(fā)生沖突的元素存入到該單元。線行探查法是開放定址法中最簡(jiǎn)單的沖突處理方法草冈，它從發(fā)生沖突的單元起她奥，依次判斷下一個(gè)單元是否為空，當(dāng)達(dá)到最后一個(gè)單元時(shí)怎棱，再從表首依次判斷哩俭。直到碰到空閑的單元或者探查完全部單元為止。

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

nextIndex方法即是線性探查尋找下一個(gè)元素的方法拳恋。同樣凡资，prevIndex用來尋找上一個(gè)元素。

2.3.4 Entry過期擦除

此外谬运，還要討論的第二個(gè)問題是隙赁，key采用WeakReference,那么被GC回收之后垦藏，key將變成null，而value此時(shí)還在堆中繼續(xù)占用內(nèi)存伞访。因此ThreadLocalMap會(huì)在每次set和get線性探測(cè)的過程中膝藕，將key為null的entry進(jìn)行擦除。

2.3.4.1 指定Entry的index擦除

        /**
         * 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;
            //對(duì)指定的staleSlot進(jìn)行擦除操作
            // expunge entry at staleSlot
            tab[staleSlot].value = null;
            tab[staleSlot] = null;
            //長度減少1
            size--;

            // Rehash until we encounter null
            Entry e;
            int i;
            //對(duì)假定某個(gè)相同key可能到達(dá)的下一個(gè)節(jié)點(diǎn)進(jìn)行線性探查咐扭，之后如果entry不為空而key為空則再次進(jìn)行擦除，如果entry為空則退出循環(huán)
            for (i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                 //拿到key
                ThreadLocal<?> k = e.get();
                //如果key為空滑废，則擦除
                if (k == null) {
                    e.value = null;
                    tab[i] = null;
                    //長度減1
                    size--;
                } else {
                //反之蝗肪，計(jì)算當(dāng)前為key的hash是否是直接命中的
                    int h = k.threadLocalHashCode & (len - 1);
                    //如果h不為k那么說明這個(gè)entry是經(jīng)過線性探查的結(jié)果
                    if (h != i) {
                        tab[i] = null;

                        // Unlike Knuth 6.4 Algorithm R, we must scan until
                        // null because multiple entries could have been stale.
                        將h上線性探測(cè)是否為空，如果為空則將e寫入h
                        while (tab[h] != null)
                            h = nextIndex(h, len);
                        tab[h] = e;
                    }
                }
            }
            return i;
        }

這個(gè)擦除過程比較復(fù)雜蠕趁，當(dāng)指定的hash表的索引staleSlot過期時(shí)薛闪，就將這個(gè)位置的元素擦除，之后俺陋，由于hash表使用了線性探查法豁延，那么有可能這個(gè)指定的位置不是第一次hash命中的位置。那么就需要對(duì)這個(gè)值之后的元素也進(jìn)行線性探測(cè)腊状，將key不為null的元素前移诱咏，將key為null的元素擦除。一直要探測(cè)到entry為null則停止缴挖。之后返回這個(gè)entry為null的索引袋狞。
nextint方法其實(shí)也很簡(jiǎn)單，如果探測(cè)的i+1大于長度映屋，則從0開始苟鸯。那么實(shí)際上就等于是個(gè)環(huán)狀數(shù)組。當(dāng)確認(rèn)某個(gè)位置的key為null需要執(zhí)行過期擦除棚点，那么需要對(duì)后面的元素進(jìn)行探測(cè)早处。如果后面的元素的hash值計(jì)算之后與i不等，那么后面這個(gè)值可能是出現(xiàn)了hash碰撞瘫析，經(jīng)過線性探測(cè)之后達(dá)到的砌梆，因此對(duì)這個(gè)值也需要再次檢測(cè)。如果也過期颁股，那么繼續(xù)擦除么库，如果沒過期，那么移動(dòng)到他合適的位置甘有。
探測(cè)過程如下圖：

image.png

在上圖中诉儒，假定開始探測(cè)的位置為2，后面的3亏掀、4都是經(jīng)過開放定址之后相同的hash值插入的Entry忱反。假定2泛释、4為同一ThreadLocal，此時(shí)都過期了温算，而3為其他threadLocal此時(shí)沒過期怜校。
首先第一步就是將2的位置擦除。得到如下圖：

image.png

然后進(jìn)入for循環(huán)計(jì)算注竿，nextIndex為3茄茁，此時(shí)計(jì)算3的hash計(jì)算結(jié)果與此時(shí)的i不等。那么將3移動(dòng)到2巩割。

image.png

此后進(jìn)一步探測(cè)裙顽，nextIndex為4，4的key為null,那么將4擦除宣谈。

image.png

之后nextIndex為5愈犹，此時(shí)為null，結(jié)束循環(huán)闻丑，返回index為5漩怎。

image.png

2.3.4.2 批量擦除cleanSomeSlots

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

這個(gè)方法循環(huán)掃描次數(shù)由第二個(gè)參數(shù)n（最大等于Entry數(shù)組長度）控制，實(shí)際為log2n嗦嗡，是一種折中式的掃描方式勋锤。之后具體的執(zhí)行過程由expungeStaleEntry控制。
方法從第一個(gè)參數(shù)指示索引的下一個(gè)元素開始掃描侥祭，返回值為是否找到擦除元素怪得，即STALE狀態(tài)元素。

2.3.4.3 全量擦除expungeStaleEntries

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

該方法將hash表中的所有元素進(jìn)行遍歷卑硫，之后擦除操作徒恋。

2.3.5 set Entry

將Entry通過set的方法設(shè)置到hash表中。

        /**
         * Set the value associated with key.
         *
         * @param key the thread local object
         * @param value the value to be set
         */
         //設(shè)置Entry到hash表
        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.
            //在執(zhí)行set的時(shí)候需要考慮三種情況欢伏，分別是 重復(fù)插入入挣、插入的key已經(jīng)過期、碰撞
            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode & (len-1);
            //根據(jù)key計(jì)算得到i
            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                ThreadLocal<?> k = e.get();
                //當(dāng)前的key與set的key相等硝拧，且值也相等径筏，那么是重復(fù)插入惊来，直接替換value膜楷。
                if (k == key) {
                    e.value = value;
                    return;
                }
               //當(dāng)前的key為null，則說明過期秦效，采用替換方法replace即可
                if (k == null) {
                    replaceStaleEntry(key, value, i);
                    return;
                }
            }
            //正潮Ь浚考慮碰撞之后重新計(jì)算的i恢氯，這個(gè)位置可以插入
            tab[i] = new Entry(key, value);
            int sz = ++size;
            //對(duì)部分元素進(jìn)行探測(cè)，clean操作，這會(huì)增加set的時(shí)間勋拟，如故擦除元素成功則不需要擴(kuò)容勋磕，否則，可能需要擴(kuò)容
            if (!cleanSomeSlots(i, sz) && sz >= threshold)
            //擴(kuò)容方法
                rehash();
        }

插入過程中可能會(huì)有三種情況敢靡，重復(fù)key插入;過期插入;常規(guī)插入挂滓。

• 重復(fù)key插入
  直接替換value即可。

  
  
  image.png

上圖紅色部分極為替換之后的value啸胧。

• 過期插入
  如果插入過程中赶站，找到的元素其key為null，則說明已過期纺念。

  
  
  image.png

之后執(zhí)行插入操作：

image.png

• 常規(guī)插入
  如果遇到空的位置亲怠，能夠進(jìn)行常規(guī)插入，那么需要首先進(jìn)行啟發(fā)式擦除操作柠辞，如果擦除操作中被擦除的元素大于1，則說明插入這個(gè)Entry之后不需要擴(kuò)容主胧。此時(shí)直接插入叭首。如果擦除操作沒用擦除元素，那么需要執(zhí)行rehash踪栋，判斷hash表是否需要擴(kuò)容焙格。之后再進(jìn)行插入。
  插入前:

  
  
  image.png

插入后：

image.png

2.3.6 replaceStaleEntry 替換過期Entry

再上一節(jié)中用到了一個(gè)特殊的方法夷都，如果再插入的過程中遇到了過期的元素眷唉，那么需要執(zhí)行 replaceStaleEntry方法，對(duì)過期的元素進(jìn)行替換囤官。

 /**
         * 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).
            //首先向前探測(cè)冬阳，找到hash碰撞的起點(diǎn)，如果不存在hash碰撞党饮，那么staleSlot不變
            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
            //之后從起點(diǎn)開始逐個(gè)向后探測(cè) 
            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.
                //如果key相同肝陪，則直接替換value，然后執(zhí)行清理
                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.
                //如果沒用key為null則即是需要替換的刑顺，再后續(xù)處理
                if (k == null && slotToExpunge == staleSlot)
                    slotToExpunge = i;
            }

            // If key not found, put new entry in stale slot
            //處理key為null的邏輯氯窍，先將value設(shè)置為null這樣消除引用，便于回收蹲堂。之new一個(gè)Entry在此
            tab[staleSlot].value = null;
            tab[staleSlot] = new Entry(key, value);

            // If there are any other stale entries in run, expunge them
            //如果替換的位置發(fā)生改變狼讨，則說明已經(jīng)將值設(shè)置到前面的節(jié)點(diǎn)上，那么后續(xù)還可能存在為空的情況柒竞，那么執(zhí)行clean回收
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }

這個(gè)方法比較復(fù)雜政供，開始以為只是一個(gè)簡(jiǎn)單的replace方法，結(jié)果發(fā)現(xiàn)不是。該方法的邏輯是鲫骗，需要替換的這個(gè)位置犬耻，通過線性探測(cè)查找其上一個(gè)位置，一直找到起始位置進(jìn)行記錄执泰，枕磁，之后再從這個(gè)位置向后探測(cè)。探測(cè)分為兩種情況术吝。如果遇到key相等的Entry计济，則直接替換value。如果沒用排苍，則在第一個(gè)key為空的位置沦寂，清除之后將Entry設(shè)置在此。
之后需要判斷淘衙，設(shè)置Entry的位置與方法開始傳入的staleSlot是否相等传藏，如果不等，則再進(jìn)行清理操作彤守。
兩種情況分別示例如下.

• key重復(fù)
  假定3為目前需要進(jìn)行replace的位置：

  
  
  image.png

之后探測(cè)到1為key的preIndex的起點(diǎn)毯侦，然后向后在4發(fā)現(xiàn)了key相等的位置。則直接替換value具垫。

image.png

由于slotToExpunge侈离！= staleSlot 此時(shí)執(zhí)行clean。

image.png

clean的結(jié)果如上圖筝蚕。

• key不重復(fù)
  如果key不重復(fù)：

  
  
  image.png

首先執(zhí)行探測(cè)：

image.png

之后在第一個(gè)key為null的位置進(jìn)行替換卦碾，再進(jìn)行clean。

image.png

2.3.7 get Entry

get Entry的過程中有兩種情況起宽。即直接命中和出現(xiàn)碰撞兩種情況洲胖。

2.3.7.1 getEntry

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

對(duì)命中key的hash計(jì)算的位置，判斷Entry的key是否相同坯沪。如果key相同宾濒，則返回。如果不同屏箍，則需要用到另外一個(gè)方法 getEntryAfterMiss 這也是解決碰撞的方法绘梦。

2.3.7.1 getEntryAfterMiss

        /**
         * 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;
            //循環(huán) 判斷Entry是否為空
            while (e != null) {
                ThreadLocal<?> k = e.get();
                //如果key相等 則返回
                if (k == key)
                    return e;
                //如果key不等，k為null則進(jìn)行擦除
                if (k == null)
                    expungeStaleEntry(i);
                else
                //反之則向后探測(cè)
                    i = nextIndex(i, len);
                e = tab[i];
            }
            return null;
        }

查找方法赴魁，首先判斷key是否相等卸奉，如果不等，則判斷key是不是為空颖御，為空則進(jìn)行擦除榄棵，之后再向后探測(cè)凝颇。
假定開始從1開始查找：

image.png

之后在3的時(shí)候?yàn)閚ull，需要進(jìn)行清理疹鳄，清理之后：

image.png

然后第三個(gè)i的key相同拧略，則返回。

image.png

2.3.8 remove

remove Entry的方法如下：

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

刪除操作比較簡(jiǎn)單瘪弓，根據(jù)hashcode計(jì)算的index進(jìn)行判斷垫蛆，找到第一個(gè)key相等的位置，執(zhí)行Reference的clear方法腺怯，之后進(jìn)行擦除操作袱饭。

2.3.9 動(dòng)態(tài)擴(kuò)容機(jī)制

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

設(shè)置負(fù)載因子為2/3。在ThreadLocalMap中呛占，只有添加Entry的set方法才會(huì)觸發(fā)擴(kuò)容虑乖。

 private void set(ThreadLocal<?> key, Object value) {
     tab[i] = new Entry(key, value);
            int sz = ++size;
            if (!cleanSomeSlots(i, sz) && sz >= threshold)
                rehash();
        }
 }

在set方法中如果clean沒有回收長度，且新加入的Entry會(huì)導(dǎo)致長度大于等于threshould觸發(fā)閾值晾虑，則執(zhí)行rehash方法擴(kuò)容疹味。

        /**
         * 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();
        }

擴(kuò)容之前執(zhí)行expungeStaleEntries，全表掃描清除過期元素帜篇。之后再執(zhí)行resize擴(kuò)容糙捺。
此時(shí)再次確認(rèn)size大于3/4。

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

以2的倍數(shù)進(jìn)行擴(kuò)容坠狡。
然后將舊的hash表的中的全部元素都按新的hash表進(jìn)行映射，重新設(shè)置值遂跟。
再重新設(shè)置的過程中逃沿，如果遇到key為null則擦除。
LocalThreadMap只有擴(kuò)容過程幻锁，不會(huì)收縮凯亮。因?yàn)橐粋€(gè)ThreadLocal的變量應(yīng)該在一個(gè)可控范圍。

3.ThreadLocal總結(jié)

Threadlocal中使用了很多比較巧妙的設(shè)計(jì)哄尔。在此進(jìn)行總結(jié)：

• ThreadLocal中假消，threadLocalmap的key是Weakreference的ThreadLocal本身。在強(qiáng)引用消失之后會(huì)被GC回收岭接。之后value由于是強(qiáng)引用不會(huì)回收富拗，任然會(huì)在內(nèi)存中。因此這依賴于我們執(zhí)行threadlocal過程中g(shù)et和set時(shí)的clean操作鸣戴。但是這個(gè)操作不是一定會(huì)發(fā)生啃沪。因此這也是導(dǎo)致內(nèi)存泄漏的根源。因此對(duì)于threadlocal窄锅。我們需要及時(shí)使用remove方法將我們不用的對(duì)象清除创千。
• ThreadLocalMap采用魔數(shù)實(shí)現(xiàn)hash算法。0x61c88647 這是一個(gè)神奇的數(shù)字。通過每次加0x61c88647之后取模能盡量均勻的分布在哈希表中追驴。
• ThreadLocalMap 對(duì)于hash沖突采用開放定址法中的線性探測(cè)法械哟。每次向后加1。因此這會(huì)導(dǎo)致每次get殿雪、set暇咆、remove、clean等操作都需要進(jìn)行線性探測(cè)冠摄。
• threadLocalMap只能擴(kuò)容糯崎，不會(huì)像hashmap那樣縮容。因此這也是一個(gè)導(dǎo)致線程內(nèi)存變大的原因河泳。

4.擴(kuò)展

對(duì)于threadlocal,還有一個(gè)變體是InheritableThreadLocal沃呢，實(shí)際上還有netty也提供了類似的FastThreadLocal，其性能比threadLocal要高很多拆挥。將在后續(xù)的文章繼續(xù)討論薄霜。