HashMap扩容机制

尘微 2023-02-16 12:12:21 11307 0 0 0

(1)底层数据存储结构是数组+链表+红黑树
(2)数组的默认长度为16
(3)负载因子为0.75,也就是说当使用容量达到总长度的四分之三时,触发扩容,新的数组长度为原数组长度的2倍。
(4)当key发生hash碰撞时,产生链表。当链表的长度大于8并且数组长度大于64时,产生红黑树。
(5)容量小于64,链表长度大于等于8也会触发一次扩容。

HashMap有两个参数影响其性能:初始容量和加载因子。

1,初始容量只是哈希表在创建时的容量。
2,加载因子其实是用来判断当前HashMap<K,V>中存放的数据量。

  当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行扩容、rehash操作(即重建内部数据结构),扩容后的哈希表将具有两倍的原容量。hashmap初始化容量时候,对容量大小做的处理,保证初始化容量为最近的2的幂次方.

HashMap初始化容量非得是2的幂次方,2的倍数不行么,奇数不行么?

  • 2的幂次方:hashmap在确定元素落在数组的位置的时候,计算方法是(n - 1) & hash,n为数组长度也就是初始容量 。hashmap结构是数组,每个数组里面的结构是node(链表或红黑树),正常情况下,如果你想放数据到不同的位置,肯定会想到取余数确定放在那个数组里,计算公式:hash % n,这个是十进制计算。在计算机中, (n - 1) & hash,当n为2次幂时,会满足一个公式:(n - 1) & hash = hash % n,**计算更加高效。(也是为了后面让元素均匀的分布在新数组中)**

  • 奇数不行:在计算hash的时候,确定落在数组的位置的时候,计算方法是(n - 1) & hash,奇数n-1为偶数,偶数2进制的结尾都是0,经过hash值&运算后末尾都是0,那么0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,**更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这样就会造成空间的浪费而且会增加hash冲突。**

HashMap加载因子为什么是0.75?

  • 如果加载因子比较大,扩容发生的频率比较低,浪费的空间比较小,发生hash冲突的几率比较大。比如,加载因子是1的时候,hashmap长度为128,实际存储元素的数量在64至128之间时间段比较多,这个时间段发生hash冲突比较多,造成数组中其中一条链表比较长,会影响性能。

  • 如果加载因子比较小,扩容发生的频率比较高,浪费的空间比较多,发生hash冲突的几率比较小。比如,加载因子是0.5的时候,hashmap长度为128,当数量达到65的时候会触发扩容,扩容后为原理的256,256里面只存储了65个浪费了。

  • 综合了一下,取了一个平均数0.75作为加载因子。当负载因子为0.75,时代入到泊松分布公式,计算出来长度为8时的概率=0.00000006,概率很小了,所以产生红黑树的概率也就很小。

    扩容之后元素的位置

  • HashMap中运算数组的位置使用的是元素的(hashcode) & (leng-1),对于初始长度为16的数组,扩容之后为32,对应的leng-1就是15,31.
  • 举例一:假设某个元素的hashcode为52,这个52与15运算做按位与运算的的结果是4,这个52与31做按位与运算的的结果是20,20不就是等于4+16吗,刚好是原数组的下标+原数组的长度。
  • 举例二:假设某个元素的hashcode为100,100&15=4,100&31=4,对于HashCode为100的元素来说,扩容后与扩容前其所在数组中的下标均为4。
  • 以上两个例子证明了,*** 经过rehash之后,元素的位置要么是在原位置,要么是在原位置加原数组长度的位置。***

  • 因为每次扩容会把原数组的长度*2,那么再二进制上的表现就是多出来一个1

    比如原数组16-1二进制为0000 1111
    那么扩容后的32-1的二进制就变成了0001 1111
    再次扩容64-1就是0011 1111
    
  • 扩容之后元素的位置是否改变则取决于与这个多出来的1的运算结果,运算结果为0则不需要换位置,运算结果为1则换新位置,新位置为老位置的高位进1
  • 既省去了重新计算hash值的时间,而且由于新增的1bit是0还是1,可以认为是随机的,*** 因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。 ***

    总结

     什么时候发生Hash碰撞:
        计算元素在数组的位置key的HashCode作为index.运算结果相同的两个对象就需要存储到同一个链表中
     数组长度16:
           默认容量太小了就有可能频繁发生扩容,影响效率。太大了又浪费空间,不划算
     链表长度为8:
          因为通常情况下,链表长度很难达到8,但是特殊情况下链表长度为8,哈希表容量又很大,造成链表性能很差的时候只能采用红黑树提高性能,这是一种应对策略