Java Set的去重原理探究 - 摩柯技术社区

Java Set的基础概念

在Java集合框架中，Set是一种特殊的集合类型，它与List的最大区别在于Set不允许包含重复元素。Set接口继承自Collection接口，为我们提供了一个用于存储唯一元素的容器。常见的Set实现类有HashSet、TreeSet和LinkedHashSet ，它们各自有着不同的特性和应用场景，但都遵循不允许重复元素这一基本原则。

HashSet的去重原理

HashSet是Set接口最常用的实现类，它基于HashMap来实现，其去重原理主要依赖于哈希表和equals()方法。

哈希表的工作原理

哈希表是一种数据结构，它通过一个哈希函数将键值映射到一个特定的位置，以便快速查找和插入元素。在HashSet中，每个元素都会通过其hashCode()方法生成一个哈希码，这个哈希码会被用来确定元素在哈希表中的存储位置。

例如，我们有如下代码：

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

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("apple");
        System.out.println(set);
    }
}

在上述代码中，当我们向HashSet中添加元素时，首先会调用元素的hashCode()方法。假设"apple"的哈希码为1234，"banana"的哈希码为5678。哈希表会根据这些哈希码计算出对应的存储位置。

hashCode()方法

hashCode()方法是定义在Object类中的方法，每个Java对象都有这个方法。默认情况下，hashCode()方法返回对象的内存地址经过特定算法计算后的结果。但在很多类中，这个方法会被重写以提供更合理的哈希码计算方式。比如，String类就重写了hashCode()方法，根据字符串的内容来计算哈希码。

在HashSet中，如果两个元素的hashCode()值不同，那么它们很可能存储在哈希表的不同位置，也就不会被认为是重复元素。然而，如果两个元素的hashCode()值相同，这并不意味着它们是重复元素，还需要进一步通过equals()方法进行判断。

equals()方法

当两个元素的hashCode()值相同，HashSet会调用它们的equals()方法来判断这两个元素是否真的相等。equals()方法也是定义在Object类中的方法，默认情况下比较的是两个对象的内存地址。但在实际应用中，我们通常会重写equals()方法，使其根据对象的实际内容来判断是否相等。

比如，我们自定义一个类Person，并在HashSet中使用它：

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

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        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;
        Person person = (Person) o;
        return age == person.age && name.equals(person.name);
    }

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

public class HashSetPersonExample {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        Person p1 = new Person("Alice", 25);
        Person p2 = new Person("Alice", 25);
        set.add(p1);
        set.add(p2);
        System.out.println(set.size());
    }
}

在上述代码中，我们重写了Person类的equals()方法，使其根据name和age属性来判断两个Person对象是否相等。同时，我们也重写了hashCode()方法，根据name和age计算哈希码。这样，当我们向HashSet中添加两个具有相同name和age的Person对象时，HashSet会认为它们是重复元素，最终集合的大小为1。

TreeSet的去重原理

TreeSet是一个有序的Set实现类，它基于红黑树（一种自平衡二叉搜索树）来实现。TreeSet的去重原理与HashSet有所不同，它主要依赖于元素的自然顺序或者自定义的比较器。

自然顺序

如果元素实现了Comparable接口，TreeSet会使用元素的自然顺序来进行排序和去重。Comparable接口中定义了compareTo()方法，这个方法用于比较当前对象与另一个对象的大小关系。

例如，我们有如下代码：

import java.util.Set;
import java.util.TreeSet;

class IntegerWrapper implements Comparable<IntegerWrapper> {
    private int value;

    public IntegerWrapper(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(IntegerWrapper other) {
        return Integer.compare(this.value, other.value);
    }
}

public class TreeSetExample {
    public static void main(String[] args) {
        Set<IntegerWrapper> set = new TreeSet<>();
        set.add(new IntegerWrapper(5));
        set.add(new IntegerWrapper(3));
        set.add(new IntegerWrapper(5));
        System.out.println(set);
    }
}

在上述代码中，IntegerWrapper类实现了Comparable接口，并在compareTo()方法中定义了比较逻辑。当我们向TreeSet中添加元素时，TreeSet会根据compareTo()方法的返回值来确定元素的位置，并且会将相等的元素（即compareTo()方法返回0的元素）视为重复元素，不会重复添加。

自定义比较器

除了使用自然顺序，我们还可以通过传递一个自定义的Comparator来让TreeSet按照我们期望的方式进行排序和去重。Comparator接口中定义了compare()方法，用于比较两个对象。

例如：

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

class PersonComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        int nameCompare = p1.getName().compareTo(p2.getName());
        if (nameCompare != 0) {
            return nameCompare;
        }
        return Integer.compare(p1.getAge(), p2.getAge());
    }
}

class Person {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

public class TreeSetPersonExample {
    public static void main(String[] args) {
        Set<Person> set = new TreeSet<>(new PersonComparator());
        Person p1 = new Person("Alice", 25);
        Person p2 = new Person("Alice", 25);
        set.add(p1);
        set.add(p2);
        System.out.println(set.size());
    }
}

在上述代码中，我们定义了一个PersonComparator类实现了Comparator接口，并在compare()方法中定义了比较Person对象的逻辑。当我们创建TreeSet时，传递了这个自定义的比较器。TreeSet会根据这个比较器的逻辑来进行排序和去重，同样会将相等的元素（根据比较器定义的相等）视为重复元素。

LinkedHashSet的去重原理

LinkedHashSet是HashSet的一个子类，它在保留HashSet去重特性的基础上，还维护了插入顺序或者访问顺序。

插入顺序

LinkedHashSet默认按照元素的插入顺序来维护集合中的元素顺序。它通过一个双向链表来记录元素的插入顺序。当我们向LinkedHashSet中添加元素时，首先会按照HashSet的去重原理判断元素是否重复，如果不重复则将元素添加到链表的尾部。

例如：

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();
        set.add("apple");
        set.add("banana");
        set.add("cherry");
        set.add("apple");
        for (String s : set) {
            System.out.println(s);
        }
    }
}

在上述代码中，LinkedHashSet会按照元素插入的顺序输出"apple"、"banana"、"cherry"，并且不会重复输出"apple"，因为它遵循了HashSet的去重原理。

访问顺序

LinkedHashSet还可以按照元素的访问顺序来维护集合。要实现这一点，我们需要使用LinkedHashSet的构造函数，传入true来表示使用访问顺序。当一个元素被访问（例如通过get()方法获取元素）时，它会被移动到链表的尾部。

例如：

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetAccessOrderExample {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>(16, 0.75f, true);
        set.add("apple");
        set.add("banana");
        set.add("cherry");
        set.contains("banana");
        for (String s : set) {
            System.out.println(s);
        }
    }
}

在上述代码中，由于我们在创建LinkedHashSet时指定了使用访问顺序，当我们调用contains("banana")访问了"banana"元素后，"banana"元素会被移动到链表的尾部。最终输出的顺序会反映这种访问顺序的调整，并且同样遵循去重原则。

不同Set实现类去重原理的比较

哈希表与树结构：HashSet基于哈希表实现，其去重主要依赖哈希码和equals()方法，查找和插入操作平均时间复杂度为O(1)。而TreeSet基于红黑树实现，去重依赖元素的顺序比较，查找和插入操作时间复杂度为O(log n)。因此，在需要快速插入和查找且对顺序无要求时，HashSet更合适；而在需要有序存储且去重时，TreeSet更合适。
插入顺序与访问顺序：LinkedHashSet在去重原理上继承自HashSet，但额外维护了插入顺序或访问顺序。如果需要在去重的同时保留元素的插入顺序或者访问顺序，LinkedHashSet是一个很好的选择。
性能考虑：在处理大量数据时，HashSet的性能优势会更加明显，因为其平均O(1)的操作复杂度。但如果数据需要有序，并且对顺序操作有较多需求，TreeSet虽然时间复杂度为O(log n)，但能提供有序性保证。而LinkedHashSet由于维护链表结构，在插入和删除操作上会比HashSet略慢一些，但能满足特定的顺序需求。

应用场景分析

数据去重：在处理大量数据且不需要关注元素顺序时，HashSet是最常用的选择。例如，在统计文本文件中不重复的单词数量时，HashSet可以快速去重，并且由于其基于哈希表，插入和查找操作效率高。
有序去重：如果需要对数据进行去重并且要求元素有序，比如在对一些编号进行去重并从小到大排序，TreeSet是理想的选择。它可以自动对元素进行排序并去重。
顺序敏感的去重：当需要在去重的同时保留元素的插入顺序或者访问顺序时，LinkedHashSet就派上用场了。例如，在实现一个简单的缓存系统，需要记录最近访问的元素时，LinkedHashSet可以按照访问顺序维护元素，并且去重避免重复记录。

自定义类在Set中的去重注意事项

重写hashCode()和equals()方法：当使用HashSet或LinkedHashSet时，对于自定义类，必须正确重写hashCode()和equals()方法。如果只重写equals()方法而不重写hashCode()方法，可能会导致在哈希表中相同内容的对象被存储在不同位置，无法达到去重效果。同样，如果只重写hashCode()方法而不重写equals()方法，当哈希码相同但对象内容不同时，也无法正确去重。
实现Comparable接口或提供Comparator：当使用TreeSet时，自定义类要么实现Comparable接口，提供自然顺序的比较逻辑；要么在创建TreeSet时提供一个Comparator，定义自定义的比较逻辑。否则，在向TreeSet中添加元素时会抛出ClassCastException异常。

深入理解Set去重原理的重要性

优化性能：了解不同Set实现类的去重原理，可以根据具体的应用场景选择最合适的Set实现，从而优化程序的性能。例如，在对性能要求极高且无序要求的场景下，选择HashSet可以获得最佳的插入和查找效率。
避免错误：正确理解去重原理有助于避免在使用Set时出现意外的错误。比如，在自定义类中正确重写hashCode()和equals()方法，能够确保HashSet和LinkedHashSet正确去重，否则可能会导致重复元素被错误地添加到集合中。
拓展应用：深入理解去重原理后，可以基于Set的特性进行更多的拓展应用。比如，结合LinkedHashSet的访问顺序特性，实现更复杂的缓存淘汰策略等。

总结Set去重原理的要点

HashSet：基于哈希表，依赖hashCode()和equals()方法去重，平均时间复杂度为O(1)。
TreeSet：基于红黑树，依赖元素的自然顺序（实现Comparable接口）或自定义比较器（Comparator）去重，时间复杂度为O(log n)。
LinkedHashSet：继承HashSet的去重原理，额外维护插入顺序或访问顺序。

通过深入理解这些要点，开发者可以在实际编程中更加灵活、高效地使用Set集合，充分发挥其去重和其他特性的优势，提升程序的质量和性能。