1.ThreadLocal

1.1 summary of ThreadLocal

Thread-private (thread-private) is a tool class for storing, retrieving, and deleting thread-related data. The actual thread-private data is not stored in this object. There is a ThreadLocalMap in the ThreadLocal class, which is an array Hash table. The Thread class has a member variable of type ThreadLocalMap.

This ThreadLocalMap object is actually created and assigned to this property when the data is stored. The data stored by calling ThreadLocal is actually stored here. This object is an internal object of the current thread, so if you want to store thread-private data, you actually store it in an object of the current thread, not in a ThreadLocal object.

1.2 ThreadLocalMap

ThreadLocalMap we all know that ThreadLocalMap is a Hash table implemented in arrays, but how is it implemented? Let’s look at the implementation of its underlying data structure.

1.2.1 Data structure of ThreadLocalMap

An Entry class is defined in ThreadLocalMap that encapsulates the Hash table’s keys and values. As you can see, the implementation uses a ThreadLocal object as a key, and the ThreadLocal reference is a weak reference.

The bottom line of ThreadLocalMap is to create an array of entries to implement a Hash table. The Hash table has an initial capacity of 16.

The capacity expansion threshold is array lengthTwo-thirds of the.

1) Then whyThreadLocalWhat about weak references?

Because if we set it to strong reference, when we no longer use the ThreadLocal object, even if we set the reference to the ThreadLocal object in the stack to NULL, we still can’t reclaim the object. Because there is also a key reference in the Entry in the heap, it points to the object as a strong reference. We implement the Hash table by maintaining an array of entries in a ThreadLocalMap, whose reference is in the current thread object. As a result, this data persists until the current thread is destroyed, resulting in a memory leak.

2) Why notvalueWhat about weak references?

ThreadLocal can be set to weak references because there is still a strong reference object in the stack that points to a ThreadLocal object in the heap during use. But if value is also set to a weak reference, there is no strong reference to value in the stack. That is, a value has only weak references to it, so whenever GC happens, even if you’re still using ThreadLocal, the value will be reclaimed.

1.2.2 ThreadLocalMap code analysis

With that in mind, how do we access data from this Hash table? Take a look at its get and set methods.

1) set method

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); // Get an array subscript int I = key.threadLocalHashCode & (len-1); For (entry e = TAB [I]; 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) {// Replace the expired entry with replaceStaleEntry(key, value, I); return; }} // If it is not iterated through the array, create an entry and add it to the position where Entry = null. tab[i] = new Entry(key, value); // Array entry number + 1 int sz = ++size; /* If a heuristic does not clear expired entries and the number of arrays is greater than the expansion threshold, rehash */ if (! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }Copy the code

(1) ThreadLocalMap hashCode

As you can see, ThreadLocalMap gets its subscript by taking the ThreadLocal attribute threadLocalHashCode and subtracting the array length by one. So how does this hashCode work?

As shown above, nextHashCode starts out as an atomic class object with a value of 0. The nextHashCode method is called each time threadLocalHashCode is fetched, adding a fixed hash increment to the value of the object. The HASH_INCREMENT value is a special value that allows data to be evenly distributed across a 2n hash table. This minimizes hash collisions

(2)replaceStaleEntry

We see that when we iterate over an expired Entry (k=null Entry), we call the replaceStaleEntry method to replace the expired Entry. `

private void replaceStaleEntry(ThreadLocal<? > key, Object value, int staleSlot) { Entry[] tab = table; int len = tab.length; Entry e; /* The index of the last expired entry is traced forward until the index of the last expired entry is null. */ for (int I = prevIndex(staleSlot, len); prevIndex(staleSlot, len); prevIndex(staleSlot, len); (e = tab[i]) ! = null; i = prevIndex(i, len)) if (e.get() == null) slotToExpunge = i; /* for (int I = nextIndex(staleSlot, len); (e = tab[i]) ! = null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get(); If (k == key) {/* If an identical key is encountered, replace it and then swap the location of the current and expired entry */ e.value = value; tab[i] = tab[staleSlot]; tab[staleSlot] = e; /* If no expired entry is found in the last traverse, the current I is used as the slot to eliminate because the current entry is already expired in the swap position. */ if (slotToExpunge == staleSlot) slotToExpunge = i; // Start probing with the current expired entry, then heuristic cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); // After clearing expired data, return; } /* If an expired entry is encountered during the backward traversal, it indicates that the cleanup should start from the front, */ if (k == null && slotToExpunge == staleSlot) slotToExpunge = I; } // If the same key is not found, a new entry TAB [staleSlot]. Value = null; tab[staleSlot] = new Entry(key, value); If (slotToExpunge!) if (slotToExpunge! = staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); } `Copy the code

(3) Why exchange?

It can be seen that when we encounter an entry with the same key, we not only overwrite the value, but also exchange the location of the expired data. Why is this?

Since ThreadLocalMap uses linear probing to resolve hash collisions, if we don’t swap their positions, the expired data will be cleared and the expired entry will become an empty entry. If the key of the next entry is the same as the key of the current entry, the entry will find the empty position through linear detection and insert directly, and duplicate keys will exist in the hash table. So, we need to swap their positions to ensure that the hash key is not duplicated.

(4) Why are we looking forward to slotToExpunge?

In order to detect as large a range as possible during exploratory cleaning.

(5) Exploratory cleaning

In the code comments above, we mentioned exploratory cleaning, which is actually what expungeStaleEntry implements. `

private int expungeStaleEntry(int staleSlot) { Entry[] tab = table; int len = tab.length; TAB [staleSlot]. Value = null; tab[staleSlot] = null; size--; // Rehash until we encounter null Entry e; int i; Null for (I = nextIndex(staleSlot, len); (e = tab[i]) ! = null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get(); // If key is null, clear if (k == null) {e.value = null; tab[i] = null; size--; } else {// If not null, rehash until a null position is found and insert int h = k.htReadLocalHashCode& (len-1); if (h ! = i) { tab[i] = null; // Unlike Knuth 6.4 Algorithm R, we must scan until // null because multiple entries could have been stale. while (tab[h] ! = null) h = nextIndex(h, len); tab[h] = e; } } } return i; } `Copy the code

In fact, the exploratory clearing process is as follows: The probe starts from the expired entry and clears the expired entry, rehashes the unexpired entry, adjusts the position, and stops the probe when the null entry is detected.

1. Why do I adjust the positions of traversal entries that are not expired?

In fact, this is to ensure that the Hash key is not repeated. If you don’t reposition the key, the previous null position will be directly occupied when the inserted key is repeated, and duplicate keys may exist later.

2. Why all of thementry = nullAs a loop stop condition?

Because the linear detection method is used, the position of the entry is adjusted to ensure the uniqueness of the key. If the entry is null, it means that there is no hash collision data.

(6) Heuristic cleaning

private boolean cleanSomeSlots(int i, int n) { boolean removed = false; Entry[] tab = table; int len = tab.length; I = nextIndex(I, len); Entry e = tab[i]; if (e ! = null && e.get() == null) { n = len; removed = true; i = expungeStaleEntry(i); } //n = n>>>1, unsigned right shift, equivalent to n = n/2. } while ( (n >>>= 1) ! = 0); return removed; }Copy the code

From the source code we can see that the heuristic cleaning is not O(n) time complexity cleaning, but O(logn) time complexity cleaning, starting from the incoming I, if an expired entry is found, then the probe cleaning will be called to clean, and the loop n reassign to the array length.

(7)rehash

If heuristic cleansing does not occur after data insertion and the number of elements is now greater than the expansion threshold, rehash is performed.

Rehash is called firstexpungeStaleEntriesMethod that iterates through the hash table, deletes all expired entries, and rehashes all unexpired data.

If the number of expired entries is still greater than 3/4 of the threshold after all expired entries are cleared, expand the capacity twice as large as the original one and reset the threshold.

(8) Summary of set method

Through the above analysis, we can summarize the execution process of set method:

1. The array subscript is obtained by subtracting the array length by 1 from ThreadLocal’s threadLocalHashCode property

2. Probe from this array subscript

   • If a duplicate key is found first, the value of the entry is replaced and the end of execution is returned.

   • If an expired entry is found first, it replaces the expired entry and returns the end of execution

     • If duplicate keys are found after the expired entry is found, the value is overridden and the location is switched.
     • If a null entry is found, a new entry is created and placed in the place of the expired entry.
     • In general, after setting values, exploratory and heuristic cleaning is performed

   • If an entry is null, a new entry is created and the data is placed there.

     • If heuristic cleansing does not occur after data insertion and the number of elements is now greater than the expansion threshold, rehash is performed
     • During rehash, all entries in the array are scanned, all expired entries are cleaned up, and all elements are repositioned.
     • If the number of entries is still greater than 3/4 of the threshold, expand the number twice.

2) the get method

The threadLocalHashCode variable is also used to get a subscript to see if the keys are equal. If the keys are equal, the entry is returned.

② If the keys are not equal, the search is backward from the current index until entry is null.

1. If the key is found equal, return entry
2. If an expired entry is found, exploratory clearing is performed.
3. If not found, null is returned.

3) the remove method

throughthreadLocalHashCodePosition, iterating from this index until entry is NULL. If the target is found, the weak reference is removed for exploratory cleanup.

1.3 ThreadLocal source

1.3.1 the get method

① Get the current thread object, and get the ThreadLocalMap object from the current thread.

② If the map is not null, the current ThreadLocal object is used to get an entry, and the value is returned.

③ If map is null, call setInitialValue and return its return value.

① place an initialValue into ThreadLocal using the initialValue method.

If the map is null, new a ThreadLocalMap object and assign it to the variable in the thread object, adding data.

3 If the value is not null, set the default value.

4 Return to the default value

1.3.2 set method

① Get the current thread object and check whether map exists

(2) If no, create a map and add data

3 If yes, add data directly

1.3.3 the remove method

If the map exists, call remove of ThreadLocalMap to delete data.