19. HashMap初始化大小如何设置
HashMap对于javer而言,可以说是非常非常熟悉的一个容器类了,可以说99.99%的java开发者都用过它,那么你知道怎样创建一个HashMap是最优雅的方式呢?
I. HashMap初始化大小的推荐姿势
1. 基本知识点
在指明正确的使用姿势之前,有必要先了解一下HashMap的基础知识;本文重点不会放在源码分析,所以直接给一些必要的知识点
数据结构
HashMap的数据存储结构,在jdk1.7中,属于标准的 数组+链表
; 在jdk1.8中,为数组 + 链表/红黑树
这里不关注1.8中链表->红黑树的转换,简单说一下存储逻辑
- 根据key计算hash值,针对数组长度取余得到这对kv在数组中的下标
- 因为hash碰撞问题,不同的key,对应的数组下标可能一致,所以数组中存的内容按列表/红黑树方式串联在一起
数组大小
在HashMap中的,数组的大小为2^n
扩容机制
HashMap默认采用了预扩容机制,简单来讲就是虽然实际存的数据量还没有达到数组的长度,就会提前扩容为原来的两倍(如果是单个加入时,扩容两倍;如果是批量加入时,可能为2^n倍)
2. 一般使用初始化姿势
首先来看一下一般的HashMap使用姿势
Map<String, String> map = new HashMap<>();
map.put(xxx, xxx);
上面这种使用方式从语法上来看,并没有什么问题;但实际情况呢?
假如我们可以确定,我们需要往map中添加的数据量有1024个,使用上面的方式,会出现(16 -> 32 -> 64 -> 128 -> 256 -> 512 -> 1024 -> 2048
=8)次的扩容,而扩容就会导致创建新的数组,数据拷贝。而如果我们在初始化的时候,直接指定大小为2048,那么就不会出现扩容了
为了验证1024个元素,扩容的次数,写一个简单的demo测试一下
@Test
public void testMap2() throws NoSuchFieldException, IllegalAccessException {
Map<Integer, Integer> map = new HashMap<>();
Field field = map.getClass().getDeclaredField("table");
field.setAccessible(true);
int lastLen = 0;
int nowLen = 0;
for (int index = 0; index <= 1024; index++) {
map.put(index, index);
nowLen = ((Object[]) field.get(map)).length;
if (lastLen == 0) {
lastLen = nowLen;
continue;
}
if (nowLen != lastLen) {
System.out.println(String.format("resize from %d -> %d, index: %d", lastLen, nowLen, index));
}
lastLen = nowLen;
}
}
执行上面的case,输出结果如下 (请注意,实例化HashMap对象时,并不会创建数组,只有在首次添加数据时才会创建数组)
resize from 16 -> 32, index: 12
resize from 32 -> 64, index: 24
resize from 64 -> 128, index: 48
resize from 128 -> 256, index: 96
resize from 256 -> 512, index: 192
resize from 512 -> 1024, index: 384
resize from 1024 -> 2048, index: 768
如果将我们的map长度设置为2048,那么就不会有一次的扩容,上面的日志将不存在
那么我们应该如何确定Map的初始化大小呢?
3. 推荐初始化姿势
仔细看一下上面的输出,结合第一节的内容,HashMap的扩容,并不是在达到数组的长度时,实现的扩容,比如在添加第13个元素时(从1开始计数),实现了16 -> 32的扩容
看过HashMap源码的同学会知道,决定上面扩容阈值的主要来自于loadFactor
这个参数,可以在初始化的时候指定,当然不太建议修改
默认的case下,loadFactor == 0.75
,也就是说当map的数据量超过数组长度的3/4(size > len ** 0.75
)时,就会扩容
所以,在初始化HashMap时,特别是当你能预估map中数据量的大小为len
时,请初始化时,指定大小 size=2^n * 0.75 > len的最小值
HashMap<String, String> map = new HashMap<>(size);
举几个实例
- map数量为2时,初始化大小为4
- map数量为12时,初始化大小为16 (因为初始化为16时,扩容的阈值为12,正好没有超过阈值)
- map数量为13时,初始化大小为32
扩展一下:
- 若项目中引入了Guava,那么有一个更好的方法来实现Map大小指定
// 传参为你预期的容器大小
Maps.newHashMapWithExpectedSize(12)