前言：上次我们讨论了Hash函数的一些算法。 但是，鹅，再好的散列算法，在实际使用中也只能尽可能减少散列碰撞。 如果发生hash冲突该怎么办呢？ 这就是今天要讨论的问题。
混列冲突的解决方案链地址法开放地址法再混列法公共溢出区链地址法采用链表结构，通过链表存储发生混列冲突的key。
JDK是HashMap，正在使用该处理。 但是，考虑到查询的性能，当散列碰撞达到8时，它是红黑树。 可比较的key有效果。
开放地址法在发生混列冲突时，探究下一个地址是否仍然冲突，否则确定该地址是该key的存储位置。 如果仍然冲突，检测下一个地址，直到知道没有冲突。
h(I )=(hash key ) Di ) % (m-1 ) ) ) ) ) ) ) )。
hash(key ) ) m-1 )是当前碰撞的位置
Di是接下来检测出偏移量
举板栗吧。 每当发生冲突时，ThreadLocalMap都会使用此方法将当前地址偏移1进行检测。 然后，使用最简单的Di，即1、2、3…n。 依次检测hash工作台整体的位置。 当然，如果超过数组的长度，则返回第一个元素。 下标0 )。
Di序列的选择也有几种方法。
上述栗子般的线性开放地址法。 平方地址法。 按2 ^ 1、2^3…、2^3…的顺序决定跳转地址，或者按21，-1)2^ 1、2^3…、-1)2^3…、2^3…、-1)2^3…的顺序决定跳转地址这个更像hash。 线性地址法容易引起二次凝聚。 key连续时，本来不会碰撞的key必须“被碰撞”，并占据以下位置。 在这个连续的位置，可能会发生凝聚情况。
其他两种寻址方法可以避免二次聚集，但如果散列冲突不激烈，可以进行更均匀的散列。 虽然散列负载已满，但不能100%地确保可以找到存储位置的位置。 因为是跳跃式的，所以不能保证所有的地方都能检测出来。 如果是线性探测的话就可以做到，
通常，hash表上有加载因子，不允许一切都满载。 混列映射为0.75，而在ThreadLocalMap 2/3中，装载量变少也是由于该线性寻址方法，为了减少凝聚现象避免了全表检测。
混列法是在混列冲突发生后，以当前冲突位置的混列[ key ] % [ m-1 ]为参数，用另一个混列函数再次进行混列。 确实，运算消费量在增加。
公共溢出区构建另一个表以存储发生混列冲突的密钥。 这感觉太不友好了。 如果要找的key在公共区域的话，找的时间也太复杂了吧。
虽然有很多ThreadLocal的Hash分析HashMap的文章，但这里很少介绍。 让我们来看看热区域地图。 呼应上次说的魔法数字： hash _ increment=0x61c 88647=1640531527。 他是什么？ 别着急，秘密在他的hash算法里。
说到hash算法的随机乘数法，有以下公式。
使hash(k )=m*[ ) k*a ) mod 1]为整数(0 A 1 )。 p=0.618…黄金比例的数量时，散列效果最好。
如果m=2^i (这里以幂的形式不是异或) ) ) ) ) ) ) ) ) ) )。
有
hash(k )=m * [ (k * a ) mod 1]
为了简化计算机的运算，假设m=2^i，如果key是32位的int型，就一定有某种值，使得a=s/(232 )成立。 即，s=A*232。 那么原来的hash(k )可以表示为
m*[(k*a ) mod 1]
=2^I*[(kamod1 ) ]
=(2^32kamod2^32 )/2^(32-I )，即分子分母同时为2^ ) 32-I
=(2^32kamod2^32 ) *2^ (I-32 ) ) ) ) ) ) ) ) 65
另一方面，2^32 A=s表示黄金比例0.618…=2，654，435，769…
等式又是
(2，654，435，769…* kmod2^ 32 )2^(I-32 ) ) ) )
=2，654，435，769…* k *2^ (I-32 ) mod 2^i
另一方面，由于key由32位的int来表示，所以2(I-32 )表示小数部分，2i表示整数部分
=2654，435，769 * k * mod2^ I
另一方面，如果用无符号int表示2，654，435，769，则为-1640531527。
使用黄金比例数的随机乘数法也被称为pgzm散列法，是其特殊的形式。 其实也可以理解，由于黄金比例不会无限循环，所以产生的散列值难以冲突。
这里也反映了pgzm数列和黄金比例的密切关系。
混列冲突解决是由ThreadLocalMap采用开放地址法解决的。