Foutin

ThreadLocal

成熟成熟


概述

ThreadLocal也是一种解决多线程并发无锁的方法。这里简单分析一下。以下内容仅仅是个人的记录。


ThreadLocal

为什么用ThreadLocal

ThreadLocal 提供了线程本地变量,它可以保证访问到的变量属于当前线程,每个线程都保存有一个变量副本,每个线程的变量都不同,而同一个线程在任何时候访问这个本地变量的结果都是一致的。当此线程结束生命周期时,所有的线程本地实例都会被 GC。ThreadLocal 相当于提供了一种线程隔离,将变量与线程相绑定。ThreadLocal 通常定义为 private static 类型。

假如让我们来实现一个变量与线程相绑定的功能,我们可以很容易地想到用HashMap来实现,Thread作为key,变量作为value。事实上,JDK 中确实使用了类似 Map 的结构存储变量,但不是像我们想的那样。下面我们来探究OpenJDK 1.8中ThreadLocal的实现。

从线程Thread的角度来看,每个线程内部都会持有一个对ThreadLocalMap实例的引用,ThreadLocalMap实例相当于线程的局部变量空间,存储着线程各自的数据,具体如下图:

ThreadLocal源码

ThreadLocal

ThreadLocal 通过 threadLocalHashCode 来标识每一个 ThreadLocal 的唯一性。threadLocalHashCode 通过 CAS 操作进行更新,每次 hash 操作的增量为 0x61c88647(为什么用这个数,可以自行查)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class ThreadLocal<T> {
/**
* ThreadLocals rely on per-thread linear-probe hash maps attached
* to each thread (Thread.threadLocals and
* inheritableThreadLocals). The ThreadLocal objects act as keys,
* searched via threadLocalHashCode. This is a custom hash code
* (useful only within ThreadLocalMaps) that eliminates collisions
* in the common case where consecutively constructed ThreadLocals
* are used by the same threads, while remaining well-behaved in
* less common cases.
*/
private final int threadLocalHashCode = nextHashCode();

/**
* The next hash code to be given out. Updated atomically. Starts at
* zero.
*/
private static AtomicInteger nextHashCode =
new AtomicInteger();

/**
* The difference between successively generated hash codes - turns
* implicit sequential thread-local IDs into near-optimally spread
* multiplicative hash values for power-of-two-sized tables.
*/
private static final int HASH_INCREMENT = 0x61c88647;

/**
* Returns the next hash code.
*/
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}

set 方法:

1
2
3
4
5
6
7
8
public void set(T value) {
Thread t = Thread.currentThread();
ThreadLocalMap map = getMap(t);
if (map != null)
map.set(this, value);
else
createMap(t, value);
}

可以看到通过Thread.currentThread()方法获取了当前的线程引用,并传给了getMap(Thread)方法获取一个ThreadLocalMap的实例。我们继续跟进getMap(Thread)方法:

1
2
3
4
5
6
7
8
9
10
/**
* Get the map associated with a ThreadLocal. Overridden in
* InheritableThreadLocal.
*
* @param t the current thread
* @return the map
*/
ThreadLocalMap getMap(Thread t) {
return t.threadLocals;
}

可以看到getMap(Thread)方法直接返回Thread实例的成员变量threadLocals。它的定义在Thread内部,访问级别为package级别:

1
2
3
/* ThreadLocal values pertaining to this thread. This map is maintained
* by the ThreadLocal class. */
ThreadLocal.ThreadLocalMap threadLocals = null;

到了这里,我们可以看出,每个Thread里面都有一个ThreadLocal.ThreadLocalMap成员变量,也就是说每个线程通过ThreadLocal.ThreadLocalMap与ThreadLocal相绑定,这样可以确保每个线程访问到的thread-local variable都是本线程的。

我们往下继续分析。获取了ThreadLocalMap实例以后,如果它不为空则调用ThreadLocalMap.ThreadLocalMap#set方法设值;若为空则调用ThreadLocal#createMap方法new一个ThreadLocalMap实例并赋给Thread.threadLocals

ThreadLocal#createMap方法的源码如下:

1
2
3
4
5
6
7
8
9
10
/**
* Create the map associated with a ThreadLocal. Overridden in
* InheritableThreadLocal.
*
* @param t the current thread
* @param firstValue value for the initial entry of the map
*/
void createMap(Thread t, T firstValue) {
t.threadLocals = new ThreadLocalMap(this, firstValue);
}

ThreadLocalMap

ThreadLocalMap 是 ThreadLocal 的静态内部类,它的结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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;
}
}

/**
* The initial capacity -- MUST be a power of two.
*/
private static final int INITIAL_CAPACITY = 16;

/**
* The table, resized as necessary.
* table.length MUST always be a power of two.
*/
private Entry[] table;

/**
* The number of entries in the table.
*/
private int size = 0;

/**
* The next size value at which to resize.
*/
private int threshold; // Default to 0

可以看到ThreadLocalMap有一个常量和三个成员变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* The initial capacity -- MUST be a power of two.
* Map的初始容量
*/
private static final int INITIAL_CAPACITY = 16;

/**
* The table, resized as necessary.
* table.length MUST always be a power of two.
* Entry类型的数组
*/
private Entry[] table;

/**
* The number of entries in the table.
*/
private int size = 0;

/**
* The next size value at which to resize.
*/
private int threshold; // Default to 0

其中 INITIAL_CAPACITY代表这个Map的初始容量;table 是一个Entry 类型的数组,用于存储数据;size 代表表中的存储数目; threshold 代表需要扩容时对应 size 的阈值。

Entry 类是 ThreadLocalMap 的静态内部类,用于存储数据。它的源码如下:

Entry类继承了WeakReference<ThreadLocal<?>>,即每个Entry对象都有一个ThreadLocal的弱引用(作为key),这是为了防止内存泄露。一旦线程结束,key变为一个不可达的对象,这个Entry就可以被GC了。

1
2
3
4
5
6
7
8
9
static class Entry extends WeakReference<ThreadLocal<?>> {
/** The value associated with this ThreadLocal. */
Object value;

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

ThreadLocalMap类有两个构造函数,其中常用的是ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue):

1
2
3
4
5
6
7
8
9
10
11
12
/**
* Construct a new map initially containing (firstKey, firstValue).
* ThreadLocalMaps are constructed lazily, so we only create
* one when we have at least one entry to put in it.
*/
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
table = new Entry[INITIAL_CAPACITY];
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
table[i] = new Entry(firstKey, firstValue);
size = 1;
setThreshold(INITIAL_CAPACITY);
}

构造函数的第一个参数就是本ThreadLocal实例(this),第二个参数就是要保存的线程本地变量。构造函数首先创建一个长度为16的Entry数组,然后计算出firstKey对应的哈希值,然后存储到table中,并设置size和threshold。

注意一个细节,计算hash的时候里面采用了hashCode & (size - 1)的算法,这相当于取模运算hashCode % size的一个更高效的实现(和HashMap中的思路相同)。正是因为这种算法,我们要求size必须是 2的指数,因为这可以使得hash发生冲突的次数减小

我们来看ThreadLocalMap#set方法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Set the value associated with key.
*
* @param key the thread local object
* @param value the value to be set
*/
private void set(ThreadLocal<?> key, Object value) {

// We don't use a fast path as with get() because it is at
// least as common to use set() to create new entries as
// it is to replace existing ones, in which case, a fast
// path would fail more often than not.

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)]) {
ThreadLocal<?> k = e.get();

if (k == key) {
e.value = value;
return;
}

if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}

tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}

如果冲突了,就会通过nextIndex方法再次计算哈希值:

1
2
3
4
5
6
/**
* Increment i modulo len.
*/
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}

到这里,我们看到 ThreadLocalMap 解决冲突的方法是 线性探测法(不断加 1),而不是 HashMap 的 链地址法,这一点也能从 Entry 的结构上推断出来。

总结

每个 Thread 里都含有一个 ThreadLocalMap 的成员变量,这种机制将 ThreadLocal 和线程巧妙地绑定在了一起,即可以保证无用的ThreadLocal被及时回收,不会造成内存泄露,又可以提升性能。假如我们把 ThreadLocalMap 做成一个Map<t extends Thread, ?> 类型的 Map,那么它存储的东西将会非常多(相当于一张全局线程本地变量表),这样的情况下用线性探测法解决哈希冲突的问题效率会非常差。而 JDK 里的这种利用 ThreadLocal 作为 key,再将ThreadLocalMap与线程相绑定的实现,完美地解决了这个问题。

总结一下什么时候无用的 Entry 会被清理:

  • Thread 结束的时候
  • 插入元素时,发现 staled entry,则会进行替换并清理
  • 插入元素时,ThreadLocalMap 的 size 达到 threshold,并且没有任何 staled entries 的时候,会调用 rehash 方法清理并扩容
  • 调用 ThreadLocalMap 的 remove 方法或set(null) 时

尽管不会造成内存泄露,但是可以看到无用的Entry只会在以上四种情况下才会被清理,这就可能导致一些 Entry 虽然无用但还占内存的情况。因此,我们在使用完 ThreadLocal 后一定要remove一下,保证及时回收掉无用的 Entry。

特别地,当应用线程池的时候,由于线程池的线程一般会复用,Thread 不结束,这时候用完更需要 remove 了。

总的来说,对于多线程资源共享的问题,同步机制采用了 以时间换空间 的方式,而 ThreadLocal 则采用了 以空间换时间 的方式。前者仅提供一份变量,让不同的线程排队访问;而后者为每一个线程都提供了一份变量,因此可以同时访问而互不影响。


哈希表-线性探测法和链地址法

哈希表

1、概念

哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。

2、散列存储的基本思路

以数据中每个元素的关键字K为自变量,通过散列函数H(k)计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。

3、哈希表查找的时间复杂度

哈希表存储的是键值对,其查找的时间复杂度与元素数量多少无关,哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的,因此,哈希表查找的时间复杂度为O(1)

常用哈希函数

1.直接寻址法

取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,知道找到H(Key)的位置没有值了就把元素放进去.

2.数字分析法

分析一组数据,比如一组员工的出生年月,这时我们发现出生年月的前几位数字一般都相同,因此,出现冲突的概率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果利用后面的几位数字来构造散列地址,则冲突的几率则会明显降低.因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址.

3.平方取中法

取关键字平方后的中间几位作为散列地址.一个数的平方值的中间几位和数的每一位都有关。因此,有平方取中法得到的哈希地址同关键字的每一位都有关,是的哈希地址具有较好的分散性。该方法适用于关键字中的每一位取值都不够分散或者较分散的位数小于哈希地址所需要的位数的情况。

4.折叠法

折叠法即将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址.数位叠加可以有移位叠加和间界叠加两种方法.移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加.

5.随机数法

选择一个随机数,去关键字的随机值作为散列地址,通常用于关键字长度不同的场合.

6.除留余数法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选得不好,则很容易产生冲突。一般p取值为表的长度tableSize。

哈希冲突的处理方法

1、开放定址法——线性探测

线性探测法的地址增量di = 1, 2, … , m-1,其中,i为探测次数。该方法一次探测下一个地址,知道有空的地址后插入,若整个空间都找不到空余的地址,则产生溢出。

线性探测容易产生“聚集”现象。当表中的第i、i+1、i+2的位置上已经存储某些关键字,则下一次哈希地址为i、i+1、i+2、i+3的关键字都将企图填入到i+3的位置上,这种多个哈希地址不同的关键字争夺同一个后继哈希地址的现象称为“聚集”。聚集对查找效率有很大影响。

2、开放地址法——二次探测

二次探测法的地址增量序列为 di =1^2, -1^2, 2^2, -2^2,… , q2, -q2(q <= m/2)。二次探测能有效避免“聚集”现象,但是不能够探测到哈希表上所有的存储单元,但是至少能够探测到一半。

3、链地址法(HashMap中用到的方法)

链地址法也成为拉链法。其基本思路是:将所有具有相同哈希地址的而不同关键字的数据元素连接到同一个单链表中。如果选定的哈希表长度为m,则可将哈希表定义为一个有m个头指针组成的指针数组T[0..m-1],凡是哈希地址为i的数据元素,均以节点的形式插入到T[i]为头指针的单链表中。并且新的元素插入到链表的前端,这不仅因为方便,还因为经常发生这样的事实:新近插入的元素最优可能不久又被访问。

坚持原创技术分享,您的支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------