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 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率,这样就会造成空间的浪费。

发表评论