HashMap的初始容量设置

先说结论

知道大小的情况下,new HashMap的时候这么写:

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

正文

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

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

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

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

于是,很多开发者(包括刚开始的我),就这么写:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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);
}
}

输出如下:

1
2
3
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有这个方法:

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

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

同样,HashSet也有类似的方法:

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

同样写个代码来验证下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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);
}
}

输出如下:

1
2
3
4
5
new HashMap
capacity changed! 0->128 for key: 0
capacity changed! 128->256 for key: 96
newHashMapWithExpectedSize
capacity changed! 0->256 for key: 0

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

作者

Robert Lu

发布于

2020-02-25

许可协议

评论