HashMap的初始容量设置

先说结论

知道大小的情况下，new HashMap的时候这么写：

HashMap<Integer, String> map = Maps.newHashMapWithExpectedSize(expectedSize);

正文

Java中的HashMap大家都很熟悉，其底层使用了Node数组来存储Map中的数据。但是如果存储的数据太多，空间不够，就需要扩容这个数组来存储新的数据了。

扩容的实现可以看下java.util.HashMap#resize函数，基本上就是将数组中的内容逐个复制到新数组中。

扩容操作的时间复杂度是O(n)，空间复杂度是O(n)，还需要计算对象的hash。在平常编码中，如果我们提前知道map的大小，就应该指定初始容量，避免发生扩容。

《阿里巴巴开发手册》中也有这么一条建议：

于是，很多开发者（包括刚开始的我），就这么写：

HashMap<Integer, String> map = new HashMap<>(expectedSize);

然后，最近看了扩容的源代码才发现，这样写是不合适的，还是不能完全避免扩容，我们写个代码来验证下：

public class Solution {
    /**
     * 获取map的容量（即内部数组的大小）
     */
    public static int getCapacity(HashMap map) {
        try {
            Field tableField = map.getClass().getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            if (table == null) {
                return 0;
            }
            return table.length;
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
        }
        return 0;
    }

    /**
     * 从0到maxVal-1，逐个put到map中，并观察map的容量变化
     */
    public static void putAndWatchCapacity(HashMap<Integer, String> map, int maxVal) {
        for (int i = 0; i < maxVal; i++) {
            int oldCapacity = getCapacity(map);
            map.put(i, "");
            int newCapacity = getCapacity(map);
            if (oldCapacity != newCapacity) {
                System.out.print("capacity changed! ");
                System.out.print(oldCapacity);
                System.out.print("->");
                System.out.print(newCapacity);
                System.out.print(" for key: ");
                System.out.println(i);
            }
        }
    }

    public static void main(String[] args) {
        HashMap<Integer, String> map;
        int expectedSize = 128;

        System.out.println("new HashMap");
        map = new HashMap<>(expectedSize);
        putAndWatchCapacity(map, expectedSize);
    }
}

输出如下：

new HashMap
capacity changed! 0->128 for key: 0
capacity changed! 128->256 for key: 96

可以看到，除了刚开始的初始化以外，还发生了一次额外的扩容。

（从这儿我们也可以看到，HashMap在放入第一个值的时候，才会创建内部的数组）

看了HashMap扩容触发的条件：

当Node数量大于 threshold = loadFactor(默认值0.75) * capacity 的时候，就会触发扩容。

而128*0.75=96，所以在put 第97个值的时候，就扩容了。

这样一算的话，初始容量应该设置成Math.ceil(exps/0.75)。·

但是业务中每次new HashMap的时候，都要记住0.75这个值，非常麻烦，一点也不优雅。

所以找了下现有的工具类库，发现guava有这个方法：

HashMap<Integer, String> map = Maps.newHashMapWithExpectedSize(expectedSize);
// 其内部的初始容量是(int)(expectedSize/ 0.75)+1

这样写，就不会遇到扩容的问题了。

同样，HashSet也有类似的方法：

HashSet<Integer> set = Sets.newHashSetWithExpectedSize(expectedSize);

同样写个代码来验证下：

import com.google.common.collect.Maps;

import java.lang.reflect.Field;
import java.util.HashMap;

public class Solution {
    /**
     * 获取map的容量（即内部数组的大小）
     */
    public static int getCapacity(HashMap map) {
        try {
            Field tableField = map.getClass().getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            if (table == null) {
                return 0;
            }
            return table.length;
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
        }
        return 0;
    }

    /**
     * 从0到maxVal-1，逐个put到map中，并观察map的容量变化
     */
    public static void putAndWatchCapacity(HashMap<Integer, String> map, int maxVal) {
        for (int i = 0; i < maxVal; i++) {
            int oldCapacity = getCapacity(map);
            map.put(i, "");
            int newCapacity = getCapacity(map);
            if (oldCapacity != newCapacity) {
                System.out.print("capacity changed! ");
                System.out.print(oldCapacity);
                System.out.print("->");
                System.out.print(newCapacity);
                System.out.print(" for key: ");
                System.out.println(i);
            }
        }
    }

    public static void main(String[] args) {
        HashMap<Integer, String> map;
        int expectedSize = 128;

        System.out.println("new HashMap");
        map = new HashMap<>(expectedSize);
        putAndWatchCapacity(map, expectedSize);

        System.out.println("newHashMapWithExpectedSize");
        map = Maps.newHashMapWithExpectedSize(expectedSize);
        putAndWatchCapacity(map, expectedSize);
    }
}

输出如下：

new HashMap
capacity changed! 0->128 for key: 0
capacity changed! 128->256 for key: 96
newHashMapWithExpectedSize
capacity changed! 0->256 for key: 0

可以看到，确实没有再遇到扩容的情况了。