ThreadLocal的散列算法

2021.03.01 15:03 411
阅读约 1 分钟

ThreadLocal原理篇已经进行过简单介绍,在创建ThreadLocal对象后尝试设置变量副本时,会先判断当前线程的threadLocalMap是否为空,否则进行初始化操作。

观察下面ThreadLocal源码:

/**
     ThreadLocals依赖于每个线程(Thread.threadLocals和* InheritableThreadLocals)
     附加的每个线程的线性探针哈希映射。 ThreadLocal对象充当键,*通过threadLocalHashCode搜索。
     这是一个自定义哈希码*(仅在ThreadLocalMaps中有用),在相同的线程使用连续构造的
     ThreadLocals *的情况下,消除了冲突。
**/
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);
 }

可以看到,其中定义了一个魔法值HASH_INCREMENT = 0x61c88647,对于实例变量threadLocalHashCode,每当创建一个新的实例时,会调用nextHashCode()生成一个新值,该值是对nextHashCode的累加。

那么0x61c88647有什么用呢?

ThreadLocalMap 的散列

先看一下 ThreadLocalMap 中的 set 方法

private void set(ThreadLocal<?> key, Object value) {
    Entry[] tab = table;
    int len = tab.length;    
    int i = key.threadLocalHashCode & (len-1);
    ...
}

ThreadLocalMap中 table 的大小必须是2的N次方,那len-1的二进制表示的是低位连续的N个1,那key.threadLocalHashCode & (len-1)就是threadLocalHashCode的低 N 位。

验证一下是否可以均匀散列

public class MagicHashCode {
    private static final int HASH_INCREMENT = 0x61c88647;
    public static void main(String[] args) {
        hashCode(16); 

    }    
    private static void hashCode(Integer length){
        int hashCode = 0;
        for(int i=0; i< length; i++){
            hashCode = i * HASH_INCREMENT+HASH_INCREMENT;//每次递增HASH_INCREMENT
            System.out.print(hashCode & (length-1));
            System.out.print(" ");
        }
        System.out.println();
    }
}

结果

7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 0 

那么0x61c88647是一个什么数字呢?查阅之后发现其与(Math.sqrt(5)-1)/2有关。也就是黄金分割点0.618…,即0x61c88647= = 2^32*黄金分割点

至于为什么黄金分割点可以均匀散列,涉及到相关数学问题,此处不做更多解释。

多个实例的情况

将ThreadLocal设置为类的私有静态变量是一种推荐的做法

private static ThreadLocal<T> = new ThreadLocal<>();

此时,对ThreadLocalMapset操作的Key永远是同一个ThreadLocal实例对象,因此也不会有哈希冲突的问题。

    public void set(T value) {
        Thread t = Thread.currentThread();
        ThreadLocalMap map = getMap(t);
        if (map != null)
        // this 就是当前的ThreadLocal对象,同一个线程this是同一个
            map.set(this, value);
        else
            createMap(t, value);
    }
    ThreadLocalMap getMap(Thread t) {
        return t.threadLocals;
    }
    
    
    // threadLocalMap中方法
     private void set(ThreadLocal<?> key, Object value) {
            Entry[] tab = table;
            int len = tab.length;
            int i = key.threadLocalHashCode & (len-1);
            ...
    }

但是,我们要讨论的是同一线程多个ThreadLocal对象的写操作。前面我们已经介绍过ThreadLocal的散列算法是通过一个黄金分割数来实现的,每当一个实例被创建时,threadLocalHashCode的值都会加上0x61c88647

假设我们有五个对象,这五个对象共享该线程下ThreadLocalMap,Map初始容量为16,那么,与之前的验证方法逻辑类似,五个对象的实例变量threadLocalHashCode被分别叠加了0—4次。

ThreadLocal<Integer> t1 = new ThreadLocalMap<>();
ThreadLocal<Integer> t2 = new ThreadLocalMap<>();  
ThreadLocal<Integer> t3 = new ThreadLocalMap<>();  
ThreadLocal<Integer> t4 = new ThreadLocalMap<>();  
ThreadLocal<Integer> t5 = new ThreadLocalMap<>();  

因此当我们调用任意对象的set方法int i = key.threadLocalHashCode & (len-1);所计算出来的索引i都是均匀分布的,一般来说我们不会创建大量的ThreadLocal实例,也就是说哈希冲突的可能性几乎是微乎其微的,即使出现哈希冲突,也会使用开放寻址法寻找下一个可以插入的位置。

 

字数:267 发布于 7 个月前
Copyright 2018-2021 Siques