hashMap的扩容原理

HashMap的扩容机制

hashMap扩容:

扩容就是重新计算容量,向hashMap不停的添加元素,当hashMap无法装载新的元素,对象将需要扩大数组容量,以便装入更多的元素。

haspMap扩容跟数据迁移具有很大的关联,我们先用图解的方式来说明数据迁移.

进行扩容前先介绍一些hahMap源码的变量

Node<K,V> loHead = null,  loTail = null;   //低位链表的头尾结点 Node<K,V> hiHead = null, hiTail = null;    //高位链表的头尾结点 Node<K,V> next;  //next指针 指向下一个元素 

迁移前: 这里将其设置为长度为 8,扩容临界点 8 * 0.75 = 6 主要是为了画图 (hashMap默认容量是16)
以下讲解都是基于数组容量为 8 讲解的,流程都是一样的.
hashMap的扩容原理
hashMap的扩容原理
从图可知,发生了扩容并且是2的次方,并且 A,B,C两元素新的位置刚好是原数组位置的索引位置,D,E,F刚好在原数组位置索引 + 8 即原数组位置索引+数组容量。是不是真的是这样呢??,这时需要看源码分析一波

流程讲解

刚开始进行第一次扩容的时候,得到A的index索引为4,put进数组中,hashMap先会将A的hash进行 & oldCap(8) 运算,判断是否 ==0,如果为true,则代表为低位链表,这里涉及到二进制运算,比如A的index =4 (二进制 = 0000 0100) oldCap = 8(二进制=0000 1000) &运算之后 =0,后4位为低位,当然hash肯定不是8个bit位,hashCode得到索引值为int类型,一个int类型占4个字节,一个字节占8个bit位,所以hash二进制所占bit为 32,后4位为低位,高位远远多于低位,所以这也是put操作的时候需要将高位参与进来,减少hasp冲突。(这是put流程,put详情操作请看我另一篇博客)

言归正传,当A进行判断后,会将 loHead和loTail赋值给A,此时链表只有A元素,当循环到第二次迁移后,也就是将B元素进行迁移 B进行 &运算之后,同样为true,所以加入低位链表,而此时链表中有A元素,所以讲A链表的尾结点.next指向B元素即可,同理C也是一样,添加到B尾结点下面,直到添加完所有元素,当添加D元素时,因为D元素的hash为12, 进行 & 运算时为false ,则代表添加到高位链表,此时 hiHead和 hiTail指向D 之后流程都是一样的。当结束循环之后,低位链表的元素将会以原数组下标索引添加到新数组中,但是高位链表的元素会将原数组的下标索引 + oldCap添加到新数组,并且低位高位都会讲原先的数组设置为null ,方便gc

源码实例

final Node<K,V>[] resize() {         Node<K,V>[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;  //数组容量(旧)         int oldThr = threshold; //扩容临界点(旧)         int newCap, newThr = 0; //数组容量(新)、扩容临界点(新)         if (oldCap > 0) {             //如果旧容量大于等于了最大的容量 2^30             if (oldCap >= MAXIMUM_CAPACITY) {                //将临界值设置为Integer.MAX_VALUE                 threshold = Integer.MAX_VALUE;                 return oldTab;             }             //扩容2倍             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY)                 newThr = oldThr << 1; // 新阈值设置2倍         }         else if (oldThr > 0) // HashMap(int initialCapacity, float loadFactor)调用             newCap = oldThr;         else {               // 第一次put操作的时候,因为jdk1.8hashMap先添加元素再扩容         //构造函数将jdk1.7的扩容移动到这                     newCap = DEFAULT_INITIAL_CAPACITY; //默认容量 16                     //临界值 16 *0.75 =12             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);          }         if (newThr == 0) {//如果新阈值为0,根据负载因子设置新阈值             float ft = (float)newCap * loadFactor;             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                       (int)ft : Integer.MAX_VALUE);         }         threshold = newThr;         @SuppressWarnings({"rawtypes","unchecked"})         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];         table = newTab;         if (oldTab != null) {             for (int j = 0; j < oldCap; ++j) {如果旧的数组中有数据,循环                 Node<K,V> e;                 if ((e = oldTab[j]) != null) {                      oldTab[j] = null; //gc处理                     if (e.next == null)                         newTab[e.hash & (newCap - 1)] = e; //只有一个节点,赋值,返回                     else if (e instanceof TreeNode) //判断是否为红黑树结点                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                     else { // preserve order                         Node<K,V> loHead = null, loTail = null; //低位链表                         Node<K,V> hiHead = null, hiTail = null;  //高位链表                         Node<K,V> next;                         do {                             next = e.next; //指向下个元素结点,做为while循环的条件                             if ((e.hash & oldCap) == 0) { //判断是否为低位链表                                 if (loTail == null)  //链表没有元素,则将该元素作为头结点                                     loHead = e;                                 else                                     loTail.next = e; //加在链表的下方                                 loTail = e;                             }                             else { {//不为0,元素位置在扩容后数组中的位置发生了改变,新的下 //标位置是(原下标位置+原数组长)                                 if (hiTail == null)                                     hiHead = e;                                 else                                     hiTail.next = e;                                 hiTail = e;                             }                         } while ((e = next) != null);                         //遍历完成后,进行数据迁移                         if (loTail != null) {                         //链表最后                             loTail.next = null;                             //将元素原位置迁移到新数组中,位置一样                             newTab[j] = loHead;                         }                          if (hiTail != null) {                             hiTail.next = null;                             //高位链表迁移 + 旧数组容量                             newTab[j + oldCap] = hiHead;                         }                     }                 }             }         }         //返回新数组         return newTab;     } 

总结(扩容与迁移):
1、扩容就是将旧表的数据迁移到新表
2、迁移过去的值需要重新计算hashCode,也就是他的存储位置
3、关于位置可以这样理解:比如旧表的长度8、新表长度16
旧表位置4有6个数据,假如前三个hashCode是一样的,后面的三个hashCode是一样的迁移的时候;就需要计算这6个值的存储位置
4、如何计算位置?采用低位链表和高位链表;如果位置4下面的数据e.hash & oldCap等于0,那么它对应的就是低位链表,也就是数据位置不变,e.hash & oldCap不等于0呢?就要重写计算他的位置也就是j + oldCap(4+8);这个12,就是高位链表位置(新数组12位置)

版权声明:玥玥 发表于 2021-04-18 5:54:12。
转载请注明:hashMap的扩容原理 | 女黑客导航