详解HashMap 的⻓度为什么是 2 的幂次⽅

本文主要是介绍详解HashMap 的⻓度为什么是 2 的幂次⽅，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

通过将 Key 的 hash 值与 length-1 进行 & 运算,实现了当前 Key 的定位,2 的幂次方可以减少冲突(碰撞)的次数,提高 HashMap 查询效率;

为什么说可以减少碰撞的次数?

如果 length 不是 2 的次幂,比如 length 为 15,则 length-1 为 14,对应的二进制为 1110,与hash 值的二进制做与运算,最后一位都为 0,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大。这里牵涉到一个无效哈希桶的感念,在这个例子中，由于最低位永远不会是 1，因此哈希表的第 15 个位置（如果我们从 0 开始计数）将永远无法被使用。这就是一个无效的哈希桶，因为它被预留出来，但是永远不会存储任何键值对。这就是所谓的“空间浪费”。

更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率!

那为什么说可以提高 HashMap 查询效率?

如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式,再与hash 值的二进制做与运算操作效率会非常的快,而且空间不浪费;

这篇关于详解HashMap 的⻓度为什么是 2 的幂次⽅的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---