46

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.

4
  • 3
    Quick&easy: You could write Set<String> diff = new HashSet<String>(s1); diff.removeAll(s2);
    – misberner
    Commented Nov 9, 2011 at 11:51
  • 4
    @polkageist: it will fail for S1={"a","b","c"},S2={"b","d"}. result should be {"a","c","d"}
    – amit
    Commented Nov 9, 2011 at 11:53
  • 3
    If by "difference" (cf. secure.wikimedia.org/wikipedia/en/wiki/…) the OP meant symmetric difference, then you're right. However, you can get this as either (A - B) + (B - A), or (A + B) - (A cap B). I don't know any quicker way in java to implement that.
    – misberner
    Commented Nov 9, 2011 at 11:57
  • 2
    Java 8 and Java 11 : stackoverflow.com/a/52268640/1216775 Commented Sep 11, 2018 at 4:26

8 Answers 8

52

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.

4
  • 1
    Having just read the javadoc for symetricDifference(), I'm a bit concerned about this statement "Results are undefined if set1 and set2 are sets based on different equivalence relations (as HashSet, TreeSet, and the keySet of an IdentityHashMap all are)." That makes it sound like the results are undefined for the OP's case (and the Sets.symmetricDifference() method seems not so useful.
    – Gus
    Commented Jun 16, 2013 at 13:58
  • 2
    @Gus The JavaDoc wants to say that the results are undefined, if you use the method with two different sets that use different equivalence relations, for example, computing the difference between a HashSet and a TreeSet may be problematic. Using the method with two HashSets, or two TreeSets, etc. is fine. Commented Jun 16, 2013 at 16:32
  • 1
    @Gus Furthermore it is also fine if you use the method with a HashSet and a TreeSet, if the compareTo() method and the equals() method of the elements agree with each other (which is strongly recommended by their documentation). So only in special cases the method cannot guarantee that the difference is computed correctly, in most practical cases it will work fine. Commented Jun 16, 2013 at 16:34
  • I had the same concern about that "results are undefined" statement. Thank you @PhilippWendler for clarifying this!
    – datv
    Commented Dec 3, 2017 at 14:48
35

You want the symmetric difference.

public static <T> Set<T> diff(final Set<? extends T> s1, final Set<? extends T> s2) {
    Set<T> symmetricDiff = new HashSet<T>(s1);
    symmetricDiff.addAll(s2);
    Set<T> tmp = new HashSet<T>(s1);
    tmp.retainAll(s2);
    symmetricDiff.removeAll(tmp);
    return symmetricDiff;
}

If you want a library, Apache Commons CollectionUtils has

CollectionUtils.disjunction(s1, s2)

which returns a non-generic Collection.

and Guava Sets has

Sets.symmetricDifference(s1, s2)

which returns an unmodifiable Set as a generic Sets.SetView.

Guava is a bit more modern, supporting generics, but either of these will work.

2
9

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);
4

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.

1
  • 1
    Note that this is O(n) for HashSet with no collision only. For TreeSets, all three operations add(key), contains(key) and remove(key) would require searching the tree once, i.e. an additional O(n log n).
    – kazenorin
    Commented May 20, 2019 at 1:19
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);
    }

}

1
  • 1
    Although this code may answer the question, providing additional context regarding why and/or how it answers the question would significantly improve its long-term value. Please edit your answer to add some explanation. Commented Jun 9, 2016 at 16:22
2

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;
}
1
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);
    }

If a and b are sets

a - b

is everything in a that's not in b.

>>> a = {1,2,3}
>>> b = {1,4,5}
>>> 
>>> a - b
{2, 3}
>>> b - a
{4, 5}

a.symmetric_difference(b) are all the elements that are in exactly one set, e.g. the union of a - b and b - a.

>>> a.symmetric_difference(b)
{2, 3, 4, 5}
>>> (a - b).union(b - a)
{2, 3, 4, 5}
1
public static <T> Set<T> symmetricDifference(Set<? extends T> a, Set<? extends T> b) {
    return Stream.of(a, b).flatMap(Collection::stream).filter(d -> !(a.contains(d) && b.contains(d)))
            .collect(Collectors.toSet());
}
3
  • Your answer is not relevant to the question. Your code is for difference the question is about symmetric difference
    – TomerBu
    Commented Jul 26, 2022 at 8:26
  • 1
    @TomerBu corrected the answer.
    – krishna T
    Commented Jul 26, 2022 at 19:33
  • 1
    Nice! this was my implementation: public static <T> Set<T> symmetricDifference(Set<? extends T> a, Set<? extends T> b) { //copy a values to resultSet Set<T> resultSet = new HashSet<>(a); //add all the items from b to resultSet and remember the ones that returned false (intersection) b.stream().filter(Predicate.not(resultSet::add)) //add b to resultSet and keep only the intersection .forEach(resultSet::remove);//remove the intersection from resultSet return resultSet; } but yours is nicer (one line :-)
    – TomerBu
    Commented Jul 27, 2022 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.