19. HashMap初始化大小如何设置

一灰灰blogJavaJDKJDKHashMap约 1085 字大约 4 分钟

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)
Loading...