Making ArrayList.containsAll run faster

Whenever using ArrayList, the method containsAll(collection) runs in time \$\mathcal{O}(mn)\$, where \$n\$ is the size of ArrayList and \$m\$ is the length of collection. However, it relies only on equals(Object)-method.

I have this subclass of ArrayList that does the same in time \$\mathcal{O}(n)\$, but relies on hashCode() as well.

My main question, should I do this optimization at expense of adding more requirements?

MyArrayList.java:

```
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
* This class provides a faster {@link #containsAll(java.util.Collection) }
* method.
*
* @author Rodion "rodde" Efremov
* @version 1.6
* @param the actual element type.
*/
public class MyArrayList extends ArrayList {

/**
* Returns {@code true} if this list contains all elements in {@code coll}
* and {@code false} otherwise.
*
* @param coll the collection to check for inclusion in this list.
* @return {@code true} if this list contains all elements in
* {@code coll}:
*/
@Override
public boolean containsAll(Collection coll) {
Set set = new HashSet<>(coll);

for (E element : this) {
if (set.contains(element)) {
set.remove(element);

if (set.isEmpty()) {
return true;
}
}
}

return false;
}

public static void main(final String... args) {
List jdkList = new ArrayList<>();
List myList = new MyArrayList<>();

for (int i = 0; i coll = new ArrayList<>();

for (int i = 0; i < 1000; ++i) {
coll.add(rnd.nextInt(myList.size()));
}

// Uncomment for failing test.
//coll.add(-1);

long ta = System.currentTimeMillis();

boolean result = jdkList.containsAll(coll);

long tb = System.c

Relying on .hashCode() may or may not be faster and may or may not produce the same results as relying on .equals().

Do you already see where this is going? The problem begins when you stop obeying the contract of the interface you implement. I'll quote the javadoc for contains here:


Returns true if this collection contains the specified element. More
formally, returns true if and only if this collection contains at
least one element e such that (o==null ? e==null : o.equals(e)).

This is the formal definition for contains that also applies to containsAll.

Now considering that a programmer seeing a Collection expects the contains method to work based on equals and countering with the fact that yours doesn't you're violating the "Principle Of Least Surprise".

This also leads to code handling collections behaving differently depending on what implementation you pass in, which is never desirable.

In general I think that relying solely on hashCode for contains is a bad idea, even when it's best practice to override hashCode so the resulting hashes of equal objects are equal and those of nonequal objects aren't.

StackExchange Code Review Q#95849, answer score: 7