ThreadLocalMapLocalMap 简介
ThreadLocalMapLocalMap 是一个散列表结构的容器，用来存储线程的本地变量。使用开放地址法解决散列冲突。它是ThreadLocal的一个静态内部类。
数据存储结构
ThreadLocal对象作为hash表的key,通过散列函数计算hash表中的下标，哈希表中每个下标下保存Entry类实例。里面存在两个属性一个是ThreadLocal作为散列表的key，另一个是key对应值(value)
image
源码中定义
static class ThreadLocalMap {
/**
* 哈希表中节点对象
* key ：类型ThreadLocal，被定义为WeakReference
* value：类型Object，引用存储值
* */
static class Entry extends WeakReference<ThreadLocal<?>> {
/** ThreadLocal */
Object value;
Entry(ThreadLocal<?> k, Object v) {
super(k);
value = v;
}
}
/**
* 默认哈希表容量，必须是2的幂次方
*/
private static final int INITIAL_CAPACITY = 16;
/**
* 哈希表(Entry)数组
*/
private Entry[] table;
/**
* 容器中存储Entry的个数
*/
private int size = 0;
/**
* 下一次需要扩容的阈值
*/
private int threshold; // Default to 0
...省略代码
Entry在数组中存在类型
image
USED:表示数组中下标位置被一个Entry占用
NULL:表示数组中下标位置为NULL
STALE:表示数组中下标位置被一个脏Entry占用，key为NULL的Entry。
什么时候存在脏Entry
image
由于Entry被WeakReference所引用，即使存在一条线程对象GCROOT(虚线路径),因而当gc回收时，如果TheadLocal对象没有被强引用则会被回收。
案例
定义一个Entry类
package threadLocal;
import java.lang.ref.WeakReference;
public class Entry extends WeakReference<ThreadLocal<Object>> {
public Object value;
Entry(ThreadLocal<Object> k, Object v) {
super(k);
value = v;
}
}
编写测试类
/**
* Salad salad = new Salad(threadLocal,new Object());
* 存在一条到GC root通路 thread <-- Salad <-- WeakReference <-- ThreadLocal
* 由于是WeakReference，因而如果ThreadLocal并没有存在其他强引用时会被gc回收
* 即threadLocal=null 代码开启将被回收
*/
public class WeakReferenceTest {
public static void main(String[] args) {
ThreadLocal<Object> threadLocal = new ThreadLocal<Object>();
Entry salad = new Entry(threadLocal,new Object());
//通过WeakReference的get()方法获取Apple
System.out.println("ThreadLocal:" + salad.get());
//开启代码threadLocal将被回收
threadLocal=null;
System.gc();
try {
//休眠一下，在运行的时候加上虚拟机参数-XX:+PrintGCDetails，输出gc信息，确定gc发生了。
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
//如果为空，代表被回收了
if (salad.get() == null) {
System.out.println("clear Apple。");
}
}
}
核心方法
设置值
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
image
我们来看下ThreadLocalMap实现
/**
* 设置ThreadLocal（key），对应值
*/
private void set(ThreadLocal<?> key, Object value) {
/** 获取哈希数组 **/
Entry[] tab = table;
/** 获取哈希数组长度 **/
int len = tab.length;
/** 通过hash运算获取ThreadLocal在哈希表的 i位置**/
int i = key.threadLocalHashCode & (len-1);
/** 获取下标位置的Entry，判断Entry是否存在，且Entry.key和传入key相同
* 如果Entry存在且Entry.key和传入key相同，则覆盖值
* 如果Entry存在且Entry,key和传入key不相同，表明发生hash碰撞，按照开放定址法，从下标位置向后查找未被暂用的哈希表节点插入
* 如果Entry存在且Entry,key==null,表明此Entry是一个脏Entry，用当前传入值构造一个新Entry，替换这个下标位置脏Entry
* **/
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
ThreadLocal<?> k = e.get();
/** 如果Entry存在且Entry.key和传入key相同，则覆盖值 **/
if (k == key) {
e.value = value;
return;
}
/** 如果Entry存在且Entry,key==null,表明此Entry是一个脏Entry，用当前传入值构造一个新Entry，替换这个下标位置脏Entry **/
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
/** 如果Entry存在且Entry,key和传入key不相同，表明发生hash碰撞，按照开放定址法，从下标位置向后查找未被暂用的哈希表节点插入 **/
}
/** 新建entry并插入哈希表 i 位置 **/
tab[i] = new Entry(key, value);
/** 哈希表节点数量+1 **/
int sz = ++size;
/** 插入后从哈希表中查找并擦除脏Entry,如果未找到脏，且哈希表容量大于阈值就需要扩容 **/
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}
这里cleanSomeSlots，replaceStaleEntry对脏Entry处理留到下一篇。
查找元素
在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中
为什么遍历到空位置就表示不存在？
因为插入元素时发生散列冲突，会找到数组一个空位置就插入了。如果查找时遍历到一个空位置还没有找到则说明要查找的元素并没有在散列表中
image
我们来看下ThreadLocalMap实现
/**
* 给定指定key，查找Entry
*/
private Entry getEntry(ThreadLocal<?> key) {
/** 通过hash运算获取ThreadLocal在哈希表的 i位置**/
int i = key.threadLocalHashCode & (table.length - 1);
/** 获取哈希表 i位置Entry **/
Entry e = table[i];
/** 如果Entry存在且Entry.key和传入的key匹配，则直接返回Entry **/
if (e != null && e.get() == key)
return e;
else
/**
* 1 传入key对应Entry不存在直接返回
* 2 传入key对应Entry存在，传入key和Entry.key不匹配(hash碰撞)，使用开放定址法在哈希表中查找
* **/
return getEntryAfterMiss(key, i, e);
}
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
while (e != null) {
ThreadLocal<?> k = e.get();
/** 对比key是否相同，如果相同则返回 **/
if (k == key)
return e;
/** 如果发现脏节点，则调用expungeStaleEntry清理 **/
if (k == null)
expungeStaleEntry(i);
else
/** 获取当前位置下一个哈希表节点 **/
i = nextIndex(i, len);
e = tab[i];
}
/** 如果ashCode映射到哈希表数组下标位置为null，说明传入key对应的节点在哈希表中不存在 **/
return null;
}
删除元素
在散列表中删除元素有些特殊，首先我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素。如果相等。此时我们如果仅仅只是删除元素对于删除元素来说是没有问题。但会影响查询元素。
在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。
解决思路
从数组中删除该元素，同时继续向后探测，将散列冲突的元素填入删除元素的位置。
我们来看下ThreadLocalMap实现
/**
* 删除ThreadLocal（key），对应的副本变量值
*/
private void remove(ThreadLocal<?> key) {
Entry[] tab = table;
int len = tab.length;
/** 通过hash运算获取ThreadLocal在哈希表的 i位置**/
int i = key.threadLocalHashCode & (len-1);
/** 获取下标位置的Entry，判断Entry是否存在，且Entry.key和传入key相同
* 如果Entry存在，且Entry.key和传入key相同，则将查找到Entry设置为脏节点，然后调用expungeStaleEntry清理
* 如果Entry存在，且Entry.key和传入key不相同，表明发生hash碰撞，按照开放定址法，从下标位置向后查找key和传入相同哈希表节
* 如果找到则将查找到Entry设置为脏节点，然后调用expungeStaleEntry清理
*/
for (Entry e = tab[i];
e != null;
e = tab[i = nextIndex(i, len)]) {
if (e.get() == key) {
e.clear();
expungeStaleEntry(i);
return;
}
}
}
/**
* 1 擦除脏Entry，并从脏Entry位置开始向后查找脏Entry，发现则擦除直到一个空节点结束
* 2 从当前staleSlot位置向后环形（nextIndex）继续搜索，发现冲突的节点填充到前面的擦除节点
*/
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;
/** 直接擦除指定索引位置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();
/** 直接擦除指定索引位置Entry； **/
if (k == null) {
e.value = null;
tab[i] = null;
size--;
} else {
/** 通过hash运算获取ThreadLocal在哈希表的 i位置**/
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表，容量*2，表示原始hash表数据拷贝过去。
/**
* 哈希表扩容
*/
private void rehash() {
/** 擦除哈希表中所有脏Entry **/
expungeStaleEntries();
/** 当容量大于阈值的3/4则扩容 **/
if (size >= threshold - threshold / 4)
resize();
}
/**
* 每次扩容偶会创建当前容量*2的哈希表，并将原来哈希表中的数据拷贝过去
*/
private void resize() {
Entry[] oldTab = table;
int oldLen = oldTab.length;
int newLen = oldLen * 2;
Entry[] newTab = new Entry[newLen];
int count = 0;
/** 遍历原始的哈希表，脏Entry擦除，非脏Entry重新计算ThreadLocal在新哈希表的 i位置
* 并插入 **/
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;
}
/**
* 擦除哈希表中所有脏Entry
* 1 擦除哈希表中所有脏Entry
*/
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);
}
}
网友评论