行百里er
行百里er
2020-09-30
目录

【优雅的避坑】HashMap正确的避免扩容带来的额外开销

作者：行百里er

博客：https://chendapeng.cn (opens new window)

提示

这里是 行百里er 的博客：行百里者半九十，凡事善始善终，吾将上下而求索！

# 设置HashMap的初始容量

设置HashMap的初始容量只是优化的开始。

HashMap在Java的使用中占据着很重要的地位，平时使用的时候，相信很多Java程序员都知道在定义HashMap的时候，给它设置一个初始容量，以便减少hashMap扩容（resize）带来的额外开销，比如像我同（zi）事（ji）的这段代码：

@Test
public void longLongAGo() {
    int count = 1000000;

    System.out.println("---------------- 不设置hashMap初始容量 ------------");
    long start = System.currentTimeMillis();
    HashMap<Integer, Object> map = new HashMap<>();
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
    }
    long end = System.currentTimeMillis();
    System.out.println("添加1000000个元素耗时：" + (end - start));

    System.out.println("---------------- 设置hashMap初始容量 -------------------");
    long start1 = System.currentTimeMillis();
    HashMap<Integer, Object> map1 = new HashMap<>(count);
    for (int i = 0; i < count; i++) {
        map1.put(i, UUID.randomUUID());
    }
    long end1 = System.currentTimeMillis();
    System.out.println("添加1000000个元素耗时：" + (end1 - start1));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

我同事说他在初始化的时候设定了map的容量，不会在添加元素的过程中进行自动扩容了，大大提高了性能，从结果看确实如此！

所以，集合初始化时，指定集合初始值大小能提升性能。

然鹅，我抱着怀疑的态度，对比了设置初始容量和不设置初始容量时，hashMap的扩容次数，当设置初始容量为1000000时，容器并不是想象中的不扩容了，而是也扩容了1次：

@SneakyThrows
@Test
public void testing() {
    int count = 1000000;

    System.out.println("---------------- 初始化hashMap容量为1000000 ------------");
    int resizeCount = 0;
    HashMap<Integer, Object> map = new HashMap<>(count);
    Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
    capacityMethod.setAccessible(true);
    int capacity = (int) capacityMethod.invoke(map);
    System.out.println("初始容量：" + capacity);
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod.invoke(map);
        if (curCapacity > capacity) {
            System.out.println("当前容量：" + curCapacity);
            resizeCount++;
            capacity = curCapacity;
        }
    }
    System.out.println("hashMap扩容次数：" + resizeCount);

    System.out.println("---------------- 不初始化hashMap容量 -------------------");
    resizeCount = 0;
    HashMap<Integer, Object> map1 = new HashMap<>();
    Method capacityMethod1 = map1.getClass().getDeclaredMethod("capacity");
    capacityMethod1.setAccessible(true);
    int capacity1 = (int) capacityMethod1.invoke(map1);
    System.out.println("初始容量：" + capacity1);
    for (int i = 0; i < count; i++) {
        map1.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod1.invoke(map1);
        if (curCapacity > capacity1) {
            System.out.println("当前容量：" + curCapacity);
            resizeCount++;
            capacity1 = curCapacity;
        }
    }
    System.out.println("扩容次数：" + resizeCount);
}
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

由于我们无法直接调用hashMap的capacity()方法，因此使用反射来查看每添加一个元素，它的容量变化，以此来监测hashMap的扩容次数。

//使用反射，调用hashMap的capacity()方法
Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
capacityMethod.setAccessible(true);
int capacity = (int) capacityMethod.invoke(map);
1
2
3
4

关于反射，欢迎阅读 Java最强大的技术之一：反射 (opens new window) ，可以对反射机制有个大致的了解。

差点跑偏了，现在回到上面程序的执行结果：

---------------- 初始化hashMap容量为1000000 ------------
初始容量：1048576
当前容量：2097152
hashMap扩容次数：1
---------------- 不初始化hashMap容量 -------------------
初始容量：16
当前容量：32
当前容量：64
当前容量：128
当前容量：256
当前容量：512
当前容量：1024
当前容量：2048
当前容量：4096
当前容量：8192
当前容量：16384
当前容量：32768
当前容量：65536
当前容量：131072
当前容量：262144
当前容量：524288
当前容量：1048576
当前容量：2097152
扩容次数：17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

通过运行结果发现：

  • 设置了初始容量的hashMap，其初始容量并不是我指定的1000000，而是1048576（2^20）
  • hashMap的容量并不是固定不变的，当达到扩容条件时会进行扩容，从 16 扩容到 32、64、128…（Hash 会选择大于当前容量的第一个 2 的幂作为容量）
  • 即使指定了初始容量，而且初始容量是1048576，添加1000000个元素（1000000是小于1048576的）执行完成后，hashMap依然扩容了1次

为什么会酱紫呢？带着上面的三个发现，来看一下HashMap的扩容机制。

# HashMap的扩容机制

先看一下HashMap的几个成员变量：

HashMap成员变量

  • DEFAULT_INITIAL_CAPACITY：默认初始容量是2^4=16
  • DEFAULT_LOAD_FACTOR：默认的装载系数是0.75，是用来衡量HashMap的容量满的程度的
  • transient int size：map中k,v对的数目
  • final float loadFactor：装载系数，默认值为0.75
  • int threshold：调整大小的下一个大小值(容量 × 装载系数)。当实际 k,v 个数超过 threshold 时，HashMap 会将容量扩容

再来看一个方法capacity()：

final int capacity() {
    return (table != null) ? table.length :
        (threshold > 0) ? threshold :
        DEFAULT_INITIAL_CAPACITY;
}
1
2
3
4
5

这是啥？前面不是已经定义了一个size变量了吗？

可以把capacity看成是HashMap这个桶的体积（这个体积是可以变大的），而size是这个桶当前装了多少东西。

桶的容量是由threshold定义的，而且默认容量是2的4次幂，也就是16，源码上是这样写的：

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
1
2
3
4

1 << 4就是左移4位的意思，也就是2^4=16。

那么什么时候扩容呢？这个很容易就能够想到，我们向hashMap这个桶里put数据，当桶的k,v对的数目size快填满桶-逼近capacity时，这个桶将要扩容！

前面的例子已经展示了，hashMap并不是等size到了capacity才扩容，而是在到达capacity的某个值时就扩容了，这个值就是threshold的时候，hashMap进行resize()，而这个，来看源码：

HashMap扩容点源码

部分源码已折叠，主要展示和容量有关的部分。

当size增长到大于threshold的时候，hashMap进行resize()，而threshold = loadFactor * capacity，这样就可以知道hashMap这个桶在什么时候自动扩大它的体积了。

# 真正的避免HashMap扩容

前面分析到，当size > threshold的时候，hashMap进行扩容，利用threshold = loadFactor * capacity这个公式，我们在初始化的时候就有方向了。

首先肯定不能直接设置成loadFactor * capacity，因为这个数有可能不是2的幂，HashMap规定的容器容量必须是2的幂，既然如此，我设置成大于loadFactor * capacity的第一个2的幂的数就行了，可以这样做：

int initCapacity = 1 + (int) (count / 0.75);
HashMap<Integer, Object> map = new HashMap<>(initCapacity);
1
2

1 + (int) (count / 0.75)这个公式来源于HashMap源码：

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

这一段代码真的是天外飞仙！其目的是：根据传入的容量值cap，通过一系列神仙操作计算，得到第一个比他大的 2 的幂并返回。

这些都是二进制的位操作，将数依次向右移位，然后和原值取或。可以随便找一个数代入代码中验证，结果就是第一个比它大的2的幂！

为什么这样做，或许就是因为 无符号右移 >>> 、或运算 | 就是快吧！

# 结果验证

计算容量的公式前面已经搞出来了，现在验证一下对不对：

@SneakyThrows
@Test
public void perfect() {
    int count = 1000000;

    int initCapacity = 1 + (int) (count / 0.75);
    HashMap<Integer, Object> map = new HashMap<>(initCapacity);
    Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
    capacityMethod.setAccessible(true);
    int capacity = (int) capacityMethod.invoke(map);
    System.out.println("jdk hashMap default capacity:" + capacity);
    int resizeCount = 0;
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod.invoke(map);
        if (curCapacity > capacity) {
            System.out.println("当前容量：" + curCapacity);
            resizeCount++;
            capacity = curCapacity;
        }
    }
    System.out.println("hashMap扩容次数：" + resizeCount);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：

扩容次数为0，perfect！

把initCapacity=1333334这个数代入到HashMap的tableSizeFor方法就能算出容量为2097152=2^21了！

# 不想计算初始化容量-仍有他途

Guava是一种基于开源的Java库，其中包含谷歌正在由他们很多项目使用的很多核心库。这个库是为了方便编码，并减少编码错误。这个库提供用于集合，缓存，支持原语，并发性，常见注解，字符串处理，I/O和验证的实用方法。

Guava中有现成的初始化HashMap的方法，它不用我们计算initCapacity，测试一把看看。

先引入Guava包：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>29.0-jre</version>
</dependency>
1
2
3
4
5

测试：

@SneakyThrows
@Test
public void perfectWithGuava() {
    int count = 1000000;

    HashMap<Integer, Object> map = Maps.newHashMapWithExpectedSize(count);
    Method capacityMethod = map.getClass().getDeclaredMethod("capacity");
    capacityMethod.setAccessible(true);
    int capacity = (int) capacityMethod.invoke(map);
    System.out.println("guava hashMap default capacity:" + capacity);
    int resizeCount = 0;
    for (int i = 0; i < count; i++) {
        map.put(i, UUID.randomUUID());
        int curCapacity = (int) capacityMethod.invoke(map);
        if (curCapacity > capacity) {
            System.out.println("当前容量：" + curCapacity);
            resizeCount++;
            capacity = curCapacity;
        }
    }
    System.out.println("hashMap扩容次数：" + resizeCount);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

运行结果：

同样能使HashMap不用扩容！

瞅一下关键代码：

... = Maps.newHashMapWithExpectedSize(count);
1

我猜这个newHashMapWithExpectedSize(int)的源码中肯定也是按照类似于HashMap的return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;这种方法计算的，来看一下：

Guava Maps源码

恭喜你，都能猜对了！

# 小结

  • 设置了初始容量的hashMap，其真实初始容量并不一定是指定的数值，而是HashMap内部计算过的
  • hashMap的容量并不是固定不变的，当达到扩容条件时会进行扩容，从 16 扩容到 32、64、128…（Hash 会选择大于当前容量的第一个 2 的幂作为容量）
  • 不要以为指定了初始容量，hashMap就不扩容了
  • 避免hashMap扩容的方法是传入一个1 + (int) (count / 0.75)计算出的初始值
  • 还可以使用Guava的newHashMapWithExpectedSize(int count)

首发公众号 行百里er ，欢迎老铁们关注阅读指正。

#Java
上次更新: 2022/10/04, 18:14:30
【优雅的避坑】从验证码生成代码的优化到 JVM 栈和堆
【优雅的避坑】不要轻易使用==比较两个Integer的值

← 【优雅的避坑】不要轻易使用==比较两个Integer的值→

最近更新
01
重要数据不能丢！MySQL数据库定期备份保驾护航！
05-22
02
分布式事务解决方案之 Seata（二）：Seata AT 模式
09-09
03
Seata 番外篇：使用 docker-compose 部署 Seata Server（TC）及 K8S 部署 Seata 高可用
09-05
更多文章>
Theme by Vdoing | Copyright © 2020-2023 行百里er | MIT License | 豫ICP备2022020385号-1