转载

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

ThreadLocal 是面试过程中非常高频的一个类,这类的复杂程度绝对是可以带出一系列连环炮的面试轰炸。biu biu biu ~~~~.

一直觉得自己对这个类很了解了,但是直到去看源码,接二连三的技术浮出水面(弱引用,避免内存溢出的操作,开放地址法解决hash 冲突,各种内部类的复杂的关系),看到你怀疑人生,直到根据代码一步一步的画图才最终理解(所以本篇文章会有大量的图)。这里也给大家一个启示,面对复杂的事情的时候,实在被问题绕晕了,就画图吧,借助图可以让问题可视化,便于理解。

WAHT

ThreadLocal 是一个线程的本地变量,也就意味着这个变量是线程独有的,是不能与其他线程共享的,这样就可以避免资源竞争带来的多线程的问题,这种解决多线程的安全问题和lock(这里的lock 指通过synchronized 或者Lock 等实现的锁) 是有本质的区别的:

  1. lock 的资源是多个线程共享的,所以访问的时候需要加锁。
  2. ThreadLocal 是每个线程都有一个副本,是不需要加锁的。
  3. lock 是通过时间换空间的做法。
  4. ThreadLocal 是典型的通过空间换时间的做法。

当然他们的使用场景也是不同的,关键看你的资源是需要多线程之间共享的还是单线程内部共享的

使用

ThreadLocal 的使用是非常简单的,看下面的代码

public class Test {

    public static void main(String[] args) {
        ThreadLocal<String> local = new ThreadLocal<>();
        //设置值
        local.set("hello word");
        //获取刚刚设置的值
        System.out.println(local.get());
    }
}


复制代码

看到这里是不是觉得特别简单?别高兴太早,点进去代码看看,你绝对会怀疑人生

源码分析

在分析源码之前先画一下ThreadLocal ,ThreadLocalMap 和Thread 的关系,如果你对他们的关系还不了解的话,请看我的另一篇文章 BAT面试必考:ThreadLocal ,ThreadLocalMap 和Thread 的关系

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

set 方法

public void set(T value) {
        Thread t = Thread .currentThread();
        // 获取线程绑定的ThreadLocalMap
        ThreadLocalMap map = getMap(t);
        if (map != null)
            map.set(this, value);
        else
           //第一次设置值的时候进来是这里
            createMap(t, value);
    }
复制代码

createMap 方法只是在第一次设置值的时候创建一个ThreadLocalMap 赋值给Thread 对象的threadLocals 属性进行绑定,以后就可以直接通过这个属性获取到值了。从这里可以看出,为什么说ThreadLocal 是线程本地变量来的了

void createMap(Thread t, T firstValue) {
        t.threadLocals = new ThreadLocalMap(this, firstValue);
    }
复制代码

值真正是放在ThreadLocalMap 中存取的,ThreadLocalMap 内部类有一个Entry 类,key是ThreadLocal 对象,value 就是你要存放的值,上面的代码value 存放的就是hello word。ThreadLocalMap 和HashMap的功能类似,但是实现上却有很大的不同:

  1. HashMap 的数据结构是数组+链表
  2. ThreadLocalMap的数据结构仅仅是数组
  3. HashMap 是通过链地址法解决hash 冲突的问题
  4. ThreadLocalMap 是通过开放地址法来解决hash 冲突的问题
  5. HashMap 里面的Entry 内部类的引用都是强引用
  6. ThreadLocalMap里面的Entry 内部类中的key 是弱引用,value 是强引用

为什么ThreadLocalMap 采用开放地址法来解决哈希冲突?

jdk 中大多数的类都是采用了链地址法来解决hash 冲突,为什么ThreadLocalMap 采用开放地址法来解决哈希冲突呢?首先我们来看看这两种不同的方式

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。列如对于关键字集合{12,67,56,16,25,37, 22,29,15,47,48,34},我们用前面同样的12为除数,进行除留余数法:

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

开放地址法

这种方法的基本思想是一旦发生了冲突,就去寻找下一个空的散列地址(这非常重要,源码都是根据这个特性,必须理解这里才能往下走),只要散列表足够大,空的散列地址总能找到,并将记录存入。

比如说,我们的关键字集合为{12,33,4,5,15,25},表长为10。 我们用散列函数f(key) = key mod l0。 当计算前S个数{12,33,4,5}时,都是没有冲突的散列地址,直接存入(蓝色代表为空的,可以存放数据):

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

计算key = 15时,发现f(15) = 5,此时就与5所在的位置冲突。

于是我们应用上面的公式f(15) = (f(15)+1) mod 10 =6。于是将15存入下标为6的位置。这其实就是房子被人买了于是买下一间的作法:

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

链地址法和开放地址法的优缺点

开放地址法:

  1. 容易产生堆积问题,不适于大规模的数据存储。
  2. 散列函数的设计对冲突会有很大的影响,插入时可能会出现多次冲突的现象。
  3. 删除的元素是多个冲突元素中的一个,需要对后面的元素作处理,实现较复杂。

链地址法:

  1. 处理冲突简单,且无堆积现象,平均查找长度短。
  2. 链表中的结点是动态申请的,适合构造表不能确定长度的情况。
  3. 删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
  4. 指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间。

ThreadLocalMap 采用开放地址法原因

  1. ThreadLocal 中看到一个属性 HASH_INCREMENT = 0x61c88647 ,0x61c88647 是一个神奇的数字,让哈希码能均匀的分布在2的N次方的数组里, 即 Entry[] table,关于这个神奇的数字google 有很多解析,这里就不重复说了
  2. ThreadLocal 往往存放的数据量不会特别大(而且key 是弱引用又会被垃圾回收,及时让数据量更小),这个时候开放地址法简单的结构会显得更省空间,同时数组的查询效率也是非常高,加上第一点的保障,冲突概率也低

弱引用

如果对弱引用不了解的同学,先看下我之前的写的一篇文章 别再找了,一文彻底解析Java 中的弱引用(参考官网)系

接下来我们看看ThreadLocalMap 中的存放数据的内部类Entry 的实现源码

static class Entry extends WeakReference<ThreadLocal<?>> {
            /** The value associated with this ThreadLocal. */
            Object value;

            Entry(ThreadLocal<?> k, Object v) {
                super(k);
                value = v;
            }
        }
复制代码

我们可以知道Entry 的key 是一个弱引用,也就意味这可能会被垃圾回收器回收掉

threadLocal.get()==null
复制代码

也就意味着被回收掉了

ThreadLocalMap set 方法

private void set(ThreadLocal<?> key, Object value) {

            Entry[] tab = table;
            int len = tab.length;
            //计算数组的下标
            int i = key.threadLocalHashCode & (len-1);

           //注意这里结束循环的条件是e != //null,这个很重要,还记得上面讲的开放地址法吗?忘记的回到上面看下,一定看懂才往下走,不然白白浪费时间
           //这里遍历的逻辑是,先通过hash 找到数组下标,然后寻找相等的ThreadLocal对象
           //找不到就往下一个index找,有两种可能会退出这个循环
           // 1.找到了相同ThreadLocal对象
           // 2.一直往数组下一个下标查询,直到下一个下标对应的是null 跳出
            for (Entry e = tab[i];
                 e != null;
                 e = tab[i = nextIndex(i, len)]) {
                ThreadLocal<?> k = e.get();
                //如果找到直接设置value 值返回,这个很简单没什么好讲的
                if (k == key) {
                    e.value = value;
                    return;
                }

               // k==null&&e!=null 说明key被垃圾回收了,这里涉及到弱引用,接下来讲
                if (k == null) {
                //被回收的话就需要替换掉过期过期的值,把新的值放在这里返回
                    replaceStaleEntry(key, value, i);
                    return;
                }
            }
            //来到这里,说明没找到
            tab[i] = new Entry(key, value);
            int sz = ++size;
            if (!cleanSomeSlots(i, sz) && sz >= threshold)
              //进行扩容,这里先不讲
                rehash();
        }
复制代码

还是拿上面解释开放地址法解释的例子来说明下。 比如说,我们的关键字集合为{12,33,4,5,15,25},表长为10。 我们用散列函数f(key) = key mod l0。 当计算前S个数{12,33,4,5,15,25}时,并且此时key=33,k=5 已经过期了(蓝色代表为空的,可以存放数据,红色代表key 过期,过期的key为null):

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

这时候来了一个新的数据,key=15,value=new,通过计算f(15)=5,此时5已经过期,进入到下面这个if 语句

if (k == null) {
    //key 过期了,要进行替换
        replaceStaleEntry(key, value, i);
        return;
     }
复制代码

replaceStaleEntry 这个方法

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

            //这里采用的是从当前的staleSlot 位置向前面遍历,i--
            //这样的话是为了把前面所有的的已经被垃圾回收的也一起释放空间出来
            //(注意这里只是key 被回收,value还没被回收,entry更加没回收,所以需要让他们回收),
            //同时也避免这样存在很多过期的对象的占用,导致这个时候刚好来了一个新的元素达到阀值而触发一次新的rehash
            int slotToExpunge = staleSlot;
            for (int i = prevIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = prevIndex(i, len))
                 //slotToExpunge 记录staleSlot左手边第一个空的entry 到staleSlot 之间key过期最小的index
                if (e.get() == null)
                    slotToExpunge = i;

            // 这个时候是从数组下标小的往下标大的方向遍历,i++,刚好跟上面相反。
            //这两个遍历就是为了在左边遇到的第一个空的entry到右边遇到的第一空的 entry之间查询所有过期的对象。
            //注意:在右边如果找到需要设置值的key(这个例子是key=15)相同的时候就开始清理,然后返回,不再继续遍历下去了
            for (int i = nextIndex(staleSlot, len);
                 (e = tab[i]) != null;
                 i = nextIndex(i, len)) {
                ThreadLocal<?> k = e.get();
                //说明之前已经存在相同的key,所以需要替换旧的值并且和前面那个过期的对象的进行交换位置,
                //交换的目的下面会解释
                if (k == key) {
                    e.value = value;

                    tab[i] = tab[staleSlot];
                    tab[staleSlot] = e;

                    //这里的意思就是前面的第一个for 循环(i--)往前查找的时候没有找到过期的,只有staleSlot
                    // 这个过期,由于前面过期的对象已经通过交换位置的方式放到index=i上了,
                    // 所以需要清理的位置是i,而不是传过来的staleSlot
                    if (slotToExpunge == staleSlot)
                        slotToExpunge = i;
                        //进行清理过期数据
                    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
                    return;
                }

                // 如果我们在第一个for 循环(i--) 向前遍历的时候没有找到任何过期的对象
                // 那么我们需要把slotToExpunge 设置为向后遍历(i++) 的第一个过期对象的位置
                // 因为如果整个数组都没有找到要设置的key 的时候,该key 会设置在该staleSlot的位置上
                //如果数组中存在要设置的key,那么上面也会通过交换位置的时候把有效值移到staleSlot位置上
                //综上所述,staleSlot位置上不管怎么样,存放的都是有效的值,所以不需要清理的
                if (k == null && slotToExpunge == staleSlot)
                    slotToExpunge = i;
            }

            // 如果key 在数组中没有存在,那么直接新建一个新的放进去就可以
            tab[staleSlot].value = null;
            tab[staleSlot] = new Entry(key, value);

            // 如果有其他已经过期的对象,那么需要清理他
            if (slotToExpunge != staleSlot)
                cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
        }
复制代码

第一个for 循环是向前遍历数据的,直到遍历到空的entry 就停止(这个是根据开放地址的线性探测法),这里的例子就是遍历到index=1就停止了。向前遍历的过程同时会找出过期的key,这个时候找到的是下标index=3 的为过期,进入到

if (e.get() == null)
                    slotToExpunge = i;
复制代码

注意此时slotToExpunge=3,staleSlot=5

第二个for 循环是从index=staleSlot开始,向后编列的,找出是否有和当前匹配的key,有的话进行清理过期的对象和重新设置当前的值。这个例子遍历到index=6 的时候,匹配到key=15的值,进入如下代码

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

复制代码

先进行数据交换,注意此时slotToExpunge=3,staleSlot=5,i=6。这里就是把5 和6 的位置的元素进行交换,并且设置新的value=new,交换后的图是这样的

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

为什么要交换

这里解释下为什么交换,我们先来看看如果不交换的话,经过设置值和清理过期对象,会是以下这张图

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

这个时候如果我们再一次设置一个key=15,value=new2 的值,通过f(15)=5,这个时候由于上次index=5是过期对象,被清空了,所以可以存在数据,那么就直接存放在这里了

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

你看,这样整个数组就存在两个key=15 的数据了,这样是不允许的,所以一定要交换数据

expungeStaleEntry

private int expungeStaleEntry(int staleSlot) {
            Entry[] tab = table;
            int len = tab.length;

            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) {
                //这里设置为null ,方便让GC 回收
                    e.value = null;
                    tab[i] = null;
                    size--;
                } else {
                //这里主要的作用是由于采用了开放地址法,所以删除的元素是多个冲突元素中的一个,需要对后面的元素作
                //处理,可以简单理解就是让后面的元素往前面移动
                //为什么要这样做呢?主要是开放地址寻找元素的时候,遇到null 就停止寻找了,你前面k==null
                //的时候已经设置entry为null了,不移动的话,那么后面的元素就永远访问不了了,下面会画图进行解释说明
                
                    int h = k.threadLocalHashCode & (len - 1);
                    //他们不相等,说明是经过hash 是有冲突的
                    if (h != i) {
                        tab[i] = null;

                        while (tab[h] != null)
                            h = nextIndex(h, len);
                        tab[h] = e;
                    }
                }
            }
            return i;
        }

复制代码

接下来我们详细模拟下整个过程 根据我们的例子,key=5,15,25 都是冲突的,并且k=5的值已经过期,经过replaceStaleEntry 方法,在进入expungeStaleEntry 方法之前,数据结构是这样的

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

此时传进来的参数staleSlot=6,

if (k == null) {
                //这里设置为null ,方便让GC 回收
                    e.value = null;
                    tab[i] = null;
                    size--;
                }
复制代码

这个时候会把index=6设置为null,数据结构变成下面的情况

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

接下来我们会遍历到i=7,经过int h = k.threadLocalHashCode & (len - 1) (实际上对应我们的举例的函数int h= f(25)); 得到的h=5,而25实际存放在index=7 的位置上,这个时候我们需要从h=5的位置上重新开始编列,直到遇到空的entry 为止

int h = k.threadLocalHashCode & (len - 1);
                    if (h != i) {
                        tab[i] = null;

                        while (tab[h] != null)
                            h = nextIndex(h, len);
                        tab[h] = e;
                    }
复制代码

这个时候h=6,并把k=25 的值移到index=6 的位置上,同时设置index=7 为空,如下图

被大厂面试官连环炮轰炸的ThreadLocal (吃透源码的每一个细节和设计原理)

其实目的跟replaceStaleEntry 交换位置的原理是一样的,为了防止由于回收掉中间那个冲突的值,导致后面冲突的值没办法找到(因为e==null 就跳出循环了)

ThreadLocal 内存溢出问题:

通过上面的分析,我们知道 expungeStaleEntry() 方法是帮助垃圾回收的,继续根据源码,我们可以发现 get 和set 方法都可能触发清理方法 expungeStaleEntry() ,所以正常情况下是不会有内存溢出的 但是如果我们没有调用get 和set 的时候就会可能面临着内存溢出,养成好习惯不再使用的时候调用remove(),加快垃圾回收,避免内存溢出

退一步说,就算我们没有调用get 和set 和remove 方法,线程结束的时候,也就以为着没有强引用再指向ThreadLocal 中的ThreadLocalMap了,这样ThreadLocalMap 和里面的元素也会被回收掉,但是有一种危险是,如果线程是线程池的, 在线程执行完代码的时候并没有结束,只是归还给线程池,这个时候ThreadLocalMap 和里面的元素是不会回收掉的

原文  https://juejin.im/post/5d8b2bde51882509372faa7c
正文到此结束
Loading...