HashMap 的 size 为什么必须是 2 的整数次方?

  1. 这样做总是能够保证 HashMap 的底层数组长度为 2 的 n 次方。当 length 为 2 的 n 次方时,h & (length – 1) 就相当于对 length 取模,而且速度比直接取模快得多,这是 HashMap 在速度上的一个优化。而且每次扩容时都是翻倍。
  2. 如果 length 为 2 的次幂,则 length – 1 转化为二进制必定是 11111……的形式,在与 h 的二进制进行与操作时效率会非常的快,而且空间不浪费。但是,如果 length 不是 2 的次幂,比如:length 为 15,则 length – 1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0 ,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率,这样就会造成空间的浪费。

发表评论

后才能评论

评论(3)

  • 一蓑烟雨 普通 2022-09-28 4:34 下午

    HashMap这样做有两点原因
    1、提升计算效率,更快算出元素的位置
    对于机器而言,位运算永远比取余运算快得多,在length为2的整数次方的情况下,hash(key)%length能被替换成高效的hash(key)&(length-1),两者的结果是相等的。
    2、减少哈希碰撞,使得元素分布均匀
    因此,数组长度是一个2的整数次方时,哈希碰撞的概率起码能下降一半,而且所有元素也能均匀地分布在数组上。

  • (-。) 普通 2022-05-22 9:27 下午

    这里第二点,如果length不是2的次幂,求元素在数组中的位置也就不能直接进行位运算了