前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >深入细节ThreadLocalMap

深入细节ThreadLocalMap

原创
作者头像
笔头
修改2022-02-14 15:18:46
1.1K3
修改2022-02-14 15:18:46
举报
文章被收录于专栏:Android记忆

前面一篇文章ThreadLocal浅析,让我们大概了解其内部运行方式,不熟悉ThreadLocal的同学,在指教下面文章前建议看下,或多或少有点帮助。

这篇文章,我这里重点是了解下ThreadLocalMap。看下get、set、remove等方法内部实现

一、set

代码语言:java
复制
private void set(ThreadLocal<?> key, Object value) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);//计算当前key的hash值,也就是数组下标
    for (Entry e = tab[i];      
         e != null;
         e = tab[i = nextIndex(i, len)]) {  //这就话就是不断向下寻找非null的Entry。
        ThreadLocal<?> k = e.get();
        --------------------- 步骤一  --------------------
        if (k == key) {//如果当前Entry的key正好就是当前ThreadLocal,则替换value值就好
            e.value = value;
            return;
        }
        --------------------- 步骤二  --------------------
        if (k == null) { //Entry中key,即ThreadLocal是弱引用,很容易被回收key=null。
            replaceStaleEntry(key, value, i); //替换Entry,清理无效Entry,整理Entry数字
            return;
        }
    }
    
    --------------------- 步骤三  --------------------
    //如果Entry数组里,没有相同的key或key=null的Entry,那就新增Entry到Entry数组里。
    tab[i] = new Entry(key, value);
    int sz = ++size;
    //清理无效Entry后,在看下当前Entry容量是否超过阀值,超过的话就要扩容。
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

1.threadLocalHashCode

看下 int i = key.threadLocalHashCode &(len-1);这句代码,粗看,这个有点像HashMap中hashcode获得方式。具体我们来看看源码

代码语言:java
复制
private final int threadLocalHashCode = nextHashCode();
private static AtomicInteger nextHashCode = new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;
private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

这里定义了一个AtomicInteger类型,每次获取threadLocalHashCode,nextHashCode当前值都要加上HASH_INCREMENT,HASH_INCREMENT=0x61c88647,是一个神奇的数字,让哈希码能均匀的分布在2的N次方的数组里,他为啥用这个数?我们看下& (len - 1) 这个这是取模的一种方式,对于2的幂作为模数取模,用此代替%(2^n),这也就是为啥用0x61c88647了。这样的话,key.threadLocalHashCode &(len-1)得出的值,也就是数组下标,就在【0~数组长度-1】之间,肯定在Entry[] table 数组长度值内。

2.nextIndex

看下nextIndex源码

代码语言:java
复制
private static int nextIndex(int i, int len) {
    return ((i + 1 < len) ? i + 1 : 0);
}

这段就是取下一个下标index,如果下一个下标就最后一个下标,则从0下标开始。就是一个正向环形移位操作。

3.replaceStaleEntry

当Entry中的key即ThreadLocal,(Entry中的ThreadLocal是弱引用),在即被回收或其他情况,导致当前Entry的key=null,这个时候调用replaceStaleEntry方法,清理、替换无效Entry、整理Entry数组。这是ThreadLocalMap核心内容。

代码语言:javascript
复制
private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                               int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    Entry e;

    int slotToExpunge = staleSlot;//staleSlot就是当前下标
    for (int i = prevIndex(staleSlot, len); //从staleSlot下标开始,不断向前遍历Entry数组,
                                            //找到key=null最小下标
         (e = tab[i]) != null;
         i = prevIndex(i, len))
        if (e.get() == null)
            slotToExpunge = i;

    for (int i = nextIndex(staleSlot, len);
         (e = tab[i]) != null;
         i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        ---------------------步骤1------------------------
        if (k == key) {//从staleSlot下标开始往后找Entry,如果当前key和位置i的Entry key一样,那就交换value
            e.value = value;
            tab[i] = tab[staleSlot];
            tab[staleSlot] = e;

            if (slotToExpunge == staleSlot)//如果上面prevIndex过程没有找到key=null的Entry,
                                           //则清理位置i的Entry
                slotToExpunge = i;
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len); //清理数据
            return;
        }
        ---------------------步骤2------------------------
        if (k == null && slotToExpunge == staleSlot)
            slotToExpunge = i;
    }

    tab[staleSlot].value = null;
    tab[staleSlot] = new Entry(key, value);

    if (slotToExpunge != staleSlot)
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

4.prevIndex

看下prevIndex源码

代码语言:javascript
复制
private static int prevIndex(int i, int len) {
    return ((i - 1 >= 0) ? i - 1 : len - 1);
}

这个和nextIndex效果类似,只不过移位方向和nextIndex相反。

5.cleanSomeSlots

看下cleanSomeSlots源码

代码语言:javascript
复制
private boolean cleanSomeSlots(int i, int n) {
    boolean removed = false;
    Entry[] tab = table;
    int len = tab.length;
    do {
        i = nextIndex(i, len);
        Entry e = tab[i];
        if (e != null && e.get() == null) {
            n = len;
            removed = true;
            i = expungeStaleEntry(i);
        }
    } while ( (n >>>= 1) != 0);
    return removed;
}

大致意思是 遍历Entry数组,e !=null&& e.get()==null条件的Entry即无效Entry的位置下标,然后调用expungeStaleEntry清理数据

6.expungeStaleEntry

看下expungeStaleEntry源码

代码语言:java
复制
private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;

    //清空位置staleSlot的Entry
    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) {  //从位置staleSlot开始,往后遇到key=null的就清理对应的Entry 
                          //这里设置为null ,方便让GC 回收
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            //计算出来的索引 h,与其现在所在位置的索引 i 不一致,置空当前的table[i]
            if (h != i) {
                tab[i] = null;
                //从h下标开始往后,遇到null的情况,则把当前Entry放在h位置,把非null的Entry放在前面
                while (tab[h] != null)
                    h = nextIndex(h, len);
                tab[h] = e;
            }
        }
    }
    return i;
}

expungeStaleEntry ,大概意思是

从下标staleSlot开始,往后遍历直到遇到Entry是null【这个staleSlot就是key=null的下标位置或者向前遍历key=null的最小下标位置】

1.清空staleSlot位置的数据.

2.遇到key=null的Entry,则清空该Entry

3.如果当前Entry的key不是null,说明Entry有数据,计算其key的hash值和当前对应数组下标比较,一样的话就当没事,如果不一样,就要把该下标的Entry设为null,同时计算该key的hash值即下标,在该下标后面遇到为null的Entry,把当前的Entry放在此处即null的位置。为何要这么做??

7.rehash

代码语言:javascript
复制
private void rehash() {
    expungeStaleEntries();
    if (size >= threshold - threshold / 4)
        resize();
}

rehash主要是两个步骤

1.expungeStaleEntries

代码语言:javascript
复制
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);
    }
}

里面调用expungeStaleEntry,还是清理、整理Entry数组

2.resize

如果当前size>= threshold - threshold /4,就走resize过程,也就是扩容过程。

代码语言:javascript
复制
private void resize() {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    int count = 0;

    for (int j = 0; j < oldLen; ++j) {
        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);
                newTab[h] = e;
                count++;
            }
        }
    }

    setThreshold(newLen);
    size = count;
    table = newTab;
}

整个过程不难理解。

扩容,容量是之前的2倍,遍历旧Entry数组,为每个Entry重新计算hash值作为key,把旧Entry放进新Entry数组里。

至此,set流程完毕,过程涉及到 替换Entry、清理无效Entry、整理Entry数组、和扩容

整个set过程差不多这样,但是感觉看懂又不懂,我们直接来个案例,加深理解。

这个画图,我先暂时用其他作者的图,后期换掉。

二、实例解读Set(重点)

场景一、

Entry数组里,起始下标后面没有相同的key或key=null的Entry。那就在首次遇到Entry=null的地方存放该数据。

我们准备表长为10的Entry数组,计算key哈希值 我们用函数f(key) = key mod l0,简单一些。现在我们有 4个树值{12,33,4,5},都是没有冲突的散列地址,直接存入(蓝色代表为空的,可以存放数据):

现在我们想set一个值,key=15,f(15)=5,也就是i=5

回看set方法,从下标5开始遍历,发现下标为6时Entry为null。此时f(15)=5,key=15和key=5不等,且f(15)=5不为null,不符合步骤一和二,我们走步骤三,此时i经过nextIndex移位,i=6。那就把key=15放在下标6的位置。

然后在判断是否要rehash,显然容量还没达到阀值,不需要扩容。

假如哈,假如。在添加key=15时,Entry数组容量正好满了,这个时候tab[11]存放key=15的Entry,需要扩容了。

场景二、

Entry数组里,起始下标后面,有key=null的Entry。

我们准备表长为10的Entry数组,计算key哈希值 我们用函数f(key) = key mod l0,简单一些。现在我们有 6个数值{12,33,4,5,15,25},并且此时key=33,k=5 已经过期了(蓝色代表为空的,可以存放数据,红色代表key 过期,过期的key为null)

现在我们想set一个值,key=15,f(15)=5,也就是i=5

回看set方法,从下标5开始遍历,发现下标为5的key=null,按道理,我们应该走步骤二,即进入replaceStaleEntry方法

里面做啥呢?回看replaceStaleEntry方法,我们知道其中内幕。

1.记录当前位置,也就是i=5,slotToExpunge = staleSlot=5

2.从下标5开始往前移动,直到遇到Entry为null为止,也就是下标1的位置。找到下标最小key=null的位置。看图,很容易直到那这个位置就是3,slotToExpunge=3。

3.从下标5开始往后遍历,直到遇到Entry为null为止,也就是下标8的位置。

在步骤3这过程中:

如果发现有待插入Entry的key和遍历过程中Entry的key相同,那就把该Entry和下标为staleSlot的Entry交换位置。也就是下标5,f(15)的数据,下标6,key=null 的数据 交换,原本key=15的数据被f(15)替换。

这个过程主要是两部分,第一,替换旧数据,第二交换位置。交换后如图。

然后看下expungeStaleEntry流程。slotToExpunge=3和staleSlot=5不等,于是从下标3开始 所有key=null的Entry被清空。

这里我们看下为什么要交换数据和清空数据?

清空数据容易理解,数据过期了嘛,自然要清空,释放空间给对方百分点。

我们来看看为什么要交换,这里说交换,这里有点难理解。起始我们的想法是,ThreadLocalMap里面的数据,不能存在相同的key,也就是冲突的key,假如key=15的Entry和下标5的Entry不交换,如果此时,我想插入f(15)的数据,那这数据就存放在下标5的地方,ThreadLocalMap里面就存在两个key=15的Entry,这肯定不行。

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

expungeStaleEntry流程最后返回i=7;

最后还要执行cleanSomeSlots,清除过期无效的Entry,但是下标7及后面没有过期无效Entry,所以结束。

三、getEntry

代码语言:javascript
复制
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);
}

这里面没啥好讲的,我们来看下getEntryAfterMiss

代码语言:javascript
复制
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;
}

其实有一种情况,不同的key hash值,但是可能他们key是一样的。上面代码主要功能就是遍历Entry数组,找到key一样的Entry,找到就返回此Entry,找不到就返回null。

四、remove

代码语言:javascript
复制
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();
            expungeStaleEntry(i);
            return;
        }
    }
}

这里面有了上面讲解基础,很好理解。根据当前key的hash值,也就是数组下标,找到对应的Entry,判断此时的Entry的key和当前ThreadLocal是不是同一个,是的话,就clear,然后expungeStaleEntry清理、整理Entry数组。

五、问题

HashMap和ThreadLocalMap区别,怕篇幅太长,为了减少阅读压力,这个留在后面一篇聊聊吧。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、set
    • 1.threadLocalHashCode
      • 2.nextIndex
        • 3.replaceStaleEntry
          • 4.prevIndex
            • 5.cleanSomeSlots
              • 6.expungeStaleEntry
                • 7.rehash
                  • 场景一、
                  • 场景二、
              • 二、实例解读Set(重点)
              • 三、getEntry
              • 四、remove
              • 五、问题
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档