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

I am trying to optimize a piece of code which compares elements of list.

Eg.

public void compare(Set<Record> firstSet, Set<Record> secondSet){
    for(Record firstRecord : firstSet){
        for(Record secondRecord : secondSet){
            // comparing logic
        }
    }
}

Please take into account that the number of records in sets will be high.

Thanks

Shekhar

firstSet.equals(secondSet)

It really depends on what you want to do in the comparison logic... ie what happens if you find an element in one set not in the other? Your method has a void return type so I assume you'll do the necessary work in this method.

More fine-grained control if you need it:

if (!firstSet.containsAll(secondSet)) {
  // do something if needs be
}
if (!secondSet.containsAll(firstSet)) {
  // do something if needs be
}

If you need to get the elements that are in one set and not the other.
EDIT: set.removeAll(otherSet) returns a boolean, not a set. To use removeAll(), you'll have to copy the set then use it.

Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);

If the contents of one and two are both empty, then you know that the two sets were equal. If not, then you've got the elements that made the sets unequal.

You mentioned that the number of records might be high. If the underlying implementation is a HashSet then the fetching of each record is done in O(1) time, so you can't really get much better than that. TreeSet is O(log n).

If you simply want to know if the sets are equal, the equals method on AbstractSet is implemented roughly as below:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return containsAll(c);
    }

Note how it optimizes the common cases where:

the two objects are the same
the other object is not a set at all, and
the two sets' sizes are different.

After that, containsAll(...) will return false as soon as it finds an element in the other set that is not also in this set. But if all elements are present in both sets, it will need to test all of them.

The worst case performance therefore occurs when the two sets are equal but not the same objects. That cost is typically O(N) or O(NlogN) depending on the implementation of this.containsAll(c).

And you get close-to-worst case performance if the sets are large and only differ in a tiny percentage of the elements.

UPDATE

If you are willing to invest time in a custom set implementation, there is an approach that can improve the "almost the same" case.

The idea is that you need to pre-calculate and cache a hash for the entire set so that you could get the set's current hashcode value in O(1). Then you can compare the hashcode for the two sets as an acceleration.

How could you implement a hashcode like that? Well if the set hashcode was:

zero for an empty set, and
the XOR of all of the element hashcodes for a non-empty set,

then you could cheaply update the set's cached hashcode each time you added or removed an element. In both cases, you simply XOR the element's hashcode with the current set hashcode.

Of course, this assumes that element hashcodes are stable while the elements are members of sets. It also assumes that the element classes hashcode function gives a good spread. That is because when the two set hashcodes are the same you still have to fall back to the O(N) comparison of all elements.

You could take this idea a bit further ... at least in theory.

WARNING - This is highly speculative. A "thought experiment" if you like.

Suppose that your set element class has a method to return a crypto checksums for the element. Now implement the set's checksums by XORing the checksums returned for the elements.

What does this buy us?

Well, if we assume that nothing underhand is going on, the probability that any two unequal set elements have the same N-bit checksums is 2^-N. And the probability 2 unequal sets have the same N-bit checksums is also 2^-N. So my idea is that you can implement equals as:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return checksums.equals(c.checksums);
    }

Under the assumptions above, this will only give you the wrong answer once in 2^-N time. If you make N large enough (e.g. 512 bits) the probability of a wrong answer becomes negligible (e.g. roughly 10^-150).

The downside is that computing the crypto checksums for elements is very expensive, especially as the number of bits increases. So you really need an effective mechanism for memoizing the checksums. And that could be problematic.

And the other downside is that a non-zero probability of error may be unacceptable no matter how small the probability is. (But if that is the case ... how do you deal with the case where a cosmic ray flips a critical bit? Or if it simultaneously flips the same bit in two instances of a redundant system?)

There is a method in Guava Sets which can help here:

public static <E>  boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}

There's an O(N) solution for very specific cases where:

the sets are both sorted
both sorted in the same order

The following code assumes that both sets are based on the records comparable. A similar method could be based on on a Comparator.

    public class SortedSetComparitor <Foo extends Comparable<Foo>> 
            implements Comparator<SortedSet<Foo>> {

        @Override
        public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) {
            Iterator<Foo> otherRecords = arg1.iterator();
            for (Foo thisRecord : arg0) {
                // Shorter sets sort first.
                if (!otherRecords.hasNext()) return 1;
                int comparison = thisRecord.compareTo(otherRecords.next());
                if (comparison != 0) return comparison;
            }
            // Shorter sets sort first
            if (otherRecords.hasNext()) return -1;
            else return 0;
        }
    }

You have the following solution from https://www.mkyong.com/java/java-how-to-compare-two-sets/

public static boolean equals(Set<?> set1, Set<?> set2){

    if(set1 == null || set2 ==null){
        return false;
    }

    if(set1.size() != set2.size()){
        return false;
    }

    return set1.containsAll(set2);
}

Or if you prefer to use a single return statement:

public static boolean equals(Set<?> set1, Set<?> set2){

  return set1 != null 
    && set2 != null 
    && set1.size() == set2.size() 
    && set1.containsAll(set2);
}

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

Related

Recent Posts