转载

HashMap为什么是2的n次幂

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

关于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

正文到此结束

所属分类： Java 编程技术

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。