转载

HashMap为什么是2的n次幂

hashMap主要由Node类型的数组,链表,红黑树组成。 从图中可以看出,数组中存储Node对象,每一个Node对象关联了一个链表,如果链表中元素超过8个就使用红黑树存储。

HashMap为什么是2的n次幂

关于2次幂

使用数组长度-1与hash值取余,用于确定元素在Node数组中的位置。

tab[i = (n - 1) & hash]
复制代码

源码中这样做的目的

总之一句话使用2次幂-1取余的方式是为了让数组中的元素分布均匀,充分利用数组空间。

基本思想

n是数组的长度,它的值是2的n次幂。

假设n=8,hashcode=0100010001100

(n-1)&hash计算方式如下:

0100010001100    //hashcode的值
&         0111    //(8-1)=7的二进制代码
          0100    //相&之后的值 

复制代码

你会发现hashcode的值为 0100010001100 ,相&之后的值为 0100 ,后面3位值相同,不错这样做就是为了获取hashcode低位值。

总结

得到低位值确定元素在hash数组中的位置,就是为了提高hash数组的利用率。

原文  https://juejin.im/post/5d2e885f51882556d1683740
正文到此结束
Loading...