Какие знаешь способы удаления дубликатов в List?

Удаление дубликатов в List — способы и сравнение производительности

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

Способ 1: HashSet (самый быстрый для уникализации)

HashSet — используется для удаления дубликатов за счёт изменения порядка элементов:

public class RemoveDuplicatesHashSet {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 2, 3, 3, 3, 4, 5, 5);
        
        // Способ 1: new HashSet<>(list)
        List<Integer> unique = new ArrayList<>(new HashSet<>(numbers));
        System.out.println(unique); // [1, 2, 3, 4, 5] (порядок может отличаться)
        
        // Способ 2: stream + distinct (более функциональный)
        List<Integer> unique2 = numbers.stream()
            .distinct()
            .collect(Collectors.toList());
        System.out.println(unique2); // [1, 2, 3, 4, 5] (порядок сохранён)
    }
}

Характеристики:

• Временная сложность: O(n)
• Пространственная сложность: O(n)
• Сохранение порядка: НЕ сохранит
• Производительность: Очень быстро ✅

Когда использовать: Когда не важен порядок элементов

Способ 2: LinkedHashSet (сохранение порядка)

LinkedHashSet — сохраняет порядок первого появления элемента:

public class RemoveDuplicatesLinkedHashSet {
    public static void main(String[] args) {
        List<String> names = Arrays.asList(
            "Alice", "Bob", "Alice", "Charlie", "Bob", "Alice"
        );
        
        // LinkedHashSet сохранит порядок появления
        List<String> unique = new ArrayList<>(
            new LinkedHashSet<>(names)
        );
        System.out.println(unique); // [Alice, Bob, Charlie]
        
        // Stream подход
        Set<String> seen = new HashSet<>();
        List<String> unique2 = names.stream()
            .filter(name -> seen.add(name))
            .collect(Collectors.toList());
        System.out.println(unique2); // [Alice, Bob, Charlie]
    }
}

Характеристики:

• Временная сложность: O(n)
• Пространственная сложность: O(n)
• Сохранение порядка: ДА ✅
• Производительность: Быстро ✅

Когда использовать: Когда важен исходный порядок (most common case)

Способ 3: Stream distinct() (функциональный подход)

Stream distinct() — встроенный способ для удаления дубликатов:

public class RemoveDuplicatesStream {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 2, 3, 3, 3, 4, 5, 5);
        
        // Базовый distinct
        List<Integer> unique = numbers.stream()
            .distinct()
            .collect(Collectors.toList());
        System.out.println(unique); // [1, 2, 3, 4, 5]
        
        // С сортировкой
        List<Integer> sorted = numbers.stream()
            .distinct()
            .sorted()
            .collect(Collectors.toList());
        System.out.println(sorted); // [1, 2, 3, 4, 5]
        
        // С фильтром
        List<Integer> filtered = numbers.stream()
            .distinct()
            .filter(n -> n > 2)
            .collect(Collectors.toList());
        System.out.println(filtered); // [3, 4, 5]
    }
}

Характеристики:

• Временная сложность: O(n)
• Пространственная сложность: O(n)
• Сохранение порядка: ДА ✅
• Ленивое вычисление: ДА (если не терминальная операция)
• Комбинируемость: ДА (с другими операциями Stream)

Когда использовать: Java 8+, функциональный стиль, нужна комбинируемость

Способ 4: LinkedHashSet + Stream (гибридный подход)

Комбинированный подход:

public class RemoveDuplicatesHybrid {
    public static <T> List<T> removeDuplicates(List<T> list) {
        return new ArrayList<>(new LinkedHashSet<>(list));
    }
    
    public static <T> List<T> removeDuplicatesStream(List<T> list) {
        Set<T> seen = new HashSet<>();
        return list.stream()
            .filter(item -> seen.add(item))
            .collect(Collectors.toList());
    }
    
    public static void main(String[] args) {
        List<String> fruits = Arrays.asList(
            "apple", "banana", "apple", "cherry", "banana"
        );
        
        // Способ 1: LinkedHashSet (самый читаемый)
        System.out.println(removeDuplicates(fruits)); 
        // [apple, banana, cherry]
        
        // Способ 2: Stream с фильтром (более функциональный)
        System.out.println(removeDuplicatesStream(fruits)); 
        // [apple, banana, cherry]
    }
}

Способ 5: Удаление дубликатов кастомных объектов

Для объектов нужно переопределить equals() и hashCode():

public class User {
    private Long id;
    private String email;
    
    public User(Long id, String email) {
        this.id = id;
        this.email = email;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(id, user.id) && 
               Objects.equals(email, user.email);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id, email);
    }
    
    @Override
    public String toString() {
        return "User{" + id + ", " + email + '}';
    }
}

public class RemoveDuplicatesObjects {
    public static void main(String[] args) {
        List<User> users = Arrays.asList(
            new User(1L, "john@example.com"),
            new User(2L, "jane@example.com"),
            new User(1L, "john@example.com"), // дубликат
            new User(3L, "bob@example.com")
        );
        
        // HashSet автоматически удалит дубликаты на основе equals/hashCode
        List<User> unique = new ArrayList<>(new LinkedHashSet<>(users));
        System.out.println(unique);
        // [User{1, john@example.com}, User{2, jane@example.com}, User{3, bob@example.com}]
        
        // Или через Stream
        Set<User> uniqueStream = users.stream()
            .collect(Collectors.toCollection(LinkedHashSet::new));
        System.out.println(new ArrayList<>(uniqueStream));
    }
}

Способ 6: Удаление дубликатов по определённому полю

Когда нужно удалить дубликаты не по целому объекту, а по одному полю:

public class RemoveDuplicatesByField {
    public static void main(String[] args) {
        List<User> users = Arrays.asList(
            new User(1L, "john@example.com"),
            new User(2L, "jane@example.com"),
            new User(3L, "john@example.com"), // другой ID, но тот же email
            new User(4L, "bob@example.com")
        );
        
        // Удалить дубликаты по email
        Set<String> seenEmails = new HashSet<>();
        List<User> unique = users.stream()
            .filter(user -> seenEmails.add(user.getEmail()))
            .collect(Collectors.toList());
        System.out.println(unique);
        
        // Или используя toMap
        List<User> unique2 = users.stream()
            .collect(Collectors.toMap(
                User::getEmail,
                Function.identity(),
                (first, second) -> first  // keep first if duplicate
            ))
            .values()
            .stream()
            .collect(Collectors.toList());
        System.out.println(unique2);
    }
}

Способ 7: Удаление дубликатов в месте (In-place)

Когда нужно изменить исходный List:

public class RemoveDuplicatesInPlace {
    public static <T> void removeDuplicatesInPlace(List<T> list) {
        Set<T> seen = new HashSet<>();
        list.removeIf(item -> !seen.add(item));
    }
    
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(
            Arrays.asList(1, 2, 2, 3, 3, 3, 4, 5, 5)
        );
        
        removeDuplicatesInPlace(numbers);
        System.out.println(numbers); // [1, 2, 3, 4, 5]
    }
}

Характеристики:

• Пространственная сложность: O(n) (для HashSet)
• Модифицирует исходный список: ДА
• Сохраняет порядок: ДА

Способ 8: Использование TreeSet (для сортировки)

Если нужны уникальные и отсортированные значения:

public class RemoveDuplicatesTreeSet {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(5, 2, 8, 2, 3, 5, 1);
        
        // TreeSet удаляет дубликаты И сортирует
        List<Integer> unique = new ArrayList<>(new TreeSet<>(numbers));
        System.out.println(unique); // [1, 2, 3, 5, 8]
        
        // С компаратором
        List<Integer> reverseUnique = new ArrayList<>(
            new TreeSet<>((a, b) -> b.compareTo(a)) {{
                addAll(numbers);
            }}
        );
        System.out.println(reverseUnique); // [8, 5, 3, 2, 1]
    }
}

Сравнение производительности

Рекомендации по выбору

Для большинства случаев (production code):

// Самый лучший выбор - LinkedHashSet
List<T> unique = new ArrayList<>(new LinkedHashSet<>(list));

Если нужна функциональность Stream:

List<T> unique = list.stream()
    .distinct()
    .collect(Collectors.toList());

Если нужна максимальная производительность:

List<T> unique = new ArrayList<>(new HashSet<>(list));

Если нужны сортированные результаты:

List<T> unique = list.stream()
    .distinct()
    .sorted()
    .collect(Collectors.toList());

Для удаления дубликатов по полю:

Set<T> seen = new HashSet<>();
List<T> unique = list.stream()
    .filter(item -> seen.add(item.getField()))
    .collect(Collectors.toList());

Важные замечания

1. Обязательно переопределяй equals() и hashCode() для кастомных объектов
2. LinkedHashSet лучше HashSet если важен порядок (обычно это так)
3. Stream.distinct() внутри использует HashSet, но сохраняет порядок
4. Для больших листов - LinkedHashSet быстрее всего
5. removeIf() изменяет исходный список - be careful!