HashMap的初始容量设置

TL;DR

知道大小的情况下,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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.