Why ThreadLocal is thread-safe?

For thread safety, all you need to do is make a tradeoff between time and space, and today’s ThreadLocal is a typical space-for-time data structure.

ThreadLocalThe use of

User information can be stored in a project via ThreadLocal, which typically initializes the user information at the entry point of the filter/interceptor and cleans it up after execution. Instead of having to retrieve the user information from the database each time the request comes in until it is returned, we only need to retrieve the user information from the thread variable ThreadLocal.

Since ThreadLocal is thread-safe, we declare it as a singleton here.

public class UserHolder {
    private final static ThreadLocal<UserInfo> CURRENT_USER = new ThreadLocal<>();

    public static UserInfo get(a) {
        return CURRENT_USER.get();
    }

    public static void set(UserInfo userInfo) {
        CURRENT_USER.set(userInfo);
    }

    public static void remove(a) { CURRENT_USER.remove(); }}Copy the code

We can then initialize and retrieve user information in the interceptor and business methods.

public class Filter{

    public void doFilter(Request request,Response response){ UserInfo userInfo = getUserInfo(request); UserHolder.set(userInfo); doHandle(request,response); UserHolder.remove(); }}public class BusinessService{

    public void serviceA(a){
        // This is thread safe because of the ThreadLocal mechanism
        UserInfo userInfo = UserHolder.get();
        / / the userInfo operation...}}Copy the code

Now that we know the basics of ThreadLocal, let’s demystify ThreadLocal from an implementation perspective.

ThreadLocalImplementation principle of

Let’s take a look at ThreadLocal through the Official Java documentation.

/ * * *... * * <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
 * @since1.2 * /
public class ThreadLocal<T> {
    // ...
}
Copy the code

Every thread that is alive holds a copy of a thread variable. This statement essentially explains the design philosophy and implementation of ThreadLocal (if this is confusing, ignore this sentence and continue reading). Let’s take a look at the use of ThreadLocal.

We’ll start by creating a new instance of ThreadLocal through its constructor. There is only one default constructor in ThreadLocal.

    /**
     * Creates a thread local variable.
     * @see #withInitial(java.util.function.Supplier)
     */
    public ThreadLocal(a) {}Copy the code

Of course, we could create a ThreadLocal with a default initial with the withInitial method, but we’ll look at get and SET just to understand how this works.

We then assign values to ThreadLocal using the set method, which is where we uncover the first layer of ThreadLocal.

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

Thread. CurrentThread is used to obtain the currentThread.

The currentThread method of a Thread is a native method used to get the currentThread. This is where the Java idea of an object in everything comes into play, with the ethereal notion of a thread represented directly by an object, which we’ll just think of as an incoming thread.

public class Thread implements Runnable {
    /**
     * Returns a reference to the currently executing thread object.
     *
     * @return  the currently executing thread.
     */
    public static native Thread currentThread(a);
}
Copy the code

We get a ThreadLocalMap by calling a getMap method after retrieving the current thread. Let’s look at the getMap method first.

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

    public class Thread implements Runnable {
         /* ThreadLocal values pertaining to this thread. This map is maintained * by the ThreadLocal class. */
        ThreadLocal.ThreadLocalMap threadLocals = null;
    }
Copy the code

As you can see from the getMap method, it is a member variable that returns a thread object directly.

This reverts to the ThreadLocal#set method, which nulls the thread object after retrieving its member, ThreadLocalMap:

• Called if it is not nullsetMethod sets the value we want to store
• If it is empty, it is createdMapObject (herevalueThe value is stored as well as created.

So far I’ve taken a look at the semantics of the set method, but if we’re going to go any further, we need to understand what ThreadLocalMap is and what it does.

    /** * 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 {
        / /...
    }

Copy the code

ThreadLocalMap is a hash table that stores the values of thread variables. A hash table is a data structure that allows us to quickly locate and find data. The details of how this hash table is implemented will be further explored below.

Since it is a hash table, we can think of it as a HashMap for the moment, so that we can go back to the ThreadLocalMap operation above. If ThreadLocalMap is not empty, We store the current object instance (ThreadLocal) as the key and the stored value as the value in the hash table.

Even a HashMap is not thread-safe. ThreadLocal is thread-safe. Take your time here, and it’ll be clear after watching createMap.

Back in the ThreadLocal#set method, the empty ThreadLocalMap is created using the createMap method, which assigns the corresponding key-value pairs. Here we go to createMap to find out:

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

After the author abridged some of the collateral, the idea here became a lot clearer. When a member variable in a thread is judged to be empty, we create an instance (containing stored key-value pairs) using the ThreadLocalMap constructor and assign values to the thread’s member variables.

Here we see why ThreadLocal is thread-safe. Here is a summary by the author:

1. Whenever we useThreadLocalWe are creating a hash key (ThreadLocal), this key is shared by all threads.
2. When we set the thread variable, we will set it in the threadThreadTake out the member variable — the hash tableTheadLocalMapAssign (This hash table is the exclusive property of the current thread, since each request is a thread)
   • If we are in a thread that already has a hash table, we assign directly to the hash table
   • If our thread does not have a hash table, create a hash instance and assign a value to it

As mentioned above, threads can be treated as Thread object instances, which means that each requesting Thread is an independent Thread object, and member variables are not shared between the objects.

Finally, ThreadLocalMap is stored as a key, which means that each ThreadLocal in the program shares the same ThreadLocalMap in the same thread (where different ThreadLocal correspond to different keys).

Now that we have set the value inside the thread variable, we can take it out of the business code — the get method

    /**
     * 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(a) {
        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;
                returnresult; }}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(a) {
        T value = initialValue();
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if(map ! =null)
            map.set(this, value);
        else
            createMap(t, value);
        return value;
    }

    /**
     * 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}.
     *
     * <p>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(a) {
        return null;
    }
Copy the code

In fact, the get method is basically the same as the set method as a whole, and the whole implementation idea is directly given here:

• Gets the hash table of the current threadThreadLocalMapAnd then through willThreadLocalAs the key fromThreadLocalMapGets the corresponding key-value pair and returns it to the caller
  • If the hash table is empty orThreadLocalIf the value as a key is empty, the method is calledsetInitialValueInitialize the corresponding value and return (default to null)
  • If the hash table is not empty and looks forThreadLocalIf the key value is not empty, the corresponding value is returned.

This flow also explains why a call to get on a ThreadLocal object with no assignment returns a null. Of course, we can also set the default value returned by overriding initialValue. There is a default class SuppliedThreadLocal, which can be created using the withInitial method.

    /**
     * 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
     * @since1.8 * /
    public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
        return new SuppliedThreadLocal<>(supplier);
    }

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

        private final Supplier<? extends T> supplier;

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

        @Override
        protected T initialValue(a) {
            returnsupplier.get(); }}Copy the code

The SuppliedThreadLocal class simply inherits ThreadLocal and overrides its initialValue method. This allows us to return the supplied default value for keys that are not assigned.

For other features, SuppliedThreadLocal is the same as ThreadLocal.

Finally, after using ThreadLocal, we need to remove it.

This step is critical because improper use can cause memory leaks or, more seriously, online accidents due to ThreadLocal skewering (as analyzed below).

    /**
     * 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.
     *
     * @since1.5 * /
     public void remove(a) {
         ThreadLocalMap m = getMap(Thread.currentThread());
         if(m ! =null)
             m.remove(this);
     }
Copy the code

For the remove method, ThreadLocal removes the key-value pairs with ThreadLocal as the key after fetching the hash table of the current thread (if not empty).

Now that I’ve answered the initial question why ThreadLocal is thread-safe? If you don’t want to go further, you can really click to stop. I have also shown the schematic design of ThreadLocal below. I’ve omitted some of the implementation details of ThreadLocalMap for ease of understanding:

│ │ │ │ │ │ │ │ │ │ │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ request1 │ │ │ │ Thread1 │ │ │ │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ │ ◄ ─ ─ ┼ ─ ─ ─ ─ ┤ ThreadLocalMap ─ ┼ ─ for │ ThreadLocal1 │ stored value │ │ │ │ │ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │ ThreadLocal2 │ stored value │ │ ▼ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ │ │ ThreadLocal3 │ stored value │ │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │ │ │ │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ │ │ │ Thread2 │ request2 │ │ ◄ ├ ─ ─ ─ ─ ┤ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ │ │ │ ThreadLocalMap ─ ┼ ─ for │ ThreadLocal1 │ stored value │ │ │ │ │ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │ ThreadLocal2 │ stored value │ │ ▼ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ │ │ ThreadLocal3 │ stored value │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ XXXXXXXXXXXXX XXXXXXXXXXX XXXXXXXXX XXXXXXX XXXXX XXX xCopy the code

ThreadLocalMapRealize the principle of

After the above analysis, we have a basic understanding of the entire workflow of ThreadLocal. However, if we want to understand ThreadLocal further, we need to do deep learning of ThreadLocalMap.

Let’s start by looking at how ThreadLocalMap’s internal data structure is constructed.

/** * 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; }}/** * The table, resized as necessary. * table.length MUST always be a power of two. */
    private Entry[] table;
}
Copy the code

If you look at the HashMap source code, you should know what a typical hash table internal implementation structure looks like, which is an array + HashMap, and this is also a typical hash table implementation.

But there is one notable point here, which designates our key (ThreadLocal) as a weak reference. I looked at some of the comments that have been made about this, and I found them in ThreadLocalMap, which says:

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.

A weak reference to a key (ThreadLocal) solves the problem of heavy and persistent use of threadLocalMaps. It may seem confusing to read this, but let’s start with the concepts of strong, soft, weak, and virtual references:

• Strong referenceIf an object has a strong reference, the garbage collector will never collect it.
• Soft referencesIf an object has only soft references, the garbage collector will not reclaim it when there is enough memory; If you run out of memory, the objects are reclaimed.
• A weak referenceWhen the garbage collector thread scans the memory area under its control, once it finds an object with only weak references, it reclaims its memory regardless of whether the current memory space is sufficient or not.
• Phantom referenceAs the name implies, a virtual reference is a virtual reference. Unlike the other references, virtual references do not determine the lifetime of the object. If an object holds only virtual references, it can be collected by the garbage collector at any time, just as if there were no references at all.

Weak references cleared atomically with placement on Reference Queue?

Based on the concept of weak references above, if the object has only weak references, it will be collected by the garbage collector. That is, if all strong references outside the key (i.e., ThreadLocal) are removed, for example, after the method stack is emptied at the end of execution, The key (ThreadLocal) will only exist in the weak reference specified in the Entry, and it will be reclaimed in the next GC, leaving the value of the fetch key (ThreadLocal) empty.

Based on this, we further explain the role of weak reference modifier through the following example.

Let’s first assume that the key (ThreadLocal) is set to a strong reference and see what problems this can cause:

• From the above, we knowThreadLocalMapIt’s unique to each thread, each threadThreadLocalEquivalent to thisThreadLocalMapStudent: a bond of theta. And becauseThreadLocalMapisThreadIs a member variable, so its life cycle is withThread(that is, the thread) walk. If each request starts with a thread, and the request ends with stack emptying and thread destroying, along withThreadLocalMap,ThreadLocalAnd theta corresponds to thetaEntryThere is no problem with using strong references. However, in a normal project, requests are processed through the thread pool, i.e. our thread is reused, and if the corresponding stack is emptied, but the key (i.eThreadLocal) There is one moreStrong referenceinThreadLocalMapCan’t be freed, causing a memory leak.

This problem is solved if we now use weak references to point to keys (i.e., ThreadLocal) :

• After the thread completes execution, the stack is cleared, and the key (i.eThreadLocal) there is only its own weak reference and no other strong reference, next timeGCThe key (i.eThreadLocal) and the corresponding value becomes null.

You think you’re done here? In fact, even if the key (ThreadLocal) is set to weak reference, there will still be a memory leak:

1. forEntryThe deletion ofThreadLocalMapA strategy of lazy deletion is adopted, that is, in the next programget,setandremoveDelete the file during the operation. If a thread in the thread pool is not called, thenEntryIt can’t be emptied, which creates a memory leak.
2. General forThreadLocalA common use of this class is to declare it as a static variable that will exist throughout the life of the project (as in the opening example), which is equivalent to the key (i.eThreadLocal) will always be pointed at by strong references if by itselfA weak referenceFeature, not only can cause memory leaks, but more seriously can cause production accidents (multiplexing threads in the thread pool, incidentally, when this key (i.eThreadLocalThe corresponding value is also reused.

For the convenience of the following analysis, the entries to be lazily deleted are called expired entries

How to avoid this situation? We’ll give the answer at the end of this article, but let’s take a look at how the hash table is implemented.

Once we have a good understanding of the data structure stored in ThreadLocalMap, we can further analyze it along the lines of its use, starting with the constructor of ThreadLocalMap.

static class ThreadLocalMap {
    /** * The initial capacity -- MUST be a power of two. */
    private static final int INITIAL_CAPACITY = 16;
 
    /** * 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

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

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

ThreadLocalMap has two constructors, one of which is a private method that isn’t very useful for understanding how ThreadLocalMap works, so it’s ignored here. In other words, ThreadLocalMap is equivalent to having only one constructor, and we’ll build around that.

Let’s review how ThreadLocalMap is used above: when setting a thread variable, if a ThreadLocalMap does not exist, it is constructed and assigned by the constructor (the ThreadLocalMap constructor discussed here).

Now let’s look at what variables are initialized in the ThreadLocalMap constructor:

1. Initialization size of hash arrayINITIAL_CAPACITYfor16It is also emphasized here that it must be2The power of
2. The number of elements in the hash tablesize
3. Expansion threshold of hash arraythreshold, its default load factorTwo-thirds of the, i.e.,0.66.

• Why is the load factorTwo-thirds of the? It’s not explained here, and so onHashMapNor is it given why the default load factor isThree quarters of, i.e.,0.75.
• Why does the array size have to be2What’s the power of theta? The specific reasons were discussed by the author beforeHashMapBlog has made the relevant note, that is, only the capacity of2The index mapping algorithm can change frommodOperations are converted to bitwise operations. In other words, onlybfor2Omega to the power of omega, algorithma mod b ==> a & (b-1)To be true.

Now let’s see how ThreadLocalMap does index mapping. It maps ThreadLocal’s hashCode to the array’s capacity:

int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1)
Copy the code

How is the Hashcode of ThreadLocal generated? Let’s go back to ThreadLocal:

public class ThreadLocal<T> {
    /** * 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(a) {
        returnnextHashCode.getAndAdd(HASH_INCREMENT); }}Copy the code

In the case of the hash algorithm, it appears that each incoming ThreadLocal gets a hashcode from the static shared variable nextHashCode that increments (HASH_INCREMENT). In fact, the Fibbonachi hashing algorithm (one of the multiplicative hashing algorithms) is used here to generate HashCode, which is somewhat different from the standard multiplicative hashing algorithm (H (k)=(ak mod W)/(W/M)). A = 0x61c88647; k = {1,2,3… , n} is calculated by substituting the formula AK.

About magic number 0x61C88647 is also a need to pay attention to the point, specific information can refer to the following link:

• Stackoverflow answer
• Information on Fibonacci Hashing
• Information on Fibonacci_hashing -wiki

Then, in the constructor, the array index is computed and immediately assigned to the appropriate slot (insert elements immediately, since the inserted element is the first element in the entire ThreadLocalMap, so there is no hash collision). However, if the element is inserted later, it can cause hash collisions. How does ThreadLocalMap solve this problem? You can see this comment on the threadLocalHashCode variable:

ThreadLocals rely on per-thread linear-probe hash maps attached to each thread (Thread.threadLocals and inheritableThreadLocals).

Here we can see that it solves hash collisions through Linear probe, that is to say, ThreadLocalMap solves hash collisions through the open addressing method with linear probe algorithm.

So linear exploration is finding slot I by the hash function, and if there is one, I +1, I +2 and so on, go to the end of the array and go back to the first slot and keep exploring until you find it. Linear probing is relatively simple to implement, but it also has a fatal disadvantage. As the number of continuously occupied slots increases, the average search time increases. We call this clustering.

ThreadLocalMap#set = ThreadLocalMap#set = ThreadLocalMap#set

    static class ThreadLocalMap {

        /**
         * 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(); }/** * Increment I Modulo len
        private static int nextIndex(int i, int len) {
            return ((i + 1 < len) ? i + 1 : 0); }}Copy the code

Let’s leave it at that and sort out the simplest process for now, ignoring the replaceStaleEntry method and the rehash method after insertion. The process becomes much clearer by removing these details, which is typical of open addressing:

1. Calculate the slot position by hashing, if it is not occupied (i.enull) Just insert it
2. If the calculated slot is occupied, we turn on linear probe (nextIndexLook for them one by one
   • And if you find theta during the probekeyIt already exists, overwriting the value to be stored
   • If I go through all the way tonullI couldn’t find a matchkeyIn this case, insert directly tonullPosition (i.e. insert into an unoccupied slot)

Having covered the fundamentals of the set method, let’s return to the governance of hash tables. Let’s start with the rehash method, which is used to scale up hash tables, because the performance of queries deteriorates dramatically when the load factor is exceeded (a common hash operation). Expansion operations in the hash table are very performance-consuming, so an optimization is made before determining the load factor. The entries mentioned above are deleted lazily. Therefore, we usually remove the entries to be deleted lazily before calculating the effective load factor, and then decide whether to expand. The specific cleanup can be seen in the method cleanSomeSlots:

   static class ThreadLocalMap {
        /**
         * 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);
            returnremoved; }}Copy the code

This method does not remove all expired slots, but deletes them proportionally, for reasons explained in the comment:

• If not, it will be faster, but there will be no garbage collection (becauseentryandvalueHave not been released)
• If we wipe them all out at once, it could lead toO(n)Time complexity of

So there’s a tradeoff here, but it’s scaled up so that each call to the method only executes log2(n) times, with n being the input parameter. The specific cleaning process is as follows:

1. First of all getiThe next slot, the algorithm is the same as the linear probenextIndex
2. If it is determined to be expired (i.ekeyIf null) performs the cleanup operation (methodexpungeStaleEntry)
3. Update the parameters after cleaningiIs used for cleaning up in the next cycle (the number of cycles islog2(n))

The parameter I indicates that there is no index slot with expired entries, so the clearing operation starts after I (since I has not expired, the clearing of I is ignored).

Next, let’s look at the actual cleanup method expungeStaleEntry:

    static class ThreadLocalMap {
        /**
         * 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; }}}returni; }}Copy the code

The expungeStaleEntry method is the actual method of clearing the slot. The following is the entire clearing process:

1. The argument passed in stands forkeyFor empty slots (i.e. expired slots), so directly putentrySet tonullremove
2. Proceed to the element after the current slotrehashOperate until the slot is encounterednullstop
   • If you encounterkeyfornull(that is, it has expired), by the way, put the correspondingentryAlso removed
   • ifentryIf it is normal, it passes againhashcodeDo a mapping
     • If the calculated index slot is different from the current one, clear the current slot (set the slot tonull), then recalculate the slot position and insert
     • If the calculated index slot is the same as the current one, the loop continues
3. Return slot fornullIndex (used here for the outer layercleanSomeSlotsContinue to cycle clean)

Why rehash here? In fact, this refers to the open addressing query and delete mechanism, after the element is deleted, it is usually used to identify the deleted element with a tag rather than leaving the element empty in order not to affect the query. The problem with this is that if we insert a large number of elements and then delete a large number of elements, the query time complexity of the entire hash table will be increased. An optimization is to rehash the following elements after deletion to push the normal entry forward, thus avoiding the problem mentioned above.

The cleanSomeSlots method and expungeStaleEntry method are two important methods for the governance of open addressing. Here we summarize the respective functions of the two methods:

• expungeStaleEntryMethod: From the input parameterstaleSlotAll the way up to the first empty slotnull) to clean up andrehashAnd returnrehashIndex of the position of the next empty slot.
• cleanSomeSlotsMethod: From the input parameteriA slot (not included) after the start, proceedlog2(n)timeexpungeStaleEntryOperation, each timeexpungeStaleEntryDepends on the last entryexpungeStaleEntryThe returned.

If the load factor is still greater than the threshold after clearing expired entries, the rehash operation is required. Let’s look at the following:

    static class ThreadLocalMap {

        /** * 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(a) {
            expungeStaleEntries();

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

        /** * Expunge all stale entries in the table. */
        private void expungeStaleEntries(a) {
            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); }}}Copy the code

Here we see that the rehash operation also does a cleanup of expired slots. If we did a cleanup of expired slots proportionally before the rehash operation came in, then we did a cleanup of all slots proportionally (as you can see from the code). If the threshold is still exceeded, resize is required:

    static class ThreadLocalMap {

        /** * Double the capacity of the table. */
        private void resize(a) {
            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; }}Copy the code

The resize process is fairly straightforward. Simply create an array that is twice the size of the original array and then use the hash function to migrate elements from the original array to the new array one by one. Although all slots are traversed to clean up before resize is called, there is also nulling of the key, as some stale ThreadLocal may also be generated during capacity expansion.

Here, we return to the point held by the set method above. If the key is found to be empty during the linear probe, we can also overwrite the new one. Now look at this method and believe you will be much easier) :

   static class ThreadLocalMap {

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

            // This is used to mark where the cleanup started
            // 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;
            // Find the first expired position from 'null' by looping forward
            for (inti = 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 (inti = 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)
                        // Remember the ith slot of the node being traversed. The ith slot is the existing key to be replaced
                        // Failed to find the first expired slot forward and failed to find the expired slot backward
                        // Because the position passed in by staleSlot is expired, the position I and staleSlot are swapped after overwriting the value
                        // Position I is out of date after the swap, so this corresponds to position I starting (including) cleanup
                        // This also explains why the swap is done. My point is to reduce the number of elements that move later
                        slotToExpunge = i;
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    return;
                }

                // Failed to search forward for the first expired slot
                // 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);

            // Execute cleanup if found; If you can't find a slot to clean, skip it. StaleSlot is excluded because staleSlot is already covered
            // If there are any other stale entries in run, expunge them
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }
    }
Copy the code

It is not difficult to just look at the replace operation, which is simply to cover the staleSlot slots, but it also performs the cleaning of expired slots. How to clean it up? You can see that the comment has this paragraph: 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.). This method clears expired entries contained between two NULls at run time. SlotToExpunge: slotToExpunge: slotToExpunge: slotToExpunge: slotToExpunge: slotToExpunge: slotToExpunge: slotToExpunge

1. First, the element is assigned
   • If it doesn’t exist in the hashkey, directly in the correspondingstaleSlotSet the value
   • If I find the corresponding in the hashkey, overrides the original value and matchesstaleSlotThe slot of the position does the swap (why do the swap here? My point is to move elements as little as possible)
2. To clear expired slots, search for the first expired slot in the range and clear the expired slot
   • By looping forward, looking for thenullStart the location of the first expired slot
   • If the forward loop doesn’t work, start looking backwards
   • Finally, if not found (i.eslotToExpunge ! = staleSlotThe situation,staleSlotIs itself replaced, so do not count), do not clean up

Finally, the cleanSomeSlots(expungeStaleEntry(slotToExpunge), len) call is a reminder of what the cleanSomeSlots and expungeStaleEntry methods do. The expungeStaleEntry method is called outside of the cleanSomeSlots method. Because the cleanSomeSlots method ignores the location of the currently passed argument (the argument also states that the passed location does not need to be cleaned up), an additional call is made outside. And the reason for using it this way rather than rewriting a specific method is probably for more reuse of the code (probably lazy…). Of course, if this scenario is more than enough, I’m sure it will create a special method. (I usually do that anyway…)

ThreadLocalMap () {get (); remove ();

   static class ThreadLocalMap {

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

• Compute the array index by hashing
  • If the slot is empty, return directlynull
  • If the slotkeyWith what to look forkeySame, return directly
  • If the slotkeyI’m going to do linear exploration until I find thetakeyThe corresponding data is returned or cannot be foundkeyReturns an empty

During this period, the expired slot was also cleaned, which will not affect the subsequent linear exploration. This is because the subsequent normal entry will be brought to the front (position I and after it) during cleaning.

Let’s look at the remove method again:

   static class ThreadLocalMap {

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

Same idea

• Compute the array index by hashing
  • If the slot is empty, end the method
  • If the slotkeyWith what to look forkeySame, callexpungeStaleEntryClean up the slot and its data (and then the adjacent slot to check again)
  • If the slotkeyI’m going to do linear exploration until I find thetakeyPerform the previous step. Otherwise, the endremoveoperation

At this point, the entire ThreadLocal analysis is really complete. After analyzing the details, I modified the above image and added some implementation details:

+---------------------------------+ +---------------------------------+ +---------------------------------+ | | | | | | | StrongReference=>ThreadLocal1 | | StrongReference=>ThreadLocal2 | | StrongReference=>ThreadLocal3 | | | | | | | +----------------+----------------+ +--------------+------------------+ +------+--------------------------+ | | | | +-----------------------------+ | | | | +----------------------------------------------------------------+ | | | | | ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | | │ Entry │ | | | ├ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | + -- -- -- -- > key │ WeakReference = > ThreadLocal1 < -- -- + | | | ├ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | | value │ │ stored value │ | | | | └ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ | | | | | | | | ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | | | │ Entry │ | | | | ├ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | │ │ | + -- -- > key │ WeakReference = > ThreadLocal2 < -- -- -- -- -- -- -- -- -- + | │ │ | | ├ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | value │ │ stored value │ | | | │ │ │ │ │ table [] | | └ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ | | | │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | | | request1 │ │ │ │ Thread1 │ │ ThreadLocal1 = > index1 + - + | ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | | │ │ │ │ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | │ Entry │ | | | │ │ ◄ ─ ─ ┼ ─ ─ ─ ─ ┤ ThreadLocalMap + - > │ ThreadLocal2 = > index2 + - + ├ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | │ │ │ │ │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ key │ WeakReference = > ThreadLocal3 < -- -- -- -- -- -- -- -- -- -- -- -- -- -- + │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ │ ThreadLocal3 = > and index3 + -- -- -- -- -- > ├ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | │ ▼ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ value │ │ stored value │ | | | │ │ └ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ | | | │ │ │ | | | │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | | │ │ │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ │ table [] │ ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | | │ │ │ │ Thread2 │ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ Entry │ | | | request2 │ │ ◄ ├ ─ ─ ─ ─ ┤ │ │ ThreadLocal1 = > index1 + -- -- -- -- - > ├ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | | │ │ │ │ ThreadLocalMap + - > ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ │ key │ WeakReference = > ThreadLocal1 < -- -- + | | │ │ │ │ │ │ ThreadLocal2 = > index2 + - + ├ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | │ │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ├ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | value │ │ stored value │ | | │ ▼ │ │ ThreadLocal3 = > and index3 + - + | └ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ | | │ │ └ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ | | | | │ │ | | ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | XXXXXXXXXXXXX | | │ Entry │ | | XXXXXXXXXXX | | ├ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | | XXXXXXXXX | + - > │ key │ WeakReference = > ThreadLocal2 < -- -- -- -- -- -- -- -- -- + | XXXXXXX | ├ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | XXXXX | value │ │ stored value │ | | XXX └ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ X | | | | ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐ | | │ Entry │ | | ├ ─ ─ ─ ─ ─ ─ ┬ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ | + -- -- -- > │ key │ WeakReference = > ThreadLocal3 < -- -- -- -- -- -- -- -- -- -- -- -- -- -- + ├ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┤ value │ │ stored value │ └ ─ ─ ─ ─ ─ ─ ┴ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘Copy the code

Extension:InheritableThreadLocal

The ThreadLocal class is only available on the current thread. If a child thread is opened to perform a task, it cannot use the value stored in the ThreadLocal. So what’s the solution? Java provides an InheritableThreadLocal class that is used in this scenario.

/**
 * This class extends <tt>ThreadLocal</tt> to provide inheritance of values
 * from parent thread to child thread: when a child thread is created, the
 * child receives initial values for all inheritable thread-local variables
 * for which the parent has values.  Normally the child's values will be
 * identical to the parent's; however, the child's value can be made an
 * arbitrary function of the parent's by overriding the <tt>childValue</tt>
 * method in this class.
 *
 * <p>Inheritable thread-local variables are used in preference to
 * ordinary thread-local variables when the per-thread-attribute being
 * maintained in the variable (e.g., User ID, Transaction ID) must be
 * automatically transmitted to any child threads that are created.
 *
 * @author  Josh Bloch and Doug Lea
 * @see     ThreadLocal
 * @since1.2 * /

public class InheritableThreadLocal<T> extends ThreadLocal<T> {
    /**
     * Computes the child's initial value for this inheritable thread-local
     * variable as a function of the parent's value at the time the child
     * thread is created.  This method is called from within the parent
     * thread before the child is started.
     * <p>
     * This method merely returns its input argument, and should be overridden
     * if a different behavior is desired.
     *
     * @param parentValue the parent thread's value
     * @return the child thread's initial value
     */
    protected T childValue(T parentValue) {
        return parentValue;
    }

    /**
     * Get the map associated with a ThreadLocal.
     *
     * @param t the current thread
     */
    ThreadLocalMap getMap(Thread t) {
       return t.inheritableThreadLocals;
    }

    /**
     * Create the map associated with a ThreadLocal.
     *
     * @param t the current thread
     * @param firstValue value for the initial entry of the table.
     */
    void createMap(Thread t, T firstValue) {
        t.inheritableThreadLocals = new ThreadLocalMap(this, firstValue); }}Copy the code

InheritableThreadLocal propagates thread variables between threads and child threads. If InheritableThreadLocal propagates thread variables with the same value as the parent thread, we can override childValue to make this different. Of course, childValue must be overridden with or without modification, because ThreadLocal does not support calls to this method. Ok, so we start parsing InheritableThreadLocal, which behaves exactly like its parent, except that it overrides three methods.

GetMap () : getMap (); getMap () : getMap (); getMap () : getMap ();

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

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

ThreadLocal obtains and stores hash tables from Thread members threadLocals. InheritableThreadLocal does this in the member variable inheritableThreadLocals of the Thread. Here we’re looking at Thread

public class Thread implements Runnable {
    /* ThreadLocal values pertaining to this thread. This map is maintained * by the ThreadLocal class. */
    ThreadLocal.ThreadLocalMap threadLocals = null;

    /* * InheritableThreadLocal values pertaining to this thread. This map is * maintained by the InheritableThreadLocal class. */
    ThreadLocal.ThreadLocalMap inheritableThreadLocals = null;
}
Copy the code

As you can see, the Thread instance also sets up a member variable that allows us to use Thread variables in this way (inheritance), and our subclasses switch by changing the Thread member variable they get. So there’s a problem here, how do you assign to a child thread? We can see the constructor for Thread creation (see the simplest one here) :

public Thread(a) {
    init(null.null."Thread-" + nextThreadNum(), 0);
}

private void init(ThreadGroup g, Runnable target, String name,
                   long stackSize) {
    init(g, target, name, stackSize, null.true);
}

private void init(ThreadGroup g, Runnable target, String name,
                    long stackSize, AccessControlContext acc,
                    boolean inheritThreadLocals) {
    / /..
    
    Thread parent = currentThread();


    // ..
    if(inheritThreadLocals && parent.inheritableThreadLocals ! =null)
        this.inheritableThreadLocals =
            ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);
    // ..
}
Copy the code

If you call currentThread, you will get the old/parent thread, even though you are initializing a new thread. So the parent. The inheritableThreadLocals access to or old/parent hash, but did new Thread objects, namely the inheritableThreadLocals Thread is new, If inheritableThreadLocals doesn’t deliver thread variables, then inheritableThreadLocals does. Here we return to the createInheritedMap and private constructor methods we ignored above:

public class ThreadLocal<T> {

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

    /**
     * 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++;
                }
            }
        }
    }
}
Copy the code

This is where childValue comes into play. ChildValue calls the parent thread, not the child thread, so the parent thread decides how to get the value. InheritableThreadLocal replicates the same value by default, and if you want to customize it, you can use InheritableThreadLocal and override childValue. (Note that this is not overwriting ThreadLocal, which is impossible because you can’t override getMap and createMap.)

Finally, let’s talk about some of the related issues mentioned above. Okay?

• Expired Entry memory leakage problem?

  As mentioned above, lazy deletion of expired entries and static variable declaration of ThreadLocal in the process of use may cause memory leaks. This problem cannot be solved by weak references alone. To solve this problem, we need to manually delete remove after using ThreadLocal

• Why open addressing instead of chaining?

  It is fine to choose open addressing in the case of small amounts of data, because it does provide better performance than chaining because of its small footprint and no newly allocated memory consumption. However, in the case of large amount of data, chaining method is preferred. Because a large amount of data takes up a large amount of contiguous space, and most of the data may be empty, thus greatly reducing the CPU cache hit ratio. Moreover, the deletion mechanism for open addressing may lead to a relatively high cost of query time complexity, which also needs to be considered. Of course, ThreadLocalMap does some optimizations of its own, such as rehash for adding and removing elements, but this can also cause a large amount of element movement, so you need to be careful when using too many ThreadLocalizations, for example.

If you want to store a little bit more data in a thread variable, you can use some optimizations, such as:

public class ThreadLocalHolder{

    /** * The constant threadContext. */
    private final static ThreadLocal<Map<String, Object>> THREAD_CONTEXT = new ThreadLocal<Map<String, Object>>() {
        @Override
        protected Map<String, Object> initialValue(a) {
            return newHashMap<>(); }};/** * get the instance of thread Context Map. * *@returnThread Context Map instance */
    private static Map<String, Object> getContextMap(a) {
        return THREAD_CONTEXT.get();
    }

    /**
     * Put.
     *
     * @param key   the key
     * @param value the value
     */
    public static void put(String key, Object value) {
        getContextMap().put(key, value);
    }

    /**
     * Remove object.
     *
     * @param key the key
     */
    public static void remove(String key) {
        getContextMap().remove(key);
    }

    /** * Clears the thread of all held objects. For reuse! * /
    public static void remove(a) { THREAD_CONTEXT.remove(); }}Copy the code

When used this way, ThreadLocalMap is treated as an intermediate layer, and the actual hash goes to the HashMap.

Reprint is prohibited without my permission