HashMap源代码分析-II-扩容策略详细分析

矫情吗；* 2023-05-29 13:17 15阅读 0赞

> 距离写第一篇关于`HashMap`的笔记（[CSDN链接][CSDN]、[HEXO链接][HEXO]）已经有1年多了，感觉当年的分析中还是少写了些内容，现在看起来有些部分有点费劲。所以现在特地补充上现在的分析笔记，主要集中在`resize()`扩容这一个操作上面。

从`put()`方法进入，经`putVal()`到达`resize()`，开始进行扩容过程。大致分为2个过程，即确定新的容量及临界容量、扩容后的调整。

## 确定新的容量及临界容量 ##

对这一部分代码的总体理解如下：

Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
         // 此时Map不为空，里面存在键值对
        if (oldCap >= MAXIMUM_CAPACITY) {
         // oldCap >= 0x3fff ffff
            threshold = Integer.MAX_VALUE; // threshold = 0x7fff ffff
            return oldTab;
        } // newCap = oldCap * 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    else if (oldThr > 0) // 此时Map为空，但是new对象的时候，把capacity当做参数，
        newCap = oldThr; // 传给了HashMap的构造函数，造成了只有threshold有值。
    else {
         // 此时Map为空，使用的是无参构造器，threshold和capacity都没有值。
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // newThr在程序开始处的默认赋值为0
    if (newThr == 0) {
         // 此处补充上述没有为newThr赋值的情况，即
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
    }
    // 使用newCap、newThr初始化扩容后的数组和threshold
    threshold = newThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

接下来对每段代码进行分析，总共分成3个片段，分别对应上述代码中的3中情况。

### ①Map不为空，里面存在键值对 ###

代码片段：

if (oldCap > 0) {
         // 此时Map不为空，里面存在键值对
        if (oldCap >= MAXIMUM_CAPACITY) {
         // oldCap >= 0x4000 0000
            threshold = Integer.MAX_VALUE; // threshold = 0x7fff ffff
            return oldTab;
        } // newCap = oldCap * 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }

有一个问题，如下：

**为什么要做`oldCap >= MAXIMUM_CAPACITY`判断**

首先`MAXIMUM_CAPACITY`的赋值为`1 << 30`，即`0x4000 0000`。然而`Integer.MAX_VALUE = 0x7fff ffff`，也就是说`MAXIMUM_CAPACITY << 1`会变成`0x8000 0000`，也就是溢出。

为了模拟一次这种情况，特意编写了下面的代码，运行下面代码的时候，JVM默认的堆大小不够，设了一个最大堆大小为10GB，参数为：`-Xmx10240m`。

public static void main(String[] args) throws Exception {
        
        disableWarning();
        showHashMapInfo(0x1fffffff);
        System.out.println("------------------------------------");
        showHashMapInfo(0x3fffffff);
    }
    /**输出结果：
    initialCapacity is : 1fffffff
    After hashMap created, capacity is : 20000000, threshold is : 20000000
    After resize(initialization), capacity is : 20000000, threshold is : 18000000
    After resize(double size), capacity is : 40000000, threshold is : 7fffffff
    ------------------------------------
    initialCapacity is : 3fffffff
    After hashMap created, capacity is : 40000000, threshold is : 40000000
    After resize(initialization), capacity is : 40000000, threshold is : 7fffffff
    After resize(double size), capacity is : 40000000, threshold is : 7fffffff
     **/
    private static void showHashMapInfo(int capacity) throws Exception {
        
        System.out.printf("initialCapacity is : %x\n", capacity);
    
        HashMap<String, String> hashMap = new HashMap<>(capacity);
    
        Class<?> hashMapClass = hashMap.getClass();
        // 通过反射的方式打印hashMap的属性值
        Method resizeMethod = hashMapClass.getDeclaredMethod("resize");
        Method capacityMethod = hashMapClass.getDeclaredMethod("capacity");
        Field thresholdField = hashMapClass.getDeclaredField("threshold");
        resizeMethod.setAccessible(true);
        capacityMethod.setAccessible(true);
        thresholdField.setAccessible(true);
    
        System.out.printf("After hashMap created, capacity is : %x, threshold is : %x\n", capacityMethod.invoke(hashMap), thresholdField.get(hashMap));
        // 会调用resize初始化Node数组
        hashMap.put("", "");
        System.out.printf("After resize(initialization), capacity is : %x, threshold is : %x\n", capacityMethod.invoke(hashMap), thresholdField.get(hashMap));
        // 手动再次resize
        resizeMethod.invoke(hashMap);
        
        System.out.printf("After resize(double size), capacity is : %x, threshold is : %x\n", capacityMethod.invoke(hashMap), thresholdField.get(hashMap));
    }
    // 去掉WARNING
    private static void disableWarning() {
        
        System.err.close();
        System.setErr(System.out);
    }

当在构造函数中指定了`initialCapacity`后，会先将`threshold`赋值成所需的`capacity`。所以先看`tableSizeFor()`函数，它用来将指定的`initialCapacity`转化成大于该值的2次幂。所以如果一开始`capacity`的初始值是大于或等于`0x40000000`的话，`HashMap`指定的`capacity`就是`0x40000000`。源代码如下：

// 1
    public HashMap(int initialCapacity) {
        
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    // 此处并未设置capacity，只是将期望的capacity赋值给了threshold
    public HashMap(int initialCapacity, float loadFactor) {
        
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        // initialCapacity超过0x40000000，只取0x40000000
        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 = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

### ②Map为空，但指定了初始大小 ###

这种情况对应于上面代码中的`HashMap<String, String> hashMap = new HashMap<>(capacity);`。这种情况下会将指`this.threshold = tableSizeFor(initialCapacity);`，导致`int oldThr = threshold;`能够获取到值，所以`if (oldThr > 0)`成立，将`newCap = oldThr`，实现了在第一次`resize()`初始化数组时，按照指定的`initialCapacity`new出数组。

### ③Map为空，未指定任何参数 ###

这种情况使用默认参数：

newCap = DEFAULT_INITIAL_CAPACITY; // 16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75

得到`newCap`和`newThr`之后便开始初始化数组大小。初始化数组后，会将原数组中的`Node`链表，按照某种规则迁移到新的数组上面去。

## 扩容后的调整 ##

接下来进入数据迁移部分。这部分主要的问题是扩容后的位置怎么算。如果`oldTab == null`，那么此次`resize`属于第一次初始化`HashMap`中的数组，直接返回刚new出来的新数组即可；当原数组中的第`i`为存在`Node`时，新的位置分布存在两种情况，即`Node`有无后续`Node`。这两种情况下，在原数组中的位置的计算方式是一样的，即：`(n - 1) & hash`，其中`n = tab.length`,所以位置也就是**Node的hash值与上`length - 1`**。

// HashMap.putVal()
    n = tab.length
    if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);

### 无后续Node扩容后的位置 ###

新的位置为：`e.hash & (newCap - 1)`

代码为：`newTab[e.hash & (newCap - 1)] = e;`

与之前的位置相比，可能是原位，可能是`oldCap + 原位`

### 有后续Node扩容后的位置 ###

这条链表上面Node的hash值的与上`oldCap`结果的含义是：**`oldCap`的最高非0位对应在hash上的那一位到底是0还是1**。因为oldCap是0x400之类的值，只有最高位是1，其他位都是0。

如果结果是0，位置为：原位；  
如果结果是1，位置为：原位+oldCap

只不过在新位置上之后，可能还是以一个链表的形式存在。

[CSDN]: https://blog.csdn.net/asahinokawa/article/details/80585354
[HEXO]: https://blog.sasurai.life/posts/1e4d6d95.html