ThreadLocalMap中hash冲突的解决_threadlocal解决hash冲突

1. ThreadLocal的set方法

作用是设置当前线程绑定的局部变量：

1. 首先是获取当前线程，并根据当前线程获取一个Map。
2. 如果获取的Map不为空，则将参数设置到Map中（当前ThreadLocal的引用作为key）。这里调用了ThreadLocalMap的set方法。
3. 如果Map为空，则给线程创建Map，并设置初始值。这里调用了ThreadLocalMap的构造方法。

2. ThreadLocalMap的构造方法

ThreadLocalMap（ThreadLocal<?> firstKey, Object firstValue）

构造函数首先创建一个长度为16的Entry数组，然后计算出firstKey对应的索引，存储到table中，并设置size和threshold。

int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1)

2.1 &前表达式

private final int threadLocalHashCode = nextHashCode();

private static int nextHashCode(){
	return nextHashCode.getAndAdd(HASH_INCREMENT);
}

// AtomicIntger是一个提供原子操作的Intger类，通过线程安全的方式操作加减，适合高并发情况下的使用
private static AtomicIntger nextHashCode = new AtomicInteger();
// 特殊的hash值
private static final int HASH_INCREMENT = 0x61c88647;
1
2
3
4
5
6
7
8
9
10

这里定义了一个AtomicInteger类型，每次获取当前值并加上HASH_INCREMENT， HASH_INCREMENT = 0x61c88647。

这个值跟斐波那契数列（黄金分割数）有关，其主要目的是为了让哈希码能均匀的分布在2的次方的数组里，也就是Entry[] table中，这样做可以尽量避免hash冲突。

2.2 &后表达式

计算hash的时候里面采用了hashCode & (size - 1)的算法，这相当于取模运算hashCode % size的一个更高效的实现。

正是因为这种算法，我们要求size必须是2的整次幂，这也能保证索引在不越界的前提下，使得hash发生冲突的次数减小。

3. ThreadLocalMap中的set方法

代码执行流程：

1. 首先还是根据key计算出索引i，然后查找位置上的Entry。
2. 若是Entry已经存在并且key等于传入的key，那么这时候直接给这个Entry赋新的value值。
3. 若是Entry存在，但是key为null，则调用replaceStaleEntry来更换这个key为空的Entry。
4. 不断循环检测，直到遇到为null的地方，这时候要是还没在循环过程中return，那么就在这个null的位置新建一个Entry，并且插入，同时size增加1。

最后调用cleanSomeSlots, 清理key为null的Entry，最后返回是否清理了Entry。

接下来再判断sz是否>=threshold达到了rehash的条件，达到的话就会调用rehash函数执行一次全表的扫描清理。

4. 使用线性探测法来解决哈希冲突

该方法一次探测下一个地址，直到有空的地址后插入，若整个空间都找不到空余的地址，则产生溢出。

举个例子，假设当前table的长度为16，也就是说如果计算出来key的hash值为14，如果table[14]上已经有值，并且其key与当前key不一致，那么就发生了hash冲突，这个时候将14加1得到15，取table[15]进行判断，这个时候如果还是冲突会回到0，取table[0],以此类推，直到可以插入。

按照上面的描述，可以把Entry[] table看成一个环形数组。

参考资料：ThreadLocalMap中hash冲突的解决