Как проверить, содержит ли коллекция дубликаты в Java

Введение

В этом практическом занятии (лабораторной работе) вы научитесь эффективно проверять Java-коллекцию на наличие дубликатов элементов. Мы рассмотрим использование HashSet, мощного инструмента из Java Collections Framework, для выявления дубликатов.

Путем практического выполнения шагов вы сначала узнаете, как использовать свойство уникальности элементов HashSet для обнаружения дубликатов. Затем вы откроете альтернативный метод, сравнивая размеры исходной коллекции и HashSet, созданного на ее основе. Наконец, мы изучим, как обрабатывать нулевые (null) элементы при проверке на дубликаты.

Использование HashSet для проверки на дубликаты

На этом этапе мы рассмотрим, как использовать HashSet в Java для эффективной проверки коллекции на наличие дубликатов элементов. HashSet является частью Java Collections Framework и особенно полезен, так как он хранит уникальные элементы и обеспечивает очень быстрый поиск.

Сначала создадим новый Java-файл с именем DuplicateCheck.java в директории ~/project. Вы можете сделать это прямо в проводнике файлов WebIDE, щелкнув правой кнопкой мыши в области списка файлов и выбрав "New File", а затем введя DuplicateCheck.java.

Теперь откройте файл DuplicateCheck.java в редакторе кода и добавьте следующий код:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateCheck {

    public static void main(String[] args) {
        // Create a list with some duplicate elements
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Alice"); // Duplicate
        names.add("Charlie");
        names.add("Bob"); // Duplicate

        System.out.println("Original List: " + names);

        // Use a HashSet to find duplicates
        Set<String> uniqueNames = new HashSet<>();
        Set<String> duplicates = new HashSet<>();

        for (String name : names) {
            if (!uniqueNames.add(name)) {
                // If add returns false, the element is already in the set
                duplicates.add(name);
            }
        }

        System.out.println("Duplicates found: " + duplicates);
    }
}

Разберем новые части этого кода:

• import java.util.ArrayList;, import java.util.HashSet;, import java.util.List;, import java.util.Set;: Эти строки импортируют необходимые классы из Java-библиотеки утилит для работы со списками и множествами.
• List<String> names = new ArrayList<>();: Эта строка создает List с именем names, который может хранить объекты типа String. Мы используем ArrayList как конкретную реализацию интерфейса List.
• names.add(...): Эта строка добавляет элементы в наш список names. Обратите внимание, что "Alice" и "Bob" добавляются дважды.
• Set<String> uniqueNames = new HashSet<>();: Эта строка создает Set с именем uniqueNames с использованием реализации HashSet. Set гарантирует, что он будет содержать только уникальные элементы.
• Set<String> duplicates = new HashSet<>();: Эта строка создает еще одно Set для хранения найденных дубликатов элементов.
• for (String name : names): Это цикл for-each, который проходит по каждому name в списке names.
• if (!uniqueNames.add(name)): Метод add() класса HashSet возвращает true, если элемент был успешно добавлен (то есть он еще не был в множестве), и false, если элемент уже был присутствует. Символ ! инвертирует результат, поэтому код внутри блока if выполняется только тогда, когда add() возвращает false, что указывает на дубликат.
• duplicates.add(name);: Если найден дубликат, мы добавляем его в наше множество duplicates.

Сохраните файл DuplicateCheck.java (Ctrl+S или Cmd+S).

Теперь откройте терминал в нижней части WebIDE. Убедитесь, что вы находитесь в директории ~/project. Вы можете это проверить, введя pwd и нажав Enter. Вывод должен быть /home/labex/project.

Скомпилируйте Java-программу с помощью команды javac:

javac DuplicateCheck.java

Если нет ошибок, вы не должны увидеть никакого вывода. Это означает, что компиляция прошла успешно, и файл DuplicateCheck.class был создан в директории ~/project. Вы можете проверить это, запустив команду ls.

Наконец, запустите скомпилированную Java-программу с помощью команды java:

java DuplicateCheck

Вы должны увидеть вывод, похожий на следующий:

Original List: [Alice, Bob, Alice, Charlie, Bob]
Duplicates found: [Alice, Bob]

Порядок элементов в выводе "Duplicates found" может отличаться, так как HashSet не сохраняет порядок вставки.

Вы успешно использовали HashSet для выявления дубликатов элементов в списке!

Сравнение размеров коллекции и множества

На предыдущем этапе мы использовали HashSet для поиска дубликатов элементов. Основная характеристика Set заключается в том, что он хранит только уникальные элементы. Это означает, что если вы добавите дубликаты элементов в Set, будет сохранен только один экземпляр каждого элемента. Это свойство очень полезно для таких задач, как удаление дубликатов из списка.

На этом этапе мы изменим нашу программу DuplicateCheck.java, чтобы продемонстрировать это свойство, сравнив размер исходного списка (который может содержать дубликаты) с размером HashSet, созданного из этого списка (который будет содержать только уникальные элементы).

Откройте файл DuplicateCheck.java в редакторе кода WebIDE.

Измените метод main так, чтобы он выглядел следующим образом:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateCheck {

    public static void main(String[] args) {
        // Create a list with some duplicate elements
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Alice"); // Duplicate
        names.add("Charlie");
        names.add("Bob"); // Duplicate
        names.add("David");

        System.out.println("Original List: " + names);
        System.out.println("Size of Original List: " + names.size());

        // Create a HashSet from the list
        Set<String> uniqueNamesSet = new HashSet<>(names);

        System.out.println("Set created from List: " + uniqueNamesSet);
        System.out.println("Size of Set: " + uniqueNamesSet.size());

        // The difference in size tells us how many duplicates were removed
        int duplicatesCount = names.size() - uniqueNamesSet.size();
        System.out.println("Number of duplicates (excluding first occurrence): " + duplicatesCount);
    }
}

Вот что мы добавили или изменили:

• Мы добавили еще одно имя, "David", в список names, чтобы получить немного больший список.
• System.out.println("Size of Original List: " + names.size());: Мы выводим размер исходного списка, используя метод size().
• Set<String> uniqueNamesSet = new HashSet<>(names);: Это удобный способ создать HashSet непосредственно из другой коллекции (например, нашего ArrayList). При этом HashSet автоматически добавляет все элементы из списка, и так как это Set, он отбрасывает все дубликаты.
• System.out.println("Size of Set: " + uniqueNamesSet.size());: Мы выводим размер HashSet. Этот размер представляет количество уникальных элементов.
• int duplicatesCount = names.size() - uniqueNamesSet.size();: Мы вычисляем разницу между размером списка и размером множества. Эта разница показывает, сколько элементов были дубликатами (после их первого появления).

Сохраните измененный файл DuplicateCheck.java.

Теперь скомпилируйте программу снова в терминале:

javac DuplicateCheck.java

Если компиляция прошла успешно, запустите программу:

java DuplicateCheck

Вы должны увидеть вывод, похожий на следующий:

Original List: [Alice, Bob, Alice, Charlie, Bob, David]
Size of Original List: 6
Set created from List: [Alice, Bob, Charlie, David]
Size of Set: 4
Number of duplicates (excluding first occurrence): 2

Обратите внимание, что размер исходного списка равен 6, но размер HashSet, созданного из него, равен 4. Разница (6 - 4 = 2) правильно показывает, что было два дублирующихся имени ("Alice" и "Bob" каждый появился еще раз после своего первого появления).

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

Тестирование с нулевыми элементами

На предыдущих этапах мы увидели, как HashSet обрабатывает дубликаты не-нулевых элементов. Теперь давайте исследуем, как ведет себя HashSet, когда мы пытаемся добавить нулевые элементы (null). Понимание того, как коллекции обрабатывают null, важно, так как это иногда может привести к неожиданному поведению или ошибкам, если не обрабатывать это осторожно.

HashSet позволяет добавить один нулевой элемент (null). Если вы попытаетесь добавить null несколько раз, будет сохранен только первый null.

Давайте еще раз изменим нашу программу DuplicateCheck.java, чтобы протестировать это.

Откройте файл DuplicateCheck.java в редакторе кода WebIDE.

Измените метод main, чтобы в список были включены нулевые значения (null):

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DuplicateCheck {

    public static void main(String[] args) {
        // Create a list with some duplicate and null elements
        List<String> names = new ArrayList<>();
        names.add("Alice");
        names.add("Bob");
        names.add(null); // Add null
        names.add("Alice"); // Duplicate
        names.add("Charlie");
        names.add(null); // Add null again
        names.add("Bob"); // Duplicate
        names.add("David");
        names.add(null); // Add null a third time

        System.out.println("Original List: " + names);
        System.out.println("Size of Original List: " + names.size());

        // Create a HashSet from the list
        Set<String> uniqueNamesSet = new HashSet<>(names);

        System.out.println("Set created from List: " + uniqueNamesSet);
        System.out.println("Size of Set: " + uniqueNamesSet.size());

        // The difference in size tells us how many duplicates were removed
        // Note: This calculation is less straightforward with nulls and duplicates combined
        // int duplicatesCount = names.size() - uniqueNamesSet.size();
        // System.out.println("Number of duplicates (excluding first occurrence): " + duplicatesCount);
    }
}

Здесь мы добавили null в список names несколько раз. Мы также закомментировали вычисление количества дубликатов, так как оно становится менее осмысленным, когда присутствует null, и мы сосредотачиваемся на поведении множества с null.

Сохраните измененный файл DuplicateCheck.java.

Скомпилируйте программу в терминале:

javac DuplicateCheck.java

Если компиляция прошла успешно, запустите программу:

java DuplicateCheck

Вы должны увидеть вывод, похожий на следующий:

Original List: [Alice, Bob, null, Alice, Charlie, null, Bob, David, null]
Size of Original List: 9
Set created from List: [null, Alice, Bob, Charlie, David]
Size of Set: 5

Обратите внимание на вывод:

• В Original List показаны все элементы, включая несколько значений null. Его размер равен 9.
• Set created from List содержит только уникальные элементы. Обратите внимание, что null появляется в множестве только один раз, даже несмотря на то, что он был добавлен в список несколько раз. Размер множества равен 5 (Alice, Bob, Charlie, David и null).

Это подтверждает, что HashSet позволяет один нулевой элемент (null) и рассматривает последующие добавления null как дубликаты, как и любые другие элементы.

Вы успешно протестировали, как HashSet обрабатывает нулевые элементы (null). Это завершает наше исследование использования HashSet для проверки на дубликаты и понимание его поведения с уникальными и нулевыми элементами.

Резюме

В этом практическом занятии (lab) мы научились эффективно проверять наличие дубликатов элементов в коллекции Java с использованием HashSet. Мы создали List с дубликатами элементов, а затем проитерировали по нему, пытаясь добавить каждый элемент в HashSet. Проверяя возвращаемое значение метода add(), которое равно false, если элемент уже присутствует, мы смогли определить и собрать дубликаты в отдельный HashSet. Этот метод использует свойство уникальности элементов и быстрый поиск в HashSet для эффективного обнаружения дубликатов.