HashMap扩容后，元素是如何重新分布的

末蓝、 2022-12-05 05:21 47阅读 0赞

## [上文回顾][Link 1] ##

在上文[**深入源码分析HashMap到底是怎样将元素put进去的**][Link 1]

我们着重分析了无参构造函数是如何创建map对象和HashMap是如何将第一个元素`put`进`table`的。

## 此篇重点 ##

这篇我们将逐行代码分析

**1、有参构造函数是如何创建map对象的  
2、当元素增多导致扩容之后，元素是如何重新分布的**  
同样，为了方便读者复盘，我截取源码是尽量将行号带上。

### jdk版本还是1.8 ###

### 结构图 ###

再重复一遍，HashMap的底层数据结构为**数组+链表+红黑树**的结构，放一个HashMap的结构示意图，有个大致印象。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center]

## 解剖思路 ##

创建一个有参构造函数，并往其中添加若干元素，直至触发扩容机制

为了方便方便计算hash值，key和value都选用比较小的字符串

关于调试键的使用请参照：[IDEA调试键的说明][IDEA]，在此不再赘诉

### 调试代码 ###

public static void main(String[] args) { 
    
            System.out.println("★★★★★★解剖开始★★★★★★");
    
            HashMap<String, String> map = new HashMap<>(12);
    
            map.put("1", "1");
            map.put("2", "2");
            map.put("3", "3");
            map.put("4", "4");
    
            // 实验key相同的情况
            map.put("4", "D");
    
            map.put("5", "5");
            map.put("6", "6");
            map.put("7", "7");
            map.put("8", "8");
            map.put("9", "9");
            map.put("10", "10");
            map.put("11", "11");
            map.put("12", "12");
    
            // 第一个扩容点
            map.put("13", "13");
            map.put("14", "14");
            map.put("15", "15");
            map.put("16", "16");
    
            map.put("17", "17");
            map.put("18", "18");
            map.put("19", "19");
            map.put("20", "20");
    
            map.put("21", "21");
            map.put("22", "22");
            map.put("23", "23");
            map.put("24", "24");
    
            //第二个扩容点
            map.put("25", "25");
    
    
        }

断点打在第一行  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 以debug模式启动，开始解剖之旅 ###

点击`Step Over`到`HashMap<String, String> map = new HashMap<>(12);`所在行

点击`Force Step Into`，会发现先调用的是类加载器  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 2]  
这不是今天的重点，我们直接`Step Out`，然后再次点击`Force Step Into`，进入源码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 3]  
调用的是双参构造函数`DEFAULT_LOAD_FACTOR`为0.75，`initialCapacity`为12，继续`Force Step Into`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 4]  
上图来到双参构造函数，继续`Force Step Into`会发现依旧调用了父类的构造函数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 5]  
掉完父类构造函数，继续双参构造函数，经过参数校验，源码`456`行之后，`loadFactor`=0.75，我们重点看看`this.threshold = tableSizeFor(initialCapacity)`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 6]  
在`457`行`Force Step Into`，会发现跳转到`tableSizeFor(int cap)`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 7]  
关于`tableSizeFor(int cap)`，在以前的文章详细分析过，有兴趣的可以去看看 [读HashMap源码之tableSizeFor][HashMap_tableSizeFor]，这里直接说结论，就是你给一个初始容量值，经过这个方法后，返回一个最接近该值的、且不小于该值本身的2^n的那个值，当然，最大不能超过`static final int MAXIMUM_CAPACITY = 1 << 30`即2的30次方

所以这里传入`12`返回的应该是`16`，n = 15 ,n+1 = 16  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 8]  
所以看到这应该明白，管你传`9 10 11 12 13 14 15 16`，经过`tableSizeFor`后都是返回`16`，这样就确保了`threshold`总是2的n次方，**后面就会发现，其实这个值不是给扩容阈值的，而是给map的初始容量**

继续`Force Step Into`回到双参函数，将`tableSizeFor`的结果赋值给`threshold`扩容阈值=16  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 9]

### 开始 put ###

到此初始化map完成，其实到了这一步，`table`还没建立，继续往下`Force Step Into`开始`put`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 10]  
继续`Force Step Into`进入`map.put("1", "1");`，来到源码的`put(K key, V value)`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 11]  
源码的`put(K key, V value)`又是调用的`putVal`，调用之前会计算一下key的hash值，进去看看  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 12]  
`key.hashCode()`调用的是`String`的`hashCode`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 13]  
然后返回`put`方法进入`putVal`，继续`Force Step Into`，此时hash值为49  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 14]  
因为在初始化时，并没有看到有初始化`table`，所以此处的`table`肯定是`null`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 15]  
那顺理成章的就要执行`resize()`了，继续`Force Step Into`，进入`resize()`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 16]  
这个我们在上文 \*\*[深入源码分析HashMap到底是怎样将元素put进去的][Link 1]\*\*已经分析了一次，鉴于比较复杂，就再分析一次，还是一样，代码执行路径用红框标记出来  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 17]  
直接返回`newTab`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 18]  
通过对上面源码的走读，发现带参构造函数创建的map，

初始容量就取决于源码`692`行的`newCap = oldThr;`，

而`oldThr`又取决于源码`680`行的`int oldThr = threshold;`

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 19]  
还记得`threshold`怎么来的吗，源码`457`行的`tableSizeFor（int initialCapacity）`，你说狗不狗，在这等你呢，  
**所以`tableSizeFor`的真实目的是为了确保所有map初始化时容量均为2的n次幂**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 20]  
扯远了，回来，拉回来，继续`Force Step Into`，刚刚走到table创建完，即首次`resize`完成  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 21]  
有了数组了，长度也知道了，该考虑元素位置了，[上文][Link 1]也详细讲解了，

决定元素位置的是`(n - 1) & hash`表达式的结果，自己想动手算的参照[上文][Link 1]的方法去算

这里直接看结果，计算出`i`=1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 22]  
因为是刚刚创建的，所以`tab[1]`自然为`null`，顺理成章的就执行`tab[i] = newNode(hash, key, value, null);`,构建一个链表的节点放入`1`号位  
![在这里插入图片描述][20200909161015814.png_pic_center]  
继续调试，执行完放入元素之后`modCount`自增，`size`自增，并和扩容阈值（当前是`12`）比较，`1`小于`12`不用扩容，

执行完毕，关于`modCount`见[上文][Link 1]  
![在这里插入图片描述][2020090916174749.png_pic_center]

自己画个示意图，大概就是这样的，只有`1`号位置有元素，其他的均为`null`  
![在这里插入图片描述][2020090916115933.png_pic_center]  
继续`Force Step Into`，继续`map.put("2", "2");`，这次算的hash值为`50`，但此时`table`不再为`null`，直接计算位置，`1`等于2，且该位置为`null`，直接构造一个`Node`放进去  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 23]  
依次类推，我们就不一一看了，直接`Step Over`到`map.put("4", "D");`，看看key值相同，value不同时怎么处理  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 24]  
一路`Force Step Into`，来到`putVal`，发现`hash`还是`52`，定位的`i`也是`4`，个位置已经有元素了，所以走了源码`634`行

仔细研究一下这行代码

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

`p.hash == hash`为`ture`，`(k = p.key) == key`也为真so执行`e = p;`，然后暂时还没有树化，所以源码`656`行直接将新的`value`覆盖旧的的`value`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 25]  
至此，覆盖问题解决，继续`Force Step Into`，后面没有值重复的，经过一路`Force Step Into`  
，1-9位置示意图如下  
![在这里插入图片描述][20200909165938322.png_pic_center]

一直`put`、`put`、`put`直到`map.put("10", "10");`，为什么到了这里停下来看呢，因为此时hash只不同了，位置大概率也会不同，进去看看  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 26]  
果然，此时`hash`已经变成了`1567`，比之前的递增大了很多，位置也变成了`15`，与此类似，`11`的位置为`0`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 27]  
截止到目前已经放了`11`个元素，位置示意图如下  
![前11个元素位置示意图][11]  
理论上，再放一个就触及到了我们的扩容阈值`threshold = 16*0.75 = 12`，但看一下源码`662`行  
![在这里插入图片描述][20200909170835925.png_pic_center]  
其实`12`的时候还不会，是要大于`12`才会，那就继续`Force Step Into`走进`map.put("12", "12")`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 28]  
事情开始起变化，这`hash`值不同，但计算的位置`i`=1上却已经有了元素  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 29]  
上面红色框就是代码执行路径，源码`642`表明`12`节点被放在`p`节点即`1`号位置的`next`，而`e`在源码`641`赋值时`p.next`此时还是`null`，所以下面的代码路径是正确的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 30]  
所以此时的`key=1`就有了`next`，此时示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 31]

继续`Force Step Into`，发现前半段`map.put("13", "13");`还是和`map.put("12", "12");`一样![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 32]  
本来按照剧本，`key=13`应该被放到`2`号位置`key=2`的`next`  
示意图应该如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 33]  
但是，万事就怕但是，在这里`if (++size > threshold)`不满足了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 34]

### 增量扩容 ###

他要再次执行`resize()`了进去瞧瞧，先不管元素移动，先看扩容  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 35]  
对比第一次的`resize`来看  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 36]

### 元素迁移 ###

第二次的容量和阈值都比第一次大了2倍，且`oldTab`不再为`null`，需要将`oldTab`迁移到`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;
                            }
                        }
                    }
                }
            }

回到正题，继续`Force Step Into`，看源码`707`行，`for (int j = 0; j < oldCap; ++j)`就是要循环整个旧表

上面的代码分三种情况来读

1.  一是位置上只有一个`Node`元素，即`next`为`null`的，类似上面的`3-9`号位置上都只有一个元素
2.  第二种一个位置上有多个元素的，类似上面的`1`、`2`号位置，目前都有两个元素
3.  第三种就是此位置上的元素为`TreeNode`类型的，目前没有，今天先不考虑

对于第一种情况，核心操作就是源码`712`行的`newTab[e.hash & (newCap - 1)] = e;`

计算该元素在新表中的位置，`e.hash & (newCap - 1)`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 37]  
所以`0`号元素经过`e.hash & (newCap - 1)`即`1568 & 31`后，[工具][Link 2]计算结果在新表的位置是`0`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 38]  
然后第二个元素即`1`号元素，正好是第二种情况，示意图再看一下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 39]  
源码`709`行`oldTab[1]`不为`null`，`711`行`e.next`也不为`null`

且`e instanceof TreeNode`也是`false`，所以核心流程来到了`719`行的`do……while`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 40]  
把`do……while`这段单独拎出来看，先定义两个链表的头和尾，一个链表用来装与旧表元素位置相同的元素，一个用来装需要重新分配位置的元素

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;
                            }

当`key=1`元素开始执行时，源码`721`行`e.hash & oldCap`即`46 & 16 != 0`，跳转至源码`729`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 41]  
继续循环`1`号位置，此时`e.hash & oldCap`为`1569 & 16`结果为`0`，所以将`e`赋值给`loHead`，同时链表尾部`loTail`也指向`e`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 42]  
由于只有两个元素，循环到此结束了

最后将`loHead`放在`newTab[1]`即在新数组中与旧数组位置**相同**的地方

而`hiHead`则被放在新的数组`newTab[1 + 16]`即在**旧数组位置基础上再加上旧数组的容量**

以此类推，`2`号位上的两个元素分别被放置在新表的`2`号和`2+16`号位置上

最后操作下来，位置关系如示意图  
![在这里插入图片描述][20200910110113610.png_pic_center]

### 总结 ###

到此目标完成，总结一下要点

##### 1、HashMap的初始化是在插入第一个元素时调用`resize`完成的（源码`629`行） #####

##### 2、不指定容量，默认容量为16（源码`694`） #####

##### 3、指定容量不一定按照你的值来，会经过`tableSizeFor`转成不小于输入值的2的n次幂，源码`378` #####

这里有个小问题，`tableSizeFor`转换成2的n次幂不是直接赋值给`capacity`，而是先将值暂时保存在`threshold`，见源码`457`，然后在put第一个元素resize时，婉转的传递给`newCap`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 43]

##### 4、put元素时，元素的位置取决于数组的长度和key的hash值按位与的结果`i = (n - 1) & hash`源码`630` #####

###### 4.1 如果这里没有元素，直接放这 ######

###### 4.2 如果有，判断是不是键冲突（源码`634`），直接新值覆盖旧值\*（源码`657`） ######

###### 4.3 如果有且不是键冲突，则将其放在原元素的next位置（源码`642`） ######

##### 5、只有当size大于了扩容阈值`size > threshold`，才会触发扩容，源码`662`，扩容前，当前元素已经放好了 #####

##### 6、扩容时，容量和扩容阈值都翻番（源码`687`），但要小于`MAXIMUM_CAPACITY` #####

##### 7、扩容时，元素在新表中的位置分情况 #####

###### 7.1 当元素只是孤家寡人即元素的`next==null`(源码)`711`时，位置为`e.hash & (newCap - 1)`（源码`712`） ######

###### 7.2 当元素有`next`节点时，该链表上的元素分两类 ######

7.21 `e.hash & oldCap = 0`的，在新表中与旧表中的位置一样(源码`738`）

###### 7.22 `e.hash & oldCap != 0`的，位置为旧表位置+旧表容量，源码`742` ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 44]

### 展望： ###

调了一天，还只是调了其中的一部分，初始化、初始扩容，和增量扩容，类似树化、拆树还没研究呢

构造树化的思路，也是从源码上找，主要是以下几行  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 45]只要你能让不同的key的hash值相同，并且key不相同，就可以制造出hash冲突，就能将多个元素放在同一个位置上，然后直至触发树化，具体情况我们下回分解。  
  
  
  
  
**为了写这玩意，死了我多少脑细胞**  
  
  
  
  
**喝瓶八二年的矿泉水，不过分吧？我自己去买，你买单就行了**

## [\--------------------> 买单 <-------------][--------------------_ _ _-------------] ##

[Link 1]: https://blog.csdn.net/leisure_life/article/details/108482840
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/51c81558c4b84700bb7b361a4df733ab.png
[IDEA]: https://blog.csdn.net/leisure_life/article/details/108483754
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/af8a57ae07244c638395e4497640e4b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/ed9b53786a274e25bcd0f4dfcf3ea2f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/1464b9e000a647a192beb06653997b9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/9ce2de2b0b244ddf83dc8a53b3eae8f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/3b331e4dadb14743be4967097c9aea66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/501b3bd22e0046bc936a7bb62dd1ff65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/8aa62c90633b4cd6a3d1c0f860aec3d0.png
[HashMap_tableSizeFor]: https://blog.csdn.net/leisure_life/article/details/101674535
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/fc4e5d95aef74d6f86dc734f4e232aea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/21191722b4884607a69ade9dbff5da2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/3101063ea01147979f4fcd4a6102570c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/122e1494851a483c833e5b7c04809bd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/d2a9dc1b62f84cf18c330857e26a22c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221123/3724e17d64bf4fbcb10a59dbc5697bae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221123/9e76f8b4aa2549ea8a4614b3fe9f1488.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221123/db6948b6be6a46679f6e85a7fb22be4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221123/ff527c42d2b64b779a76ac2f25b1023a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221123/eb6357c3559a4f499262dbdd7c139b03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221123/ac2654daa008483fb9fd756cacb103b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 19]: /images/20221123/bb7ea6968669421bb91539e003184920.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 20]: /images/20221123/11abba8a660341358f03af0b9092d3c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 21]: /images/20221123/85fb3d21a89c404f81d804fe3cb08e06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 22]: /images/20221123/e6f1b60c250940dc9086e208a4363bc3.png
[20200909161015814.png_pic_center]: /images/20221123/2ee119c4ada14a0b836bf57b846b033e.png
[2020090916174749.png_pic_center]: /images/20221123/ff64a92232da4ffd84fe96ddf78c8cca.png
[2020090916115933.png_pic_center]: /images/20221123/0e86cafa6a924fb18308e1961f49fdd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 23]: /images/20221123/89b7124e6bd940d4a41b5e9a52ed4924.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 24]: /images/20221123/566f0cdde4d048d8bfad5490eadd3d28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 25]: /images/20221123/633cd0e40a844be491bfed6d6c5af011.png
[20200909165938322.png_pic_center]: /images/20221123/dda76669b12f4b9e93869d544ea02cb4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 26]: /images/20221123/403049f462b347d9a7525cb6e014058c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 27]: /images/20221123/f692add4add641e68737ce4864ea0df7.png
[11]: /images/20221123/7e5055c4be3a4b96aa88ec1438dcf445.png
[20200909170835925.png_pic_center]: /images/20221123/07cbc669c4db418a8714b0019b80b441.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 28]: /images/20221123/49ad47b573f04b0e9931af50c70f490b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 29]: /images/20221123/d81f1e82d87048a8a2e220c5c59b09f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 30]: /images/20221123/16f7b94059804d29a8e539ee7f4d8673.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 31]: /images/20221123/71ade9bccccc4e86848e6d16b84c8e92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 32]: /images/20221123/8e0c4508456541aabb43f80f086ec179.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 33]: /images/20221123/913e0ace23db4ff8b9935971789250f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 34]: /images/20221123/8cc6a79c5d3e49bfbf6d45884e927aca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 35]: /images/20221123/bd3ff8beb7a74b8fa8f527cce95b30aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 36]: /images/20221123/3707364db8fa487b97e0db3143796e14.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 37]: /images/20221123/c7b3ab1374334918b8d14aff2992a560.png
[Link 2]: https://www.jisuan.mobi/pz6mbHu3B1z6BJUx.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 38]: /images/20221123/bd6eafe2632243ceb62b5968f3f9d881.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 39]: /images/20221123/b7000df9b5374bfd92a0c7d489d2ea26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 40]: /images/20221123/7308a3b8497b4bff8bb260bc3891c5fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 41]: /images/20221123/78b405836af64868bdd7a9159d13a0ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 42]: /images/20221123/0ef3974c3e0b4a91b15e45dabb6b0fac.png
[20200910110113610.png_pic_center]: /images/20221123/258e0648d0544af99e6d7be6c1b8aaec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 43]: /images/20221123/aa16fe1d1e1c4d299036770659ad06fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 44]: /images/20221123/01d72832d6e1402b9df61d7417b9ae6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlaXN1cmVfbGlmZQ_size_16_color_FFFFFF_t_70_pic_center 45]: /images/20221123/aefb7298c28f4f66b0d65f9ef81d2875.png
[--------------------_ _ _-------------]: http://www.youma1688.cn/p.php?8tp=t1.16799a687b200.pg0