Java HashMap 保留所有时间复杂度

Question

我测试了HashMap的retainAll方法来测试JMH哪个更快。

两个HashMap A、B

• 尺寸：A > B，A：300~400，B：100~200
• 大部分 B 元素都在 A 中，所以 B - A 大概是 10~20 个，很小

测试：获取两个 HashMap 的交集

1. A.keySet().retainAll(B.keySet())

2. B.keySet().retainAll(A.keySet())

//JMH 
@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)

private Map<String, MyClass> bigOne, smallOne;

private final int testIteration = 1000;

@Benchmark
public void smallToBig(){
    for(int i=0;i<testIteration;i++){
        smallOne.keySet().retainAll(bigOne.keySet());
    }
}

@Benchmark
public void bigToSmall(){
    for(int i=0;i<testIteration;i++){
        bigOne.keySet().retainAll(smallOne.keySet());
    }
}

RetainAll方法使用AbstractMap中的contains，因此HashMap contains是O(1)。所以迭代 Map 将占用大部分性能，意味着小迭代应该更快。

我预计前者会更快，但实际结果不同

我尝试了很多时间，但得到了相同的结果。你能告诉我为什么 Big.retainAll(Small) 更快吗？

感谢您的帮助。

Answer 1

在这种情况下，

retainAll(set)

方法是通过迭代

set

的元素并将它们从目标映射的键集中删除来实现的。当然，当

O(N)

的大小为

N

时，这就是

set

。