Java Collection. 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.

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.)

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.