没用好HashMap，性能影响这么大

没用好HashMap，性能影响这么大 前言

Java中的HashMap是一种(K,V)数据结构，在java中也是采用数组+链接的数据结构保存数据。

在使用HashMap的时候，可能关注到下面这两个点：

1. 装载因子
2. 扩容

装载因子

装载因子是针对HashMap中hash冲突对性能影响和空间消耗的一种权衡，表示HashMap的底层数组还剩余多少空位的时候进行扩容。

装载因子越大，表示HashMap中的可用空间越少的时候才进行扩容，也就越容易出现hash冲突；装载因子越小，HashMap的空闲位置还有很多就要扩容，hash冲突的概率也大大减小。

打个比方：Java的HashMap默认装载因子是0.75，如果元素数超过容量的75%，就要扩容了。

扩容

HashMap容易不足时会进行扩容，每次是之前的2倍。

使用场景 场景说明

因为查询平均时间复杂度是O(1)，所以在实际开发中缓存使用会相对多点。

在业务开发中，使用HashMap其实很少关注性能的，更多情况下我都是new HashMap<>()就完事了，但是在关注性能场景的情况下，如果没有使用好，这真的很糟糕。

以一个实际场景来展示一下它的性能问题：

在2021年9月份开启了2021第二届云原生编程挑战赛1：针对冷热读写场景的RocketMQ存储系统设计https://tianchi.aliyun.com/competition/entrance/531922/information我写了多个版本的实现，以某个版本使用的HashMap在本次举例说明。

当在文件中写入一条消息的时候，会保存它的物理位置，即文件中的写入位置，当读取这条消息的时候，可以快速定位。

所以，我考虑使用HashMap来保存消息的索引信息，key是这条消息的偏移量，value是这条消息的物理位置。

先看一下内存信息：

•  JVM堆内存6G
• 共写入125G数据
• 每条消息大小100B-17KB(随机）

我考虑用HashMap来保存这个消息的索引信息是因为：

HashMap基于JVM堆内存，存取非常快。

假定每条消息100B，共有125*1024M*1024kB*1024B/100B=1342177280条消息，如果每个索引8B（key: 消息偏移, 占用4B，value: 物理位置，占用4B），这么多条消息共需要使用10G内存。

如果每条消息17KB，索引信息占用内存大概不到100M（将近60M吧）。

因为消息大小是随机的，所以消息的索引大小 就在100M到10G之间。实际内存占用肯定大于这个区间，因为HashMap的每个Node是个链表节点，前趋后继指针等都占用内存。

我用HashMap试一下，看6G堆内存下，索引信息全放堆内存是否导致内存溢出，事实证明，没有溢出，而且多次测试都是没有出现内存不足。

那我就假定，这个HashMap占用内存了2-5个G吧。如果真的溢出再持久化到文件中，按需加载。

索引这里实现了两个版本，第一个版本是用HashMap做缓存。但是考虑到内存可能溢出，所以另一个版本使用了傲腾持久内存来保存索引信息。

经过对比，试了几次，版本2比版本1可能快了200秒左右（只是索引存储的不一样）。这个版本性能不太好，所以只是索引调整，时间上差距就这么明显（也不排除内存占用多，GC更频繁导致）。

按理论上来说直接在堆内存存取速度应该最快才对呀。

分析一下我当时写的影响性能的地方：

代码分析

    // 逻辑偏移表，每条队列相对偏移的物理位置，使用逻辑偏移是因为int只有4个字节，节省内存
    private Map> logicOffsetTable = new HashMap<>(1, 1.0f);

    @Override public void write(int queueId, long offset, int pos) {
        // 记录索引信息
        Map logicOffset = logicOffsetTable.get(queueId);
        if (logicOffset == null) {
            logicOffset = new HashMap<>(8, 1.0f);
            logicOffsetTable.put(queueId, logicOffset);
        }
        logicOffset.put((int) (offset - offsetBoundMap.get(queueId).min), pos);
    }

    @Override public int pos(int queueId, long offset) {
        Map logicOffset = logicOffsetTable.get(queueId);
        if (logicOffset == null) {
            return -1;
        }
        Integer logicOff = (int) (offset - offsetBoundMap.get(queueId).min);
        Integer pos = logicOffset.get(logicOff);
        return pos == null ? -1 : pos;
    }

前置说明：这个索引的缓存对象是每个topic一个实例（无锁实现写法）

我构造HashMap的时候，指定了初始空间为1，装载因子1.0：

new HashMap<>(1, 1.0f);

总之这里是为了节约内存考虑，要知道，最大的情况下占用是10G多，远远超于分配的6G堆内存，我也不清楚这样写堆内存是否够用。所以呢就把装载因子设置为1.0,没敢设置更大了，要不hash冲突太厉害了。装载因子尽量大，减少闲置内存占用。

初始空间设置为1是因为，不知道每个topic的消息量有多少，如果初始值不大，减少的几次扩容对性能影响可以忽略，如果设置特别大，担心有的内存浪费，使用不了这么多空间。

所以这里有两个特别影响性能的地方：

• 扩容

因为可能索引信息在几百M的时候扩容，这个数据量大的时候，复制这么多数据，对性能影响还是挺大的。

• hash冲突

hash冲突应该是这里最影响性能的，主要原因是，HashMap底层数据结构是链表，然后我们保存的每个元素的数据其实都很小，只有8个字节，结果就是如果hash冲突太厉害，是要遍历链表的，无论是插入还是查询，在从HashMap中同一个hash槽找合适位置的时候，因为链表的地址不连续，cpu 缓存完全就失效了，导致查询在硬件上的优化都没有用了。

另一个不适合在这里使用HashMap的原因是，保存的索引信息内存占用太小，每个HashMap的node节点的指针占用的内存，和我们实际有效数据占用的内存差不多大小，内存损耗也比较严重。

总结

经过实际场景对比，如果要用好HashMap，注意以下几点：

1. 如果可以预测空间占用大小并且内存充裕的情况，构造HashMap的时候，指定初始化空间大小，尽量避免扩容
2. HashMap对于空间占用小K,V数据，因为每个节点还有指针等相关属性占用，所以额外内存开销还是挺大的
3. HashMap的底层存储结构是链表，会导致cpu缓存失效
4. 如果需要考虑空间占用，装载因子可以设置大点，但是要考虑hash冲突带来的影响

最后，日常工程中，如果数据量不大，个人感觉用起来还是随意就行，不用太讲究了。