https://www.nowcoder.com/discuss/695659297362976768

chatgpt：

在处理大量数据时，寻找重复项是一项常见任务。可以通过以下步骤高效地找到重复的学生信息。这里我们假设学生类包含 id（学号）、name（姓名）和 age（年龄）等字段。

方法：使用哈希表去重

利用哈希表存储已出现的学生信息，找到重复项。

示例代码：

import java.util.*;

class Student {
    String id;
    String name;
    int age;

    public Student(String id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id) &&
               Objects.equals(name, student.name) &&
               age == student.age;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name, age);
    }

    @Override
    public String toString() {
        return "Student{id='" + id + "', name='" + name + "', age=" + age + '}';
    }
}

public class FindDuplicates {
    public static void main(String[] args) {
        // 假设有十万条学生信息
        List<Student> students = generateStudents(100000);

        // 用来存储已存在的学生
        Set<Student> seen = new HashSet<>();
        // 用来存储重复的学生
        Set<Student> duplicates = new HashSet<>();

        for (Student student : students) {
            if (!seen.add(student)) {
                duplicates.add(student); // 如果添加失败，说明重复
            }
        }

        // 输出重复的学生
        System.out.println("重复的学生信息有：" + duplicates.size() + " 条");
        for (Student student : duplicates) {
            System.out.println(student);
        }
    }

    // 模拟生成十万个学生信息
    private static List<Student> generateStudents(int count) {
        List<Student> students = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            students.add(new Student("ID" + (i % 50000), "Name" + (i % 1000), 18 + (i % 5)));
        }
        return students;
    }
}

方法解析：

1. 使用 HashSet 检测重复：
   • HashSet 的 add 方法返回 false 时表示已有重复项。
   • 通过重写 equals 和 hashCode 方法，定义两个 Student 对象是否相等。
2. 时间复杂度：
   • 遍历学生列表：O(n)。
   • 每次插入或查询哈希表的时间复杂度为 O(1)，总复杂度为 O(n)。
3. 内存复杂度：
   • 需要额外的 O(n) 空间来存储已见过的学生和重复的学生。

优化方案：

如果数据量非常大，内存不足，可以考虑：

1. 使用外部存储：

   • 将数据存储到文件或数据库中，通过 SQL 查询 GROUP BY 或排序处理。

   • 示例 SQL 查询：

     SELECT id, name, age, COUNT(*)
     FROM students
     GROUP BY id, name, age
     HAVING COUNT(*) > 1;
     
     

2. 使用流式处理：

   • 对数据进行分片，逐片读取和处理以节省内存。