一 点睛

在大学严蔚敏版数据结构中，提到过哈希线探测法，当时觉得很神奇，当然学的也都是一些理论，今天在看 ThreadLocalMap 源码时，终于找到了实际的应用。

Hash 冲突的解决是 Map 中的一个重要内容。我们以 Hash 冲突的解决为线索，来研究一下 ThreadLocalMap 的核心源码。

二 ThreadLoca的 set() 方法入手分析

/**
* 设置当前线程绑定的局部变量
* @param value 将药保存在当下线程对应的 ThreadLocal 的值
* 1 首先获得当前线程，并根据当前线程获取一个 map
* 2 如果获取 map 不为空，则将参数设置到 map 中（当前 ThreadLocal 的引用作为 key）
* 3 如果 Map 为空，则给该线程创建 map，然后将参数设置到 map 中
*/
public void set(T value) {
    // 获取当前线程对象
    Thread t = Thread.currentThread();
    // 获取此此案吃对象中维护的 ThreadLocalMap 对象
    ThreadLocalMap map = getMap(t);
    // 判断 map 是否存在
    if (map != null)
        // 存在，则设置实体 entry
        map.set(this, value);  // 这个方法要重点分析
    else
        // 1 当前线程不存在 ThreadLocalMap 对象
        // 2 调用 createMap 进行 ThreadLocalMap 对象的初始化
        // 3 并将 t （当前线程）和 value （t对应的值）作为第一个 entry 存放到 ThreadLocalMap 中
        createMap(t, value); // 这个方法要重点分析
}

/**
* 获取当前线程对应维护的 ThreadLocalMap
*
* @param  t 当前线程
* @return 对应维护的 ThreadLocalMap
*/
ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
}

/**
* 创建当前线程对应维护的 ThreadLocalMap
* InheritableThreadLocal.
*
* @param t 当前线程
* @param 创建map，并存放在 map 中第一个entry 的值
*/
void createMap(Thread t, T firstValue) {
    // this 是调用此方法的 threadLocal
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}

这个方法的作用是设置当前线程绑定的局部变量。

其中有两个方法我们要重点分析。

private void set(ThreadLocal<?> key, Object value)
void createMap(Thread t, T firstValue){
    t.threadLocals = new ThreadLocalMap(this, firstValue);
}

三 分析构造方法 ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue)

/**
* firstKey：ThreadLocal 实例（this）
* firstValue：要保存的线程本地变量
*/
ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
    // 初始化 table，大小为 16
    table = new Entry[INITIAL_CAPACITY];
    // 计算索引，这行代码要重点分析
    int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
    // 设置值
    table[i] = new Entry(firstKey, firstValue);
    size = 1;
    // 设置阀值
    setThreshold(INITIAL_CAPACITY);
}

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

1 关于 firstKey.threadLocalHashCode

private final int threadLocalHashCode = nextHashCode();

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

// AtomicInteger 是一个提供原子操作的 Integer 类，通过线程安全的方式操作加减，适合高并发情况下的使用
private static AtomicInteger nextHashCode = new AtomicInteger();

// 特殊的 hash 值
private static final int HASH_INCREMENT = 0x61c88647;

这里定义了一个 AtomicInteger 类型，每次获取当前值并加上 HASH_INCREMENT，HASH_INCREMENT = 0x61c88647，这个值跟斐波那契数列（黄金分割数）有关，其主要目的就是为了让哈希码能均匀的分布在2的n次方的数组中，也就是 Entry[] table 中，这样可以尽量避免 hash 冲突

2 关于 & (INITIAL_CAPACITY - 1)

计算 hash 的时候采用了 hashCode & （size-1）的算法，这相对于取模运算 hash % size 的一个更高效的实现。正是因为这种算法，我们要求 size 必须是 2 的整次方，这也能保证在索引不越界的前提下，使得 hash 发生冲突的次数减小。

四 ThreadLocalMap 中的 set 方法

private void set(ThreadLocal<?> key, Object value) {
    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)]) { // 这个循环体现了线性探索的思想，在一个 size 元素的环形数组中，一个元素一个元素的探测
        ThreadLocal<?> k = e.get();

        // ThreadLocal 对应的 key 存在，直接覆盖之前的值
        if (k == key) {
            e.value = value;
            return;
        }

        // key 为 null，但是值不为 null，说明之前的 ThreadLocal 对象已经被回收了，当前数组中的 Entry 是一个陈旧（stable）的元素
        if (k == null) {
            // 用新元素替换陈旧的元素，这个方法进行了不少垃圾清理动作，防止内存泄漏
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    // ThreadLocal 对应的 key 不存在并且没有找到陈旧的元素，则在空元素的位置创建一个新的 Entry
    tab[i] = new Entry(key, value);
    int sz = ++size;
    // cleanSomeSlots 用于清理那些 e.get == null 的元素，这种数据 key 关联的对象已经被回收，所以 tab[staleSlot].value 可以被设置为 null
    // 如果没有清除任何 entry，并且当前使用量达到负载因子所定义的（2/3），那么就进行一次 rehash（执行一次全表扫描清理工作）
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}

//  让 tab 变成了环形数组，获取环形数组的下一个索引
private static int nextIndex(int i, int len) {
    return ((i + 1 < len) ? i + 1 : 0);
}

代码执行流程：

1 首先还是根据 key 计算出索引 i，然后查找 i 位置商的 Entry。

2 若是 Entry 已经存在并且 key 等于传入的 key，那么这个时候就给这个 Entry 赋新的 value 值。

3 若是 Entry 存在，但是 key 为 null，则调用 replaceStablEntry 来更换这个 key 为空的 Entry。

4 不断循环检测，直到探测到一个可 set 的位置，经过一轮的循环，如果还是没有找到，那么就在这个 null 的位置新建一个 Entry，并且插入，同时 size 增加1。

5 最后调用 cleanSomeSlots，清理 key 为 null 的Entry，最后返回是否清理了 Entry，最后判断 sz 是否达到了 阈值，达到的话就调用 rehash 函数执行一次全表扫描清理。

五 线下探测的核心思想

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

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

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