hashMap主要由Node类型的数组,链表,红黑树组成。 从图中可以看出,数组中存储Node对象,每一个Node对象关联了一个链表,如果链表中元素超过8个就使用红黑树存储。
使用数组长度-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数组的利用率。