java - 为什么代码使用较小的列表实例化哈希集？

Question

我正在检查 org.apache.commons.collections4.ListUtils 类，并注意到代码如下:

public static <e> List<e> intersection(final List<? extends E> list1, final List<? extends E> list2) {
        final List<e> result = new ArrayList<>();

        List<? extends E> smaller = list1;
        List<? extends E> larger = list2;
        if (list1.size() > list2.size()) {
            smaller = list2;
            larger = list1;
        }

        final HashSet<e> hashSet = new HashSet<>(smaller);

        for (final E e : larger) {
            if (hashSet.contains(e)) {
                result.add(e);
                hashSet.remove(e);
            }
        }
        return result;
    }

我们知道为什么他们将较小的列表转换为哈希集并循环较大的列表吗？谢谢。

Answer 1

假设较小的列表有 M 个条目，较大的列表有 N 个条目，并且 Set 为您提供基本操作(添加、包含)的恒定时间访问。

如果我使用 Big O 表示法对该算法进行分类，则运行时将为 O(M+N) 和额外的内存消耗 O(M)。

如果我们用较大的列表切换较小的列表，则有 2 个观察结果:

• 额外的内存使用量将增加到 O(N)，因此这是不这样做的原因之一。
• 理论上，运行时不会改变，仍然是 O(M+N)，但实际上，创建一组 N 条目将是比迭代更繁重的操作。

如果您想验证这些假设，请尝试 JMH这是一个在 Java 中运行微基准测试的工具。

我使用 M=1000、N=10000 对此进行了不科学的基准测试。这就是我得到的:

Benchmark               (size)  Mode  Cnt       Score      Error  Units
IntersectBench.larger    10000  avgt    5  190481.075 ± 6488.649  ns/op
IntersectBench.smaller   10000  avgt    5  125997.594 ± 1616.975  ns/op

有趣的值是在 Score 中，这里越小越好。 IntersectBench.smaller 与上面的算法相同，IntersectBench.larger 是交换列表的算法，并且删除了交换列表的优化。正如您所看到的，未优化的版本慢了 50%。