Java Collections containsAll Weired Behavior

Question

I have following code , where I am using superList and subList , I want to check that subList is actually a subList of superList.

My objects do not implement hashCode or equals methods. I have created the similar situation in the test. When I run the test then the result show very big performance difference between results from JDK collection and common collections.After Running the test I am getting following output.

Time Lapsed with Java Collection API 8953 MilliSeconds & Result is true Time Lapsed with Commons Collection API 78 MilliSeconds & Result is true

My question is why is java collection , so slow in processing the containsAll operation. Am I doing something wrong there? I have no control over collection Types I am getting that from legacy code. I know if I use HashSet for superList then I would get big performance gains using JDK containsAll operation, but unfortunately that is not possible for me.

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

Different algorithms:

ArrayList.containsAll() offers O(N*N), while CollectionUtils.isSubCollection() offers O(N+N+N).