Java Collections - Quickest way to find if there is a Common element between two Sets

Question

I have two sets from Guava HashMultimap.values().

I need to find out if there's an intersection of these two non-empty sets with the best possible time complexity.

I don't need to know about the common elements, just if there's at least one common element.

I was thinking of using Sets.intersection(), but it has time complexity O(m+n). Can we find out whether there's a common element without creating the entire intersection?

Something like (pseudocode):

set.intersection(set2).any()

The data set is pretty big and this operation happens within a loop, and hence performance is paramount.

Quantic

Answer 1

With the normal JDK, this is just

!Collections.disjoint(set1, set2)

This bails immediately if an element is found in common.

(Although -- for what it's worth -- Sets.intersection is lazier than you realize. It returns a view in constant time, and its isEmpty() method would also bail immediately upon finding the first element in common, so it'd be just as efficient.)

Cindy

Answer 2

You may use Collection#retainAll().

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

Staats

But this is similar to Sets.intersection() right. This operation still creates the complete intersection. – Quantic

@doc_180:- Yes thats right. You may try to go with Louis Wasserman idea. That is what you want probably!! – Staats

I am going to use his idea. Sets.intersection might just work since it is lazy. Thank you for answering. – Quantic

Answer 3

It can be done with the best case time complexity Ω(1) with Stream API.

We can create a stream over the elements from the fist set, and check each element against the second set using anyMatch().

boolean hasIntersection = set1.stream().anyMatch(set2::contains);

Streams are lazy, and anyMatch() - is a short-circuit terminal operation, which means that after the first element for which the predicate passed as argument would be evaluated to true the stream would terminate producing the resulting value, and all remained elements would not be processed.

Pollaiuolo