1. What is ThreadLocal? And its general purpose
(1) Definition (2) function
ThreadLocal is used to provide local variables for internal use in threads. In other words, it uses a set of mechanisms to ensure that you create a new variable ThreadLocal. In a thread, set the ThreadLocal variable to an instance a of type A that an individual thread cannot access. Then, after a period of time, you can get instance a from the ThreadLocal variable. The key point is that this ThreadLocal variable can cross threads. At the same time, JDK recommends that you set the ThreadLocal variable to static, because it needs to be globally unique in multiple threads, and it also has the ability to provide local variables in multiple threads when it is globally unique.
- Summary:
- Thread Concurrency: in the scenario of multithreading concurrency
- Pass data: we can pass public variables in the same thread and different components through ThreadLocal
- Thread isolation: the variables of each thread are independent and will not affect each other
- Firstly, ThreadLocal is not used to solve the problem of multi-threaded access to shared objects. Generally, ThreadLocal The object set () to the thread is the object used by the thread itself. Other threads do not need to access it or cannot access it. Different objects are accessed in each thread.
- In addition, ThreadLocal enables each thread to maintain an independent object, not through ThreadLocal Set (), but an object created by the operation of the new object in each thread. Each thread creates one, not a copy or copy of any object. Through ThreadLocal Set () saves the reference of the newly created object to each thread's own map. Each thread has such a map and executes ThreadLocal When get (), each thread takes out the objects put in from its own map, so the objects taken out are the objects in its own thread, and the ThreadLocal instance is used as the key of the map.
- If ThreadLocal What set () goes into is the same object shared by multiple threads, so the ThreadLocal of multiple threads Get () still gets the shared object itself, and there is still a problem of concurrent access.
- In short, ThreadLocal is not used to solve the problem of object sharing access, but mainly provides a method to maintain objects and a convenient object access method to avoid parameter passing. Two points are summarized:
- Each thread has its own ThreadLocalMap class object, which can keep the thread's own objects in it. Each tube has its own, and the thread can correctly access its own objects.
- Take a shared static ThreadLocal instance as the key, save the references of different objects to the ThreadLocalMap of different threads, and then get the object saved by your own thread through the get() method of this static ThreadLocal instance everywhere the thread executes, avoiding the trouble of passing this object as a parameter.
2. What is the implementation principle of ThreadLocal?
(1) Guess principle (2) actual situation (3) what are the design advantages?
Benefits of this design
(1) After this design, the number of entries stored in each Map will be reduced. Because the previous storage quantity was determined by the number of threads, now it is determined by the number of ThreadLocal. In practical application, the number of ThreadLocal is often less than the number of threads.
(2) After the Thread is destroyed, the corresponding ThreadLocalMap will also be destroyed, which can reduce the use of memory.
- Threads retain their own data
- The key is optimized and weak reference is adopted
Implementation of ThreadLocal (Section 2)
1. Preliminary
- threadLoaclHashCode
//Thread get threadLocal During get(), if it is the first time to get on a threadLocal object, a value will be assigned to the current thread //The value and the current threadLocal object are wrapped as an entry. Where key is the threadLocal object and value is the value generated by the threadLocal object for the current thread //Where is the entry stored in the map of threadlocales of the current thread? It is related to the threadLocalHashCode of the current threadLocal object. // The location obtained by using threadlocalhashcode & (table. Length - 1) is the location where the current entry needs to be stored. private final int threadLocalHashCode = nextHashCode();
- nextHashCode
/** * The next hash code to be given out. Updated atomically. Starts at * zero. * It will be used when creating ThreadLocal objects. Each time a ThreadLocal object is created, it will use nextHashCode to assign a hash value to this object. */ private static AtomicInteger nextHashCode = new AtomicInteger();
- HASH_INCREMENT
/** * 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. * Each time a ThreadLocal object is created, the ThreadLocal The value of nexthashcode will increase by 0x61c88647. * This value is very special. It is Fibonacci number, also known as golden section number. The hash increment is this number, which brings the advantage that the hash distribution is very uniform. */ private static final int HASH_INCREMENT = 0x61c88647;
- nextHashCode()
/**
* Returns the next hash code.
* When creating a new ThreadLocal object, a hash will be assigned to the current object. Use this method.
*/
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
- initialValue()
/*
* Returns the "initial value" of the current thread for this thread local variable. This method will use get for the first time in the thread
* Method is called when accessing variables, unless the set method is invoked before the thread is used. In this case, the initialValue method will not be invoked for the thread.
* Typically, this method is called at most once per thread, but may be called again in the case of subsequent calls to remove followed by get.
* This implementation only returns null. If the programmer wants the thread local variable to have an initial value other than null, he must subclass ThreadLocal and override this method. Typically, anonymous inner classes will be used.
* @return The initial value of this thread's local
* null is returned by default. Generally, we need to override this method.
*/
protected T initialValue() {
return null;
}
2. Get the copy data of the current thread and deeply analyze the source code of the get() method
- 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
*
* Returns the thread local variable associated with the current thread and the current ThreadLocal object, which can only be accessed by the current thread.
* If the current thread is not allocated, it is allocated to the current thread (using the initialValue() method)
*/
public T get() {
//Get current thread
Thread t = Thread.currentThread();
//Get the threadLocals of the Thread object of the current Thread, that is, the reference of the ThreadLocalMap object of the current Thread
ThreadLocalMap map = getMap(t);
//map!=null condition holds: it indicates that the current thread already has its own ThreadLocalMap object
if (map != null) {
//key: (this) current threadLocal object
//Call map Getentry () method to get the entry associated with the threadLocal in threadLocalMap
ThreadLocalMap.Entry e = map.getEntry(this);
//Condition true: indicates that the current thread has initialized the thread local variable associated with the current threadLocal object
if (e != null) {
@SuppressWarnings("unchecked")
T result = (T)e.value;
//Return value
return result;
}
}
//How many situations are there in the implementation?
//1. The threadLocalMap corresponding to the current thread is null
//2. The current thread and the current threadLocal object have not generated associated thread local variables
//The setInitialValue() method initializes the value associated with the current threadLocal object of the current thread.
//If the current thread does not have threadLocalMap, it will also initialize and create the map.
return setInitialValue();
}
- initialValue() initializes the thread copy variable
/*
* null is returned by default. Generally, we need to override this method.
*/
protected T initialValue() {
return null;
}
- setInitialValue() sets the thread copy variable
/**
* Variant of set() to establish initialValue. Used instead
* of set() in case user has overridden the set() method.
*
* setInitialValue()Method to initialize the value associated with the current threadLocal object of the current thread.
* If the current thread does not have threadLocalMap, it will also initialize and create the map.
* @return the initial value
*/
private T setInitialValue() {
//Call the initialValue method of the current ThreadLocal object. In most cases, we will override this method to return the value of the initial value.
//value is the thread local variable associated with the current thread by the current ThreadLocal object.
T value = initialValue();
//Gets the current thread object
Thread t = Thread.currentThread();
//Get the threadLocals inside the current thread, that is, the threadLocalMap object.
ThreadLocalMap map = getMap(t);
//Condition holds: it indicates that the threadLocalMap object has been initialized inside the current thread. (threadlocales of each thread will be initialized only once.)
if (map != null) {
//Save the current threadLocal and thread local variables generated by the current thread.
//key: current threadLocal object value: local variables related to the current threadLocal of the thread
map.set(this, value);
} else {
//This indicates that threadLocalMap has not been initialized inside the current thread. Here, call createMap to create a map for the current thread
//Parameter 1: current thread parameter 2: thread local variables related to current threadLocal
createMap(t, value);
}
//Returns the local variable of the thread related to the current threadLocal
return value;
}
- createMap() initializes thread ThreadLocalMap variable
void createMap(Thread t, T firstValue) {
//The meaning of passing t is to access the t.threadLocals field of the current thread and initialize this field.
//new ThreadLocalMap(this, firstValue)
//Create a ThreadLocalMap object. The initial k-v value is: This < current threadLocal Object >, which is the local variable related to the current threadLocal
t.threadLocals = new ThreadLocalMap(this, firstValue);
}
3. Modify the source code of the current thread replica data set() method and deeply analyze it
/**
* 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.
*
* Modify the thread local variable associated with the current threadLocal object for the current thread.
*/
public void set(T value) {
//Get current thread
Thread t = Thread.currentThread();
//Gets the threadLocalMap object of the current thread
ThreadLocalMap map = getMap(t);
//Condition holds: it indicates that the threadLocalMap of the current thread has been initialized
if (map != null) {
//Call threadlocalmap Override or add the set method.
map.set(this, value);
} else {
//This indicates that the current thread has not created a threadLocalMap object.
//Parameter 1: current thread parameter 2: thread local variables related to current threadLocal
createMap(t, value);
}
}
4. Delete the copy data of the current thread and deeply analyze the source code of the remove() method
/**
* 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
*
* Removes the thread local variable associated with the current threadLocal object from the current thread.
*/
public void remove() {
//Gets the threadLocalMap object of the current thread
ThreadLocalMap m = getMap(Thread.currentThread());
//Condition holds: it indicates that the current thread has initialized the threadLocalMap object
if (m != null)
//Call threadlocalmap Remove (key = current threadLocal)
m.remove(this);
}
Kernel analysis: (Section III)
- The core of ThreadLocal is actually ThreadLocalMap object
1) Static internal class Entry analysis (0 ~ 12:58)
Weak reference
Internal class 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.
*
* What is a weak reference?
* A a = new A(); //Strong reference
* WeakReference weakA = new WeakReference(a); //Weak reference
*
* Strong reference a = null; Time
* At the next GC, object a is recycled, regardless of whether there are weak references associated with the object.
*
* key Weak reference reservation is used, and the key stores the threadLocal object.
* value Strong reference is used, and value stores the value associated with the current thread by the threadLocal object.
*
* entry What are the benefits of this design?
* When the threadLocal object loses its strong reference and the object is recycled by GC, the key of the entry associated with the threadLocal object in the hash table is null
* Go to key again When you get (), you get null.
* From the perspective of map, you can distinguish which entries are expired and which entries are not expired.
*/
static class Entry extends WeakReference<ThreadLocal<?>> {
/** The value associated with this ThreadLocal. */
Object value;
Entry(ThreadLocal<?> k, Object v) {
//Through super(k); The construction method of WeakReference is called to realize weak reference
super(k);
value = v;
}
}
2) ThreadLocalMap field analysis / simple methods setThreadshold(), nextIndex(), prevIndex() (12:58 ~ 22:50)
- Initial length of hash table array
/** * The initial capacity -- MUST be a power of two. * Initializes the initial length of the hash table array within the current map */ private static final int INITIAL_CAPACITY = 16;
- threadLocalMap internal hash array reference
/** * The table, resized as necessary. * table.length MUST always be a power of two. * threadLocalMap Internal hash table array reference. The length of the array must be to the power of 2 */ private Entry[] table;
- Hash table array occupancy
/** * The number of entries in the table. * How many entries are stored in the current hash table array. */ private int size = 0;
- Capacity expansion trigger threshold
/** * The next size value at which to resize. * Capacity expansion trigger threshold, initial value: len * 2/3 * The rehash() method is invoked after triggering. * rehash() Method first do a full check of the global expired data and remove all expired entries in the hash table. * If the number of entries in the current hash table still reaches threshold - threshold/4 after removal, the capacity will be expanded. */ private int threshold; // Default to 0
setThreadshold()
/**
* Set the resize threshold to maintain at worst a 2/3 load factor.
* Set the threshold to (current array length * 2) / 3.
*/
private void setThreshold(int len) {
threshold = len * 2 / 3;
}
nextIndex
/**
* Increment i modulo len.
* Gets the next location subscript of the current location
* Parameter 1: current subscript
* Parameter 2: current hash array length
*/
private static int nextIndex(int i, int len) {
//If the current subscript + 1 is less than the hash table array, the value after + 1 is returned
//Otherwise, it is subscript + 1 == len and returns 0
//Actually form a surround access.
return ((i + 1 < len) ? i + 1 : 0);
}
prevIndex
/**
* Decrement i modulo len.
* Gets the previous location subscript of the current location
* Parameter 1: current subscript
* Parameter 2: current hash array length
*/
private static int prevIndex(int i, int len) {
//If the current subscript - 1 is greater than or equal to 0, the value returned after - 1 is ok.
//Otherwise, the current subscript is - 1 = = - 1 The hash table maximum subscript is returned.
//Actually form a surround access.
return ((i - 1 >= 0) ? i - 1 : len - 1);
}
3) Analysis of ThreadLocalMap construction method (22:50 ~ 30:00)
Construct a new mapping that initially contains (firstKey, firstValue). ThreadLocalMaps are built lazily, so we only create them when there is at least one entry to put in
/**
* 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.
*
* Because thread The threadlocals field is delayed initialization. The threadLocalMap object will be created only when the thread stores ThreadLocal value for the first time.
*
* Parameter firstkey: ThreadLocal object
* Parameter firstValue: the value associated with the threadLocal object of the current thread.
*/
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
//Create an entry array with a length of 16, which represents the hash table inside threadLocalMap.
table = new Entry[INITIAL_CAPACITY];
//Addressing algorithm: key threadLocalHashCode & (table.length - 1)
//The length of the table array must be to the power of 2.
//What are the characteristics of the power of 2 - 1? After conversion to binary, it is 1 16==> 1 0000 - 1 => 1111
//1111 must be < = 1111 after & calculating with any value
//i the calculated result must be < = b1111
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
//Create an entry object and store it in the slot at the specified location. (each cell in the array, we call it slot)
table[i] = new Entry(firstKey, firstValue);
//Stored an element, set size=1
size = 1;
//Set capacity expansion threshold: (current array length * 2) / 3 = > 16 * 2 / 3 = > 10
setThreshold(INITIAL_CAPACITY);
}
Construct a new mapping from the given parent mapping, including all inheritable threadlocales. Called only by createInheritedMap.
/**
* 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")
//Get the key of the entry object in the parent map, that is, the threadLocal object
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++;
}
}
}
}
4) ThreadLocalMap getEntry() [quick query] get the Entry method source code according to the key and conduct in-depth analysis (30:00 ~ 38:20)
/**
* 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
*
* ThreadLocal The object get() operation is actually performed by threadlocalmap Getentry () is completed by the agent.
*
* key:A ThreadLocal object because of the entry stored in the hash table The key type is ThreadLocal.
*/
private Entry getEntry(ThreadLocal<?> key) {
//Routing rule: ThreadLocal threadLocalHashCode & (table.length - 1) ==> index
int i = key.threadLocalHashCode & (table.length - 1);
//Access the slot at the specified location in the hash table
Entry e = table[i];
//Condition 1: it indicates that the slot has a value
//Condition 2: the establishment description entry#key is consistent with the key of the current query, and the current entry can be returned to the upper layer.
if (e != null && e.get() == key) {
return e;
} else {
//How many situations will be implemented here?
//1.e == null
//2.e.key != key
//getEntryAfterMiss method will continue to search the entry with e.key == key behind the current bucket
//Why??
//Because there is no linked list at the entry level after hash conflict during storage. The process of storage is to find a usable slot linearly backward and store it. (therefore, the method for handling hash conflicts here is the linear detection method)
return getEntryAfterMiss(key, i, e);
}
}
5) After the ThreadLocalMap getEntryAfterMiss() fast query fails, continue to probe down and analyze the source code of the query method (38:20 ~ 48:15)
/**
* Version of getEntry method for use when key is not found in
* its direct hash slot.
*
* @param key the thread local object threadLocal Object, representing key
* @param i the table index for key's hash code key Calculated index
* @param e the entry at table[i] table[index] entry in
* @return the entry associated with key, or null if no such
*/
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
//Gets the hash table table in the current threadLocalMap
Entry[] tab = table;
//Get table length
int len = tab.length;
//Condition: e= Null Description: the scope of backward search is limited. In case of slot == null, the search ends.
//e: Loop through the current element
while (e != null) {
/* Get the key of the entry object in the current slot, that is, the threadLocal object
get()Method is the method in Reference,
e Is an instance object of entry. Entry inherits WeakReference and inherits Reference */
ThreadLocal<?> k = e.get();
//If the condition is true: it means that the appropriate entry is found in the backward query process, and it is ok to return the entry.
if (k == key) {
//When it is found, it returns from here.
return e;
}
// Condition holds: it indicates that the ThreadLocal object associated with the entry#key in the current slot has been recycled by GC.
// Because key is a weak reference, key = e.get() == null
if (k == null) {
//Do a probe expired data recovery.
expungeStaleEntry(i);
}
else {
//Get the next index and continue to search backward.
i = nextIndex(i, len);
}
//Get the entry in the next slot.
e = tab[i];
}
//This indicates that no corresponding data is found in the associated section.
return null;
}
6) In depth analysis on the source code of ThreadLocalMap expungeStaleEntry() method to erase expired data segments (48:15 ~ 1:05:36)
/**
* 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).
*
* Parameter staleSlot: table[staleSlot] is an expired data (entry.key == null). Start from this position and continue to look for the expired data backward until the situation of slot == null is met.
* Return: the index of the next empty slot after the staleSlot (all between the staleSlot and this slot will be checked for clearing).
*/
private int expungeStaleEntry(int staleSlot) {
//Get hash table
Entry[] tab = table;
//Gets the current length of the hash table
int len = tab.length;
// expunge entry at staleSlot
// help gc (it is expired data, so it is set to null)
tab[staleSlot].value = null;
//Because the entry at the staleSlot position is expired, it is directly set to Null here
tab[staleSlot] = null;
//Because it kills an element, so - 1
size--;
// Rehash until we encounter null
//e: Represents the current traversal node
Entry e;
//i: Indicates the index of the current traversal
int i;
//The for loop starts searching for expired data from the next position of staleSlot until it meets slot == null.
for (i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
//When entering the for loop, the current entry must not be null
//Get the key of the current traversal node entry
ThreadLocal<?> k = e.get();
//Condition holds: it indicates that the threadLocal object represented by k has been recycled by GC, and the current entry belongs to dirty data.
if (k == null) {
//help gc
e.value = null;
//Set the slot corresponding to dirty data to null
tab[i] = null;
//Because it kills an element, so - 1
size--;
} else {
//This step shows that the corresponding entry in the currently traversed slot is non expired data
//Because several expired data may have been cleaned up, the location may be empty.
//If the following if condition is true, it indicates that the current entry encountered a hash conflict during storage and offset the storage later,
//At this time, we should optimize the position and find a position closer to the correct position
//In this way, the efficiency of query will be higher!
//Recalculate the index corresponding to the current entry
int h = k.threadLocalHashCode & (len - 1);
//The condition holds: it indicates that the hash conflict occurred when the current entry was stored, and then it was offset backward.
if (h != i) {
//Set the current location of the entry to null
tab[i] = null;
// Unlike Knuth 6.4 Algorithm R, we must scan until
// null because multiple entries could have been stale.
//h is the correct position.
//Start with the correct location h and look back for the first location where the entry can be stored.
while (tab[h] != null)
h = nextIndex(h, len);
//Put the current element closer to the correct position (possibly the correct position).
tab[h] = e;
}
}
}
//Return: index of the next empty slot after staleSlot
return i;
}
Series summary 4-6 (1:05:36 ~ 1:07:54)
7) In depth analysis of the source code of ThreadLocalMap set() write data method (1:07:54 ~ 1:16:38)
/**
* Set the value associated with key.
*
* ThreadLocal Use the set method to add a ThreadLocal value key value pair to the current thread.
*
* @param key the thread local object
* @param value the value to be set
*/
private void set(ThreadLocal<?> key, Object value) {
//Get hash table
Entry[] tab = table;
//Get hash array length
int len = tab.length;
//Calculate the corresponding position of the current key in the hash table
int i = key.threadLocalHashCode & (len-1);
//Job of the whole for loop: query backward with the slot position corresponding to the current key to find the available slot.
//What kind of slot can be used?
// 1.k == key indicates that 660 lines are replaced
// 2.k == null indicates that an expired slot is encountered. At this time, we can forcibly occupy it. Line 667
// 3. The loop terminates, indicating that slot == null was encountered during the search. Line 677
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
//Get current element key
ThreadLocal<?> k = e.get();
//Condition true: indicates that the current set operation is a replacement operation.
if (k == key) {
//Do the logic to replace the value value.
e.value = value;
return;
}
//The condition holds: it indicates that the entry#key == null is encountered during the downward search, indicating that the current entry is expired data.
if (k == null) {
//When we encounter an expired slot, we can forcibly occupy it at this time.
//Logic to replace expired data.
replaceStaleEntry(key, value, i);
return;
}
}
//This indicates that the for loop encounters slot == null.
//Directly create a new entry object in the appropriate slot.
tab[i] = new Entry(key, value);
//Because it is a new addition, + + size
int sz = ++size;
//Do a heuristic cleanup
//Condition 1:! cleanSomeSlots(i, sz) is established, which indicates that the heuristic cleanup has not cleaned up any data
//Condition 2: SZ > = threshold is true, indicating that the entry in the current table has reached the capacity expansion threshold The rehash operation is triggered.
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}
8) Threadlocalmap replacestateentry() finds key == null Entry during data writing, and executes the logic of replacing expired Entry (1:16:38 ~ 1:37:33)
/**
* 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.
* key: Key threadLocal object
* value: The value associated with the key
* staleSlot: The upper set method finds that the current slot is an expired entry during iterative search.
*/
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
int staleSlot) {
//Get hash table
Entry[] tab = table;
//Get hash array length
int len = tab.length;
//Temporary variable
Entry e;
//The starting subscript that indicates the start of probe cleanup of expired data. By default, it starts from the current staleSlot.
int slotToExpunge = staleSlot;
//Start with the passed in staleSlot and iterate up to find whether there is expired data. The for loop ends when null is encountered.
for (int i = prevIndex(staleSlot, len);
(e = tab[i]) != null;
i = prevIndex(i, len)){
//If the condition is true: it indicates that the expired data is found forward, and the starting subscript of update detection and cleaning up the expired data is i
if (e.get() == null){
slotToExpunge = i;
}
}
//Start with the passed in staleSlot and look for the next one until it encounters null.
for (int i = nextIndex(staleSlot, len);
(e = tab[i]) != null;
i = nextIndex(i, len)) {
//Get current element key
ThreadLocal<?> k = e.get();
//Condition holds: description is a replacement logic.
if (k == key) {
//Replace new data.
e.value = value;
// This is due to linear detection. The staleSlot is closer to the correct location and the data has expired, so there is the following exchange logic
//Logic of swap location:
//Put the expired data of table[staleSlot] into the table[i] to which the current loop is looped.
tab[i] = tab[staleSlot];
//Save the tab[staleSlot] as the current entry. In this way, our data location will be optimized
tab[staleSlot] = e;
//The conditions are true: there are the following two points
// 1. Explain that the replacestateentry looks for expired data forward at the beginning, but the expired entry is not found
// 2. No expired data is found during the backward check (780 lines. If expired data is found during the backward check, the slotToExpunge will be updated)
if (slotToExpunge == staleSlot)
//The subscript of the expired data is modified to the index of the current cycle.
slotToExpunge = i;
//cleanSomeSlots: heuristic cleanup
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
return;
}
//Condition 1: k == null holds, indicating that the currently traversed entry is an expired data
//Condition 2: slotToExpunge == staleSlot holds. At the beginning, the forward search for expired data does not find the expired entry
if (k == null && slotToExpunge == staleSlot)
//Because an expired data is found in the backward query process, the slotToExpunge is updated to the index of the current cycle.
//The precondition is that no expired data is found during precursor scanning
slotToExpunge = i;
}
//When will it be implemented here?
//During backward lookup, no entry with k == key is found, indicating that the current set has no replacement operation and directly forcibly occupies the location of expired data
//Directly add the new data to the slot corresponding to table[staleSlot].
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);
//Condition holds: in addition to the current staleSlot, other expired slots are found So start the logic of cleaning data
if (slotToExpunge != staleSlot)
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}
9) In depth analysis of the source code of ThreadLocalMap cleanSomeSlot() heuristic method to clean up expired data (1:37:33 ~ 1:52:28)
/**
* Heuristics scan some cells for obsolete entries.
* This is called when a new element is added or another obsolete element has been deleted.
* It performs logarithmic scans as a balance between no scans (fast but garbage retaining) and scans proportional to the number of elements
* This will find all garbage, but will cause some inserts to take O(n) time.
*
* @param i A location that is known not to hold obsolete entries. The scan starts with the element after i.
*
* @param n Scan control: {@ code log2(n)} cells were scanned
* Unless an obsolete entry is found, {@ code log2(table.length)-1} additional cells are scanned in this case.
* When invoked from an insert, this parameter is the number of elements.
* But when invoked from replaceStaleEntry, it is the length of the table.
* (Note that all of this can be changed by weighting n rather than using only the direct logarithm n. But this version is simple, fast, and seems to work well.)
*
* Parameter i: heuristic cleanup start position
* Parameter n: generally passed is table Length, where n also represents the end condition.
* @return true if any stale entries have been deleted.
*/
private boolean cleanSomeSlots(int i, int n) {
//Indicates whether the heuristic cleanup has cleared expired data
boolean removed = false;
//Gets the hash table reference of the current map
Entry[] tab = table;
//Gets the length of the current hash table array
int len = tab.length;
do {
//Why don't you check here from i?
//Because cleanSomeSlots(i = expungeStaleEntry(...), n) ， expungeStaleEntry(...) The return value of the method must be null.
//Gets the next subscript of the current i
i = nextIndex(i, len);
//Gets the element in the table whose current subscript is i
Entry e = tab[i];
//Condition 1: e= null
//Condition 2: e.get() == null holds, indicating that the entry saved in the current slot is an expired data
if (e != null && e.get() == null) {
//Re update n to the length of table array
n = len;
//Indicates that the data has been cleaned
removed = true;
//Take the currently expired slot as the starting node for a probe cleanup
i = expungeStaleEntry(i);
}
// Suppose the length of the table is 16
// 16 >>> 1 ==> 8
// 8 >>> 1 ==> 4
// 4 >>> 1 ==> 2
// 2 >>> 1 ==> 1
// 1 >>> 1 ==> 0
} while ( (n >>>= 1) != 0);
return removed;
}
10) Threadlocalmap rehash() - > resize() hash expansion method source code analysis (1:52:28 ~ 2:03:20)
/**
* Repackage and / or resize the table.
* First scan the entire table to delete stale entries.
* If this is not enough to reduce the size of the table, double the table size.
*/
private void rehash() {
//After this method is executed, all expired data in the current hash table will be killed.
expungeStaleEntries();
// Use lower threshold for doubling to avoid hysteresis
//The condition holds: after clearing the expired data, the number of entries in the current hash table still reaches the threshold * 3/4, which really triggers capacity expansion!
if (size >= threshold - threshold / 4)
//Expansion.
resize();
}
/**
* Clear 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);
}
}
/**
* Double the capacity of the table.
*/
private void resize() {
//Get current hash table
Entry[] oldTab = table;
//Gets the current hash table length
int oldLen = oldTab.length;
//Calculate the table size after capacity expansion oldLen * 2
int newLen = oldLen * 2;
//Create a new hash table
Entry[] newTab = new Entry[newLen];
//Indicates the number of entries in the new table.
int count = 0;
//Traverse the old table and migrate the data to the new table.
for (int j = 0; j < oldLen; ++j) {
//A slot that accesses the specified location of the old table
Entry e = oldTab[j];
//Condition holds: indicates that there is data at the specified location in the old table
if (e != null) {
//Get entry#key
ThreadLocal<?> k = e.get();
//Condition holds: it indicates that the entry at the current position in the old table is an expired data
if (k == null) {
e.value = null; // Help the GC
} else {
//Here, it is explained that the elements in the current location of the old table are non expired data and normal data, which need to be migrated to the new table after capacity expansion..
//Calculate the storage location of the new table of the current entry after capacity expansion.
int h = k.threadLocalHashCode & (newLen - 1);
//while loop: to get a usable slot closest to h.
while (newTab[h] != null)
h = nextIndex(h, newLen);
//Store the data in the appropriate slot of the new table.
newTab[h] = e;
//Quantity + 1
count++;
}
}
}
//Set the next trigger expansion indicator.
setThreshold(newLen);
size = count;
//Save the reference of the expanded new table to the table of the threadLocalMap object.
table = newTab;
}
11) ThreadLocalMap remove() remove data method source code analysis (2:03:20 ~ 2:04:30)
/**
* 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;
}
}
}