关于HashMap的一些思考
点击上方蓝色字体，选择“标星公众号”
优质文章，第一时间送达
作者 | 蜗牛大师
来源 | urlify.cn/na6vae
一、HashMap的负载因子的作用
当 HashMap 中的元素个数（包含链表、红黑树上的元素）达到数组长度的0.75倍的时候，开始扩容。
二、HashMap的负载因子为什么是0.75
主要是为了提高空间利用率和减少查询成本（也可以说是尽可能减少hash冲突）。
三、为什么槽位数必须使用2^n
如果想让 Hash 结果分布更加均匀，首先想到的就是使用取余（%）操作。重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash % length == hash & (length - 1) 的前提是 length 是 2 的 n 次方）。” 并且采用二进制位操作 &，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。
四、解决Hash冲突的方法
1、开放地址法
公式：fi(key) = (f(key)+di) MOD m (di=0,1,2,3,......,m-1)
key：待放入数组（hash表）的元素；m：数组长度
当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
（1）线性探测法
思想是：通过公式计算出元素在数组中的下标，如果下标上没有元素，直接放进去；如果下标中有元素，则公式中的 di 依次 +1 重新计算，直到查找到没有元素的下标。不然数组就满了，需要扩容。
（2）二次探测法
思想是：通过改变 di 的计算方式来查询没有元素的下标，具体计算方式就是 di=-12,12,-22,22,…,-(q * 10 + 2),(q * 10 + 2)，q <=m / 2。至于这个 di 的取值我也没研究，摘抄过来的，但是这个探测法的思想得知道。
考虑的情况是，如果通过公式计算出来下标之后的所有下标都有元素占据了，而这个下标的前面的有空闲的，通过第一种方法可以算出来，但是计算的次数比较多，通过这个方法可以减少计算次数。
（3）伪随机数探测再散列
思想是：di 的值是通过随机函数得到的。如果随机函数的种子相同，那么得出来的 di 也相同，查询就ok了。
总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。
2、拉链法
就是当产生 Hash 冲突时，在冲突的节点上形成链表，HashMap 就是使用的拉链法解决的 Hash 冲突。
五、为什么链表长度达到 8 的时候就要转为红黑树了？
当使用 0.75 作为负载因子时，链表中的长度达到 8 几乎是不可能的，均衡策略吧。
引用 HashMap 源码中的注释：
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
六、HashMap扩容时元素的位置发生了什么变化？
分为三种情况：
对于数组上的元素：直接使用已经计算出来的hash值重新计算新下标放入新数组。
对于链表：将一条链表拆分为两条，hash值大于数组长度的新链表放在新数组，小于的就放在原数组。
对于红黑树：将数拆为两条链表，hash值大于数组长度的新链表放在新数组，小于的就放在原数组，最后，重新判断两条链表是否需要转为红黑树。
关键代码：
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
例如：oldCap 是 16，那么扩容之后的新数组长度就是 32，链表上的元素分别是 7,23,39。（整数的hash值就是本身）
7 ：0000 0111
& 16：0001 0000
---------------
= ：0000 0000 # 0，仍旧在原位
17：0001 0001
& 16：0001 0000
---------------
= ：0001 0000 # 非0，需要放在 [17, 32) 之间
23：0001 0111
& 16：0001 0000
---------------
= ：0001 0000 # 非0，需要放在 [17, 32) 之间
39：0010 0111
& 16：0001 0000
---------------
= ：0000 0000 # 0，仍旧在原位，因为它的的值大于数组的长度
粉丝福利：Java从入门到入土学习路线图
👇👇👇
👆长按上方微信二维码 2 秒
感谢点赞支持下哈 