大话 ThreadLocal

概述

• ThreadLocal 介绍
• ThreadLocal 关键方法讲解
• ThreadLocalMap 内部类介绍
• ThreadLocalMap 算法讲解
• ThreadLocalMap 实现点讲解

ThreadLocal

该类提供了线程本地变量。该变量不同于普通的副本，因为访问这个变量（通过 get 或 set 方法）的每个线程都是自己独立初始化该变量的。

ThreadLocal实例通常是Thread类中典型的静态私有属性，由于关联线程的状态（比如，user ID 或 Transaction ID）

每个线程都持有其局部变量副本的隐式引用（即，每个线程都持有一个该变量的副本，因此，每个线程间的变量是独立的），在其整个生命周期中，只要该引用可访问。一旦线程消亡，它的所有局部变量都会被GC（除非存在其他对该副本的引用）

ThreadLocal 关键方法

initialValue

protected T initialValue() {
    return null;
}

返回当前线程局部变量的初始化值。这个方法将在 get 方法第一次调用时被调用，除非线程再次之前调用了 set 方法，那么该方法将不会被调用。通常，该方法只会被调用一次，但如果在后续的操作中，在调用了remove方法后调用get方法，那么该方法（initialValue）将会被调用多次（因为，此时线程的局部变量需要重新被初始化）。

也就是说，该方法主要就是用于初始化线程的局部变量的，如果变量已经通过其他方式初始化了（如，set方法），那么该方法就不会被调用。

get

public T get() {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        ThreadLocalMap.Entry e = map.getEntry(this);
        if (e != null) {
            @SuppressWarnings("unchecked")
            T result = (T)e.value;
            return result;
        }
    }
    return setInitialValue();
}

返回当前线程该局部变量的值。如果当前线程该变量不存在，那么会调用“initialValue”方法进行变量的初始化，并返回初始化后该变量的值。

set

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null)
        map.set(this, value);
    else
        createMap(t, value);
}

将当前线程的局部变量设置为指定的值。大部分的子类无需重写该方法，只需要重写“initialValue”方法来设置局部变量的值。

remove

public void remove() {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if (m != null)
        m.remove(this);
}

删除当前线程该局部变量值。如果当前线程在后续又调用了 get 方法，那么该局部变量的值会通过调用“initialValue”方法被重新初始化，除非再次期间“set”方法被调用了。这就是导致“initialValue”方法在当前线程中被调用多次的原因。

ThreadLocalMap 内部类

ThreadLocalMap 是一个自定义的 hash map，它仅适用于维护线程的局部变量。该类的所有操作都没有暴露在 ThreadLocal 类之外。为了帮助大对象和长生命周期对象的使用，ThreadLocalMap 的 Key 使用 WeakReferences 类型。然后，因为不使用引用队列，那么仅保证在 hash map 表空间不足的情况下，才会将无用的对象（stale entries）从 map 中移除。

ThreadLocalMap 是一个“懒”构造（即，延迟构造）。它会在至少有一个 Entry 需要被输入时，才会进行构造。

ThreadLocalMap 的 Key 是WeakReference 的子类

ThreadLocalMap 是使用一个 Entry 类来表示一个线程局部变量（Key）和这个变量的值（Value）。 其中 Key 是 WeakReference 的子类，而 WeakReference 所维护的引用通常就是 ThreadLocal。

注意：当 Entry#get() 返回 null 的时候，说明对应的 key 不存在了，即，这个对象已不再被任何对象引用了。因此，该 Entry 能被从当前的 hash map 中清除。这样的对象下 ThreadLocalMap 的操作中称为“stale entries”

WeakReference

WeakReference 是Java引用类型的一种。用来描述非必须的对象，被弱引用关联的对象只能生存到下一次垃圾收集发生之前。当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。

ThreadLocalMap 其中涉及的 Hash 算法

理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。

因此，一个 Hash 算法主要有2个部分：Hash函数、解决碰撞的方法

ThreadLocalMap 使用的 Hash 函数是“斐波那契（Fibonacci）哈希法”；而解决碰撞的方法是“线性探测法”

斐波那契（Fibonacci）哈希法

在说“斐波那契（Fibonacci）哈希法”前，我们先来说说“乘法哈希法”

• 乘法哈希法 公式：hash(key) = floor( M/W * ( a * key mod W) ) 其中 floor 表示对表达式进行下取整

注意：

1. 通常设置 M 为 2 的幂次方。
2. W 为计算机字长大小（也为2的幂次方）。
3. a 为一个非常接近于W的数。

其实，“乘法哈希”的思想就是：提取关键字 key 中间 k 位数字。

• 斐波那契（Fibonacci）哈希法 而斐波那契（Fibonacci）哈希法就是当 “乘法哈希法” 的 a ≈ W/φ，1/φ ≈ (√5-1)/2 = 0.618 033 988 时情况。而，1/φ ≈ (√5-1)/2 = 0.618 033 988，可称为黄金分割点。

Q：那，为什么“斐波那契（Fibonacci）哈希法”能够更好的将关键字 key 进行散列了? A：Why is 'a ≈ W/φ' special? It has to do with what happens to consecutive keys when they are hashed using the multiplicative method. As shown in Figure ‘Fibonacci Hashing’ , consecutive keys are spread out quite nicely. In fact, when we use 'a ≈ W/φ' to hash consecutive keys, the hash value for each subsequent key falls in between the two widest spaced hash values already computed. Furthermore, it is a property of the golden ratio, φ , that each subsequent hash value divides the interval into which it falls according to the golden ratio!undefined

线性探测法（linear probing）

• “开放地址”哈希表 实现哈希表的另一种方式就是用大小为 M 的数组保存 N 个键值对，其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表
• 线性探测法（“开放地址”哈希表的一种实现方式） 开放地址哈希表中最简单的方法叫做“线性探测”法：当碰撞发生时（当一个键的Hash值已经被另一个不同的键占用），我们直接检测哈希表中的下一个位置（将索引值加 1）。这样的线性探测可能会产生三种结果： a）命中，该位置的键和被查找的键相同； b）未命中，键为空（该位置没有键） c）继续查找，该位置的键和被查找的键不同。 我们用Hash函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。如果不同则继续查找（将索引增大，到达数组结尾时折回数组的开头），直到找到该键或者遇到一个空元素。 我们习惯将检查一个数组位置是否含有被查找的键的操作称作探测。在这里它可以等价于我们一直使用的比较，不过有些探测实际上是在测试键是否为空。
• 核心思想 “开放地址”哈希表的核心思想是与其将内存用于链表，不如将它们作为哈希表的空元素。这些空元素可以作为查找结束的标志。
• 删除操作 如何从基于线性探测的哈希表中删除一个键？仔细想一想，你会发现直接将该键所在的位置设为null是不行的，因为这会使得在此位置之后的元素无法被查找。 因此，我们需要将簇中被删除键的右侧的所有键重新插入哈希表。
• 键簇 线性探测的平均成本取决于元素在插入数组后聚集成的一组连续的条目，也叫做键簇。 如图?所示，例如，在示例中插入键 C 会产生一个长度为 3 的键簇（ A C S ）。这意味着插入 H 需要探测 4 次，因为 H 的Hash值为该键簇的第一个位置。

显然，短小的键簇才能保证较高的效率。随着插入的键越来越多，这个要求很难满足，较长的键簇也会越来越多。另外因为（基于均匀性假设）数组的每个位置都有相同的可能性被插入一个新键，长键簇被选中的可能被短键簇更大，同时因为新键的Hash值无论落在簇中的任何位置都会使簇的长度加 1（甚至更多，如果这个簇和相邻的簇之间只有一个空元素相隔的话）

• 线性探测法的性能分析 开放地址哈希表的性能依赖于 α = N/M 的比值。我们将 α 称为哈希表的使用率。对于基于拉链法的哈希表，α 是每条拉链表的长度，因此一般大于 1 ；对于基于线性探测的哈希表，α 是表中已被占用的空间的比例，它是不可能大于 1 的。事实上，在 LinearProbingHashST 中我们不允许 α 达到 1 （列表被占满），因为此时未命中的查找会导致无限循环（因为，在元素不存在的情况下，空元素作为查找结束的标志）。为了保证性能，我们会动态调整数组的大小来保证使用率在 1/8 到 1/2 之间。

假设J（均匀哈希假设）。我们使用的Hash函数能够均匀并独立地将所有的键散布于 0 到 M-1 之间。 讨论。我们在实现Hash函数时随意指定了很多参数，这显然无法实现一个能够在数学意义上均匀并独立地散布所有键的Hash函数。事实上，深入的理论研究报告告诉我们想要找到一个计算简单但又拥有一致性和均匀性的Hash函数是不太可能的。在实际应用中，和使用 Math.random() 生成随机数一样，大多数程序员都会满足于随机数生成器类的Hash函数。很少人会去检验独立性，而这个性质一般都不会满足。

命题 M ：在一张大小为 M 并含有 N = α * M 个键的基于线性探测的哈希表中，基于假设 J ，命中和未命中的查找所需的探测次数分别为：

特别是当 α 约为 1/2 时，查找命中所需要的探测次数约为 3/2，未命中所需要的约为 5/2。当 α 趋于 1 时，这些估计值的精确度会下降，但不需要担心这些情况，因为我们会保证哈希表的使用率小于 1/2。

当哈希表快满的时候查找所需的探测次数是巨大的（α 越趋近于1，由公式可知探测的次数也越来越大），但当使用率 α 小于 1/2 时探测的预计次数只在 1.5 到 2.5 之间。

ThreadLocalMap 实现点讲解

其中，ThreadLocalMap 会在 get()、set() —— 添加或修改 操作对表中的失效元素进行清除。

• get方法会清除，发现的第一个 key为null（即，entry != null && null == entry.get()）的slot 到 遇到的第一个 entry 为null 之间的所有entry。
• 而set方法，发现 key 对应的 slot 非空，且 nextIndex 的slot发现了失效entry（即，hash(key)'entry != null && hash(nextIndex)’entry != null && null == nextIndex_entry.get() ）时会清除 key slot所在的整个键簇上的失效的entry。这是因为，key 本应该待的索引位置已经被其他entry占用了，这个被占用的entry可能不属于该位置。而根据“线性探测法”，key 真是的 slot >= hash(key)，这个占用目标 key 位置的 entry 可能它本身的位置在更前面（但肯定是在这个簇族的范围内），而这个’侵占者’的真是slot上的entry可能也失效了，这样的话应该让’侵占者’回到它的位置，而将其侵占的位置还出。 而这么做的目的，是为了避免簇族的长度持续的增长。

ThreadLocalMap 会在“添加”操作中，判断是否需要对表进行“扩张”（resize()操作），其中 α = 1/2；但，不会在remove操作对表进行“缩减”

当执行“添加"操作后，hash map 元素（可能包括“失效”还未清除的元素）的长度超过表长度的 2/3 时，就会触发 rehash()操作。而rehash()操作，则会先对这个 hash map 中的失效元素进行清除，若清除后hash map中元素个数，依旧大等于表长度的 1/2 （size >= threshold - threshold / 4，即，size >= tab.length/2），则进行 hash map resize操作，将表长度扩大为原先的 2 倍。并将所有有效元素，重新插入扩建后的 hash map中。

null == entry 以及 null != entry && null == entry.get() 的含义

• null == entry：表示给位置没有对象
• null != entry && null == entry.get() ：表示该位置有对象，但对象已经失效了，即，该对象除了被entry引用外，不再被其他可达性对象引用，并且还说明，这个对象已经被垃圾收集器回收了。因为这里的 entry.get() 实际上就是调用 WeakReference#get() 方法。

ThreadLocal 与 Thread 之间的关系

• 一个 thread 可以有多个 ThreadLocal 对象。一个 ThreadLocal 对象维护了一个线程本地变量。
• 每个 Thread 对象通过 threadLocals 属性来维护它的 ThreadLocals（ThreadLocal.ThreadLocalMap threadLocals）