• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

MS

开发技术 开发技术 3小时前 1次浏览

JDK 1.8对hash算法和寻址算法如何优化的

MS

有一个32位的key的hash值,将此二进制值右移16位,低16位的值变为高16位的值,然后在进行异或运算

MS

[16个元素]->hash值对数组长度取模,定位到数组的一个位置,塞进去

寻址算法优化

(n-1)& hash ->数组里的一个位置

1111 1111 1111 1111 1111 1010 0111 1101(没有经过优化的 hash 值)

0000 0000 0000 0000 0000 0000 0000 1111(n-1)

取模运算性能比较差,为了优化寻址效率,所以(n-1)& hash -> 效果是和hash对n取模是一样的,但是与运算的性能要比hash对n取模要高很多。数学问题,只要保持数组长度是2的n次方,hash 对 n 取模的效果就和 hash&(n-1)是一样的,后者性能更高。

(n-1)一般很小,高16位一般都为0,没有经过优化的hash值的高16位和n-1的高16位之间的与运算都为0,是可以忽略的,核心点在于低16位的与运算。hash值的高16位没有参与到运算

1111 1111 1111 1111 0000 0101 1000 0011(经过优化的hash值),优化后的hash值的低16位包含了原来未优化的hash值的高16位和低16位的特性,在有些hash值的低16位很相似,优化后的hash值融合了原来高低16位的特征,让hash值尽量不一样,避免hash冲突的发生。
MS


程序员灯塔
转载请注明原文链接:MS
喜欢 (0)