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

JavaJavaBeginner
Практиковаться сейчас

💡 Этот учебник переведен с английского с помощью ИИ. Чтобы просмотреть оригинал, вы можете перейти на английский оригинал

Введение

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

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


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL java(("Java")) -.-> java/ObjectOrientedandAdvancedConceptsGroup(["Object-Oriented and Advanced Concepts"]) java(("Java")) -.-> java/DataStructuresGroup(["Data Structures"]) java/DataStructuresGroup -.-> java/arrays("Arrays") java/DataStructuresGroup -.-> java/collections_methods("Collections Methods") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/arraylist("ArrayList") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/hashset("HashSet") subgraph Lab Skills java/arrays -.-> lab-559948{{"Как проверить, содержит ли список дубликаты элементов в Java"}} java/collections_methods -.-> lab-559948{{"Как проверить, содержит ли список дубликаты элементов в Java"}} java/arraylist -.-> lab-559948{{"Как проверить, содержит ли список дубликаты элементов в Java"}} java/hashset -.-> lab-559948{{"Как проверить, содержит ли список дубликаты элементов в Java"}} end

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

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

Сначала создадим новый Java-файл с именем DuplicateDetector.java в директории ~/project. Это можно сделать с помощью проводника файлов WebIDE слева. Щелкните правой кнопкой мыши в области ~/project, выберите "Новый файл" и введите DuplicateDetector.java.

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

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

public class DuplicateDetector {

    public static boolean containsDuplicates(List<String> list) {
        // Create a HashSet to store unique elements
        Set<String> uniqueElements = new HashSet<>();

        // Iterate through the list
        for (String element : list) {
            // If the element is already in the HashSet, it's a duplicate
            if (uniqueElements.contains(element)) {
                return true; // Found a duplicate
            }
            // Otherwise, add the element to the HashSet
            uniqueElements.add(element);
        }

        // If the loop finishes without finding duplicates, return false
        return false;
    }

    public static void main(String[] args) {
        // Example usage
        List<String> myListWithDuplicates = new ArrayList<>();
        myListWithDuplicates.add("apple");
        myListWithDuplicates.add("banana");
        myListWithDuplicates.add("apple"); // Duplicate
        myListWithDuplicates.add("orange");

        List<String> myListWithoutDuplicates = new ArrayList<>();
        myListWithoutDuplicates.add("grape");
        myListWithoutDuplicates.add("mango");
        myListWithoutDuplicates.add("kiwi");

        System.out.println("List with duplicates: " + myListWithDuplicates);
        System.out.println("Contains duplicates? " + containsDuplicates(myListWithDuplicates)); // Expected: true

        System.out.println("\nList without duplicates: " + myListWithoutDuplicates);
        System.out.println("Contains duplicates? " + containsDuplicates(myListWithoutDuplicates)); // Expected: false
    }
}

Постараемся понять ключевые части этого кода:

  • import java.util.ArrayList;, import java.util.HashSet;, import java.util.List;, import java.util.Set;: Эти строки импортируют необходимые классы из Фреймворка коллекций Java.
  • public static boolean containsDuplicates(List<String> list): Это метод, который принимает в качестве входных данных список (List) объектов String и возвращает true, если он содержит дубликаты, и false в противном случае.
  • Set<String> uniqueElements = new HashSet<>();: Эта строка создает пустой HashSet с именем uniqueElements. HashSet предназначен для хранения только уникальных элементов.
  • for (String element : list): Этот цикл проходит по каждому element во входном list.
  • if (uniqueElements.contains(element)): Эта строка проверяет, присутствует ли текущий element уже в HashSet uniqueElements. Если да, это означает, что мы нашли дубликат, и метод возвращает true.
  • uniqueElements.add(element);: Если элемент еще не находится в HashSet, он добавляется. Поскольку HashSet хранит только уникальные элементы, добавление уже существующего элемента не имеет эффекта.
  • return false;: Если цикл завершается без нахождения дубликатов, метод возвращает false.
  • Метод main демонстрирует, как использовать метод containsDuplicates с примерами списков.

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

Теперь скомпилируем и запустим эту программу в терминале. Убедитесь, что вы находитесь в директории ~/project.

Скомпилируйте код:

javac DuplicateDetector.java

Если нет ошибок компиляции, вы не увидите никакого вывода.

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

java DuplicateDetector

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

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Этот вывод подтверждает, что наш метод containsDuplicates правильно определил список с дубликатами. Использование HashSet - это эффективный способ проверки на дубликаты, так как проверка наличия элемента в HashSet (с использованием contains()) в среднем очень быстра.

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

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

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

Давайте модифицируем файл DuplicateDetector.java, чтобы реализовать этот подход. Откройте файл ~/project/DuplicateDetector.java в редакторе кода.

Замените метод containsDuplicates следующим кодом:

    public static boolean containsDuplicates(List<String> list) {
        // Create a HashSet from the list
        Set<String> uniqueElements = new HashSet<>(list);

        // Compare the size of the list with the size of the HashSet
        return list.size() != uniqueElements.size();
    }

Вот что происходит в новом коде:

  • Set<String> uniqueElements = new HashSet<>(list);: Эта строка сразу создает HashSet и инициализирует его всеми элементами из входного list. HashSet автоматически обеспечивает уникальность элементов, поэтому любые дубликаты из списка не будут добавлены в множество.
  • return list.size() != uniqueElements.size();: Эта строка сравнивает количество элементов в исходном list (list.size()) с количеством уникальных элементов в HashSet (uniqueElements.size()). Если размеры различны (!=), это означает, что в списке были дубликаты, и метод возвращает true. Если размеры одинаковы, дубликатов не было, и метод возвращает false.

Метод main может остаться таким же, так как он уже вызывает метод containsDuplicates.

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

Теперь скомпилируем и запустим модифицированную программу. Убедитесь, что вы находитесь в директории ~/project в терминале.

Скомпилируйте код:

javac DuplicateDetector.java

Запустите скомпилированный код:

java DuplicateDetector

Вы должны увидеть такой же вывод, как и раньше:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

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

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

В реальной программировании важно учитывать крайние случаи, например, когда список может быть пустым или даже null. Наш текущий метод containsDuplicates хорошо работает для списков с элементами, но что произойдет, если мы передадим пустой список или список со значением null?

Давайте протестируем это, добавив больше примеров в метод main в файле ~/project/DuplicateDetector.java. Откройте файл в редакторе кода и добавьте следующие строки в метод main после существующего кода:

        System.out.println("\nEmpty list: " + new ArrayList<>());
        System.out.println("Contains duplicates? " + containsDuplicates(new ArrayList<>())); // Expected: false

        List<String> nullList = null;
        System.out.println("\nNull list: " + nullList);
        // The following line will cause a NullPointerException if not handled
        // System.out.println("Contains duplicates? " + containsDuplicates(nullList));

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

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

Скомпилируйте:

javac DuplicateDetector.java

Запустите:

java DuplicateDetector

Вы должны увидеть вывод для пустого списка:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Empty list: []
Contains duplicates? false

Вывод для пустого списка правильный; пустой список не содержит дубликатов.

Однако, если вы раскомментируете строку System.out.println("Contains duplicates? " + containsDuplicates(nullList)); и попытаетесь скомпилировать и запустить программу, вы получите исключение NullPointerException. Это происходит потому, что мы пытаемся создать HashSet из списка со значением null, что не допускается.

Чтобы сделать наш метод containsDuplicates более надежным, мы должны обработать случай, когда входной список имеет значение null. Мы можем добавить проверку в начале метода.

Модифицируйте метод containsDuplicates в файле ~/project/DuplicateDetector.java, чтобы включить проверку на null:

    public static boolean containsDuplicates(List<String> list) {
        // Handle null input
        if (list == null) {
            return false; // A null list does not contain duplicates
        }

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

        // Compare the size of the list with the size of the HashSet
        return list.size() != uniqueElements.size();
    }

Теперь раскомментируйте строку, которая тестирует список со значением null в методе main:

        List<String> nullList = null;
        System.out.println("\nNull list: " + nullList);
        System.out.println("Contains duplicates? " + containsDuplicates(nullList)); // Expected: false

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

Скомпилируйте и запустите программу в последний раз.

Скомпилируйте:

javac DuplicateDetector.java

Запустите:

java DuplicateDetector

Теперь вывод должен включать результат для списка со значением null без сбоя программы:

List with duplicates: [apple, banana, apple, orange]
Contains duplicates? true

List without duplicates: [grape, mango, kiwi]
Contains duplicates? false

Empty list: []
Contains duplicates? false

Null list: null
Contains duplicates? false

Добавив проверку на null, наш метод containsDuplicates стал более надежным и может корректно обрабатывать входные данные со значением null. Это важная практика в программировании для предотвращения непредвиденных ошибок.

Резюме

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

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