A:
ThreadLocal is often used for data isolation at the thread level. How does ThreadLocal implement data isolation? Let’s take a look at how ThreadLocal works.
Two: TheadLocal principle analysis
1. Storage structure of ThreadLocal
Each Thread object has a member variable called threadLocals, which is a map of type ThreadLocalMap on which ThreadLocal implements thread-level data isolation.
Let’s start with the member variables of ThreadLocalMap
// The default initialization capacity
private static final int INITIAL_CAPACITY = 16;
// The actual data structure stored in the Entry array
private Entry[] table;
// Record the current number of elements
private int size = 0;
// Capacity expansion threshold
private int threshold;
Copy the codeThe Entry array is where the data is actually stored. As you can see, Entry is a key-value storage structure. The reference of the current ThreadLocal object is used as the key and the value stored is value. Entry inherits WeakReference, and when constructing, super(k) (that is, WeakReference’s constructor) is called to initialize key, so the key of Entry is a WeakReference.
static class Entry extends WeakReference<ThreadLocal<? >>{
/** The value associated with this ThreadLocal. */Object value; Entry(ThreadLocal<? > k, Object v) {super(k); value = v; }}Copy the codeFrom the above analysis, we can know that the storage structure of ThreadLocal is roughly like this:
2. Source code analysis
The set(), get(), and remove() methods of ThreadLocal are used as entry points.
The set () method
Determine whether the threadLocals of the current thread is initialized. If not, call createMap() to initialize and set the value; otherwise, call ThreadLocalMap’s set() to set the value.
Flow chart:
Source code analysis:
public void set(T value) {
// Use the current thread to obtain its threadLocals (threadLocals is a ThreadLocalMap)
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
// Call ThreadLocalMap's set() method if it is already initialized
if(map ! =null)
map.set(this, value);
else
// Initialize before initialization
createMap(t, value);
}
Copy the code ThreadLocalMap getMap(Thread t) {
// Returns the threadLocals of the current thread
return t.threadLocals;
}
Copy the codecreateMap()
CreateMap () calls the constructor of ThreadLocalMap to initialize the current thread’s threadLocals and the Entry array, then calculates the array subscript using a hash algorithm, and stores the set values in the Entry array.
void createMap(Thread t, T firstValue) {
t.threadLocals = new ThreadLocalMap(this, firstValue);
}
Copy the codeThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) {// Initializes the Entry array
table = new Entry[INITIAL_CAPACITY];
// Compute the array subscript
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
table[i] = new Entry(firstKey, firstValue);
size = 1;
// Set the default capacity expansion threshold to the same as the default capacity
setThreshold(INITIAL_CAPACITY);
}
Copy the codeIf threadLocals is already initialized, the set() method of ThreadLocalMap is called directly. Then look at the set() method of ThreadLocalMap.
First, the hash algorithm is used to calculate the array subscript. If there is no value in the calculated position, the value is directly set. If there is a value (hash conflict occurs), there are three cases:
1. If the keys are the same, overwrite the values directly
2. If the key of the calculated Entry is null, it indicates that the data is invalid (the key is null but the Entry is not null). To avoid memory leakage, you need to clear the data. So the replaceStaleEntry() method is called to clean up the invalid data and set the values that need to be set into the Entry array.
3. If the key is different and the Entry key of the calculated position is not null, enter the next for loop and calculate the subscript +1 (if the subscript maximum value is reached, it is set to 0), and judge again using the new position. Until a valid location is obtained (linear addressing resolves hash collisions).
Note: Here you can discuss in the comments section why you don’t use linked lists to resolve hash conflicts like HashMap. My personal opinion is that the amount of data in ThreadLocal is not as large as that in HashMap, so there is no need to use linked lists and red-black trees to resolve hash conflicts. Linked list resolution code is relatively complex and it is more troublesome to expand and migrate data.
Source:
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;
// Compute the array subscript
int i = key.threadLocalHashCode & (len-1);
// If a hash conflict occurs, the for loop is entered
for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<? > k = e.get();// Overwrite the value if the key is the same
if (k == key) {
e.value = value;
return;
}
// If the key is null, the data is invalid and needs to be cleared
if (k == null) {
// Call the replaceStaleEntry() method to clear the data and set the value
replaceStaleEntry(key, value, i);
return; }}// If there is no hash conflict, assign the value directly to the corresponding index
tab[i] = new Entry(key, value);
// Add the current number of elements +1
int sz = ++size;
// If there are no elements to be cleared and the number of elements has reached the capacity expansion threshold, expand the capacity
if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }Copy the codeNext look at replaceStaleEntry() to see how ThreadLocal cleans up invalid data.
If the current node is invalid, then there may also be invalid data around it. Therefore, ThreadLocal will remove the contiguous invalid data around it by using the for loop to traverse the current node. Adjust the value of slotToExpunge (slotToExpunge is used to store the subscript where invalid data is deleted), and then iterate backwards. If there is an entry key that is the same as the one that needs to be stored, the value is overwritten and the value of the current node is swapped with the value of the new entry.
Flow chart:
private void replaceStaleEntry(ThreadLocal<? > key, Object value,int staleSlot) {
Entry[] tab = table;
int len = tab.length;
Entry e;
// slotToExpunge is used to save the subscript position where invalid data is started
int slotToExpunge = staleSlot;
// Traverse from the current position until a valid subscript is found
for (inti = prevIndex(staleSlot, len); (e = tab[i]) ! =null;
i = prevIndex(i, len))
// LLDB () returns Entry keys, where null indicates invalid data
// Enter the for loop only if entry is not null
// The for loop moves the index that clears invalid data forward
if (e.get() == null)
slotToExpunge = i;
// iterate backwards from the current position
for (inti = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();// If there is an Entry with the same key as the current Entry, switch the two positions
if (k == key) {
e.value = value;
tab[i] = tab[staleSlot];
tab[staleSlot] = e;
// If slotToExpunge and staleSlot are equal
// Prove that there is no invalid data before the current node
Call cleanSomeSlots() and expungeStaleEntry() to clean up the invalid data and then return.
if (slotToExpunge == staleSlot)
slotToExpunge = i;
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
return;
}
// If the key is null and the current entry is preceded by no consecutive invalid data from the current node
// refresh starts to clear invalid data subscripts
if (k == null && slotToExpunge == staleSlot)
slotToExpunge = i;
}
// If key not found, put new entry in stale slot
// If no consecutive invalid data is found, reset the value of the current node to null and assign the new value to the current position
// Because the current entry is invalid data
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);
// If there are any other stale entries in run, expunge them
// If slotToExpunge and staleSlot are not equal, continuous invalid data needs to be removed
if(slotToExpunge ! = staleSlot) cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); }Copy the codeNote: we can talk about it in the comments section, why want to exchange the data here, personally, I think the first is to ensure that as much as possible, the location of the data is stored in the hash to calculate the position, is conducive to the follow-up of the get () method, the second: after swap places conducive to make invalid data continuously rise, improve the efficiency of removing invalid data.
The methods that actually clean up invalid data are the expungeStaleEntry() and cleanSomeSlots() methods
Let’s start with the expungeStaleEntry() method
expungeStaleEntry()
The expungeStaleEntry() method iterates backwards from the current node (until it encounters a node with ENrty null), removes the invalid data, and recalculates the array subscripts of valid entries. If the calculated subscripts are different from the entry subscripts (this is because of linear addressing), So the hash index may not be the same as the actual index), find the appropriate position again.
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
// expunge entry at staleSlot
// Clear the current node first
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) {
// If the key is null, invalid data is cleared
e.value = null;
tab[i] = null;
size--;
} else {
// Recalculate the array subscript. If the array subscript changes, migrate the data to the new location
int h = k.threadLocalHashCode & (len - 1);
if(h ! = i) { tab[i] =null;
// Reuse linear addressing to find the appropriate subscript position
while(tab[h] ! =null) h = nextIndex(h, len); tab[h] = e; }}}return i;
}
Copy the codeThen there is the cleanSomeSlots() method
cleanSomeSlots()
The expungeStaleEntry() method is called log(n) times to clean up invalid data. This official says not to call n times to clean up, for efficiency, and it has been tested that calling log(n) times to clean up invalid data is good enough. N indicates the length of the entry array.
private boolean cleanSomeSlots(int i, int n) {
//removed Indicates whether the data is removed
boolean removed = false;
Entry[] tab = table;
int len = tab.length;
do {
i = nextIndex(i, len);
Entry e = tab[i];
if(e ! =null && e.get() == null) {
n = len;
removed = true; i = expungeStaleEntry(i); }}while ( (n >>>= 1) != 0);
return removed;
}
Copy the codeIf the set() method sets the value, the rehash() method is called to expand the capacity.
Call expungeStaleEntries() to clean up the data, and if you still need to expand, call resize().
rehash()
private void rehash(a) {
// Try clearing the data again
expungeStaleEntries();
// Use lower threshold for doubling to avoid hysteresis
// Resize () will be called if expansion is still required
if (size >= threshold - threshold / 4)
resize();
}
Copy the coderesize()
The resize() method creates an array of twice the size, migrates the data to the new array, and assigns the new array to the table variable. (Expansion method is relatively simple)
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);
// Linear addressing resolves hash collisions
while(newTab[h] ! =null)
h = nextIndex(h, newLen);
newTab[h] = e;
count++;
}
}
}
setThreshold(newLen);
size = count;
table = newTab;
}
Copy the codeThe get () method
Get the threadLocals of the current thread, and if threadLocals is already initialized, call the getEntry() method to get the value. Otherwise call setInitialValue() to get the initialized value we set in initialValue().
public T get(a) {
Thread t = Thread.currentThread();
// Use the current thread to obtain its threadLocals (threadLocals is a ThreadLocalMap)
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();
}
Copy the codeNow let’s look at the getEntry() method
Return if an Entry with the same key is found, otherwise call the getEntryAfterMiss() method
getEntry()
private Entry getEntry(ThreadLocal
key) {
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
// Return if an Entry with the same key is found
if(e ! =null && e.get() == key)
return e;
else
return getEntryAfterMiss(key, i, e);
}
Copy the codegetEntryAfterMiss()
GetEntryAfterMiss () iterates back from the current node to find an entry with the same key and returns null if it does not. If there is invalid data, clear it.
private Entry getEntryAfterMiss(ThreadLocal<? > key,int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
while(e ! =null) { ThreadLocal<? > k = e.get();// Return an entry with the same key
if (k == key)
return e;
if (k == null)
// The current data is invalid
expungeStaleEntry(i);
else
// Otherwise continue looking backwards
i = nextIndex(i, len);
e = tab[i];
}
return null;
}
Copy the codeFinally, the remove() method
remove()
Use the hash algorithm to calculate the subscript, traverse from the subscript position to find the entry with the same key, delete the entry, and call expungeStaleEntry() to remove invalid data.
public void remove(a) {
ThreadLocalMap m = getMap(Thread.currentThread());
if(m ! =null)
m.remove(this);
}
Copy the codeprivate 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 codeFour:
This article examines the data storage structure of ThreadLocal, as well as the set(), get(), and remove() methods. One more question: Why do ThreadLocal Entry keys use weak references?