【0号元素】HashMap扩展后如何重新分配元素？

这一篇的重点

我们会做代码分析。

1、引用构造函数如何创建映射对象。

2、元素增加导致扩张后，元素如何重新分配

同样，为了方便读者复盘，我截取源代码是尽量带上行号。

Jdk版本或1.8

原理图

再次，HashMap的基本数据结构是数组链红黑树的结构，加入HashMap的结构图，给人一个大致的印象。

剖析想法

创建参数构造函数并添加多个元素，直到扩展机制被触发为止

键和值都使用小字符串，以便于计算散列值

有关使用调试密钥的信息，请参阅IDEA调试密钥的说明。这里不详细说明

调试代码

public static void main(string[]args){

诗(《开始解剖》)；

Hashmapstring，string map=new hashmap(12)；

Map.put('1 '，' 1 ')；

Map.put('2 '，' 2 ')；

Map.put('3 '，' 3 ')；

Map.put('4 '，' 4 ')；

//实验钥匙之类的情况

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 ')；

}

12345678910112819202123242526272829303373839404142434445断点撞在第一排

以Debug模式开始解剖旅行

单击“Step Over”以设置hashmap string、string map=new hash map(12)；相应的线路

单击Force Step Into后，您将看到首先调用了类加载程序

/p9.toutiaoimg.com/large/pgc-image/ad66765e0997441991aed56b3733d624?from=article.detail&_iz=31825&index=2" width="640" height="260"/>

这不是今天的重点，我们直接Step Out，然后再次点击Force Step Into，进入源码

调用的是双参构造函数DEFAULT_LOAD_FACTOR为0.75，initialCapacity为12，继续Force Step Into

上图来到双参构造函数，继续Force Step Into会发现依旧调用了父类的构造函数

调完父类构造函数，继续双参构造函数，经过参数校验，源码456行之后，loadFactor=0.75，我们重点看看 = tableSizeFor(initialCapacity)

在457行Force Step Into，会发现跳转到tableSizeFor(int cap)

关于tableSizeFor(int cap)，在以前的文章详细分析过，有兴趣的可以去看看读HashMap源码之tableSizeFor，这里直接说结论，就是你给一个初始容量值，经过这个方法后，返回一个最接近该值的、且不小于该值本身的2^n的那个值，当然，最大不能超过static final int MAXIMUM_CAPACITY = 1 << 30即2的30次方

所以这里传入12返回的应该是16，n = 15 ,n+1 = 16

所以看到这应该明白，管你传9 10 11 12 13 14 15 16，经过tableSizeFor后都是返回16，这样就确保了threshold总是2的n次方，后面就会发现，其实这个值不是给扩容阈值的，而是给map的初始容量

继续Force Step Into回到双参函数，将tableSizeFor的结果赋值给threshold扩容阈值=16

开始 put

到此初始化map完成，其实到了这一步，table还没建立，继续往下Force Step Into开始put

继续Force Step Into进入map.put("1", "1");，来到源码的put(K key, V value)

源码的put(K key, V value)又是调用的putVal，调用之前会计算一下key的hash值，进去看看

key.hashCode()调用的是String的hashCode

然后返回put方法进入putVal，继续Force Step Into，此时hash值为49

因为在初始化时，并没有看到有初始化table，所以此处的table肯定是null

那顺理成章的就要执行resize()了，继续Force Step Into，进入resize()

这个我们在上文 **深入源码分析HashMap到底是怎样将元素put进去的**已经分析了一次，鉴于比较复杂，就再分析一次，还是一样，代码执行路径用红框标记出来

直接返回newTab

通过对上面源码的走读，发现带参构造函数创建的map，

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

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

还记得threshold怎么来的吗，源码457行的tableSizeFor（int initialCapacity），你说狗不狗，在这等你呢，
所以tableSizeFor的真实目的是为了确保所有map初始化时容量均为2的n次幂

扯远了，回来，拉回来，继续Force Step Into，刚刚走到table创建完，即首次resize完成

有了数组了，长度也知道了，该考虑元素位置了，上文也详细讲解了，

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

这里直接看结果，计算出i=1

因为是刚刚创建的，所以tab[1]自然为null，顺理成章的就执行tab[i] = newNode(hash, key, value, null);,构建一个链表的节点放入1号位

继续调试，执行完放入元素之后modCount自增，size自增，并和扩容阈值（当前是12）比较，1小于12不用扩容，

执行完毕，关于modCount见上文

自己画个示意图，大概就是这样的，只有1号位置有元素，其他的均为null

继续Force Step Into，继续map.put("2", "2");，这次算的hash值为50，但此时table不再为null，直接计算位置，1等于2，且该位置为null，直接构造一个Node放进去

依次类推，我们就不一一看了，直接Step Over到map.put("4", "D");，看看key值相同，value不同时怎么处理

一路Force Step Into，来到putVal，发现hash还是52，定位的i也是4，个位置已经有元素了，所以走了源码634行

仔细研究一下这行代码

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

p.hash == hash为ture，(k = p.key) == key也为真so执行e = p;，然后暂时还没有树化，所以源码656行直接将新的value覆盖旧的的value

至此，覆盖问题解决，继续Force Step Into，后面没有值重复的，经过一路Force Step Into
，1-9位置示意图如下

一直put、put、put直到map.put("10", "10");，为什么到了这里停下来看呢，因为此时hash值不同了，位置大概率也会不同，进去看看

果然，此时hash已经变成了1567，比之前的递增大了很多，位置也变成了15，与此类似，11的位置为0

截止到目前已经放了11个元素，位置示意图如下

理论上，再放一个就触及到了我们的扩容阈值threshold = 16*0.75 = 12，但看一下源码662行

其实12的时候还不会，是要大于12才会，那就继续Force Step Into走进map.put("12", "12")

事情开始起变化，这hash值不同，但计算的位置i=1上却已经有了元素

上面红色框就是代码执行路径，源码642表明12节点被放在p节点即1号位置的next，而e在源码641赋值时p.next此时还是null，所以下面的代码路径是正确的

所以此时的key=1就有了next，此时示意图如下：

继续Force Step Into，发现前半段map.put("13", "13");还是和map.put("12", "12");一样

本来按照剧本，key=13应该被放到2号位置key=2的next
示意图应该如下

但是，万事就怕但是，在这里if (++size > threshold)不满足了

增量扩容

他要再次执行resize()了进去瞧瞧，先不管元素移动，先看扩容

对比第一次的resize来看

元素迁移

第二次的容量和阈值都比第一次大了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  == 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  & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                     = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                             = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
12345678910111281920212223242526272829303373839404142

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

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

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

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

计算该元素在新表中的位置，e.hash & (newCap - 1)

所以0号元素经过e.hash & (newCap - 1)即1568 & 31后，工具计算结果在新表的位置是0

然后第二个元素即1号元素，正好是第二种情况，示意图再看一下

源码709行oldTab[1]不为null，711行e.next也不为null

且e instanceof TreeNode也是false，所以核心流程来到了719行的do……while

把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  & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                     = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                             = null;
                            newTab[j + oldCap] = hiHead;
                        }
123456789101112819202122232425262728

当key=1元素开始执行时，源码721行e.hash & oldCap即46 & 16 != 0，跳转至源码729