让星星⭐月亮告诉你，HashMap的resize()即扩容方法源码解读(已重新完善，如有不足之处，欢迎指正~)

本文主要是介绍让星星⭐月亮告诉你，HashMap的resize()即扩容方法源码解读(已重新完善，如有不足之处，欢迎指正~)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分析HashMap的resize()即扩容方法的源码，会发现主要分两部分操作:

1. 为创建新数组初始化新数组容量和新数组扩容阈值;
2. 创建新数组后,需将数据从旧数组转移到新数组上来,旧数组上的数据会根据(e.hash & oldCap) 是否等于0,重新rehash计算其在新数组上的索引位置，分成2类:
   ① 等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记未低位区链表lo开头-low;
   ② 不等于0时,则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区链表hi开头high(具体推导过程，详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导》).
   具体,详见下述的源码解析:
   /*HashMap的resize()方法/

/*** Initializes or doubles table size.  If null, allocates in* accord with initial capacity target held in field threshold.
*初始化或者加倍数组长度.若未指定要扩的容量值，则按照字段threshold所持有的初始容量目标分配.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.
*另外，因为我们使用的数组长度是2的n次幂的格式，当扩容后，数组原来的每个桶中的元素要么保存在原位置，要么相比旧数组，扩容到新数组后，位置的偏移量为2的n次幂。** @return the table*/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) {//如果旧数组容量>0if (oldCap >= MAXIMUM_CAPACITY) {//如果旧数组容量大于等于最大容量threshold = Integer.MAX_VALUE; //则直接修改旧数组扩容阈值为最大值return oldTab; //并返回旧数组容量，不再做其他操作}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//若旧数组容量小于最大容量且新数组容量扩大至旧数组容量的2倍后依旧小于最大容量，并且//旧数组容量大于等于默认的初始化容量16newThr = oldThr << 1; // double threshold //则将新数组扩容阈值扩大至旧数组扩容阈值的2倍}else if (oldThr > 0) // initial capacity was placed in threshold//若旧数组容量小于等于0，且旧数组扩容阈值大于0(当new HashMap(0)后再put时，会走到这里)newCap = oldThr; //则将旧数组扩容阈值赋给新数组容量else {// zero initial threshold signifies using defaults//若旧数组容量和旧数组扩容阈值均不大于0，说明数组需要初始化newCap = DEFAULT_INITIAL_CAPACITY; //将新数组容量设为默认初始化容量16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //将新数组扩容阈值设为默认负载因子0.75*默认初始化容量16=12}if (newThr == 0) {//经上述逻辑后新数组扩容阈值仍为0，说明新数组扩容阈值尚未处理过，但走到这里之前新数组容量已经被处理完了，所以需按照新数组容量*负载因子的公式重新计算float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);}threshold = newThr; //将新数组扩容阈值赋值给HashMap的扩容阈值字段@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //按照新数组容量创建新数组table = newTab; //将创建的新数组赋值给HashMap的数组字段if (oldTab != null) {//若旧数组不为null，则需要将旧数组中的数组迁移到新数组中，并将旧数组各位置置为null.for (int j = 0; j < oldCap; ++j) {//根据旧数组长度，循环遍历各数组索引下标Node<K,V> e;if ((e = oldTab[j]) != null) {//判断每个数组索引位置对应的链表的头节点是否为空，若为空则该索引位置无数据，就不需要接下来的操作，不为空才继续往下进行处理，将该链表的数据转移赋值给新数组oldTab[j] = null; //将旧数组该位置置为null，提醒gc回收if (e.next == null) //头节点无后续节点，说明只需将头节点移动到新数组newTab[e.hash & (newCap - 1)] = e; //根据新数组长度和该链表头节点已有的hash重新计算该链表头节点在新数组中的索引下标位置，并将头节点直接赋值给新数组的该索引下标。else if (e instanceof TreeNode) //判断链表头节点类型是否是红黑树((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //将树中的数据从旧数组移到新数组(此方法解读详见：《HashMap中红黑树TreeNode的split方法源码解读》)else { // preserve order//走到这里，说明链表头节点有后续节点，后面会保留原有链表的顺序进行新旧数组的数据转移
//旧数组的每个索引位置里的链表头节点转移到新数组后的索引位置是要重新rehash，重新计算的：根据(e.hash & oldCap) 是否等于0，分成2类：①等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,记未低位区链表lo开头-low；②不等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组长度，记为高位区链表hi开头high(具体推导过程，详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》)。
Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next; //用于循环递进链表(若链表上有多个节点)，保持原链表的顺序if ((e.hash & oldCap) == 0) {//详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》：用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算，若(e.hash & oldCap)的结果为0，则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与在旧数组的索引下标位置相同(处于同一条链表中的所有节点的hash值相同)：(2oldCap -1) & e.hash=(oldCap -1) & e.hash.[注意：1.旧数组长度oldCap为2的n次幂；2.计算某链表节点e在长度为n的数组中的索引下标的公式为(n-1)&e.hash；3.数据e的hash是根据e的key计算得到的，公式为(h=key.hashCode()) ^ (h>>>16)].if (loTail == null) //低位链表的末尾为null, 对于每个链表来说，说明是第一次走到这里，而且此处也只会走进来一次,因为后续会将非null的e赋值给loTail了。loHead = e; //说明e为低位链表头节点,并将其赋给代表低位链表头节点的loHead else//说明低位链表末尾不为null，说明至少处理过一次loTail了，即头节点肯定已经处理过了，下面应该去处理低位链表头节点的后续节点了loTail.next = e; //处理完低位链表头节点后，根据next=e.next和while((e=next)!=null)，依次循环递进处理低位链表头节点的后续节点，将旧数组中的链表头节点的后续节点，追加到低位链表头节点loHead的next里。loTail=e; //将非null的e赋给loTail,首次走到这里时,loTail和loHead都指向e。}else {//详见《HashMap扩容时的rehash方法中(e.hash & oldCap) == 0源码解读》: 用链表节点的hash值与为2的n次幂的旧数组长度直接进行与的位运算，若(e.hash & oldCap)的结果不为0，则可以推导得到该链表节点所在的链表头节点移动到扩容为2倍的新数组时的所在索引下标位置与在(旧数组的索引下标位置+旧数组长度)相等(处于同一条链表中的所有节点的hash值相同)：(2oldCap -1) & e.hash=(oldCap -1) & e.hash+oldCap.[注意：1.旧数组长度oldCap为2的n次幂；2.计算某链表节点e在长度为n的数组中的索引下标的公式为(n-1)&e.hash；3.数据e的hash是根据e的key计算得到的，公式为(h=key.hashCode()) ^ (h>>>16)].if (hiTail == null) //高位链表的末尾为null，对于每个链表来说，说明是第一次走到这里，而且此处也只会走进来一次,因为后续会将非null的赋值给hiTail了。hiHead = e; //说明e为高位链表头节点,并将其赋给代表高位链表头节点的hiTail else//说明高位链表末尾不为null，说明至少处理过一次hiTail了，即头节点肯定已经处理过了，下面应该去处理高位链表头节点的后续节点了hiTail.next = e; //处理完高位链表头节点后，根据next=e.next和while((e=next)!=null)，依次循环递进处理高位链表头节点的后续节点，将旧数组中的链表头节点的后续节点，追加到高位链表头节点loHead的next里。hiTail=e; //将非null的e值赋给hiTail,首次走到这里时,hiTail和hiHead都指向e。}} while ((e = next) != null); //链表后续还有节点时，才继续处理，否则跳出循环if (loTail != null) {//低位链表尾节点不为空，说明旧数组向低位链表的数据转移已处理完，可做进一步处理loTail.next = null; //要保证低位链表尾节点的后续节点为null newTab[j] = loHead; //loHead代表了低位链表的头节点，也就代表了整条低位链表(其上已经将旧数组中j索引位置上的链表里的所有节点都转移到了该低位链表上)，而从前面的处理逻辑可知，低位链表移动到新数组时的索引下标位置，与在旧数组上的索引位置相同，故直接将低位链表头节点赋给新数组的j索引下标位置即完成转移。}if (hiTail != null) {//高位链表尾节点不为空，说明旧数组向高位链表的数据转移已处理完，可做进一步处理hiTail.next = null; //要保证高位链表尾节点的后续节点为null newTab[j + oldCap] = hiHead; // hiHead代表了高位链表的头节点，也就代表了整条高位链表(其上已经要移动到新数组(j+oldCap)索引位置上的所有节点都转移到了高位链表上)，而从前面的处理逻辑可知，高位链表移动到新数组时的索引下标位置，与在旧数组上的索引位置相差了一个旧数组长度oldCap，故直接将高位链表头节点赋给新数组的(j+oldCap)索引下标位置即完成转移。}}}}}return newTab; //返回处理完的新数组}

这篇关于让星星⭐月亮告诉你，HashMap的resize()即扩容方法源码解读(已重新完善，如有不足之处，欢迎指正~)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---