Java Map 初始化容量的最佳实战以及初始化容量算法！

❝

众所周知，map 自动扩容的时候有一个 rehash 的过程会进行大量操作。那么我们有没有一个方式可以指定一个合适的初始化容量呢？

❞

当然是可以的，老司机都会在创建 Map 时，主动设置 Map 的初始容量。

最近我在面试其他人的时候，就提过这个问题。想通过这个问题，看看面试者有没有对一些性能优化，提出自己的严格要求。

基于此，本文就来探讨一下这个问题。

❝

本文提供的算法只考虑 Map 默认负载系数 0.75

❞

• 假设 list 长度为 6，那么我们知道该给 map 指定 8。
• 假设 list 长度为 7，那么我们知道该给 map 指定 16。

可是这些东西是经过了大脑的计算才获得的，计算机能有办法知道吗？

1. 二进制下的规律

先来看一下前面整数的关系。

十进制值:二进制值
    0 0
    1 1
    2 10
    3 11
    4 100
    5 101
    6 110
    7 111
    8 1000
    9 1001
   10 1010
   11 1011
   12 1100
   13 1101
   14 1110
   15 1111
   16 10000
   17 10001
   18 10010
   19 10011
   20 10100
   21 10101
   22 10110
   23 10111
   24 11000
   25 11001

脑海中知道不满足 3/4 有： (3/4比较的是这个数与它后面最近一个满足2的N次方的数相比较)。

    7 111
   13 1101
   14 1110
   15 1111
   25 11001

那么一个与其他数不同的很明显的现象就出来了：前两位都为11,后面的数出现了1。

2. 验证规律

看看每个满足 2 的 N 次方的数的二进制是多少：

2 的 0次方: 2   , 二进制值为: 10
2 的 1次方: 4   , 二进制值为: 100
2 的 2次方: 8   , 二进制值为: 1000
2 的 3次方: 16  , 二进制值为: 10000
2 的 4次方: 32  , 二进制值为: 100000
2 的 5次方: 64  , 二进制值为: 1000000
2 的 6次方: 128 , 二进制值为: 10000000
2 的 7次方: 256 , 二进制值为: 100000000
2 的 8次方: 512 , 二进制值为: 1000000000
2 的 9次方: 1024, 二进制值为: 10000000000

他们的 3/4 又是多少：

2 的 0次方的3/4值: 1   , 二进制值为: 1
2 的 1次方的3/4值: 3   , 二进制值为: 11
2 的 2次方的3/4值: 6   , 二进制值为: 110
2 的 3次方的3/4值: 12  , 二进制值为: 1100
2 的 4次方的3/4值: 24  , 二进制值为: 11000
2 的 5次方的3/4值: 48  , 二进制值为: 110000
2 的 6次方的3/4值: 96  , 二进制值为: 1100000
2 的 7次方的3/4值: 192 , 二进制值为: 11000000
2 的 8次方的3/4值: 384 , 二进制值为: 110000000
2 的 9次方的3/4值: 768 , 二进制值为: 1100000000

由此可得，规律确实存在。

3. 解决问题

一句话来概括代码逻辑就是：

• 如果前两位都为11,后面的数出现了1。那么初始容量等于这个数后面的第二个满足 2 的 N 次方的数
• 否则初始容量等于这个数后面的最近的满足 2 的 N 次方的数

/**
 * 根据List长度计算Map初始化容量
 *
 * @param i List长度
 * @return Map初始化容量
 */
public static int getInitialCapacity(int i) {
    if (i <= 1) return 2;
    if (i <= 3) return 4;
    final String b = Integer.toBinaryString(i);

    return "11".equals(b.substring(0, 2)) && b.substring(2).contains("1")
        ? 1 << (b.length() + 1)
        : 1 << b.length();
}

3.1. 测试结果，成功解决问题

测试了 10000 以内的数据均可满足，因为不会折叠，所以只展示了一点点结果集。

public static void main(String[] args) {
    for (int i = 0; i < 10000; i++) {
        final int initialCapacity = getInitialCapacity(i);
        final boolean b = (initialCapacity * 3 / 4) >= i;
        System.out.println(new Formatter().format("[%d]选择的初始化大小是[%d], 是否满足3/4不用扩容: %b", i, initialCapacity, b));
    }
}

测试结果集，满足默认扩容规律。

[0]选择的初始化大小是[2], 是否满足3/4不用扩容: true
[1]选择的初始化大小是[2], 是否满足3/4不用扩容: true
[2]选择的初始化大小是[4], 是否满足3/4不用扩容: true
[3]选择的初始化大小是[4], 是否满足3/4不用扩容: true
[4]选择的初始化大小是[8], 是否满足3/4不用扩容: true
[5]选择的初始化大小是[8], 是否满足3/4不用扩容: true
[6]选择的初始化大小是[8], 是否满足3/4不用扩容: true
[7]选择的初始化大小是[16], 是否满足3/4不用扩容: true
[8]选择的初始化大小是[16], 是否满足3/4不用扩容: true
[9]选择的初始化大小是[16], 是否满足3/4不用扩容: true
[10]选择的初始化大小是[16], 是否满足3/4不用扩容: true
[11]选择的初始化大小是[16], 是否满足3/4不用扩容: true
[12]选择的初始化大小是[16], 是否满足3/4不用扩容: true
[13]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[14]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[15]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[16]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[17]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[18]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[19]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[20]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[21]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[22]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[23]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[24]选择的初始化大小是[32], 是否满足3/4不用扩容: true
[25]选择的初始化大小是[64], 是否满足3/4不用扩容: true

3.2. 算法优化

/**
 * 根据List长度计算Map初始化容量
 *
 * @param i List长度
 * @return Map初始化容量
 */
public static int getInitialCapacity3(int i) {
    if (i <= 1) return 2;
    if (i <= 3) return 4;
    int numberOfLeadingZeros = Integer.numberOfLeadingZeros(i);
    if (i >> 32 - numberOfLeadingZeros - 2 == 3
            && i << (numberOfLeadingZeros + 2) != 0) {
        return 1 << 32 - numberOfLeadingZeros + 1;
    } else {
        return 1 << 32 - numberOfLeadingZeros;
    }
}

4. 规律背后的数学理论支撑

❝

假设有一个2的N次方的值为Y,扩容临界点X = Y * 3 / 4。

当我们输入的数字i，满足X < i <= Y时，Y会扩容到原来的两倍。

❞

那么，扩容临界点X = ( Y * 1 / 4 ) + ( Y * 2 / 4 )

把Y值转换为二进制：X = ( 2^N * 1 / 4 ) + ( 2^N * 2 / 4 )

把分数转换为二进制：X = ( 2^N * 2^-2 ) + ( 2^N * 2^-1 )

再次计算值：X = ( 2^(N-2) ) + ( 2^(N-1) )

根据二进制规则可得：X = '11'后面补上(N-2)个0, N为Y值的次方， N>=2

5. 对比guava包的方法

对比 guava 包的Maps.newHashMapWithExpectedSize()方法。

先说比较的 guava 版本："com.google.guava:guava:20.0"

假设我的 list 长度为 24，比较结果：

直接初始化长度为 24

容量32 3/4:32 元素数量0
容量32 3/4:24 元素数量1
容量32 3/4:24 元素数量2
容量32 3/4:24 元素数量3
容量32 3/4:24 元素数量4
容量32 3/4:24 元素数量5
容量32 3/4:24 元素数量6
容量32 3/4:24 元素数量7
容量32 3/4:24 元素数量8
容量32 3/4:24 元素数量9
容量32 3/4:24 元素数量10
容量32 3/4:24 元素数量11
容量32 3/4:24 元素数量12
容量32 3/4:24 元素数量13
容量32 3/4:24 元素数量14
容量32 3/4:24 元素数量15
容量32 3/4:24 元素数量16
容量32 3/4:24 元素数量17
容量32 3/4:24 元素数量18
容量32 3/4:24 元素数量19
容量32 3/4:24 元素数量20
容量32 3/4:24 元素数量21
容量32 3/4:24 元素数量22
容量32 3/4:24 元素数量23
容量32 3/4:24 元素数量24

使用 guava 方法

使用 guava 方法Maps.newHashMapWithExpectedSize(24)。

容量64 3/4:64 元素数量0
容量64 3/4:48 元素数量1
容量64 3/4:48 元素数量2
容量64 3/4:48 元素数量3
容量64 3/4:48 元素数量4
容量64 3/4:48 元素数量5
容量64 3/4:48 元素数量6
容量64 3/4:48 元素数量7
容量64 3/4:48 元素数量8
容量64 3/4:48 元素数量9
容量64 3/4:48 元素数量10
容量64 3/4:48 元素数量11
容量64 3/4:48 元素数量12
容量64 3/4:48 元素数量13
容量64 3/4:48 元素数量14
容量64 3/4:48 元素数量15
容量64 3/4:48 元素数量16
容量64 3/4:48 元素数量17
容量64 3/4:48 元素数量18
容量64 3/4:48 元素数量19
容量64 3/4:48 元素数量20
容量64 3/4:48 元素数量21
容量64 3/4:48 元素数量22
容量64 3/4:48 元素数量23
容量64 3/4:48 元素数量24

提供测试代码

public static void main(String[] args) throws Exception {

    int listSize = 24;
//        HashMap m = new HashMap(listSize);
    HashMap m = Maps.newHashMapWithExpectedSize(listSize);

    Class mapType = m.getClass();
    Field threshold = mapType.getDeclaredField("threshold");
    threshold.setAccessible(true);
    Method capacity = mapType.getDeclaredMethod("capacity");
    capacity.setAccessible(true);
    System.out.println("容量" + capacity.invoke(m) + "\t3/4:" + threshold.get(m) + "\t元素数量" + m.size());

    for (int i = 0; i < listSize; i++) {
        m.put(i, i);
        System.out.println("容量" + capacity.invoke(m) + "\t3/4:" + threshold.get(m) + "\t元素数量" + m.size());
    }
}

结论

当长度恰好等于阈值的时候，guava 会多扩充一倍。