斐波那契散列,解决一般概率问题

斐波那契散列斐波那契散列属于乘法散列的一种特例通过该算法 可以减少hash冲突的发生。其核心原理是利用黄金分割比(约0.618)来构造哈希函数。ThreadLocal底层使用ThreaLocalMap存储 数据存储数据时就是使用斐波那契散列计算key的索引。适用场景‌促销活动‌为每个用户生成唯一优惠码避免重复领取。‌抽奖系统‌生成公平的抽奖号码确保概率均等。‌缓存 路由‌在数据库索引或缓存系统中提升查询效率。 ‌主要优势‌分布均匀性‌利用黄金分割比的数学特性能够使哈希值在地址空间中分布更加均匀‌减少冲突‌相比传统除法散列能有效降低哈希冲突概率‌计算效率‌在硬件实现上通常只需要一次乘法和位移操作效率较高算法index(v*HASH_INCREMENTHASH_INCREMENT)(length-1)注意0.6180339887黄金分割点计算公式是(√5 - 1)/2HASH_INCREMENTMath.pow(2, 32) * 0.6180339887 0x61c88647该值相当于有符号整数的黄金分割值length表示最大的数组长度必须是2^n测试代码1数组 长度128相当于2^8TestvoidtestHash(){Integer[]testArrnewInteger[128];for(inti0;i100;i){inthashCodei*0x61c886470x61c88647;intindexhashCode(128-1);if(testArr[index]!null){System.out.println(发生碰撞索引index);}else{testArr[index]i;}}}运行后不会有hash 冲突测试代码2TestvoidtestHash(){Integer[]testArrnewInteger[110];for(inti0;i100;i){inthashCodei*0x61c886470x61c88647;intindexhashCode(110-1);if(testArr[index]!null){System.out.println(发生碰撞索引index);}else{testArr[index]i;}}}运行后会有hash冲突经过多次测试计算索引时length长度必须是2^n本博客只展示了部分测试代码读者可以自行测试其他长度