/**
 * 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).
 */
private int expungeStaleEntry(int staleSlot) {
    // 入?yún)?staleSlot: 待清理位置下標(biāo)
    
    // 獲取 ThreadLocalMap 中的 Entry 數(shù)組。
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    // len 為當(dāng)前 Entry 數(shù)組容量。
    int len = tab.length;

    // expunge entry at staleSlot
    // 清除當(dāng)前 staleSlot 位置的過時 Entry。
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    // 元素數(shù)量減一。
    size--;

    // Rehash until we encounter null
    // 因為 ThreadLocalMap 解決哈希沖突采用的是線性探測法，如將當(dāng)前下標(biāo)位置賦值為 null ，但不對后續(xù) Entry
    // 元素進(jìn)行 rehash 操作，就可能導(dǎo)致存在哈希沖突的后置元素?zé)o法被探測到。所以將當(dāng)前元素清理后需要
    // 對后續(xù)元素進(jìn)行 rehash 操作，直到遇到下一個為 null 的元素。
    ThreadLocal.ThreadLocalMap.Entry e;
    int i;
    // nextIndex 用于向后遞增索引 ((i + 1 < len) ? i + 1 : 0)
    for (i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        if (k == null) {
            // 此時 Entry 不為 null，key 為 null，Entry 為過時 Entry 需清理掉。
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            // 此時為有效 Entry，需要進(jìn)行 rehash 操作重新定位。
            int h = k.threadLocalHashCode & (len - 1);
            if (h != i) {
                // 進(jìn)入到這個分支說明 rehash 后，新的下標(biāo)與原來下標(biāo)不等。
                // 將當(dāng)前下標(biāo)位置清空。
                tab[i] = null;

                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                // 從 h 位置開始遍歷，直到遇到為 null 的元素，并將 rehash 后的元素插入到該位置。
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    
    // i 為 staleSlot 后的第一個 null 元素的位置下標(biāo)。
    return i;
}

/**
 * Heuristically scan some cells looking for stale entries.
 * This is invoked when either a new element is added, or
 * another stale one has been expunged. It performs a
 * logarithmic number of scans, as a balance between no
 * scanning (fast but retains garbage) and a number of scans
 * proportional to number of elements, that would find all
 * garbage but would cause some insertions to take O(n) time.
 *
 * @param i a position known NOT to hold a stale entry. The
 * scan starts at the element after i.
 *
 * @param n scan control: {@code log2(n)} cells are scanned,
 * unless a stale entry is found, in which case
 * {@code log2(table.length)-1} additional cells are scanned.
 * When called from insertions, this parameter is the number
 * of elements, but when from replaceStaleEntry, it is the
 * table length. (Note: all this could be changed to be either
 * more or less aggressive by weighting n instead of just
 * using straight log n. But this version is simple, fast, and
 * seems to work well.)
 *
 * @return true if any stale entries have been removed.
 */
private boolean cleanSomeSlots(int i, int n) {
    // 入?yún)?i: 一個已知不為過時 Entry 的下標(biāo)。掃描從 i 之后的位置開始。
    // 入?yún)?n: 掃描次數(shù)控制值
    
    // 是否清理了任意過時 Entry 標(biāo)志，
    // 為 false 代表本次方法調(diào)用未能清理任何過時 Entry，為 true 代表本次方法調(diào)用至少清理了一個過時 Entry。
    boolean removed = false;
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    int len = tab.length;
    // doWhile 循環(huán)，至少執(zhí)行一次。
    do {
        i = nextIndex(i, len);
        ThreadLocal.ThreadLocalMap.Entry e = tab[i];
        if (e != null && e.get() == null) {
            // 進(jìn)入到當(dāng)前分支說明當(dāng)前 Entry 為過時 Entry。
            // 將 n 置為數(shù)組容量，將當(dāng)前循環(huán)遍歷次數(shù)進(jìn)行追增（n 變大了）。
            n = len;
            // 將標(biāo)志置為 true，證明本次方法調(diào)用并不是無功而返。
            removed = true;
            // 調(diào)用清理過時 Entry 方法，并將 expungeStaleEntry 方法返回的 null 元素的下標(biāo)賦值給 i，
            // 在這之間的下標(biāo)都在 expungeStaleEntry 方法中進(jìn)行了清理，所以這里直接跳過避免重復(fù)操作。
            i = expungeStaleEntry(i);
        }
        // >>>= 無符號右移并賦值，相當(dāng)于除以 2 操作。
    } while ( (n >>>= 1) != 0);
    // 返回本次是否至少清理了一個過時 Entry。
    return removed;
}

/**
 * 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.
 */
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                               int staleSlot) {
    // 入?yún)?key: set 操作傳過來的 key
    // 入?yún)?value: set 操作傳過來的 value，與參數(shù) key 相關(guān)聯(lián)
    // 入?yún)?staleSlot: 待替換的過時 Entry 的下標(biāo)
    
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    int len = tab.length;
    ThreadLocal.ThreadLocalMap.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).
    // slotToExpunge 變量目標(biāo)是存儲當(dāng)前區(qū)間段（兩個 null 元素之間），第一個過時 Entry 的下標(biāo)。
    // 將入?yún)⒌倪^時 Entry 下標(biāo)賦值給 slotToExpunge。
    int slotToExpunge = staleSlot;
    // 這里需要格外注意一下，這里并不是遞增下標(biāo)，而是對下標(biāo)進(jìn)行遞減。
    // prevIndex ((i - 1 >= 0) ? i - 1 : len - 1)。
    // 向前進(jìn)行遍歷直到遇到為 null 的元素。
    for (int i = prevIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = prevIndex(i, len))
        if (e.get() == null)
            // 將遍歷過程中過時 Entry 的下標(biāo)賦值給 slotToExpunge 變量。
            // 經(jīng)過當(dāng)前遍歷邏輯，slotToExpunge 將存儲兩個 null 元素之間第一個過時 key 的下標(biāo)。
            slotToExpunge = i;

    // Find either the key or trailing null slot of run, whichever
    // occurs first
    // 這里是由入?yún)⒌倪^時 Entry 下標(biāo)開始向后遍歷，直到遇到 null 元素。
    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) {
            // 進(jìn)入當(dāng)前分支表示在遍歷的過程中找到了被 set 的 Entry 對象的本體。
            // 將和 key 關(guān)聯(lián)的新 value 值賦值給本體。
            e.value = value;
            // 操作一
            // 將 Entry 對象本體和入?yún)?staleSlot 位置的過時 Entry 進(jìn)行交換，
            // 結(jié)果是set操作的 key 與 value，無論之前本體存儲在哪里，
            // 最終都會存儲在入?yún)⒌?staleSlot 下標(biāo)，符合方法名中的 replace 含義。
            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;

            // Start expunge at preceding stale entry if it exists
            if (slotToExpunge == staleSlot)
                // 如果當(dāng)前區(qū)間段第一個過時 Entry 下標(biāo)仍是 staleSlot 下標(biāo)，
                // 那么需要將當(dāng)前 i 下標(biāo)賦值給 slotToExpunge ，因為 staleSlot 下標(biāo)已經(jīng)存儲了 set 操作的 Entry 對象，
                // 導(dǎo)致當(dāng)前 i 下標(biāo)變成了第一個過時 Entry 的下標(biāo)。
                slotToExpunge = i;
            // 先調(diào)用 expungeStaleEntry 方法清除 slotToExpunge 下標(biāo)的過時 Entry，
            // 再從 expungeStaleEntry 方法返回的 null 元素的下標(biāo)開始執(zhí)行 cleanSomeSlots 方法。
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            // 已經(jīng)完成替換過時條目操作，退出當(dāng)前方法。
            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)
            // 進(jìn)入當(dāng)前分支說明當(dāng)前 Entry 是過時 Entry。
            // 如果當(dāng)前區(qū)間段第一個過時 Entry 下標(biāo)仍是入?yún)⒌?staleSlot 下標(biāo)，
            // 則需要將當(dāng)前位置下標(biāo)賦值給 slotToExpunge，因為最終當(dāng)前位置的過時 Entry 將是
            // 當(dāng)前區(qū)間段的第一個過時 Entry。因為 staleSlot 下標(biāo)位置的過時 Entry 在之后的邏輯
            // 里要么被交換到當(dāng)前下標(biāo)之后（上文操作一），要么被新的 set 傳入的 Entry 覆蓋掉（下文操作二）。
            slotToExpunge = i;
    }

    // If key not found, put new entry in stale slot
    // 操作二
    // 代碼執(zhí)行到當(dāng)前位置說明 set 的 key 與 value 是一個新的 Entry，在之前并不存在。
    // 以 set 方法傳入的 key 和 value 值 new 一個新的 Entry 對象，并覆蓋在入?yún)⒌?staleSlot 下標(biāo)處。
    tab[staleSlot].value = null;
    tab[staleSlot] = new ThreadLocal.ThreadLocalMap.Entry(key, value);

    // If there are any other stale entries in run, expunge them
    if (slotToExpunge != staleSlot)
        // slotToExpunge 與 staleSlot 相等則說明當(dāng)前區(qū)間段只有入?yún)?staleSlot 位置有過時 Entry，
        // 并且該過時 Entry 已被覆蓋，所以無需清理，無需進(jìn)入當(dāng)前分支。
        
        // 進(jìn)入當(dāng)前分支說明當(dāng)前區(qū)間段，除了被覆蓋的過時 Entry，至少還存在一個過時 Entry，
        // slotToExpunge 下標(biāo)為第一個過時 Entry 的下標(biāo)。
        // 先調(diào)用 expungeStaleEntry 方法清除 slotToExpunge 下標(biāo)的過時 Entry，
        // 再從 expungeStaleEntry 方法返回的 null 元素的下標(biāo)開始執(zhí)行 cleanSomeSlots 方法。
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}