Previous article Analysis of ThreadLocal , let's have a general understanding of its internal operation mode. Students who are not familiar with ThreadLocal are advised to read it before instructing the following articles, which is more or less helpful.
In this article, I focus on understanding ThreadLocalMap. Look at the internal implementation of get, set, remove and other methods
1, set
private void set(ThreadLocal<?> key, Object value) {
Entry[] tab = table;
int len = tab.length;
int i = key.threadLocalHashCode & (len-1);//The value of the current subscript array is hash
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) { //This means constantly looking down for non null entries.
ThreadLocal<?> k = e.get();
--------------------- Step 1 --------------------
if (k == key) {//If the key of the current Entry is exactly the current ThreadLocal, replace the value value
e.value = value;
return;
}
--------------------- Step 2 --------------------
if (k == null) { //The key in the Entry, i.e. ThreadLocal, is a weak reference and can be easily recycled. key=null.
replaceStaleEntry(key, value, i); //Replace entries, clean up invalid entries, and sort out Entry numbers
return;
}
}
--------------------- Step 3 --------------------
//If there is no Entry with the same key or key=null in the Entry array, add an Entry to the Entry array.
tab[i] = new Entry(key, value);
int sz = ++size;
//After clearing the invalid entries, check whether the current Entry capacity exceeds the threshold value. If it exceeds the threshold value, expand the capacity.
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}1.threadLocalHashCode
Look at int i = key threadLocalHashCode &(len-1); At first glance, this code is a bit like the hashcode acquisition method in HashMap. Let's take a look at the source code
private final int threadLocalHashCode = nextHashCode();
private static AtomicInteger nextHashCode = new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}An AtomicInteger type is defined here. Each time threadLocalHashCode is obtained, the current value of nextHashCode must be added with HASH_INCREMENT，HASH_INCREMENT=0x61c88647 is a magic number that allows hash codes to be evenly distributed in the N-th power array of 2. Why does he use this number? Let's look at this & (len - 1), which is a way to take the module. For the power of 2 as the module, use this instead of% (2^n). That's why 0x61c88647 is used. In that case, key The value obtained from threadLocalHashCode & (len-1), that is, the array subscript, is between [0 ~ array length - 1], which must be within the length value of the Entry[] table array.
2.nextIndex
Look at the nextIndex source code
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}This paragraph is to take down a subscript index. If the next subscript is the last subscript, it starts from 0 subscript. Is a forward circular shift operation.
3.replaceStaleEntry
When the key in the Entry is ThreadLocal (ThreadLocal in the Entry is a weak reference), it will be recycled or other conditions will cause the key of the current Entry to be null. At this time, call the replacestateentry method to clean up and replace invalid entries and tidy up the Entry array. This is the core content of ThreadLocalMap.
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
int staleSlot) {
Entry[] tab = table;
int len = tab.length;
Entry e;
int slotToExpunge = staleSlot;//staleSlot is the current subscript
for (int i = prevIndex(staleSlot, len); //Starting from the staleSlot subscript, continue to traverse the Entry array forward,
//Find the minimum subscript with key=null
(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();
---------------------Step 1------------------------
if (k == key) {//Start from the staleSlot subscript and look for the Entry later. If the current key is the same as the Entry key of position i, exchange value
e.value = value;
tab[i] = tab[staleSlot];
tab[staleSlot] = e;
if (slotToExpunge == staleSlot)//If the prevIndex process above does not find an Entry with key=null,
//Then clear the Entry of location i
slotToExpunge = i;
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); //Clean up data
return;
}
---------------------Step 2------------------------
if (k == null && slotToExpunge == staleSlot)
slotToExpunge = i;
}
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);
if (slotToExpunge != staleSlot)
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}4.prevIndex
Look at the prevIndex source code
private static int prevIndex(int i, int len) {
return ((i - 1 >= 0) ? i - 1 : len - 1);
}The effect is similar to that of nextIndex, except that the shift direction is opposite to that of nextIndex.
5.cleanSomeSlots
Take a look at the source code of cleanSomeSlots
private boolean cleanSomeSlots(int i, int n) {
boolean removed = false;
Entry[] tab = table;
int len = tab.length;
do {
i = nextIndex(i, len);
Entry e = tab[i];
if (e != null && e.get() == null) {
n = len;
removed = true;
i = expungeStaleEntry(i);
}
} while ( (n >>>= 1) != 0);
return removed;
}It roughly means traversing the entry array, e= The Entry of the null&& e.get () ==null condition is invalid Entry's location subscript, and then calls expungeStaleEntry to clean up the data.
6.expungeStaleEntry
Take a look at the source code of expungeStaleEntry
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
//Empty the Entry of the position staleSlot
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;
Entry e;
int i;
for (i = nextIndex(staleSlot, len);
(e = tab[i]) != null;
i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
if (k == null) { //Start from the position of staleSlot, and then clean up the corresponding Entry if key=null
//Set null here to facilitate GC recycling
e.value = null;
tab[i] = null;
size--;
} else {
int h = k.threadLocalHashCode & (len - 1);
//The calculated index h is inconsistent with the index I of its current location, so empty the current table[i]
if (h != i) {
tab[i] = null;
//Starting from the h subscript, in case of null, put the current Entry in the h position and the non null Entry in front
while (tab[h] != null)
h = nextIndex(h, len);
tab[h] = e;
}
}
}
return i;
}expungeStaleEntry
Start with the subscript staleSlot and traverse backward until the Entry is null [this staleSlot is the subscript position of key=null or traverse forward the minimum subscript position of key=null]
1. Clear the data of staleSlot position
2. If an Entry with key=null is encountered, the Entry will be cleared
3. If the key of the current Entry is not null, it means that the Entry has data. Calculate the hash value of the key and compare it with the index of the current corresponding array. If it is the same, it will be OK. If it is different, set the Entry of the index to null, and calculate the hash value of the key, that is, the index. If a null Entry is encountered after the index, put the current Entry here, that is, the null position. Why??
7.rehash
private void rehash() {
expungeStaleEntries();
if (size >= threshold - threshold / 4)
resize();
}rehash mainly consists of two steps
1.expungeStaleEntries
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);
}
}Inside, you can call expungeStaleEntry, or clean up and sort out the Entry array
2.resize
If the current size > = threshold - threshold / 4, go through the resize process, that is, the capacity expansion process.
private void resize() {
Entry[] oldTab = table;
int oldLen = oldTab.length;
int newLen = oldLen * 2;
Entry[] newTab = new Entry[newLen];
int count = 0;
for (int j = 0; j < oldLen; ++j) {
Entry e = oldTab[j];
if (e != null) {
ThreadLocal<?> k = e.get();
if (k == null) {
e.value = null; // Help the GC
} else {
int h = k.threadLocalHashCode & (newLen - 1);
while (newTab[h] != null)
h = nextIndex(h, newLen);
newTab[h] = e;
count++;
}
}
}
setThreshold(newLen);
size = count;
table = newTab;
}The whole process is not difficult to understand.
Expand the capacity, double the previous capacity, traverse the old Entry array, recalculate the hash value for each Entry as the key, and put the old Entry into the new Entry array.
So far, the set process is completed, which involves replacing entries, cleaning up invalid entries, sorting out Entry arrays, and capacity expansion
The whole set process is almost like this, but I don't think I understand it. Let's take a case directly to deepen our understanding.
For this drawing, I will use the drawings of other authors for the time being and replace them later.
2, Example interpretation (key)
Scenario 1
In the Entry array, there is no Entry with the same key or key=null after the starting subscript.
We prepare an Entry array with a table length of 10 and calculate the key hash value. We use the function f(key) = key mod l0, which is simpler. Now we have four tree values {12,33,4,5}, all of which are hash addresses without conflict. They are stored directly (blue means empty, which can store data):
Now we want to set a value, key=15, f(15)=5, that is, i=5
Looking back at the set method, we traverse from subscript 5 and find that the Entry is null when the subscript is 6. At this time, f(15)=5, key=15 and key=5 are different, and f(15)=5 is not null, which does not comply with steps 1 and 2. Let's go to step 3. At this time, i shifts through nextIndex, i=6. Then put key=15 in the position of subscript 6.
It is obvious that the capacity does not reach the rehash threshold, and then it is necessary to judge whether the capacity needs to be expanded.
If ha, if. When adding key=15, the capacity of the Entry array is just full. At this time, tab[11] stores entries with key=15, which needs to be expanded.
Scenario 2
In the Entry array, after the starting subscript, there is an Entry with key=null.
We prepare an Entry array with a table length of 10 and calculate the key hash value. We use the function f(key) = key mod l0, which is simpler. Now we have four tree values {12,33,4,5,15,25}, and at this time, the key = 33 and K = 5 have expired (blue represents empty and can store data, red represents expired key and null expired key)
Now we want to set a value, key=15, f(15)=5, that is, i=5
Looking back at the set method, we traverse from subscript 5 and find that the key with subscript 5 = null. According to the truth, we should go to step 2, that is, enter the replacestateentry method
What's in there? Looking back at the replacestateentry method, we know the inside story.
1. Record the current position, i.e. i=5, slotttoexpunge = staleslot = 5
2. Move forward from subscript 5 until the Entry is null, that is, the position of subscript 1. Find the location where the subscript minimum key=null. Look at the picture, it's easy until the position is 3, slotToExpunge=3.
3. Go back from subscript 5 until the Entry is null, that is, the position of subscript 8.
In the process:
If it is found that the key of the Entry to be inserted is the same as the key of the Entry during traversal, the Entry is exchanged with the Entry with the subscript staleSlot. That is, subscript 5 puts f(15) data, subscript 6 puts key=null,
Then take a look at the expungeStaleEntry process. slotToExpunge=3 and staleSlot=5, so all entries with key=null are cleared from subscript 3.
Let's traverse to i=7, after int h = k.threadlocalhashcode & (len - 1) (actually corresponding to our example function int h= f(25)); The obtained h=5, while 25 is actually stored in the position of index=7. At this time, we need to restart the listing from the position of h=5 until we encounter an empty entry
The expungeStaleEntry process finally returns i=7;
Finally, execute cleanSomeSlots to clear expired and invalid entries, but there are no expired and invalid entries after subscript 7, so it ends.
3, getEntry
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);
}There's nothing to talk about here. Let's take a look at getEntryAfterMiss
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;
}In fact, there is a case where there are different key hash values, but their keys may be the same. The main function of the above code is to traverse the Entry array. If you find an Entry with the same key, you will return this Entry. If you can't find it, you will return null.
4, remove
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;
}
}
}With the basis of the above explanation, it's easy to understand. Find the corresponding Entry according to the hash value of the current key, that is, the array subscript. Judge whether the key of the Entry at this time is the same as the current ThreadLocal. If so, clear, and then expungeStaleEntry clean up and sort out the Entry array.
5, Question
HashMap is different from ThreadLocalMap. I'm afraid it's too long. In order to reduce the reading pressure, I'll leave it in the following article.