HashMap中扩容为什么是2的n次幂
已解决HashMap中扩容为什么是2的n次幂
展开
收起
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
31
条回答
写回答
-
Hi there 👋 我是阿朗。公众号《程序猿阿朗》网站：https://www.wdbyte.com采纳回答
为啥容量都是 2 的幂？ 容量是 2 的幂时，key 的 hash 值然后 & (容量-1) 确定位置时碰撞概率会比较低，因为容量为 2 的幂时，减 1 之后的二进制数为全 1，这样与运算的结果就等于 hasｈ值后面与 1 进行与运算的几位。
下面是个例子。
hash HEX(97) = 0110 0001 n-1 HEX(15) = 0000 1111 -------------------------- 结果 = 0000 0001 # 计算得到位置是 1 hash HEX(99) = 0110 0011 n-1 HEX(15) = 0000 1111 -------------------------- 结果 = 0000 0011 # 计算得到位置是 3 hash HEX(101) = 0110 0101 n-1 HEX(15) = 0000 1111 -------------------------- 结果 = 0000 0101 # 计算得到位置是 5如果是其他的容量值，假设是 9，进行与运算结果碰撞的概率就比较大。
hash HEX(97) = 0110 0001 n-1 HEX(09) = 0000 1001 -------------------------- 结果 = 0000 0001 # 计算得到位置是 1 hash HEX(99) = 0110 0011 n-1 HEX(09) = 0000 1001 -------------------------- 结果 = 0000 0001 # 计算得到位置是 1 hash HEX(101) = 0110 0101 n-1 HEX(09) = 0000 1001 -------------------------- 结果 = 0000 0001 # 计算得到位置是 1另外，每次都是 2 的幂也可以让 HashMap 扩容时可以方便的重新计算位置。
hash HEX(97) = 0110 0001 n-1 HEX(15) = 0000 1111 -------------------------- 结果 = 0000 0001 # 计算得到位置是 1 hash HEX(97) = 0110 0001 n-1 HEX(31) = 0001 1111 -------------------------- 结果 = 0000 0001 # 计算得到位置是 12022-04-06 13:32:27赞同 展开评论 -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
滑动查看更多
相关问答