Behaviour of "containsAll" with duplicates

Question

The official documentation (archive) of containsAll only says "Returns true if this list contains all of the elements of the specified collection.". However, I just tested this:

List<Integer> list1 = new ArrayList<>();
list1.add(1);
list1.add(2);
list1.add(1);
List<Integer> list2 = new ArrayList<>();
list2.add(2);
list2.add(1);
list2.add(2);
System.out.println(list1.containsAll(list2));

The result is true, even though list1 does not contain a second 2.

So what is the official, completely defined behaviour of containsAll? Does it act as if all duplicates were removed from both lists? I remember reading somewhere that it can cause problems with duplicates, but I don't know the exact case.

Answer 1

The List.containsAll method behaves just as documented: it returns true if all the elements of the given collection belong to this collection, false otherwise. The docs say nothing about the order or cardinality of the elements.

The documentation for containsAll does not explicitly say how it determines whether an element belongs to the Collection. But the documentation for contains (which is implicitly specifying the semantics of "contains") does: it uses equals. Again, no mention of cardinality.

The containsAll method is declared in the Collection interface and re-declared in the List and Set interfaces, but it's first implemented in the Collection hierarchy by the AbstractCollection class, as follows:

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

As far as I know, this implementation is inherited by most common classes that implement the Collection interface in the Java Collections framework, except for the CopyOnWriteArrayList class and other specialized classes, such as empty lists and checked and immutable wrappers, etc.

So, if you look at the code, you'll see that it fulfils the docs you quoted:

Returns true if this list contains all of the elements of the specified collection.

In the docs of the AbstractList.containsAll method, there's also an @implSpec tag, which says the following:

@implSpec

This implementation iterates over the specified collection, checking each element returned by the iterator in turn to see if it's contained in this collection. If all elements are so contained true is returned, otherwise false.

With regard to possible optimizations, they're all relayed to the different implementations of the contains method, which is also implemented by AbstractCollection in a naive, brute-force-like way. However, contains is overriden in i.e. HashSet to take advantage of hashing, and also in ArrayList, where it uses indexes, etc.