深入解析ThreadLocalMap的开放地址法实现

84 - 这篇文章属于一个选集。

背景
#

在前面的博客中，我们介绍了ThreadLocal的实现原理，其中最核心的部分就是ThreadLocalMap这个数据结构。我们都知道HashMap是使用红黑树或者链表来解决哈希冲突的，那么ThreadLocalMap底层又是如何处理冲突的呢？

ThreadLocalMap的构造
#

ThreadLocalMap内部实际上也是使用Entry数组来存储数据，这点与HashMap类似。但在处理哈希冲突时，ThreadLocalMap采用了完全不同的策略——开放地址法（Open Addressing）。

什么是开放地址法？
#

开放地址法的核心思想是：当发生哈希冲突时（即目标槽位i已被占用），不是像HashMap那样使用链表或红黑树，而是顺序查找下一个可用的槽位（i+1, i+2,…），直到找到一个空槽位为止。

这种方法在哈希冲突严重时性能会下降，但ThreadLocal通过两个巧妙的设计来减少冲突：

使用AtomicInteger在类加载时就生成唯一的hashCode
采用斐波那契散列乘数（0x61c88647）来均匀分布哈希值

斐波那契散列的魔力
#

让我们通过一个示例代码来展示这种哈希算法的精妙之处：

import java.util.concurrent.atomic.AtomicInteger;  
  
public class OpenAddressHashDemo {  
    // 哈希表大小（必须为2的幂）  
    private static final int TABLE_SIZE = 16;  
  
    // 哈希增量（黄金分割数）  
    private static final int HASH_INCREMENT = 0x61c88647;  
  
    // 哈希码生成器（类似ThreadLocal的机制）  
    private static AtomicInteger nextHashCode = new AtomicInteger(0);  
  
    // 生成下一个哈希码  
    private static int nextHashCode() {  
        return nextHashCode.getAndAdd(HASH_INCREMENT);  
    }  
  
    // 计算初始索引  
    private static int getIndex(int hashCode) {  
        return hashCode & (TABLE_SIZE - 1); // 等价于 hashCode % TABLE_SIZE  
    }  
  
    // 开放地址法插入（线性探测）  
    public static void insert(int[] table, int hashCode) {  
        int index = getIndex(hashCode);  
        while (true) {  
            if (table[index] == 0) { // 空槽  
                table[index] = hashCode;  
                System.out.println("哈希码 " + hashCode + " 插入到索引 " + index);  
                return;  
            } else {  
                System.out.println("哈希码 " + hashCode + " 在索引 " + index + " 发生碰撞，探测下一个位置");  
                index = (index + 1) & (TABLE_SIZE - 1); // 线性探测（循环）  
            }  
        }  
    }  
  
    public static void main(String[] args) {  
        int[] table = new int[TABLE_SIZE]; // 哈希表初始化为0  
  
        // 生成并插入多个哈希码  
        for (int i = 0; i < 10; i++) { // 负载因子 10/16 = 0.625  
            int hashCode = nextHashCode();  
            insert(table, hashCode);  
        }  
  
        // 打印最终哈希表状态  
        System.out.println("\n最终哈希表内容：");  
        for (int j = 0; j < TABLE_SIZE; j++) {  
            System.out.println("索引 " + j + ": " + (table[j] != 0 ? table[j] : "空"));  
        }  
    }  
}

运行结果令人惊叹：

哈希码 0 插入到索引 0  
哈希码 1640531527 插入到索引 7  
哈希码 -1013904242 插入到索引 14  
哈希码 626627285 插入到索引 5  
哈希码 -2027808484 插入到索引 12  
哈希码 -387276957 插入到索引 3  
哈希码 1253254570 插入到索引 10  
哈希码 -1401181199 插入到索引 1  
哈希码 239350328 插入到索引 8  
哈希码 1879881855 插入到索引 15  
  
最终哈希表内容：  
索引 0: 空  
索引 1: -1401181199  
索引 2: 空  
索引 3: -387276957  
索引 4: 空  
索引 5: 626627285  
索引 6: 空  
索引 7: 1640531527  
索引 8: 239350328  
索引 9: 空  
索引 10: 1253254570  
索引 11: 空  
索引 12: -2027808484  
索引 13: 空  
索引 14: -1013904242  
索引 15: 1879881855

10个值插入到16个槽位的哈希表中，竟然没有发生任何哈希冲突！这就是斐波那契散列乘数的神奇之处。