为何HashMap大集合retainAll小集合比反向操作更快？JMH测试存疑

核心问题：测试代码的设计缺陷 #

你的JMH测试代码存在致命问题：未在每次迭代前重置集合状态。

bigOne和smallOne是Scope.Benchmark级别的状态对象，整个测试周期内仅初始化一次。第一次调用retainAll后，原集合会被直接修改为交集集合（仅保留双方共有的元素），后续999次循环都是在这个已经缩小的集合上执行retainAll——此时集合中几乎没有元素需要删除，操作开销极低。

这种设计导致测试结果完全无法反映原始大小集合执行retainAll的真实性能，反而混合了首次修改集合的开销与后续无意义的重复操作开销，最终出现反直觉的结果。

正确逻辑下的性能分析 #

先明确retainAll的底层实现（基于JDK的AbstractCollection）：

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

核心逻辑：迭代调用方集合的所有元素，检查是否存在于传入集合中，不存在则删除。结合HashMap的特性（containsKey为O(1)），两种操作的时间复杂度为：

1. 大集合调用retainAll(小集合)：迭代300_{400个元素，删除220}320个元素（因为B中仅10_{20个元素不在A中，A中不在B里的元素数量为300}400 - (100_200-1020)），总操作量约为520~720次。
2. 小集合调用retainAll(大集合)：迭代100_{200个元素，仅删除10}20个元素，总操作量约为110~220次。

显然，在测试逻辑正确的前提下，小集合调用retainAll的性能应该更优。

修复测试代码的建议 #

要得到真实的测试结果，需要在每次测试迭代前重置集合状态，比如使用@Setup(Level.Invocation)注解在每次基准方法调用前重新初始化集合：

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Fork(value = 1, jvmArgs={"-Xms4G", "-Xmx4G"})
@Warmup(iterations = 5, time = 5)
@Measurement(iterations = 10, time = 5)
public class RetainAllBenchmark {

    private Map<String, MyClass> bigOne, smallOne;
    private final int bigSize = 350;
    private final int smallSize = 150;
    private final int smallNotInBig = 15;

    @Setup(Level.Invocation)
    public void setup() {
        // 重新初始化大集合
        bigOne = new HashMap<>();
        for (int i = 0; i < bigSize; i++) {
            bigOne.put("key_" + i, new MyClass());
        }
        // 重新初始化小集合：大部分元素在大集合中，仅smallNotInBig个不在
        smallOne = new HashMap<>();
        // 添加存在于大集合中的元素
        for (int i = 0; i < smallSize - smallNotInBig; i++) {
            smallOne.put("key_" + i, new MyClass());
        }
        // 添加不存在于大集合中的元素
        for (int i = bigSize; i < bigSize + smallNotInBig; i++) {
            smallOne.put("key_" + i, new MyClass());
        }
    }

    @Benchmark
    public void smallToBig() {
        smallOne.keySet().retainAll(bigOne.keySet());
    }

    @Benchmark
    public void bigToSmall() {
        bigOne.keySet().retainAll(smallOne.keySet());
    }
}

修复后，每次基准方法调用都会使用原始大小的集合执行retainAll，此时测试结果会符合你的预期：小集合调用retainAll的性能更优。

内容的提问来源于stack exchange，提问作者박효상