[HashMap源码学习之路]---数组扩容后元素的前后变化

╰半夏微凉° 2023-10-17 23:06 12阅读 0赞

#### HashMap数组扩容后元素的前后变化 ####

前一段时间看了`HashMap` 的扩容方法，觉得写的太好了，对我很有帮助，现以我理解的来写一下。主要说两方面：

1.  扩容后元素的位置
2.  扩容后元素如何分布的

##### 1、resize方法的源码 #####

`HashMap` 中扩容方法为`resize()` 。代码如下：

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) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 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;
                        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;
                                //说明③
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    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;
        }

上边是整个`resize()` 方法的源码，今天说的是其中的这部分，即从上边带有注释的`说明①` 位置下边的`if (oldTab != null) {` 这一行开始。  
  从这一行的判断里看到，意思是原有`table` 里如果没有元素的话，会走的逻辑，其实就是`hashMap` 针对于数组长度达到`负载因子*数组长度` 的时候，会进行数据的重新分布，这一步上也是性能消耗的地方。

##### 2、扩容后数组元素的位置（无链） #####

先来看上边源码的`说明②` 位置，即下边这行：

if (e.next == null)
       newTab[e.hash & (newCap - 1)] = e;

这行的意思是，如果当前数组下标上有元素，但是没有子元素，`也就是没有形成链，就只有一个元素` ，那么该元素放置的位置按照`newTab[e.hash & (newCap - 1)]` 来放置。  
  首先来看一张图，`hashMap` 中，确定元素在数组哪个位置，是通过`hash` 值（通过一个hash方法进一步运算过的）与数组长度减一进行`与运算` 得到的，如下图所示：  
![这里写图片描述][70]  
  做法特别巧妙，那如果扩容后，比如对上边的数组长度`16` ，现在变成了长度为`32` ，也就是上边提到的这个`newTab[e.hash & (newCap - 1)]` ，相同的三个数，在扩容后的放置位置是什么呢？看下图：  
![这里写图片描述][70 1]  
  为什么会出现不同的位置呢，请仔细看那两个`hash`数，对应的`100000` 中的`1` 上的数，有的有`1` ，有的有`0` ，因为这是个随机数，并不知道到底是几，反正不是`0` ，就是`1` 了，这样就会使算出来的下标，分到两个位置上，使扩容后的数组，对元素又均匀的分摊一下。

######   **总结：`HashMap` 扩容后，原来的元素，要么在原位置，要么在`原位置+原数组长度` 那个位置上。** ######

![这里写图片描述][70 2]

##### 2、扩容后元素的位置（有链） #####

借用别人的图，如下：  
![这里写图片描述][70 3]  
  通过上图来看，左边是`扩容前` ，右边是`扩容后` ，对于下标为`15` 上整条链上的元素，扩容一倍后，元素要么在原位置`15` 上，要么在原位置加原数组长度，即`15+16` 那个位置上。并且整条链上的元素，不管在原位置`15`，还是在`31` 上，它们的排列顺序没有变化。（据说这与1.7版本不同，我没看过1.7版本）  
  那是如何做到的呢，再继续看上边的源码，位置在上边源码的`说明③` 处，即下边这个位置：

do {
         next = e.next;
          //说明③
          if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                  loHead = e;
              else
                  loTail.next = e;
              loTail = e;
          }
          else {
              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;
      }

上边的代码中，根据`说明③` 处的`(e.hash & oldCap) == 0` 来将链上的元素分成两份，然后又在`说明④` 处，对元素分别放到了`原位置` 和`原位置+原数组长度` 上。  
  用几个数据来举个例子，就会如下图所示：  
  比如一个链上的数据如下图，三种颜色，形成了链。  
![这里写图片描述][70 4]

如果对于它们三个，扩容一倍后，就会变成下边这样：  
![这里写图片描述][70 5]  
  理解的不对的话，请大神及时指正。  
![这里写图片描述][70 6]

[70]: https://img-blog.csdn.net/201808072019461?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180807202051356?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180807083742650?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: https://img-blog.csdn.net/20180807125628647?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: https://img-blog.csdn.net/20180807201103583?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 5]: https://img-blog.csdn.net/20180807201205814?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 6]: https://img-blog.csdn.net/2018080720234285?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvaGFxaXlp/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70