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.

The two `2`s are the same element in a comparison-wise sense. — luk2302, Jan 12 '18 at 16:20
It _does_ contain all elements of the specified collection. It contains 2; it contains 1; and it still contains 2. The spec doesn't say "contains all elements in at least the same quantities". — khelwood, Jan 12 '18 at 16:20
Both list **do** contain same elements: `1` and `2`, but different amount of times. — Pshemo, Jan 12 '18 at 16:22
It checks whether every element in the target collection is in this collection. That is all. There is a 2, there is a 1 and there is a 2, so it returns true. — Bernhard Barker, Jan 12 '18 at 16:28
it doesn't mean what is the sequence of object, by getting use of equals() and hashCode(), the containsAll() method checks the all containing Objects of list2 inside list1 in similar way of method contains(Object) one by one, and returns true if all Objects are availble in list1 also, thats it...and as per the definition Returns true if this list contains all of the elements of the specified collection. — ArifMustafa, Jan 12 '18 at 16:32
@Oleksandr Where does one get the code of Java methods? If I press F3 in Eclipse, it shows me bytecode. — Fabian Röling, Jan 12 '18 at 16:33
@ArifMustafa So you mean it goes through all elements of `list2` and if `list1.contains(element)` is true for all of them, then `containsAll` returns true? If yes, can you please write that as an answer? — Fabian Röling, Jan 12 '18 at 16:34
@Fabian http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/AbstractCollection.java?av=f#line-303 — Oleksandr Pyrohov, Jan 12 '18 at 16:40
@Fabian what I mean is describe in tail of my comment, but internally it checks in similar way, this containsAll() method is the first of its kind to check all Objects of other collection util with the current one collection, thats it, but once somewhere I got this from a niche kind of guy long time before that it performs internally that kind of process handled by JVM, and if you were asking about the answer, I think the web is full of example on containsAll(CollectionObject)! — ArifMustafa, Jan 12 '18 at 16:44
@ArifMustafa I don't quite understand what you mean by that. Could you please restructure your sentence? — Fabian Röling, Jan 12 '18 at 16:44
@Oleksandr Interesting, I would have expected some fancy optimisation tricks. Anyway, I'll wait for someone to write an answer, otherwise I'll do it myself based on the comments. — Fabian Röling, Jan 12 '18 at 16:45
@Fabian what I mean is very clear and I also watched the **Oleksandr** suggested URL, that is similar what I illustrated above, now it's on you, that you quite don't understand or don't want to be! — ArifMustafa, Jan 12 '18 at 16:49
@ArifMustafa No, I actually do not understand your second comment, because you wrote one long complex sentence with grammatical errors and weird language. It's not about the content, it's about the language. — Fabian Röling, Jan 12 '18 at 16:53
@Fabian See Dear, probably results are good with complex things. I illustrated above that internally JVM checks the existence of list2 all Objects in list1 one by one through a loop and returns true if all list2 Objects are inside list1(as the OP asked above), it doesn't mean with the sequence but with the Object existence, that's it, Are you Okay now! — ArifMustafa, Jan 12 '18 at 17:01
As I already said, I'm just waiting for an answer saying that, possible with link and quote to/from what Oleksandr wrote, otherwise I'll write my own. — Fabian Röling, Jan 12 '18 at 17:05
The `Collection.contains` method uses `equals`, not `==`. So see https://stackoverflow.com/questions/7520432/what-is-the-difference-between-and-equals-in-java But in this case, because of caching of small `Integer` instances, there is no difference. — Raedwald, Dec 28 '20 at 08:43

score 5 · Accepted Answer · edited Dec 28 '20 at 08:50

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.

Georgy Gobozov · Answer 2 · 2020-12-31T08:19:13.937

You can iterate over one list and remove elements by value from another, then check if another list size == 0. If it is, then that means all second list elements were present in first list at least as many times as in the second list.

 public boolean containsAll(List<Character> source, List<Character> target) {
    
    for (Character character : source) {
        target.remove(character);
        if (target.isEmpty()) {
            return true;
        }
    }

    return target.size() == 0;
}

HashMap will be more efficient if lists are huge

 public static boolean containsAll(List<Character> source, List<Character> target) {
    Map<Character, Long> targetMap = target.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    for (Character character : source) {
        Long count = targetMap.get(character);
        if (count != null) {
            if (count > 1) {
                targetMap.put(character, --count);
            } else {
                targetMap.remove(character);
            }
        }
    }
    return targetMap.isEmpty();
}

Behaviour of "containsAll" with duplicates

2 Answers2