// 由于hash表的容量上限为int的最大值,亦即2的32次方,所以将n按16位,做高低分区。 // 对于n的二进制数,最高的为1的位置,向右排,若全为1,这个右侧全1对齐的数加上1,就是hash表的容量。 k = n - 1; k_1 = k ^ 1; k_2 = k_1 ^ 2; k_3 = k_2 ^ 4; k_4 = k_3 ^ 8; k_5 = k_4 ^ 16; //经过上述步骤计算后,得到的k_5就是n的低位全1值,k_5 + 1就是最中的hash表的容量。
hash碰撞概率:根据泊松分布,当负载因子大于0.75时,hash碰撞的概率会显著升高。
内存空间利用率:负载因子越小,碰撞率越低,但是会造成更多的空间浪费,所以,0.75是一个平衡两者的结果。
头插法:因为可以直接找到一个链表的头元素O(1),不需要遍历任何元素,故头插法最高效。若扩容后还同链,元素间的相对顺序会发生翻转。
尾插法:因为需要从头遍历一个链表中的所有元素,才能找到其尾元素,然后才能追加新元素,时间复杂度为O(n),所以,尾插法的效率较低。若扩容后仍同链,元素间的相对顺序不变。
并发扩容时:
- 设原顺序为:a -> b
- 线程1持有元素a,还没来得及做扩容操作,就被挂起了。
- 就在此时,线程2顺利的完成了扩容,此时的链表顺序被翻转了:b -> a。
- 线程1被唤醒,拿着手里的a继续它的扩容过程,往新链表上以头插法存a,发现b是头元素,就将a的next设为b,环就形成了,此时顺序是a -> b -> a。带环的链表会导致死循环。
//hashCode是一个int值,一个32位的数。 //把hashCode分为各16位的高低两个区,然后让这两块进行异或运算,名曰“扰动函数”。 //扰动函数的作用,降低碰撞率,均匀,位运算高效。 //由于直接用hashCode同(n - 1)做与运算,只用到了hashCode的低位区,碰撞概率必然增大,进过一次扰动函数计算,能使定位更分散。
- put时,1.7先判断是否需要扩容再写入,1.8则是先写入在判断是否需要扩容。
- 扩容时,1.7将所有元素通通rehash一遍,1.8则是要么原位置安放,要么原容量 + 原索引值安放。
- 1.7、1.8都不是线程安全的,1.7会形成死循环、数据丢失、数据覆盖,1.8会发生数据覆盖。
- 经统计,在hash函数设计合理的情况下,发生hash碰撞8次的几率为百万分之6,从概率看,8够用了。
- 至于为什么转回来是6,因为如果hash碰撞次数在8附近徘徊,会频繁发生链表和红黑树的转化,为了预防这种情况的发生。