堆转储实例重复检测的比对结果高效缓存优化方案咨询

现有实现的核心内存痛点 #

当前采用的Map<Long, Map<Long, Boolean>>嵌套结构，在存储大量实例比对结果时内存效率极低，核心开销来源：

• 两层独立HashMap的结构冗余：每个内层Map都需要单独维护哈希表数组、负载因子阈值、大小统计、修改计数等固定元数据，单这部分就会产生大量无意义的内存占用
• 包装对象的额外开销：每个Long类型的键、Boolean类型的值都是独立的堆对象，每个对象至少包含16字节的对象头，单个键值对的实际内存开销是原始二进制数据的5~10倍
• 逻辑冗余：现有代码已经通过强制ID排序，将无向的比对对(a,b)转换为固定顺序的唯一有序对(小ID, 大ID)，嵌套Map的分层索引本质没有带来逻辑收益，只是多了一层完全没必要的哈希跳转。

可落地的分层优化方案 #

按照内存优化的投入产出比，从易落地、无逻辑改动的方案开始，到极致内存效率的方案依次递进：

1. 单层Map存储双长复合键 #

完全保留现有强制排序ID的逻辑，将两个long类型的ID打包为一个不可变的复合键，彻底移除嵌套Map的结构：

• 实现一个零冗余的有序长对键类，所有字段使用原始long类型，不做自动装箱，构造时自动完成ID排序，保证无序的比对对永远生成同一个键对象
• 用单层Map<有序长对键, Boolean>替换原来的两层嵌套结构，缓存命中、miss的统计逻辑完全不需要改动
• 内存收益：相比原有实现，单这一步就能将内存占用降到原来的1/3~1/5。
  示例代码：

// 基于JDK16+ Record的极简实现，无冗余字段
record OrderedInstancePair(long smallerId, long largerId) {
    // 紧凑构造器中完成ID排序，保证无向对的键唯一性
    public OrderedInstancePair {
        if (smallerId > largerId) {
            long temp = smallerId;
            smallerId = largerId;
            largerId = temp;
        }
    }

    @Override
    public int hashCode() {
        // 组合两个long的哈希值，避免拆箱
        return Long.hashCode(smallerId) * 31 + Long.hashCode(largerId);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof OrderedInstancePair(long first, long second))) return false;
        return first == smallerId && second == largerId;
    }
}

// 替换原嵌套Map的单层缓存
private final Map<OrderedInstancePair, Boolean> cache = new HashMap<>();

2. 基于位存储替换Boolean对象开销 #

比对结果只有两个状态（重复/不重复），完全不需要存储Boolean包装对象，每个结果只需要1位二进制位就能表示：

• 拆分两个独立的位集合：一个用来记录所有「已比对且结果为重复」的有序对，另一个用来记录所有「已比对且结果为不重复」的有序对
• 查询逻辑调整为：先判断有序对是否存在于任意一个位集合中，存在则根据所属集合返回对应的布尔结果（缓存命中），不存在则返回空（缓存miss）
• 内存收益：这一步会消除所有Boolean对象的开销，存储密度相比存Boolean的Map提升至少64倍。
  注意：这部分的位集合可以采用原生的BitSet，或者针对稀疏ID优化的Roaring算法位集，不需要存储具体的键值对映射，仅通过位的存在性标记结果

3. 稀疏场景下的极致内存优化 #

heap dump导出的instanceId通常是顺序分配的连续/近连续值，可以进一步移除哈希表结构的开销：

• 按照排序后的小ID做一维数组索引，每个小ID对应一个独立的位集，用来记录所有和它比对过的大ID，以及对应的比对结果
• 这种结构完全没有哈希表的空槽位、元数据开销，存储密度接近100%，相比HashMap结构内存效率再提升40%以上。

落地注意事项 #

• 所有缓存的键值仅存储原始long类型的instanceId，不要持有任何InstanceDump对象的引用，避免缓存持有不必要的对象引用造成内存泄漏
• 保留现有强制ID排序的逻辑，这是所有优化方案能够成立的核心基础，不需要做额外的对称存储
• 原有缓存命中率、miss率的统计逻辑可以完全复用，不需要随底层存储结构改动调整。

内容的提问来源于stack exchange，提问作者user7826451