jdk8之HashMap resize方法详解（深入讲解为什么1.8中扩容后的元素新位置为原位置+原数组长度）

客官°小女子只卖身不卖艺 2022-03-22 09:26 289阅读 0赞

# 缘起 #

在此之前，笔者对HashMap的工作原理进行过简单的[解析][Link 1]， jdk8中的HashMap相对于jdk7有比较大的更新，本文主要是对改动后的resize()方法进行详细解析。看本文需要一定的HashMap基础，如果没有基础的同学建议先看笔者的[另一篇文章][Link 1]

# resize()方法的作用 #

resize()方法会在HashMap的键值对达到“阈值”后进行数组扩容，而扩容时会调用resize()方法，此外，在jdk1.7中数组的容量是在HashMap初始化的时候就已经赋予，而在jdk1.8中是在put第一个元素的时候才会赋予数组容量，而put第一个元素的时候也会调用resize()方法。

# resize()方法jdk1.8中和1.7中实现有什么不同 #

## JDK1.7 ##

### resize()源码 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70 1]

### 解释 ###

在1.7中，resize()方法的原理为（图中为了简单只画出来了hashMap的数组大小为4.实际上默认是16）  
![在这里插入图片描述][20190127170344903.png]

1.  先新建一个数组，数组长度为原数组的2倍
2.  循环遍历原数组的每一个键值对的，得到键的Hashcode然后与新数组的长度（此处为8）进行&运算得到新数组的位置。然后把键值对放到对应的位置。故扩容之后可能会变成这样  
    ![在这里插入图片描述][20190215091558820.png]

而在jdk1.8中虽然扩容之后的数组也是一样是上面那样，但是在计算元素位置的方式上不太一样，jdk1.7需要与新的数组长度进行重新hash运算，这个方式是相对耗性能的，而且多线程环境下会造成死锁。而在1.8中对这一步进行了优化，下面我们来详细解释一下进行了哪些优化。

## JDK1.8 ##

### resize() 关键源码 ###

只列举与本文有关的关键代码

if (loTail != null) { 
       loTail.next = null;
       //这里很重要，新的位置为原老所处的位置，为什么扩容之后的位置还是原数组位置呢？下面解释
       newTab[j] = loHead;
    }
    if (hiTail != null) { 
       hiTail.next = null;
       //这里很重要，新的位置为原老所处的位置+原数组的长度，为什么是这个值呢？下面解释
       newTab[j + oldCap] = hiHead;  
    }

理解上文代码需要对JDK7里面的HashMap扩容方法有一定的了解，本文就不展开了。  
看不懂没关系，只需要注意`newTab[j] = loHead`和`newTab[j + oldCap] = hiHead`这两行代码，其中`newTab`为新的数组，`j`为元素在原数组中的下标，`oldCap`为原数组的长度，loHead和hiHead都为元素。那么这两行的代码的意思就是说：

*  `newTab[j] = loHead`：元素在新数组中的位置还是在原数组中的位置
 *  `newTab[j + oldCap] = hiHead`：元素在新数组中的位置是在老数组中的位置加原数组的长度

经过rehash之后，**元素的位置要么是在原位置，要么是在原位置加原数组长度的位置**。  
那么为什么是这样的呢？这一步，是一个非常巧妙的地方，也是本文分析的重点。

### 解释：为什么经过rehash之后，**元素的位置要么是在原位置，要么是在原位置加原数组长度的位置**？ ###

要搞明白这个问题首先要清楚

1.  HashMap的数组长度恒定为2的n次方，也就是说只会为16，32，64，128这种数。源码中有限制，也就是说即使你创建HashMap的时候是写的

Map<String,String> hashMap = new HashMap<>(13);

最后数组长度也会变成16，而不是你的13. 会取与你传入的数最近的一个2的n次方的数。

public HashMap(int initialCapacity, float loadFactor) { 
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }

static final int tableSizeFor(int cap) { 
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

那么明确这一点有什么用呢？HashMap中运算数组的位置使用的是leng-1，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70 2]  
那么就是对于初始长度为16的数组，扩容之后为32，对应的leng-1就是15，31，他们所对应的二进制为

> 15：0000 0000 0000 0000 0000 0000 0000 1111  
> 31：0000 0000 0000 0000 0000 0000 0001 1111

现在我们开始做假设，假设某个元素的hashcode为52：

> 52：0000 0000 0000 0000 0000 0000 0011 0100

这个52与15运算做按位与运算的的结果是4，用二进制表示如下

> 4：0000 0000 0000 0000 0000 0000 0000 0100

这个52与31做按位与运算的的结果是20，用二进制表示如下

> 20：0000 0000 0000 0000 0000 0000 0001 0100

二十不就是等于4+16吗，刚好是原数组的下标+原数组的长度，再看个栗子

假设某个元素的hashcode为100：

> 100： 0000 0000 0000 0000 0000 0000 0110 0100

100&15=4，100&31=4

> 4：0000 0000 0000 0000 0000 0000 0000 0100

也就是说对于HashCode为100的元素来说，扩容后与扩容前其所在数组中的下标均为4。

通过这两个栗子我们证明了，经过rehash之后，元素的位置要么是在原位置，要么是在原位置加原数组长度的位置。  
我们接着来看为什么会是这样  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70 3]  
可以看到，扩容之后元素的位置是否改变，完全取决于紫色框框中的运算是为0还是1，为0则新位置与原位置相同，不需要换位置，不为零则需要换位置。

而为什么新的位置是原位置+原数组长度，是因为每次扩容会把原数组的长度\*2，那么再二进制上的表现就是多出来一个1

*  比如原数组16-1二进制为`0000 1111`
 *  那么扩容后的32-1的二进制就变成了`0001 1111`
 *  再次扩容64-1就是`0011 1111`

扩容之后元素的位置是否改变则取决于与这个多出来的1的运算结果，运算结果为0则不需要换位置，运算结果为1则换新位置，新位置为老位置的高位进1，比如对于上诉52来说，老位置为`0100`，新位置为`10100`，而每一次高位进1都是在加上原数组长度的过程。  
![20190127184352812.png][]

# 总结 #

jdk1.8中在计算新位置的时候并没有跟1.7中一样重新进行hash运算，而是用了原位置+原数组长度这样一种很巧妙的方式，而这个结果与hash运算得到的结果是一致的，只是会更块。

至于为什么新位置要么是原位置，要么是原位置+原数组长度的位置是由于每次扩容相当于数组长度的高位多了一个1，新的hash运算取决于hashCode在这一位上的值是0还是1，如果是0则无需变化位置，如果是1则位置为原位置+原数组长度的位置

参考：https://www.jianshu.com/p/9e5d235b4ade

[Link 1]: https://blog.csdn.net/qq32933432/article/details/53013393
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70]: /images/20220322/485d4041079b4b4f8ef08508e6d2754d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70 1]: /images/20220322/fbacd75a65ce41f881c72a1af45075d4.png
[20190127170344903.png]: /images/20220322/18216ced3f164725964f5f07618b4414.png
[20190215091558820.png]: /images/20220322/f785e55a36834df7a60a0e3a38446649.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70 2]: /images/20220322/37e1cdc9414642c1b45e759f27db81f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMzI5MzM0MzI_size_16_color_FFFFFF_t_70 3]: /images/20220322/b487405baaf440c69456989169ccee8f.png
[20190127184352812.png]: /images/20220322/2b3148108f13430592df56f0557f1596.png