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

Question

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

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

使用 Java Collection API 的时间流逝 8953 MilliSeconds & 结果为真 使用 Commons Collection API 的时间流逝 78 MilliSeconds & 结果为真

我的问题是为什么 java collection 在处理 containsAll 操作时如此缓慢。我在那里做错了吗？我无法控制从遗留代码中获得的集合类型。我知道如果我对 superList 使用 HashSet 那么我会使用 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

不同的算法：

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