Найдите разницу между двумя наборами

2 апреля 2022 г. · 7 мин. чтения

1. Обзор

Set — один из наиболее часто используемых типов коллекций в Java. Сегодня мы обсудим, как найти разницу между двумя заданными множествами.

2. Введение в проблему

Прежде чем мы более подробно рассмотрим реализации, нам нужно сначала понять проблему. Как обычно, пример может помочь нам быстро понять требование.

Допустим, у нас есть два объекта Set , set1 и set2 :

set1: {"Kotlin", "Java", "Rust", "Python", "C++"}
set2: {"Kotlin", "Java", "Rust", "Ruby", "C#"}

Как мы видим, оба набора содержат имена некоторых языков программирования. Требование « Нахождение разницы между двумя множествами » может иметь два варианта:

Асимметричная разница — поиск тех элементов, которые содержатся в set1 , но не содержатся в set2 ; в этом случае ожидаемый результат {"Python", "C++"}
Симметричная разность - нахождение элементов в любом из наборов, но не в их пересечении; если мы посмотрим на наш пример, результат должен быть {"Python", "C++", "Ruby", "C#"}

В этом руководстве мы рассмотрим решение для обоих сценариев. Во-первых, мы сосредоточимся на поиске асимметричных различий. После этого мы займемся поиском симметричной разницы между двумя множествами.

Далее давайте посмотрим на них в действии.

3. Асимметричная разница

3.1. Использование стандартного метода `removeAll`

Класс Set предоставляет метод removeAll . Этот метод реализует метод removeAll из интерфейса Collection .

Метод removeAll принимает объект Collection в качестве параметра и удаляет все элементы параметра из заданного объекта Set . Итак, если мы передаем объект set2 в качестве параметра таким образом, « set1.removeAll(set2) », результатом будут остальные элементы в объекте set1 .

Для простоты покажем это как модульный тест:

Set<String> set1 = Stream.of("Kotlin", "Java", "Rust", "Python", "C++").collect(Collectors.toSet());
Set<String> set2 = Stream.of("Kotlin", "Java", "Rust", "Ruby", "C#").collect(Collectors.toSet());
Set<String> expectedOnlyInSet1 = Set.of("Python", "C++");

set1.removeAll(set2);

assertThat(set1).isEqualTo(expectedOnlyInSet1);

Как показано в приведенном выше методе, сначала мы инициализируем два `` объекта Set с помощью Stream . Затем, после вызова метода removeAll , объект набора 1 содержит ожидаемые элементы.

Этот подход довольно прост. Однако недостаток очевиден: после удаления общих элементов из set1 исходный `` set1 модифицируется .

Поэтому нам нужно сделать резервную копию исходного объекта set1 , если он нам все еще нужен после вызова метода removeAll , или нам нужно создать новый изменяемый объект набора, если set1 является неизменяемым Set .

Далее давайте рассмотрим другой подход к возврату асимметричной разницы в новом объекте Set без изменения исходного набора.

3.2. Использование метода `Stream.filter`

Stream API существует с Java 8. Он позволяет нам фильтровать элементы из коллекции с помощью метода Stream.filter .

Мы также можем решить эту проблему, используя Stream.filter, не изменяя исходный объект set1 . Давайте сначала инициализируем два набора как неизменяемые:

Set<String> immutableSet1 = Set.of("Kotlin", "Java", "Rust", "Python", "C++");
Set<String> immutableSet2 = Set.of("Kotlin", "Java", "Rust", "Ruby", "C#");
Set<String> expectedOnlyInSet1 = Set.of("Python", "C++");

Начиная с Java 9, в интерфейсе Set появился статический метод. Это позволяет нам удобно инициализировать неизменяемый объект Set . То есть, если мы попытаемся изменить immutableSet1, будет выдано исключение UnsupportedOperationException . `` ``

Затем давайте напишем модульный тест, который использует Stream.filter для поиска разницы:

Set<String> actualOnlyInSet1 = immutableSet1.stream().filter(e -> !immutableSet2.contains(e)).collect(Collectors.toSet());
assertThat(actualOnlyInSet1).isEqualTo(expectedOnlyInSet1);

Как мы видим в приведенном выше методе, ключом является « filter(e -> !immutableSet2.contains(e)) ». Здесь мы берем только элементы из immutableSet1 , но не из immutableSet2 .

Если мы выполним этот тестовый метод, он пройдет без каких-либо исключений. Это означает, что этот подход работает, и исходные наборы не модифицируются.

3.3. Использование библиотеки гуавы

Guava — это популярная библиотека Java, которая поставляется с некоторыми новыми типами коллекций и удобными вспомогательными методами. Гуава предоставил метод для поиска асимметричных различий между двумя наборами. Поэтому мы можем использовать этот метод для легкого решения наших проблем.

Но сначала нам нужно включить библиотеку в наш путь к классам. Допустим, мы управляем зависимостями проекта с помощью Maven . Возможно, нам потребуется добавить зависимость Guava в pom.xml :

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

Как только Guava станет доступна в нашем Java-проекте, мы сможем использовать его метод Sets.difference для получения ожидаемого результата :

Set<String> actualOnlyInSet1 = Sets.difference(immutableSet1, immutableSet2);
assertThat(actualOnlyInSet1).isEqualTo(expectedOnlyInSet1);

Стоит отметить, что метод Sets.difference возвращает неизменное представление Set , содержащее результат. Это означает:

Мы не можем изменить возвращаемый набор
Если исходный набор является изменяемым, изменения в исходном наборе могут быть отражены в результирующем представлении набора.

3.4. Использование библиотеки Apache Commons

Apache Commons — еще одна широко используемая библиотека. Библиотека Apache Commons Collections4 предоставляет множество хороших методов, связанных с коллекциями, в дополнение к стандартному API коллекции.

Прежде чем мы начнем его использовать, давайте добавим зависимость в наш pom.xml :

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.4</version>
</dependency>

Точно так же мы можем найти последнюю версию в центральном репозитории Maven.

В библиотеке commons-collections4 есть метод CollectionUtils.removeAll . Он похож на стандартный метод Collection.removeAll , но возвращает результат в новом объекте Collection вместо изменения первого объекта Collection .

Затем давайте проверим его с двумя неизменяемыми объектами Set :

Set<String> actualOnlyInSet1 = new HashSet<>(CollectionUtils.removeAll(immutableSet1, immutableSet2));
assertThat(actualOnlyInSet1).isEqualTo(expectedOnlyInSet1);

Тест пройдет, если мы его выполним. Но следует отметить, что метод CollectionUtils.removeAll возвращает результат в типе Collection .

Если требуется конкретный тип — например, Set в нашем случае — нам нужно будет преобразовать его вручную. В тестовом методе выше мы инициализировали новый объект HashSet , используя возвращенную коллекцию.

4. Симметричная разница

До сих пор мы научились получать асимметричную разность между двумя множествами. Теперь давайте подробнее рассмотрим другой сценарий: нахождение симметричной разности между двумя множествами.

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

Ожидаемый результат:

Set<String> expectedDiff = Set.of("Python", "C++", "Ruby", "C#");

Далее посмотрим, как решить проблему.

4.1. Использование `хэш-карты`

Одна из идей решения этой проблемы — сначала создать объект Map<T, Integer> .

Затем мы перебираем два заданных набора и помещаем каждый элемент на карту в качестве ключа. Если ключ существует в карте, это означает, что это общий элемент в обоих наборах. В качестве значения мы устанавливаем специальное число — например, Integer.MAX_VALUE . В противном случае мы помещаем элемент и значение 1 в качестве новой записи на карту.

Наконец, мы узнаем ключи, значение которых равно 1 в карте, и эти ключи являются симметричной разностью между двумя заданными множествами.

Далее реализуем идею на Java:

public static <T> Set<T> findSymmetricDiff(Set<T> set1, Set<T> set2) {
    Map<T, Integer> map = new HashMap<>();
    set1.forEach(e -> putKey(map, e));
    set2.forEach(e -> putKey(map, e));
    return map.entrySet().stream()
      .filter(e -> e.getValue() == 1)
      .map(Map.Entry::getKey)
      .collect(Collectors.toSet());
}

private static <T> void putKey(Map<T, Integer> map, T key) {
    if (map.containsKey(key)) {
        map.replace(key, Integer.MAX_VALUE);
    } else {
        map.put(key, 1);
    }
}

Теперь давайте протестируем наше решение и посмотрим, может ли оно дать ожидаемый результат:

Set<String> actualDiff = SetDiff.findSymmetricDiff(immutableSet1, immutableSet2);
assertThat(actualDiff).isEqualTo(expectedDiff);

Тест проходит, если мы его запускаем. То есть наша реализация работает так, как ожидалось.

4.2. Использование библиотеки Apache Commons

Мы уже представили библиотеку Apache Commons при поиске асимметричной разницы между двумя множествами. На самом деле в библиотеке commons-collections4 есть удобный метод SetUtils.disjunction для прямого возврата симметричной разницы между двумя множествами :

Set<String> actualDiff = SetUtils.disjunction(immutableSet1, immutableSet2);
assertThat(actualDiff).isEqualTo(expectedDiff);

Как показано в приведенном выше методе, в отличие от метода CollectionUtils.removeAll , метод SetUtils.disjunction возвращает объект Set . Нам не нужно вручную преобразовывать его в Set .

5. Вывод

В этой статье мы рассмотрели, как найти различия между двумя объектами Set на примерах. Далее мы обсудили два варианта этой задачи: нахождение асимметричных разностей и симметричных разностей.

Мы рассмотрели решение двух вариантов с помощью стандартного Java API и широко используемых внешних библиотек, таких как Apache Commons-Collections и Guava.

Как всегда, исходный код, используемый в этом руководстве, доступен на GitHub .

1. Обзор​

2. Введение в проблему​

3. Асимметричная разница​

3.1. Использование стандартного метода removeAll​

3.2. Использование метода Stream.filter​

3.3. Использование библиотеки гуавы​

3.4. Использование библиотеки Apache Commons​

4. Симметричная разница​

4.1. Использование хэш-карты​

4.2. Использование библиотеки Apache Commons​

5. Вывод​