前景知识
学习知识只有存在一定理论知识背景下才会事半功倍，在了解ThreadLocalMap我们需要了解如下知识点。
黄金分割数与斐波那契数列
首先复习一下斐波那契数列，下面的推导过程来自某搜索引擎的wiki：
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
通项公式：假设F(n)为该数列的第n项（n ∈ N*），那么这句话可以写成如下形式：F(n) = F(n-1) + F(n-2)。
有趣的是，这样一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，前一项与后一项的比值越来越逼近0.618（或者说后一项与前一项的比值小数部分越来越逼近0.618），而这个值0.618就被称为黄金分割数。证明过程如下：
image
黄金分割数的准确值为(根号5 - 1)/2，约等于0.618。
三. 黄金分割数的应用
黄金分割数被广泛使用在美术、摄影等艺术领域，因为它具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值，能够激发人的美感。当然，这些不是本文研究的方向，我们先尝试求出无符号整型和带符号整型的黄金分割数的具体值：
public static void main(String[] args) throws Exception {
//黄金分割数 * 2的32次方 = 2654435769 - 这个是无符号32位整数的黄金分割数对应的那个值
long c = (long) ((1L << 32) * (Math.sqrt(5) - 1) / 2);
System.out.println(c);
//强制转换为带符号为的32位整型，值为-1640531527
int i = (int) c;
System.out.println(i);
}
通过一个线段图理解一下：
image
也就是2654435769为32位无符号整数的黄金分割值，而-1640531527就是32位带符号整数的黄金分割值。而ThreadLocal中的哈希魔数正是1640531527(十六进制为0x61c88647)。为什么要使用0x61c88647作为哈希魔数？这里提前说一下ThreadLocal在ThreadLocalMap(ThreadLocal在ThreadLocalMap以Key的形式存在)中的哈希求Key下标的规则：
哈希算法：keyIndex = ((i + 1) * HASH_INCREMENT) & (length - 1)
其中，i为ThreadLocal实例的个数，这里的HASH_INCREMENT就是哈希魔数0x61c88647，length为ThreadLocalMap中可容纳的Entry(K-V结构)的个数(或者称为容量)。在ThreadLocal中的内部类ThreadLocalMap的初始化容量为16，扩容后总是2的幂次方，因此我们可以写个Demo模拟整个哈希的过程：
public class Main {
private static final int HASH_INCREMENT = 0x61c88647;
public static void main(String[] args) throws Exception {
hashCode(4);
hashCode(16);
hashCode(32);
}
private static void hashCode(int capacity) throws Exception {
int keyIndex;
for (int i = 0; i < capacity; i++) {
keyIndex = ((i + 1) * HASH_INCREMENT) & (capacity - 1);
System.out.print(keyIndex);
System.out.print(" ");
}
System.out.println();
}
}
上面的例子中，我们分别模拟了ThreadLocalMap容量为4,16,32的情况下，不触发扩容，并且分别”放入”4,16,32个元素到容器中，输出结果如下：
3 2 1 0
7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 0
7 14 21 28 3 10 17 24 31 6 13 20 27 2 9 16 23 30 5 12 19 26 1 8 15 22 29 4 11 18 25 0
每组的元素经过散列算法后恰好填充满了整个容器，也就是实现了完美散列。实际上，这个并不是偶然，其实整个哈希算法可以转换为多项式证明：证明(x - y) * HASH_INCREMENT != 2^n * (n m)，在x != y，n != m，HASH_INCREMENT为奇数的情况下恒成立，具体证明可以自行完成。HASH_INCREMENT赋值为0x61c88647的API文档注释如下：
连续生成的哈希码之间的差异(增量值)，将隐式顺序线程本地id转换为几乎最佳分布的乘法哈希值，这些不同的哈希值最终生成一个2的幂次方的哈希表。
WeakReference
弱引用是使用WeakReference创建的引用，弱引用也是用来描述非必需对象的，它是比软引用更弱的引用类型。在发生GC时，如果一个对象仅仅只被弱引用引用，不管系统堆空间是否足够，都会将对象进行回收。
弱引用对应的类为WeakReference，举个栗子：
String s = new String("Frank");
WeakReference<String> weakRef = new WeakReference<String>(s);
s = null;
这里我们把s设置为null后，字符串对象便只有弱引用指向它。
Hash表数据结构
散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”，散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置
image
再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢？我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。
这里重点我们看下开放寻址法（open addressing）逻辑
插入元素
当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
image
从图中可以看出，散列表的大小为 10，在元素 x 插入散列表之前，已经 6 个元素插入到散列表中。x 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。于是我们就顺序地往后一个一个找，看有没有空闲的位置，遍历到尾部都没有找到空闲的位置，于是我们再从表头开始找，直到找到空闲位置 2，于是将其插入到这个位置。
查找元素
在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中
为什么遍历到空位置就表示不存在？
因为插入元素时发生散列冲突，会找到数组一个空位置就插入了。如果查找时遍历到一个空位置还没有找到则说明要查找的元素并没有在散列表中
image
删除元素
在散列表中删除元素有些特殊，首先我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素。如果相等。此时我们如果仅仅只是删除元素对于删除元素来说是没有问题。但会影响查询元素。
在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。
解决思路
- 1 我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
image
- 2 从数组中删除该元素，同时继续向后探测，将散列冲突的元素填入删除元素的位置。参考ThreadLocalMap
网友评论