Set是如何保证元素不重复的

1. 引言

在Java中，Set是一种用于存储元素的集合，但与List不同的是，Set中的元素是不可重复的。这意味着当我们向Set中添加一个元素时，Set会自动检查是否已经存在相同的元素，如果存在则不会添加，保证了Set中的元素是唯一的。本文将介绍Java中Set的工作原理，以及它是如何保证元素不重复的。

2. Set接口和实现类

在Java中，Set是一个接口，它继承自Collection接口，并且没有提供额外的方法。Java中常用的Set的实现类有HashSet、LinkedHashSet和TreeSet。其中，HashSet是最常用的实现类，它基于哈希表实现；LinkedHashSet是一个按照插入顺序排序的Set，它继承自HashSet，并使用链表维护插入顺序；TreeSet是基于红黑树实现的Set，它可以对元素进行排序。

3. Set如何判断元素的唯一性

Set是如何保证元素的唯一性呢？答案是利用了元素的equals()和hashCode()方法。当我们将一个元素添加到Set中时，它会首先通过元素的hashCode()方法计算出一个哈希值，然后根据这个哈希值找到对应的位置，如果该位置上已经存在相同的元素，就通过equals()方法比较两个元素是否相等，如果相等则不添加，否则添加到Set中。

Set<String> set = new HashSet<>();
set.add("apple");
set.add("pear");
set.add("banana");
set.add("apple");

System.out.println(set);

输出结果：

[apple, pear, banana]

在上面的代码中，我们向Set中添加了四个元素，其中包含了一个重复的元素"apple"。但由于Set的唯一性特性，最终Set中只有三个元素。这是因为Set在添加元素时，通过hashCode()和equals()方法判断新添加的元素是否与已有元素相等，如果相等则不进行添加。

4. hashCode()和equals()方法的重写

为了保证Set的唯一性，我们通常需要重写元素的hashCode()和equals()方法。默认情况下，Java使用Object类中的hashCode()和equals()方法，它们是基于对象的内存地址的。但对于自定义的类，我们经常需要根据对象的实际属性来判断两个对象是否相等。

public class Person {
    private String name;
    private int age;

    // getters and setters

    @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 && Objects.equals(name, person.name);
    }

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

在上面的代码中，我们重写了Person类的hashCode()和equals()方法。在equals()方法中，我们首先比较两个对象的内存地址，如果相等则直接返回true；否则，我们再判断两个对象的类是否相同，以及它们的属性是否相等。在hashCode()方法中，我们使用Objects类的hash()方法根据对象的属性计算出一个哈希值。

Set<Person> set = new HashSet<>();
set.add(new Person("Alice", 20));
set.add(new Person("Bob", 30));
set.add(new Person("Alice", 20));

System.out.println(set);

输出结果：

[Person{name='Alice', age=20}, Person{name='Bob', age=30}]

在上面的代码中，我们向Set中添加了三个Person对象，其中包含了一个重复的对象。通过重写hashCode()和equals()方法，我们可以保证Set中的元素是唯一的。注意，在重写hashCode()方法时，如果两个对象的equals()方法返回true，则它们的hashCode()方法应该返回相同的值，这是为了保证相等的对象具有相等的哈希值。

5. Set的性能分析

Set的性能与其实现类有关，下面我们来分析HashSet、LinkedHashSet和TreeSet的性能特点。

5.1 HashSet

HashSet是基于哈希表实现的Set，它通过哈希值来定位元素的位置，具有很好的插入和查找性能。

Set<Integer> set = new HashSet<>();

// 添加10000个元素
for (int i = 0; i < 10000; i++) {
    set.add(i);
}

// 查找元素
boolean contains = set.contains(100);
System.out.println(contains);

输出结果：

true

在上面的代码中，我们向HashSet中添加了10000个元素，并且通过contains()方法查找了一个元素。HashSet的插入和查找操作都具有常数时间复杂度O(1)，这是因为哈希表能够快速定位元素的位置。

5.2 LinkedHashSet

LinkedHashSet是一个按照插入顺序排序的Set，它在HashSet的基础上使用了链表来维护插入顺序。因此，在插入和查找操作上，它的性能与HashSet基本相同。

Set<Integer> set = new LinkedHashSet<>();

// 添加10000个元素
for (int i = 0; i < 10000; i++) {
    set.add(i);
}

// 查找元素
boolean contains = set.contains(100);
System.out.println(contains);

输出结果：

true

在上面的代码中，我们向LinkedHashSet中添加了10000个元素，并且通过contains()方法查找了一个元素。与HashSet类似，LinkedHashSet的插入和查找操作都具有常数时间复杂度O(1)。

5.3 TreeSet

TreeSet是基于红黑树实现的Set，它可以对元素进行排序，并且插入和查找操作的时间复杂度为O(logN)。注意，TreeSet要求元素实现Comparable接口或者提供Comparator比较器。

Set<Integer> set = new TreeSet<>();

// 添加10000个元素
for (int i = 0; i < 10000; i++) {
    set.add(i);
}

// 查找元素
boolean contains = set.contains(100);
System.out.println(contains);

输出结果：

true

在上面的代码中，我们向TreeSet中添加了10000个元素，并且通过contains()方法查找了一个元素。TreeSet的插入和查找操作的时间复杂度为O(logN)，这是因为红黑树能够保持树的平衡。

6. 总结

本文介绍了Java中Set的工作原理，以及它是如何保证元素不重复的。我们了解了Set接口和常用的实现类HashSet、LinkedHashSet和TreeSet。通过重写hashCode()和equals()方法，我们可以自定义类的相等性判断。最后，我们分析了HashSet、LinkedHashSet和TreeSet的性能特点。