Java 集合包含所有奇怪的行为

Question

我有以下代码，其中我使用 superList 和 subList ，我想检查 subList 实际上是 superList 的子列表。

我的对象没有实现 hashCode 或 equals 方法。我在测试中也创造了类似的情况。当我运行测试时，结果显示 JDK 集合和普通集合的结果之间存在很大的性能差异。运行测试后，我得到以下输出。

Java Collection API 8953 毫秒的时间流逝结果为真 Commons Collection API 的时间流逝 78 毫秒 &结果是 true

我的问题是为什么 java collection 在处理 containsAll 操作时如此缓慢。我在那里做错了什么吗？我无法控制我从遗留代码中获取的集合类型。我知道如果我使用 HashSet 作为 superList，那么使用 JDK containsAll 操作我会获得很大的性能提升，但不幸的是这对我来说是不可能的。

package com.mycompany.tests;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;

import org.apache.commons.collections.CollectionUtils;
import org.junit.Before;
import org.junit.Test;

public class CollectionComparison_UnitTest {

    private Collection<MyClass> superList = new ArrayList<MyClass>();
    private Collection<MyClass> subList = new HashSet<MyClass>(50000);

    @Before
    public void setUp() throws Exception {

        for (int i = 0; i < 50000; i++) {
            MyClass myClass = new MyClass(i + "A String");
            superList.add(myClass);
        subList.add(myClass);
    }

    @Test
    public void testIt() {
        long startTime = System.currentTimeMillis();
        boolean isSubList = superList.containsAll(subList);
        System.out.println("Time Lapsed with Java Collection API "
                + (System.currentTimeMillis() - startTime)
                + " MilliSeconds & Result is " + isSubList);

        startTime = System.currentTimeMillis();
        isSubList = CollectionUtils.isSubCollection(subList, superList);
        System.out.println("Time Lapsed with Commons Collection API "
                + (System.currentTimeMillis() - startTime)
                + " MilliSeconds & Result is " + isSubList);
    }   
}

class MyClass {
    String myString;

    MyClass(String myString) {
        this.myString = myString;
    }

    String getMyString() {
        return myString;
    }

}

Answer 1

您至少应该以相反的顺序尝试测试。您的结果很可能只是表明 JIT 编译器做得很好:-)

Answer 2

不同的算法：

ArrayList.containsAll()提供O(N*N)，而CollectionUtils.isSubCollection()提供O(N) +N+N）。

Answer 3

ArrayList.containsAll 继承自 AbstractCollection.containsAll，是一个检查行中所有元素的简单循环。每一步都是缓慢的线性搜索。我不知道 CollectionUtils 是如何工作的，但是比使用简单循环更快地完成它并不难。将第二个列表转换为 HashSet 是肯定的胜利。对两个列表进行排序并并行浏览它们可能会更好。

编辑：

CollectionUtils 源代码 说得很清楚。他们将这两个集合转换为“基数映射”，这对于许多操作来说是一种简单而通用的方法。在某些情况下，这可能不是一个好主意，例如，当第一个列表为空或非常短时，您实际上会浪费时间。在你的情况下，与 AbstractCollection.containsAll 相比，这是一个巨大的胜利，但你可以做得更好。

几年后的附录

OP 写道

我知道如果我使用 HashSet 作为 superList，那么使用 JDK containsAll 操作我会获得很大的性能提升，但不幸的是这对我来说是不可能的。

那是错误的。没有 hashCode 和 equals 的类从 Object 继承它们，并且可以与 HashSet 一起使用 > 一切都很完美。除了每个对象都是唯一的，这可能是无意的和令人惊讶的，但OP的测试 superList.containsAll(subList) 做了完全相同的事情。

所以快速的解决方案是

new HashSet<>(superList).containsAll(subList)