ThreadLocal. Threadlocalmap analysis

Reference article ：ThreadLocal Source code analysis _02 kernel (ThreadLocalMap)

Loop to get subscript , Form a ring .

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

• getEntry Method ：
  First, according to key Calculate the index subscript , Get entry. If you don't get the corresponding entry, call getEntryAfterMiss Keep getting
  No corresponding entry, There may be 2 In this case ：
  1, There is no corresponding thread value;
  2,hash Conflict , The entry Was put in the back （ solve hash Conflict is not in the right place slot Use linked list on , But put it in the follow-up slot in ）

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

• getEntryAfterMiss Method ：
  If it doesn't exist , return null.
  If it is entry Put it in the back , Traverse the following entry, until slot by null until ：
  If entry.key= At present key, It means that , return ; Otherwise compare the next
  If entry.key=null, explain key By GC Recycled , To be called expungeStaleEntry Do a probe expired data recovery

( vernacular ： If it's all null, That's no more , return null. If there's any more entry, Just look back , It may have been pushed to the back , Compare the key Whether it is equal or not , Equal to return to ; If there are entry Of key yes null, To do exploratory data recovery )

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;
                    }
                }
            }
            return i;
        }

• expungeStaleEntry Method （ Probe data recovery , Clean up the recycled key Corresponding value and entry, Readjustment entry The location of ）：
  Clean up the data of the current location ( Include value and entry), And traverse the following entry, until null
  If the follow-up entry.key still null, Keep cleaning up ：
  If entry.key No null, The entry It could be hash Conflict ( Compare the hash And index subscript ), Need to move forward ,
  find hash value （ The original position that should be placed ） The next nearest vacant seat

（ vernacular ： This method is used to clean key by null Of entry and value, From the current slot Start cleaning up one by one later , Until I met slot by null The situation of .
If you encounter key Not empty , Need to judge the entry Is it in the right place , in other words , Maybe it was pushed back , The front is empty , Just move forward ）

        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();
        }

• set Method （ Heuristic cleanup is used ）：
  If originally key There is , The description is to replace , Return after execution
  If only entry Exist and key non-existent （ By gc Recycled ）, Show the current entry It's overdue , call replaceStaleEntry Forcibly occupy the bucket space , return
  If the above conditions are not met , To traverse back , until slot=null
  If you traverse to slot=null( There may also be no traversal , This position is the calculated index subscript position ), Not yet set success , The explanation should be in slot=null Add this new location value.

（ vernacular ： If the position to be inserted is empty , Just insert it directly ; If not , Just plug it in the back . If one of the following slot Of key It's the one to insert key,
Just replace it ; If slot Of key yes null, Just occupy it ; If not , Just keep looking for an empty seat to put . If this is the first case and the data is not cleaned up , Also determine whether to expand the capacity ）

        private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                                       int staleSlot) {
    
            Entry[] tab = table;
            int len = tab.length;
            Entry e;

            // 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;
            for (int i = 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 (int i = 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)
                        slotToExpunge = i;
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    return;
                }

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

            // If there are any other stale entries in run, expunge them
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }

• replaceStaleEntry Method ：
  This method does complex operations , It's not a simple replacement slot Of entry Just a matter of .
  Go ahead and find the first expired data , Look back for the last expired data .
  In the process of looking back, if you find the same key, Replace with new data , And will be entry and set Method call entry（ Be overdue entry） Interchange location .
  If you don't find the same key, Just create one entry, Replace... Where this method is called entry.
  Call again cleanSomeEntry Method for heuristic cleanup

Pay attention here , Replace the current slot, It is possible that there is a value to be set after the array key, That is, in the case of replacement . So in this method , You have to go back , Determine whether k==key, exist , Replace , And swap positions

• cleanSomeSlots Method ：
  Jump to call expungeStaleEntry Clean up expired data .

• resize Method ：
  Let's expand it to the original 2 times .
  Create a new entry Array , Migrate old data to a new array