LocalMap

成员属性

ThreadLocalMap 是 ThreadLocal 的内部类，没有实现 Map 接口，用独立的方式实现了 Map 的功能，其内部 Entry 也是独立实现

// 初始化当前 map 内部散列表数组的初始长度 16
private static final int INITIAL_CAPACITY = 16;

// 存放数据的table，数组长度必须是2的整次幂。
private Entry[] table;

// 数组里面 entrys 的个数，可以用于判断 table 当前使用量是否超过阈值
private int size = 0;

// 进行扩容的阈值，表使用量大于它的时候进行扩容。
private int threshold;

存储结构 Entry：

• Entry 继承 WeakReference，key 是弱引用，目的是将 ThreadLocal 对象的生命周期和线程生命周期解绑
• Entry 限制只能用 ThreadLocal 作为 key，key 为 null (entry.get() == null) 意味着 key 不再被引用，entry 也可以从 table 中清除

static class Entry extends WeakReference\<ThreadLocal\<?\>\> {
    Object value;
    Entry(ThreadLocal\<?\> k, Object v) {
        // this.referent = referent = key;
        super(k);
        value = v;
    }
}

构造方法：延迟初始化的，线程第一次存储 threadLocal - value 时才会创建 threadLocalMap 对象

ThreadLocalMap(ThreadLocal\<?\> firstKey, Object firstValue) {
    // 初始化table，创建一个长度为16的Entry数组
    table = new Entry[INITIAL_CAPACITY];
    // 【寻址算法】计算索引
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    // 创建 entry 对象，存放到指定位置的 slot 中
    table[i] = new Entry(firstKey, firstValue);
    // 数据总量是 1
    size = 1;
    // 将阈值设置为 （当前数组长度 * 2）/ 3。
    setThreshold(INITIAL_CAPACITY);
}

成员方法

• set()：添加数据，ThreadLocalMap 使用线性探测法来解决哈希冲突

• 该方法会一直探测下一个地址，直到有空的地址后插入，若插入后 Map 数量超过阈值，数组会扩容为原来的 2 倍 假设当前 table 长度为16，计算出来 key 的 hash 值为 14，如果 table[14] 上已经有值，并且其 key 与当前 key 不一致，那么就发生了 hash 冲突，这个时候将 14 加 1 得到 15，取 table[15] 进行判断，如果还是冲突会回到 0，取 table[0]，以此类推，直到可以插入，可以把 Entry[] table 看成一个环形数组

• 线性探测法会出现堆积问题，可以采取平方探测法解决

• 在探测过程中 ThreadLocal 会复用 key 为 null 的脏 Entry 对象，并进行垃圾清理，防止出现内存泄漏

private void set(ThreadLocal\<?\> key, Object value) {
    // 获取散列表
    ThreadLocal.ThreadLocalMap.Entry[] tab = table;
    int len = tab.length;
    // 哈希寻址
    int i = key.threadLocalHashCode & (len-1);
    // 使用线性探测法向后查找元素，碰到 entry 为空时停止探测
    for (ThreadLocal.ThreadLocalMap.Entry e = tab[i]; e != null; e = tab[i = nextIndex(i, len)]) {
        // 获取当前元素 key
        ThreadLocal\<?\> k = e.get();
        // ThreadLocal 对应的 key 存在，【直接覆盖之前的值】
        if (k == key) {
            e.value = value;
            return;
        }
        // 【这两个条件谁先成立不一定，所以 replaceStaleEntry 中还需要判断 k == key 的情况】
        
        // key 为 null，但是值不为 null，说明之前的 ThreadLocal 对象已经被回收了，当前是【过期数据】
        if (k == null) {
            // 【碰到一个过期的 slot，当前数据复用该槽位，替换过期数据】
            // 这个方法还进行了垃圾清理动作，防止内存泄漏
            replaceStaleEntry(key, value, i);
            return;
        }
    }
	// 逻辑到这说明碰到 slot == null 的位置，则在空元素的位置创建一个新的 Entry
    tab[i] = new Entry(key, value);
    // 数量 + 1
    int sz = ++size;
    
    // 【做一次启发式清理】，如果没有清除任何 entry 并且【当前使用量达到了负载因子所定义，那么进行 rehash
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        // 扩容
        rehash();
}
// 获取【环形数组】的下一个索引
private static int nextIndex(int i, int len) {
    // 索引越界后从 0 开始继续获取
    return ((i + 1 < len) ? i + 1 : 0);
}
// 在指定位置插入指定的数据
private void replaceStaleEntry(ThreadLocal\<?\> key, Object value, int staleSlot) {
    // 获取散列表
    Entry[] tab = table;
    int len = tab.length;
    Entry e;
	// 探测式清理的开始下标，默认从当前 staleSlot 开始
    int slotToExpunge = staleSlot;
    // 以当前 staleSlot 开始【向前迭代查找】，找到索引靠前过期数据，找到以后替换 slotToExpunge 值
    // 【保证在一个区间段内，从最前面的过期数据开始清理】
    for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len))
        if (e.get() == null)
            slotToExpunge = i;

	// 以 staleSlot 【向后去查找】，直到碰到 null 为止，还是线性探测
    for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
        // 获取当前节点的 key
        ThreadLocal\<?\> k = e.get();
		// 条件成立说明是【替换逻辑】
        if (k == key) {
            e.value = value;
            // 因为本来要在 staleSlot 索引处插入该数据，现在找到了i索引处的key与数据一致
            // 但是 i 位置距离正确的位置更远，因为是向后查找，所以还是要在 staleSlot 位置插入当前 entry
            // 然后将 table[staleSlot] 这个过期数据放到当前循环到的 table[i] 这个位置，
            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;
			
            // 条件成立说明向前查找过期数据并未找到过期的 entry，但 staleSlot 位置已经不是过期数据了，i 位置才是
            if (slotToExpunge == staleSlot)
                slotToExpunge = i;
            
            // 【清理过期数据，expungeStaleEntry 探测式清理，cleanSomeSlots 启发式清理】
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            return;
        }
		// 条件成立说明当前遍历的 entry 是一个过期数据，并且该位置前面也没有过期数据
        if (k == null && slotToExpunge == staleSlot)
            // 探测式清理过期数据的开始下标修改为当前循环的 index，因为 staleSlot 会放入要添加的数据
            slotToExpunge = i;
    }
	// 向后查找过程中并未发现 k == key 的 entry，说明当前是一个【取代过期数据逻辑】
    // 删除原有的数据引用，防止内存泄露
    tab[staleSlot].value = null;
    // staleSlot 位置添加数据，【上面的所有逻辑都不会更改 staleSlot 的值】
    tab[staleSlot] = new Entry(key, value);

    // 条件成立说明除了 staleSlot 以外，还发现其它的过期 slot，所以要【开启清理数据的逻辑】
    if (slotToExpunge != staleSlot)
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

private static int prevIndex(int i, int len) {
    // 形成一个环绕式的访问，头索引越界后置为尾索引
    return ((i - 1 >= 0) ? i - 1 : len - 1);
}

• getEntry()：ThreadLocal 的 get 方法以当前的 ThreadLocal 为 key，调用 getEntry 获取对应的存储实体 e

private Entry getEntry(ThreadLocal\<?\> key) {
    // 哈希寻址
    int i = key.threadLocalHashCode & (table.length - 1);
    // 访问散列表中指定指定位置的 slot 
    Entry e = table[i];
    // 条件成立，说明 slot 有值并且 key 就是要寻找的 key，直接返回
    if (e != null && e.get() == key)
        return e;
    else
        // 进行线性探测
        return getEntryAfterMiss(key, i, e);
}
// 线性探测寻址
private Entry getEntryAfterMiss(ThreadLocal\<?\> key, int i, Entry e) {
    // 获取散列表
    Entry[] tab = table;
    int len = tab.length;

    // 开始遍历，碰到 slot == null 的情况，搜索结束
    while (e != null) {
		// 获取当前 slot 中 entry 对象的 key
        ThreadLocal\<?\> k = e.get();
        // 条件成立说明找到了，直接返回
        if (k == key)
            return e;
        if (k == null)
             // 过期数据，【探测式过期数据回收】
            expungeStaleEntry(i);
        else
            // 更新 index 继续向后走
            i = nextIndex(i, len);
        // 获取下一个槽位中的 entry
        e = tab[i];
    }
    // 说明当前区段没有找到相应数据
    // 【因为存放数据是线性的向后寻找槽位，都是紧挨着的，不可能越过一个 空槽位 在后面放】，可以减少遍历的次数
    return null;
}

• rehash()：触发一次全量清理，如果数组长度大于等于长度的 2/3 * 3/4 = 1/2，则进行 resize

private void rehash() {
    // 清楚当前散列表内的【所有】过期的数据
    expungeStaleEntries();
    
    // threshold = len * 2 / 3，就是 2/3 * (1 - 1/4)
    if (size >= threshold - threshold / 4)
        resize();
}
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);
    }
}

Entry 数组为扩容为原来的 2 倍 ，重新计算 key 的散列值，如果遇到 key 为 null 的情况，会将其 value 也置为 null，帮助 GC

private void resize() {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    // 新数组的长度是老数组的二倍
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    // 统计新table中的entry数量
    int count = 0;
	// 遍历老表，进行【数据迁移】
    for (int j = 0; j < oldLen; ++j) {
        // 访问老表的指定位置的 entry
        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);
                // 将数据存放到新表合适的 slot 中
                newTab[h] = e;
                count++;
            }
        }
    }
	// 设置下一次触发扩容的指标：threshold = len * 2 / 3;
    setThreshold(newLen);
    size = count;
    // 将扩容后的新表赋值给 threadLocalMap 内部散列表数组引用
    table = newTab;
}

• remove()：删除 Entry

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)]) {
        // 找到了对应的 key
        if (e.get() == key) {
            // 设置 key 为 null
            e.clear();
            // 探测式清理
            expungeStaleEntry(i);
            return;
        }
    }
}

清理方法

• 探测式清理：沿着开始位置向后探测清理过期数据，沿途中碰到未过期数据则将此数据 rehash 在 table 数组中的定位，重定位后的元素理论上更接近 i = entry.key & (table.length - 1)，让数据的排列更紧凑，会优化整个散列表查询性能

// table[staleSlot] 是一个过期数据，以这个位置开始继续向后查找过期数据
private int expungeStaleEntry(int staleSlot) {
    // 获取散列表和数组长度
    Entry[] tab = table;
    int len = tab.length;

    // help gc，先把当前过期的 entry 置空，在取消对 entry 的引用
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    // 数量-1
    size--;

    Entry e;
    int i;
    // 从 staleSlot 开始向后遍历，直到碰到 slot == null 结束，【区间内清理过期数据】
    for (i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
        ThreadLocal\<?\> k = e.get();
        // 当前 entry 是过期数据
        if (k == null) {
            // help gc
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            // 当前 entry 不是过期数据的逻辑，【rehash】
            // 重新计算当前 entry 对应的 index
            int h = k.threadLocalHashCode & (len - 1);
            // 条件成立说明当前 entry 存储时发生过 hash 冲突，向后偏移过了
            if (h != i) {
                // 当前位置置空
                tab[i] = null;
                // 以正确位置 h 开始，向后查找第一个可以存放 entry 的位置
                while (tab[h] != null)
                    h = nextIndex(h, len);
                // 将当前元素放入到【距离正确位置更近的位置，有可能就是正确位置】
                tab[h] = e;
            }
        }
    }
    // 返回 slot = null 的槽位索引，图例是 7，这个索引代表【索引前面的区间已经清理完成垃圾了】
    return i;
}

• 启发式清理：向后循环扫描过期数据，发现过期数据调用探测式清理方法，如果连续几次的循环都没有发现过期数据，就停止扫描

//  i 表示启发式清理工作开始位置，一般是空 slot，n 一般传递的是 table.length 
private boolean cleanSomeSlots(int i, int n) {
    // 表示启发式清理工作是否清除了过期数据
    boolean removed = false;
    // 获取当前 map 的散列表引用
    Entry[] tab = table;
    int len = tab.length;
    do {
        // 获取下一个索引，因为探测式返回的 slot 为 null
        i = nextIndex(i, len);
        Entry e = tab[i];
        // 条件成立说明是过期的数据，key 被 gc 了
        if (e != null && e.get() == null) {
            // 【发现过期数据重置 n 为数组的长度】
            n = len;
            // 表示清理过过期数据
            removed = true;
            // 以当前过期的 slot 为开始节点 做一次探测式清理工作
            i = expungeStaleEntry(i);
        }
        // 假设 table 长度为 16
        // 16 >>> 1 ==> 8，8 >>> 1 ==> 4，4 >>> 1 ==> 2，2 >>> 1 ==> 1，1 >>> 1 ==> 0
        // 连续经过这么多次循环【没有扫描到过期数据】，就停止循环，扫描到空 slot 不算，因为不是过期数据
    } while ((n >>>= 1) != 0);
    
    // 返回清除标记
    return removed;
}

参考视频：https://space.bilibili.com/457326371/