Что такое дедупликация?

Дедупликация

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

Дедупликация в коллекциях Java

1. Удаление дубликатов из List

import java.util.*;
import java.util.stream.Collectors;

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

2. Дедупликация объектов (сравнение equals())

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

public class UserDeduplicationExample {
    public static void main(String[] args) {
        List<User> users = Arrays.asList(
            new User(1, "john@example.com", "John"),
            new User(1, "john@example.com", "John"), // Дубликат
            new User(2, "jane@example.com", "Jane"),
            new User(2, "jane@example.com", "Jane"), // Дубликат
            new User(3, "bob@example.com", "Bob")
        );
        
        // HashSet удаляет дубликаты
        List<User> deduped = new ArrayList<>(new HashSet<>(users));
        System.out.println("Уникальные пользователи: " + deduped.size());
        deduped.forEach(System.out::println);
        
        // Stream approach
        List<User> deduped2 = users.stream()
            .distinct()
            .collect(Collectors.toList());
        System.out.println("\nЧерез Stream: " + deduped2.size());
    }
}

3. Дедупликация по конкретному полю

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class SelectiveDeduplicationExample {
    public static void main(String[] args) {
        List<User> users = Arrays.asList(
            new User(1, "john@example.com", "John"),
            new User(1, "john@example.com", "John Doe"), // Разные имена
            new User(2, "jane@example.com", "Jane"),
            new User(3, "bob@example.com", "Bob")
        );
        
        // Дедупликация по email (оставляем только первый с каждым email)
        List<User> deduped = users.stream()
            .collect(Collectors.toMap(
                User::getEmail, // ключ - email
                u -> u,         // значение - пользователь
                (existing, replacement) -> existing // при дубликате берём первый
            ))
            .values()
            .stream()
            .collect(Collectors.toList());
        
        System.out.println("Уникальные по email: ");
        deduped.forEach(System.out::println);
    }
}

Дедупликация в базе данных

SQL пример - удаление дубликатов:

// SQL запрос для поиска дубликатов
public class DatabaseDeduplication {
    // Найти дубликаты
    public static final String FIND_DUPLICATES = 
        "SELECT email, COUNT(*) as count FROM users GROUP BY email HAVING COUNT(*) > 1";
    
    // Удалить дубликаты (оставить самый старый)
    public static final String REMOVE_DUPLICATES = 
        "DELETE FROM users WHERE id NOT IN (" +
        "  SELECT MIN(id) FROM users GROUP BY email" +
        ")";
    
    // Или с использованием window function
    public static final String REMOVE_DUPLICATES_WITH_CTE = 
        "WITH ranked_users AS (" +
        "  SELECT id, ROW_NUMBER() OVER (PARTITION BY email ORDER BY created_at) as rn" +
        "  FROM users" +
        ")" +
        "DELETE FROM users WHERE id IN (SELECT id FROM ranked_users WHERE rn > 1)";
}

Дедупликация в потоках данных

1. Обработка потока данных без дубликатов

import java.util.LinkedHashSet;

public class StreamDeduplicationExample {
    // Используем LinkedHashSet для сохранения порядка
    public static <T> List<T> deduplicateStream(Stream<T> stream) {
        return stream.collect(Collectors.toCollection(LinkedHashSet::new))
                    .stream()
                    .collect(Collectors.toList());
    }
    
    // Для больших потоков (когда всё не помещается в памяти)
    public static <T> void processWithDeduplication(Stream<T> stream) {
        Set<T> seen = new LinkedHashSet<>();
        stream.filter(seen::add) // Добавляем в set и фильтруем дубликаты
              .forEach(System.out::println);
    }
    
    public static void main(String[] args) {
        Stream<Integer> numbers = Stream.of(1, 2, 2, 3, 3, 3, 4, 5, 5);
        processWithDeduplication(numbers);
    }
}

2. Дедупликация по сложным критериям

import java.util.HashSet;
import java.util.Set;

public class ComplexDeduplicationExample {
    static class Product {
        int id;
        String name;
        double price;
        
        Product(int id, String name, double price) {
            this.id = id;
            this.name = name;
            this.price = price;
        }
    }
    
    public static void main(String[] args) {
        List<Product> products = Arrays.asList(
            new Product(1, "Laptop", 999.99),
            new Product(1, "Laptop", 999.99), // Дубликат
            new Product(2, "Mouse", 29.99),
            new Product(3, "Keyboard", 79.99),
            new Product(3, "Keyboard", 79.99)  // Дубликат
        );
        
        // Дедупликация с использованием собственного критерия
        Set<String> seen = new HashSet<>();
        List<Product> deduped = products.stream()
            .filter(p -> seen.add(p.id + ":" + p.name))
            .collect(Collectors.toList());
        
        System.out.println("Уникальные продукты: " + deduped.size());
    }
}

Производительность дедупликации

Сравнение методов:

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

public class PerformanceComparison {
    public static void main(String[] args) {
        int size = 1_000_000;
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            numbers.add(i % 1000); // 1000 уникальных значений, повторяются
        }
        
        // HashSet - O(n), быстро, не сохраняет порядок
        long start = System.currentTimeMillis();
        List<Integer> deduped1 = new ArrayList<>(new HashSet<>(numbers));
        System.out.println("HashSet: " + (System.currentTimeMillis() - start) + "ms");
        
        // LinkedHashSet - O(n), быстро, сохраняет порядок
        start = System.currentTimeMillis();
        List<Integer> deduped2 = new ArrayList<>(new LinkedHashSet<>(numbers));
        System.out.println("LinkedHashSet: " + (System.currentTimeMillis() - start) + "ms");
        
        // Stream distinct - O(n), немного медленнее
        start = System.currentTimeMillis();
        List<Integer> deduped3 = numbers.stream()
            .distinct()
            .collect(Collectors.toList());
        System.out.println("Stream: " + (System.currentTimeMillis() - start) + "ms");
    }
}

Лучшие практики дедупликации

// ✅ Используй LinkedHashSet если важен порядок
List<String> deduped = new ArrayList<>(new LinkedHashSet<>(items));

// ✅ Используй stream().distinct() для читаемости
List<String> deduped = items.stream().distinct().collect(Collectors.toList());

// ✅ Правильно реализуй equals() и hashCode()
public class Entity {
    @Override
    public boolean equals(Object o) { ... }
    
    @Override
    public int hashCode() { ... }
}

// ❌ Не используй TreeSet без необходимости сортировки
Set<String> set = new TreeSet<>(items); // Медленнее из-за сортировки

// ❌ Не удаляй дубликаты в цикле, если много элементов
for (int i = 0; i < list.size(); i++) { // Очень медленно
    // ...
}

Дедупликация — это важный навык при работе с данными. Правильный выбор метода дедупликации влияет на производительность приложения, особенно при работе с большими объёмами данных.