散列与哈希算法

1.斐波那契散列

ThreadLocal散列算法

• ThreadLocalMap底层采用数组存储每个变量副本，并对ThreadLocal采用斐波那契散列计算元素存储的数组地址，产生碰撞时采用开放寻址法+1向后寻址。

• 斐波那契数列是描述黄金分割法则的最经典表达式，因为当n趋于无穷大时，前一项与后一项比值的极限如果存在，那么它就等于(根号5 - 1)/2，约等于0.618

• 在平方散列中，不再是利用value待散列值作为乘数，而是利用黄金分割法则生成，就得到了斐波那契散列中的哈希魔数:

  位数	散列乘方值
  16	0.618*2^16=40503
  32	0.618*2^32=2654435769

• 对于32位整数，最终得到的斐波那契散列公式如下：index = (value * 2654435769) >> 28 。其中右移28位相当于保留高4位，无特别意义。当然这里右移操作也可以改成取余计算&(length-1)，其中length表示ThreadLocal的容量大小。

🚀抽奖场景应用

在抽奖场景中，使用斐波那契散列生成随机数：

int hashcode = val * 0x61c88647 + 0x61c88647;
return hashcode&(128-1);

• 这里还进行一轮加法运算，目的是增加多种运算法则，既有乘法又有加法，从而散列更充分。
• 选择大于100的最近2的幂次方数进行与运算，实际上与取余运算等价，目的是为了提高运算效率。

2.HashMap散列

扰动函数

哈希索引下标计算：

①首先根据key.hashCode()计算得到一个哈希值。

②经过扰动函数进行均匀散列，减少碰撞。具体来说，取哈希值的高16位与原哈希值进行异或操作。从而增加低位的随机性，

③将上述得到的结果与哈希表初始大小(8)进行与操作。

具体计算公式如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

扩容拆分

在HashMap进行扩容时，所有元素不需要重新计算哈希值填入到新数组的位置。只需要判断原哈希值在旧数组大小(2的幂次方数)二进制比特位上是否为1，那么新索引位置为旧索引加上旧数组大小。

举例：从16扩容到32，那么原哈希值低5位的大小在16~31之间的，元素的索引都需要改变。

if((e.hash & oldCap)==0) //不动
else //移动到新的位置;

🚀路由组件运用

int idx = (size - 1) & (dbKeyAttr.hashCode() ^ (dbKeyAttr.hashCode() >>> 16));

• 这里路由场景中选择HashMap扰动函数的散列算法，根据订单uID值散列到分库表的索引中。注意这里库表要求尽量是2的幂次方数，否则进行与运算的散列效果不好。
• 实际上大厂的路由策略基本都是除法散列。因为后续如果增加数据库，扩容比较简单。使用扰动函数主要①场景不大②可以结合源码学习知识。

3.漫谈ThreadLocal

Thread,ThreadLocal,ThreadLocalMap三者关系

• 一个线程Thread对应一个ThreadLocalMap，和多个ThreadLocal，每个ThreadLocal相当于一个工具类，用于一对一管理线程里的每个变量副本。一个线程要想保存多个变量副本，就需要创建多个ThreadLocal。
• ThreadLocalMap底层是一个Entry数组，保存多对K-V键值对，K是ThreadLocal对象，V值为副本变量值。其中K值并没有采用传统ThreadLocal的hashcode方法，而是采用斐波那契散列令哈希槽位分配得更均匀。

弱引用与内存泄漏

前提：ThreadLocalMap采用弱引用来引用key(ThreadLocal对象)。当前ThreadLocal对象被多个对象引用。

为什么需要设置为弱引用？

• 假设当前除了当前线程ThreadLocalMap以外，引用ThreadLocal的所有对象都GC回收了，即使没有手动删除，因为ThreadLocal是弱引用，最后也会被GC回收。
• 在java8中，副本变量value则在下一次get,set方法调用时(或是在线程结束时)，会自动将Entry中key为null的对象进行回收，避免内存泄露的问题。因此只要ThreadLocal对象被回收，那么对应的线程变量也会被回收。
• 场景举例：一般来说ThreadLocalMap生命周期和Thread一样长，线程使用结束后会归还给线程池进行重用，并不会销毁，如果是强引用场景下KV不再被使用但也不会GC回收，出现内存泄漏。而如果是弱引用场景下，就会被GC回收。

然而即便如此，依然存在当前线程结束，但是ThreadLocal对象被另一个对象强引用持有，从而发生内存泄露的情况。比如：①静态变量持有ThreadLocal强引用②异步任务当中使用了ThreadLocal对象③线程池任务中使用。因此为了避免内存泄露的情况，使用完后都需要手动删除。

🚀项目ThreadLocal手动删除的场景

①路由项目中，执行切面方法，拿到被注解的的属性值并生成分库索引后，最后关系销毁ThreadLocal

②抽奖项目中，xxl-job执行定时任务，扫描个人活动记录进行补偿

try{
	return userTakeActicityRepository.scanInboiceMqState(); 
}finally{
	ThreadLocal.remove();
}

4.雪崩标准测试

密码学上雪崩效应指的是输入轻微变化，输出会发生显著变化。简单来说，如果使用斐波那契散列，当从8库32表扩容到16库32表时，根据路由算法得到的每个区间得数据变化量应该为50%。