Каков наилучший способ получить симметричную разницу между двумя наборами в Java?

Question

Мне интересно, есть ли быстрый / чистый способ получить симметричную разницу между двумя наборами?

У меня есть:

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

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

Мне нужно что-то вроде:

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

---

Просто чтобы уточнить, мне нужна симметричная разница.

Answer 1

Вы можете использовать некоторые функции из библиотеки Google Guava (что действительно здорово, я настоятельно рекомендую!):

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

Javadocs для Разница () и Симметричная Разница ()

symmetricDifference() делает точно то, что вы просите , но difference() также часто помогает.

Оба метода возвращают отображение в реальном времени, но вы можете, например, вызвать .immutableCopy() в результирующем наборе, чтобы получить неизменяемый набор. Если вам не нужен вид, но вам нужен установленный экземпляр, который вы можете изменить, позвоните .copyInto(s3). См. SetView для этих методов.

Answer 2

Вы хотите симметричную разность .

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

Если вам нужна библиотека, Apache Commons CollectionUtils имеет

CollectionUtils.disjunction(s1, s2)

, который возвращает неуниверсальный Collection.

и Наборы гуавы имеет

Sets.symmetricDifference(s1, s2)

, который возвращает неизменяемый Set как универсальный Sets.SetView.

Guava немного более современен, поддерживает дженерики, но любой из них будет работать.

Answer 3

Если вы можете использовать Коллекции Apache-Commons , вы ищете CollectionUtils.disjunction(Collection a, Collection b). Возвращает симметричную разность обеих коллекций.

Если нет, вычтите (removeAll) пересечение (retainAll) обоих множеств в объединение обоих (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);

Answer 4

Перебрать один комплект и сравнить.

Это только O(n), чтобы пройти через один из наборов. Рассмотрим этот код:

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

И newSet теперь будет содержать только уникальные записи из обоих наборов. Это быстро, потому что вам нужно только пройтись по элементам в одном из наборов, и вам не нужно создавать наборы, если вам явно не нужна копия.

Answer 5

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 6

Решение Java 8

Мы можем написать два служебных метода (для java 8 и более ранних) в некотором классе SetUtils (say) как:

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

Метод add возвращает false, еслиэлемент уже существует, и метод отрицания используется для отрицания предиката

Java 11

У нас есть метод Predicate # not для предиката в Java 11 и мы можем использовать его как:

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 7

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

Должно работать.