【Review】深入理解ThreadLocal（内存泄漏+线性探测）

妖狐艹你老母 2022-09-07 01:20 367阅读 0赞

### 1、简介 ###

线程内共享，线程间隔离。  
线程本地变量

与lock相比：  
ThreadLocal：空间换时间  
Lock等：时间换空间

### 2、实现原理 ###

1）ThreadLocalMap Entry\[\] table 环形数组  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70]  
2） Entry弱引用  
弱引用：GC时会被回收。  
key:ThreadLocal<?> value:Object  
key定位采用hash，碰撞后采用线性探测法，未再使用链表。

private static int nextIndex(int i, int len) \{  
return ((i + 1 < len) ? i + 1 : 0);  
\}

3）InheritableThreadLocal  
可继承 子线程会继承父线程变量

核心源码如下：

static class ThreadLocalMap { 
    
            /** * The entries in this hash map extend WeakReference, using * its main ref field as the key (which is always a * ThreadLocal object). Note that null keys (i.e. entry.get() * == null) mean that the key is no longer referenced, so the * entry can be expunged from table. Such entries are referred to * as "stale entries" in the code that follows. */
            static class Entry extends WeakReference<ThreadLocal<?>> { 
                /** The value associated with this ThreadLocal. */
                Object value;
    
                Entry(ThreadLocal<?> k, Object v) { 
                    super(k);
                    value = v;
                }
            }
    
            private Entry[] table;
    
            //remove set方法都是通过hash定位到key所在的数组位置。
            private void set(ThreadLocal<?> key, Object value) { 
                  Entry[] tab = table;
                int len = tab.length;
                int i = key.threadLocalHashCode & (len-1);
    
                //数组中i位置有值，发生碰撞。
                for (Entry e = tab[i];
                     e != null;
                     e = tab[i = nextIndex(i, len)]) { 
                    ThreadLocal<?> k = e.get();
    
                    if (k == key) { 
                        e.value = value;
                        return;
                    }
                    
                    //清理陈旧的entry
                    if (k == null) { 
                        replaceStaleEntry(key, value, i);
                        return;
                    }
                }
                
                //put new element into tab[]
                tab[i] = new Entry(key, value);
                int sz = ++size;
                if (!cleanSomeSlots(i, sz) && sz >= threshold)
                    rehash();
            }
    
            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();
                        //清理陈旧的entry
                        expungeStaleEntry(i);
                        return;
                    }
                }
            }
    
    }

其中，set、remove、getEntry等方法中，都会针对key=null的脏entry进行清理，尽力保证不出现内存泄漏的情况。

//清理过期的entry
    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();
                    //若key为null，清理
                    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;
            }

这里采用的是闭散列中的开放寻址方式，在插入和删除时较为复杂。

> 探测——若hash后的位置有值，就后移查找。最终会插入到该序列的首个空节点。因此，在探查时，若遇到空节点，就会认为其后节点也都是空的。  
> 所以，在删除元素时，首先要将元素置空，其次，将所有后续节点依次前移，或者通过特殊标记来应对。

举例说明：  
index=5的结点已过期（key=null）  
![在这里插入图片描述][9f60fc88d7be47a186eb87eeb2647cf7.png]  
新增节点 k=15 value=new  
分两个步骤：  
1.1向前遍历，找到一个空的entry停止，如上图的1，此时找到了另一个key为null的节点，下标为3.  
1.2 向后遍历，找到了key值相同的index=6，交换index5和6，并设置value=new。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70 1]

### 3、存在问题 ###

内存泄漏：  
弱引用 key被回收，value还存在

Why弱引用？  
若使用强引用，在业务代理中执行threadlocalInstance=null，来清理实例时，ThreadLocalMap强引用threadlocal，如下图虚线的关系。在GC可达性分析时，threadlocal仍然可达，不会被回收。因此也就达不到清理的目的了。

使用弱引用的话，尽管会出现内存泄漏的问题（threadlocal实例没有了，但entry中仍存在key为null的对象），但在set、remove、getEntry等方法中，都会针对key=null的脏entry进行清理，尽力保证不出现内存泄漏的情况。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70 2]

### 4、扩展-哈希碰撞 ###

哈希碰撞处理方法：  
1）【闭散列】开放寻址（结点存入散列表）  
**a.线性探测**

探测时从i=0开始，首先探查T\[h’(k)\]，然后依次探测T\[h’(k)+1\]，…，直到T\[h’(k)+m-1\]，此后又循环到T\[0\]，T\[1\]，…，直到探测到T\[h’(k)-1\]为止。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70 3]  
注意：  
散列表的载荷因子：a = 插入元素个数 / 散列表的长度  
a是散列表装满程度的标志因子。对于开放地址法，载荷因子非常重要，应严格限制在 0.7~0.8 以下。超过 0.8 ，查表时的CPU缓存按照指数曲线上升。

b.二次探测  
发生碰撞后，继续查找时，有偏移量。  
c.双重探测

该方法是开放寻址的最好方法之一，因为其产生的排列具有随机选择的排列的许多特性。采用的散列函数为：h(k,i)=(h1(k)+i\*h2(k)) mod m。其中h1和h2为辅助散列函数。初始探测位置为T\[h1(k)\]，后续的探测位置在此基础上加上偏移量h2(k)模m。

它不是检查冲突位置后的每一个位置，而是采用另一个散列函数产生一个固定的增量。（跳跃式检查和插入，减小聚焦大小）

2）【开散列】链接法（散列表+链表）  
应用：  
HashMap和ConcurrentHashMap1.8实现，不再展开。

比较：  
开放地址法：容易产生堆积，不适合大规模的数据存储。删除其中一个冲突的元素时，需要移动元素。  
链地址法：平均查找长度短，指针额外空间开销。适合大规模数据。

参考链接：  
https://www.cnblogs.com/xzwblog/p/7227509.html  
https://www.jianshu.com/p/dde92ec37bd1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70]: /images/20220829/e5cfc1c03cad42808165fff999884375.png
[9f60fc88d7be47a186eb87eeb2647cf7.png]: /images/20220829/a2cf2c7b70964da181e9ab8cf4a689aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/ada4e7c8d68541e6b27d42a05ec158d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/86dafb742fbd406eac9b6b45239aa704.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwNjY5MzQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/9f0a864452b84a21b4ed9bb254278282.png