为什么HashMap的容量是2的幂次方

标签:数组下标   没有   int   空间   影响   容量   ==   stat   hash   

在jdk1.7中 哈希函数为

static int indexFor(int h,int length){
      return h & (length-1);
}

理由一:充分利用数组空间

  • 假设长度不是2的幂次方
长度为基数  (假设长度为5)
      01010101  01010101  01010101  01010111    --->key
 &  00000000  00000000  00000000  00000100    --> length = 5,参与hash运算的是 length-1 = 4
 -------------------------------------------------------------------------
      00000000  00000000  00000000  00000100   
      【这里得到的结果永远是偶数,代表获取到的数组下标永远是偶数,即不能获取到基数位的数组下标,数组就浪费了一半空间,很容易造成哈希冲突,影响性能】

长度为偶数  (假设长度为6)
      10101010  01010101  01010101  01010111    --->key
&   00000000  00000000  00000000  00000101    --> length = 6,参与hash运算的是 length-1 = 5
-------------------------------------------------------------------
      00000000  00000000  00000000  00000101
      【这里第二位就会是0,导致2,3索引为不可能有值,浪费了数组空间,容易造成哈希冲突】
  • 长度是2的幂次方
假设长度为8
                                                                              任意数    --->key
 &  00000000  00000000  00000000  00000111    --> length = 8,参与hash运算的是 length-1 = 7
-----------------------------------------------------------------------------------------------
      00000000  00000000  00000000  00000000  --  00000000  00000000  00000000  00000111  
      【此时的数据就在0到7之间,没有浪费数据空间】

理由二:扩容后,迁移数据不需要rehash

数组长度为2的幂次方,在进行数组扩容时,扩容后的长度是原来数组长度的2倍结果还是2的幂次方。

  • 假设原来数组是16
    • 参与hash运算的是length-1 = 15
      00000000 00000000 00000000 00001111
  • 扩容后是32
    • 参与hash运算的是length-1 = 31
      00000000 00000000 00000000 00011111
      在扩容时,数据要从原数组迁移到新数组中
假设原来的数据为:
      00000000  00000000  00010101 10010111  
那么原来的下标为:
      00000000  00000000  00010101 10010111  
&   00000000  00000000  00000000 00001111
---------------------------------------------------------------
      00000000  00000000  00000000 00000111   ===>7
扩容后的下标为
       00000000  00000000  00010101 10010111  
&    00000000  00000000  00000000 00011111
---------------------------------------------------------------
      00000000  00000000  00000000 00010111  ==> 16+7 = 23

      【这样设置扩容后的下标为原数组的下标或者是原数组下标+ 扩容长度】 这样就不需要rehash。

为什么HashMap的容量是2的幂次方

标签:数组下标   没有   int   空间   影响   容量   ==   stat   hash   

原文地址:https://www.cnblogs.com/liuzhidao/p/14238321.html

版权声明:完美者 发表于 2021-01-07 12:43:34。
转载请注明:为什么HashMap的容量是2的幂次方 | 完美导航

暂无评论

暂无评论...