ThreadLocal源码阅读四：如何解决hash碰撞的？

古城微笑少年丶 2023-07-07 11:20 3阅读 0赞

#### 背景 ####

1.  推荐阅读[ThreadLocal工作过程][ThreadLocal]
2.  推荐阅读[ThreadLocal的魔数引发的疑问与思考][ThreadLocal 1]
3.  什么样的使用场景会出现hash碰撞？
4.  如何解决hash碰撞的？

#### 过程 ####

1.  **可能产生hash碰撞的场景**
    
    分析ThreadLocal的hash碰撞知识，需要理解魔数扮演了什么角色有什么职能，entry\[\]中装的是什么，有什么特点。（推荐阅读中会加深对ThreadLocal相关知识的理解）。否则分析hash碰撞，是没有任何意义的。
    
    在同一个线程中使用的ThreadLocal实例越多就越可能产生hash碰撞。不管是环形数组还是弱引用的ThreadLocal，产生hash碰撞的本质原因是有多个实例，而这多个实例在环形数组且弱引用的ThreadLocal中会增加产生hash碰撞的概率。
2.  **解决hash碰撞** 这里假设已经产生了碰撞  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L291dHNhbmRpbmc_size_16_color_FFFFFF_t_70]  
    假如已经有一个entry实例在entry\[\]中了。如果发生hash碰撞的话，当前这个tab中的下标 i 已经被占用了。因此，tab\[i\]已经有值了。
    
    第一次循环，判断 k 不为 key, k也不是null,因此尝试试探一下，下一个，脚标呢？
    
    想一下，程序是严格的，如果下一个也发生碰撞，又怎么办？得求下一个脚标，直到k为null的情况，把值替换上replaceStaleEntry（key, value, i）。
    
    这就是解决hash碰撞的工作原理。
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L291dHNhbmRpbmc_size_16_color_FFFFFF_t_70 1]  
    从这个nextIndex(int i, int len)方法中，可以得到，当i + 1 >= len的时候，返回了0，则充分说明了，作者使用了环形数组的设计实现。
    
    想一下，这个环形数组有必要吗？是有必要的。因为，散列出来的值是均匀随机的，并不是从0，1，2，3…这样的，而是i是0，下一个i可能是12这样的，因此，如果找不到，则就从0开始变量整个数组，直到找key为null的情况，然后把值替换上去即可。
    
    正是因为，**散列出来的是不规则的，因此需要循环检测**，**就是因为循环检测了，找到key为null的情况**，因此这才是体现了它是环形数组设计。

#### 小结 ####

1.  通过线性探测方式，线性地找到下一个脚标中key为null的情况。以此解决hash碰撞。为什么叫线性探测法呢？线性是说，下脚标依次取值，为什么叫探测呢？因为它也不知道下一个脚标是否有值还是没有值，有还是没有值，尝试一下就知道了。因此叫做：**线性探测法**。
2.  由于hash散列算法是不规则的，因此必须要循环检测。可就是因为循环检测，找到key为null的情况，把值替换上去。正是因为有这样的操作，所以才说**环形数组**设计。
3.  **预留问题，以后分析**
    
    作者为什么要设计ThreadLocal源码，threadLocalHashCode & (length - 1)求得的值是不规则的？
    
    为什么不直接是0，1，2，3…呢？
    
    均匀的完美的散列背后的原因究竟是什么？
    
    这样的做法背后的优缺点是什么？

[ThreadLocal]: https://blog.csdn.net/outsanding/article/details/104419579
[ThreadLocal 1]: https://blog.csdn.net/outsanding/article/details/104688125
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L291dHNhbmRpbmc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200307164651443.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L291dHNhbmRpbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L291dHNhbmRpbmc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200307165513581.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L291dHNhbmRpbmc=,size_16,color_FFFFFF,t_70