How to efficiently compare Sets? [duplicate]

Question

This question already has an answer here:

• What is the fastest way to compare two sets in Java? 9 answers

Given two Sets: how to compare them efficiently in Java?

• (a) keep them as Lists, sort them and compare them. (Comparable)
• (b) keep them as Sets and compare the hashCode of the Sets?

background:

many comparisons need to be done Sets are small (usually < 5 elements per set).

Answer 1

Assuming you want to do a comparison whether set1 has exactly the same elements of set2.

set1.equals(set2) and also set2.equals(set1) as to make sure both are exactly the same.

Answer 2

If you have two HashSets, comparing them by Set.equals will be O(n) because only one set needs to be iterated through, and the other will be checked by contains, which is itself O(1).

Note that for sets as small as yours the difference between O(n) and O(n²) is neglible, so even the naïvest approaches will yield good performance.

Answer 3

The proper way to compare two sets is to use the equals method. I would not worry about performance unless you have proven that this is a part of your code that is causing performance issue (which I doubt). And considering the size of your sets (5 elements) this will be very fast (probably sub millisecond).

keep them as lists, sort them and compare them. (comparable)

will certainly be slower as you will need to copy the elements, sort them and compare.

keep them as sets and compare the hashcode of the sets?

if 2 sets are equal (have the same content) they will have the same hashcode. The reciprocal is not true: 2 sets with different content may have the same hashcode. Also note that for a HashSet for example, the hashcode is calculated by iterating over all the elements so it is not a free operation.

Answer 4

What's wrong with equals? The docs states that it returns true if both are of same size and if containsAll() returns true, sounds pretty efficient to me.

In any case, you should never compare the hashcode to test for equality, two different objects might have the same hashcode.

Update: As noted in the comments (and in assylias' answer) the hashcode can be used as part of the equality test logic (different hashcodes imply different objects - but not the reverse). My remark above means that the hashcode alone is not (in general) enough.