Java Stream distinct 方法去重原理

在 Java 编程中，处理集合数据时经常会遇到需要去除重复元素的场景。Java 8 引入的 Stream API 为我们提供了一种便捷的方式来处理这类操作，其中 distinct 方法就是专门用于去重的。本文将深入探讨 Java Stream distinct 方法的去重原理，并通过丰富的代码示例来帮助读者更好地理解。

1. Stream API 简介

Stream API 是 Java 8 引入的一个强大的功能，它允许以一种声明式的方式处理集合数据。Stream 不是数据结构，它并不直接存储数据，而是在数据上定义了一系列的操作，比如过滤、映射、归约等。Stream 操作可以分为中间操作和终端操作，中间操作返回一个新的 Stream，允许链式调用多个操作，而终端操作会触发计算并返回结果。distinct 方法属于中间操作，它返回一个由该流的不同元素（根据 Object.equals(Object) 方法）组成的流。

2. distinct 方法的基本使用

在开始深入原理之前，先来看一下 distinct 方法的基本使用。假设我们有一个包含重复元素的 List，想要去除其中的重复元素，可以使用如下代码：

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

public class DistinctExample {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 2, 3, 4, 4, 5);
        List<Integer> distinctNumbers = numbers.stream()
                                             .distinct()
                                             .collect(Collectors.toList());
        System.out.println(distinctNumbers);
    }
}

上述代码中，我们通过 stream() 方法将 List 转换为 Stream，然后调用 distinct() 方法去除重复元素，最后使用 collect(Collectors.toList()) 将处理后的 Stream 转换回 List。运行结果将输出 [1, 2, 3, 4, 5]，重复的 2 和 4 都被去除了。

3. 去重原理 - 基于 `equals` 方法

distinct 方法的去重原理是基于对象的 equals 方法。当流中的元素依次经过 distinct 操作时，它会维护一个已处理元素的集合。对于每个新元素，distinct 方法会调用该元素的 equals 方法与已处理集合中的元素进行比较。如果新元素与已处理集合中的任何元素都不相等（根据 equals 方法的定义），则该元素会被保留在结果流中，并添加到已处理集合中；否则，该元素将被丢弃。

在 Java 中，所有类都继承自 Object 类，Object 类提供了默认的 equals 方法，其实现是基于对象的内存地址比较。这意味着如果一个类没有重写 equals 方法，那么 distinct 方法在去重时将基于对象的内存地址判断是否重复。对于大多数自定义类，我们需要重写 equals 方法以实现基于业务逻辑的去重。

例如，假设有一个自定义类 Person：

class Person {
    private String name;
    private int age;

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

    // Getters and setters
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

如果我们使用 Person 对象的 Stream 并调用 distinct 方法，由于没有重写 equals 方法，即使两个 Person 对象具有相同的 name 和 age，它们也会被视为不同的对象，因为它们的内存地址不同。

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

public class PersonDistinctExample {
    public static void main(String[] args) {
        Person person1 = new Person("Alice", 25);
        Person person2 = new Person("Alice", 25);
        Person person3 = new Person("Bob", 30);

        List<Person> people = Arrays.asList(person1, person2, person3);
        List<Person> distinctPeople = people.stream()
                                            .distinct()
                                            .collect(Collectors.toList());

        System.out.println(distinctPeople.size()); // 输出 3，因为没有重写 equals 方法
    }
}

4. 重写 `equals` 和 `hashCode` 方法

为了让 distinct 方法按照我们期望的方式工作，即基于对象的某些属性判断是否重复，我们需要重写 equals 方法。同时，为了保证 HashSet 等基于哈希的集合类能够正确工作，我们还需要重写 hashCode 方法。

在重写 equals 方法时，应该遵循以下几个原则：

自反性：对于任何非空引用值 x，x.equals(x) 应该返回 true。
对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应该返回 true。
传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应该返回 true。
一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 应该始终返回 true 或者始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。
对于任何非空引用值 x，x.equals(null) 应该返回 false。

重写 hashCode 方法时，应该保证如果两个对象根据 equals 方法比较相等，那么它们的 hashCode 方法返回的值也必须相等。

以下是重写 Person 类的 equals 和 hashCode 方法的示例：

class Person {
    private String name;
    private int age;

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

    // Getters and setters
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && name.equals(person.name);
    }

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + name.hashCode();
        result = 31 * result + age;
        return result;
    }
}

现在，再次运行 PersonDistinctExample 代码，结果将是 2，因为具有相同 name 和 age 的 person1 和 person2 被视为相同的对象，distinct 方法去除了重复的对象。

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

public class PersonDistinctExample {
    public static void main(String[] args) {
        Person person1 = new Person("Alice", 25);
        Person person2 = new Person("Alice", 25);
        Person person3 = new Person("Bob", 30);

        List<Person> people = Arrays.asList(person1, person2, person3);
        List<Person> distinctPeople = people.stream()
                                            .distinct()
                                            .collect(Collectors.toList());

        System.out.println(distinctPeople.size()); // 输出 2
    }
}

5. 去重过程中的数据结构

在 distinct 方法的实现中，通常会使用 HashSet 来维护已处理元素的集合。HashSet 是基于哈希表实现的集合，它通过计算元素的哈希值来快速定位元素的存储位置，从而实现高效的查找和插入操作。

当流中的元素依次经过 distinct 操作时，HashSet 会先计算元素的哈希值，根据哈希值快速定位到对应的存储桶（bucket）。如果该存储桶为空，说明该元素是第一次出现，将其插入到 HashSet 中；如果该存储桶不为空，再调用元素的 equals 方法与存储桶中的元素进行比较，若不相等则插入，相等则丢弃。

这种基于哈希表的实现方式使得 distinct 方法在大多数情况下能够高效地去除重复元素。对于包含大量元素的流，HashSet 的平均查找时间复杂度为 O(1)，相比线性查找（例如使用 ArrayList 并逐个比较元素），大大提高了去重的效率。

以下是一个简单的模拟 HashSet 去重过程的示例代码，以帮助理解其工作原理：

import java.util.ArrayList;
import java.util.List;

class MyHashSet {
    private static final int DEFAULT_CAPACITY = 16;
    private List<List<Object>> buckets;

    public MyHashSet() {
        buckets = new ArrayList<>(DEFAULT_CAPACITY);
        for (int i = 0; i < DEFAULT_CAPACITY; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    public boolean add(Object o) {
        int hash = o.hashCode();
        int index = hash & (DEFAULT_CAPACITY - 1);
        List<Object> bucket = buckets.get(index);
        for (Object element : bucket) {
            if (element.equals(o)) {
                return false;
            }
        }
        bucket.add(o);
        return true;
    }
}

public class HashSetSimulation {
    public static void main(String[] args) {
        MyHashSet set = new MyHashSet();
        set.add("apple");
        set.add("banana");
        set.add("apple");
        set.add("cherry");

        // 可以通过遍历 buckets 来查看存储情况
        for (int i = 0; i < set.buckets.size(); i++) {
            System.out.println("Bucket " + i + ": " + set.buckets.get(i));
        }
    }
}

上述代码模拟了一个简单的 HashSet，add 方法实现了类似 HashSet 的插入逻辑。当插入元素时，先计算哈希值确定存储桶位置，再在存储桶内通过 equals 方法检查是否重复。

6. 并行流中的去重

当使用并行流（通过 parallelStream 方法创建）时，distinct 方法的工作原理基本相同，但实现上会更加复杂。在并行流中，流数据会被分成多个部分，由不同的线程并行处理。每个线程在处理自己负责的部分数据时，会维护各自的局部 HashSet 来进行去重。

在并行处理完成后，需要将各个局部 HashSet 中的元素合并到一个最终的结果集中。这个合并过程需要保证去重的正确性，即避免重复元素的再次出现。通常，合并过程会采用一种叫做“归约”（reduction）的操作，将各个局部结果逐步合并成最终结果。

以下是一个简单的并行流去重示例：

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

public class ParallelDistinctExample {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 2, 3, 4, 4, 5);
        List<Integer> distinctNumbers = numbers.parallelStream()
                                             .distinct()
                                             .collect(Collectors.toList());
        System.out.println(distinctNumbers);
    }
}

在并行流中，distinct 方法能够利用多核处理器的优势，提高去重的效率，特别是对于大规模数据集。但需要注意的是，并行流的性能提升并非总是显著的，因为并行处理引入了线程创建、数据划分和合并等额外开销，对于小规模数据集，串行流可能反而更高效。

7. 与其他去重方法的比较

除了 Stream 的 distinct 方法，Java 中还有其他方法可以实现集合元素的去重，例如使用 HashSet 直接构造集合。以下是几种常见去重方法的比较：

7.1 使用 `HashSet` 构造集合

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

public class HashSetDeduplication {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 4, 4, 5));
        Set<Integer> set = new HashSet<>(numbers);
        List<Integer> distinctNumbers = new ArrayList<>(set);
        System.out.println(distinctNumbers);
    }
}

这种方法直接利用 HashSet 的特性，在构造 HashSet 时自动去除重复元素。优点是简单直观，缺点是如果需要对集合进行更多的流操作，还需要将 HashSet 转换回 List 等其他集合类型，操作相对繁琐。

7.2 使用 `Stream` 的 `distinct` 方法

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

public class StreamDistinctDeduplication {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(1, 2, 2, 3, 4, 4, 5);
        List<Integer> distinctNumbers = numbers.stream()
                                             .distinct()
                                             .collect(Collectors.toList());
        System.out.println(distinctNumbers);
    }
}

Stream 的 distinct 方法在功能上与使用 HashSet 构造集合类似，但它提供了更灵活的链式操作方式，可以方便地与其他流操作（如过滤、映射等）结合使用。对于复杂的数据处理场景，Stream 的 distinct 方法更具优势。

7.3 使用 `Guava` 库的 `Sets` 工具类

Google Guava 库提供了 Sets 工具类，其中的 Sets.newHashSet(Iterable<E> iterable) 方法也可以用于去重：

import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class GuavaDeduplication {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 2, 3, 4, 4, 5));
        Set<Integer> set = Sets.newHashSet(numbers);
        List<Integer> distinctNumbers = new ArrayList<>(set);
        System.out.println(distinctNumbers);
    }
}

这种方法与直接使用 HashSet 构造集合类似，但借助了 Guava 库的便利性。如果项目中已经引入了 Guava 库，使用这种方法也是一个不错的选择。

8. 注意事项

性能问题：虽然 distinct 方法在大多数情况下能够高效地去重，但对于非常大的数据集，由于 HashSet 的内存占用和计算哈希值等操作，可能会导致性能问题。在这种情况下，可以考虑分块处理数据或者使用更高效的数据结构。
自定义类的重写：对于自定义类，一定要正确重写 equals 和 hashCode 方法，否则 distinct 方法可能无法按预期工作。同时，在重写这两个方法时，要遵循相关的规范和原则，以保证代码的正确性和一致性。
并行流的开销：在使用并行流进行去重时，要充分考虑并行处理带来的额外开销。对于小规模数据集，串行流可能更高效。在实际应用中，需要通过性能测试来确定是否使用并行流以及如何配置并行流的参数。

综上所述，Java Stream distinct 方法为我们提供了一种便捷且高效的去重方式。通过深入理解其去重原理、掌握正确的使用方法以及注意相关的性能和实现细节，我们能够在处理集合数据时更加得心应手。无论是简单的数值集合还是复杂的自定义对象集合，distinct 方法都能帮助我们快速有效地去除重复元素，提升代码的质量和效率。

Java Stream distinct 方法去重原理