HashMap的扩容时机和初始化集合容量时是否根据公式计算

た入场券 2022-03-15 02:22 204阅读 0赞

阿里巴巴`Java`开发手册中提到：集合初始化时，指定集合初始值大小。  
对于集合的初始化大小，网上流传两种观点：

<table> 
 <thead> 
  <tr> 
   <th>观点</th> 
   <th>对错</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>初始化大小 = (元素个数 / 负载因子) + 1</td> 
   <td>错误</td> 
  </tr> 
  <tr> 
   <td>直接指定集合大小</td> 
   <td>正确</td> 
  </tr> 
 </tbody> 
</table>

为什么第二个观点正确？我们断点调试一下寻找答案。

扩容相关的属性：

/**
     * 底层数据结构：节点数组
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    /**
     * 当前元素的个数
     */
    transient int size;
    /**
    * 临界值，创建集合时，如果指定集合大小为 5，那么 threshold = 5，否则默认值为 16，详见
    * public HashMap(int initialCapacity, float loadFactor) 构造器
    */
    int threshold;

调试代码如下

HashMap<Integer, Integer> map = new HashMap<>(5);
    for (int i = 0; i < 5; i++) {
        map.put(i, i);    // @1
    }

在`@1`处打断点，进入`put`方法，发现`key`和`value`不是我们预期的值，`key`是`java.security.ProtectionDomain`对象，`value`是`Object`对象，我们在`@2`处打断点，直接跳到下一个断点处，此时又跳到了`@2`的断点处，这时候的`key`和`value`才是我们预期的值。

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {    // @2
            inflateTable(threshold);
        }
        ... 省略了部分代码
        addEntry(hash, key, value, i);    // @3
        return null;
    }

第一次调用`put`方法是由`JVM`主动调用的，并且只会调用，之后不管你创建多少个`Map`，调用了多少次`put`方法，`JVM`都不再调用。  
第二次调用时，`if (table == EMPTY_TABLE)`为真，进入`inflateTable`方法，参数为`threshold`，创建集合时 `threshold` 的默认值为`16`，如果指定了集合大小，`threshold`值为集合大小。

private void inflateTable(int toSize) {
        int capacity = roundUpToPowerOf2(toSize);    // @4
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);    // @5
        table = new Entry[capacity];    // @6
        ... 省略了部分代码
    }

断点`@4`是计算容器的真实容量，例如我们指定集合大小为`5`，那么真实容量为`8`。真实容量 `X` 的规则：

1.  X > 5
2.  X 是 2 的次幂，并且是第一个大于 5 的数

断点`@5`是计算下次扩容的 `threshold` 的临界值，`threshold = 6`

断点`@6`初始化容器 `table`

我们再回到断点`@3` `addEntry` 方法，此处是将数据存储到 `table` 数组中

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {    // @7
            resize(2 * table.length);
            ... 省略了部分代码
        }
        createEntry(hash, key, value, bucketIndex);
    }

断点`@7`处校验是否达到扩容的条件，当且仅当满足下面这两条，才需要扩容

1.  当前元素个数 `size` 大于临界值 `threshold`，在断点`@5`处计算的`threshold = 6`
2.  `table[bucketIndex]` 不为 `null`，`bucketIndex`是元素`key`计算的数组下标

由上可知，观点二是正确的，即：集合初始化时，指定集合初始值大小，不需要手动计算。