What is the best way get the symmetric difference

Question

I'm wondering if there is a quick/clean way to get the symmetric difference between two sets ?

I have:

Set<String> s1 = new HashSet<String>();
s1.add("a");
s1.add("b");
s1.add("c");

Set<String> s2 = new HashSet<String>();
s2.add("b");

I need something like:

Set<String> diff = Something.diff(s1, s2);
// diff would contain ["a", "c"]

---

Just to clarify I need the symmetric difference.

Answer 1

Loop through one set and compare.

It's only O(n) to loop through one of the sets. Consider this code:

for (String key: oldSet) {
    if (newSet.contains(key))
        newSet.remove(key);
    else
        newSet.add(key);
}

And the newSet will now contain only the unique entries from both sets. It's fast, because you only need to loop through the elements in one of the sets and you don't have to create sets unless you explicitly need a copy.

Answer 2

public class Practice {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        set1.add(1);
        set1.add(4);
        set1.add(7);
        set1.add(9);

        set2.add(2);
        set2.add(4);
        set2.add(5);
        set2.add(6);
        set2.add(7);

        symmetricSetDifference(set1, set2);
    }

    public static void symmetricSetDifference(Set<Integer>set1, Set<Integer>set2){
        //creating a new set
        Set<Integer> newSet = new HashSet<Integer>(set1);
        newSet.removeAll(set2);
        set2.removeAll(set1);
        newSet.addAll(set2);
        System.out.println(newSet);
    }

}

Answer 3

Java 8 Solution

We can write two utility methods (for java 8 and prior) in some class SetUtils (say) as:

public static <T> Set<T> symmetricDifferenceJava8(final Set<T> setOne, final Set<T> setTwo) {
    Set<T> result = new HashSet<>(setOne);
    setTwo.stream().filter(not(resultSet::add)).forEach(resultSet::remove);
    return result;
}

public static <T> Set<T> symmetricDifference(final Set<T> setOne, final Set<T> setTwo) {
    Set<T> result = new HashSet<T>(setOne);
    for (T element : setTwo) {
        if (!result.add(element)) {
            result.remove(element);
        }
    }
    return result;
}

public static <T> Predicate<T> not(Predicate<T> t) {
    return t.negate();
}

The method add returns false if element already exists and method negate is used to negate the predicate.

Java 11

We have a Predicate#not method for predicate in Java 11 and can use it as:

public static <T> Set<T> symmetricDifferenceJava11(final Set<T> setOne, final Set<T> setTwo) {
    Set<T> result = new HashSet<>(setOne);
    setTwo.stream().filter(Predicate.not(resultSet::add)).forEach(resultSet::remove);
    return result;
}

Answer 4

s1.addAll(s2);
s1.removeAll(s2);

Should work.

Answer 5

You can use some functions from the Google Guava library (which is really great, I strongly recommend it!):

Sets.difference(s1, s2);
Sets.symmetricDifference(s1, s2);

Javadocs for difference() and symmetricDifference()

symmetricDifference() does exactly what you are asking for, but difference() is also often helpful.

Both methods return a live view, but you can for example call .immutableCopy() on the resulting set to get a non-changing set. If you don't want a view, but need a set instance you can modify, call .copyInto(s3). See SetView for these methods.

Answer 6

If you can use Apache-Commons Collections, you are looking for CollectionUtils.disjunction(Collection a, Collection b). It returns the symmetric difference of both Collections.

If not, substract (removeAll) the intersection (retainAll) of both sets to the union of both (addAll):

Set<String> intersection = new HashSet<String>(set1);
intersection.retainAll(set2);

Set<String> difference = new HashSet<String>();
difference.addAll(set1);
difference.addAll(set2);
difference.removeAll(intersection);