HashMap扩展问题:为什么容量要保证在2的N次方?

发布时间:2023年12月20日

HashMap扩展问题:为什么容量要保证在2的N次方?

先说结论,为了减少哈希碰撞,提高代码效率。

问题1:为什么是2的N次幂而不是3的N次幂或者8的N次幂?

之前我们在这里提到过,在HashMap进行扩容的时候,对于链表中只存在一个Node节点的情况,是通过 e.hash & (newCap - 1) 来计算他在新数组中存储的位置。
而使用2的N次幂的原因则是为了提高 e.hash & (newCap - 1)这一段代码的效率。看例子:


|00000000 00000000 00000000 00000101 | ->5
|00000000 00000000 00000000 00000111 | ->7(2的3次幂-1)
|-------------------------------------------------------- |
|00000000 00000000 00000000 00000101 |

2的N次幂保证了在&运算时尽可能的不受容量的影响。


如果不是2的N次幂呢?:
|00000000 00000000 00000000 00000101 | ->5
|00000000 00000000 00000000 00010001 | ->9(3的2次幂)
|-------------------------------------------------------- |
|00000000 00000000 00000000 00000001 |

10001的中间那个0,导致了不管上面的数是0还是1,都使结果变成了0,因此增大了哈希冲突的概率。

上面解释了为什么使用的是2的N次幂,为什么不是8的N次幂,16的N次幂是因为2的粒度最小,效率更高。
那么问题又来了,我们不 & 运算,是不是就没有这个问题了?这里就带来了第二个问题

问题2:为什么我们需要使用e.hash & (newCap - 1)

众所周知,有一个1-9一共九个数字,我们想让他均匀的分在3个坑里,是不是每个坑我们期望都是分配3个,因此一个元素在哪一个坑就是 1%3 = 1(第一个坑),2%3 = 2(第二个坑)以此类推。最后得到每个坑均匀分配三个元素。
那么e.hash & (newCap - 1)也是同样的道理,我们想要每个Node节点的e.hash均匀的分配在数组的坑里,我们想做的是 e.hash % capacity(容量),这个公式优化就得到了e.hash & (2的N次方-1)。

固定公式:
    取余(%)操作 : 如果除数是2的幂次则等价于与其除数减一的与(&)操作.

综上所述,源码就采用了e.hash & (newCap - 1)的方式来保证Node节点均匀的分配到数组中。

大家好,我是小羊炒饭。感谢大家的关注,有任何问题可以提出,我们一起学习共同进步。公司的前辈告诉我,想涨工资人情>技术,我不懂人情,所以我想深耕技术,希望有一天能涨工资哈哈。
这一篇就不往下扩展啦,再扩展就只能是往内存方向了,比如为什么1个字节是8位之类的,大家可以自己研究。晚安玛卡巴卡。

文章来源:https://blog.csdn.net/qq_45948401/article/details/135094514
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。