HashSet 与 TreeSet：集合的无序性、唯一性与排序性
各位看官，咱们今天聊聊Java集合框架里两位性格迥异的“明星”——HashSet和TreeSet。它们都属于Set接口的实现类，拥有Set家族的共同特征：不允许重复元素。但是，它们在元素存储和访问方式上却有着截然不同的脾气，一个奔放不羁，一个井然有序。接下来，咱们就一起扒一扒它们的底裤，看看它们是如何各显神通的。
1. Set家族的共同特征：唯一性
在深入了解HashSet和TreeSet之前，我们先来明确一下Set接口的核心特性：唯一性。 也就是说，Set中不允许存在重复的元素。如果你尝试将重复元素添加到Set中，它会默默地忽略你的请求，就像一个高冷的管家，不动声色地拒绝不速之客。
这唯一性是如何保证的呢？ 这就要归功于Object类的两个重要方法：equals()和hashCode()。
equals()方法： 用于判断两个对象是否相等。hashCode()方法： 用于生成对象的哈希码，一个int类型的数值，可以理解为对象的指纹。
当向Set中添加元素时，Set会首先根据元素的hashCode()方法计算哈希码，然后将该元素存储到哈希表中对应的位置。如果该位置已经存在元素，则会调用equals()方法比较这两个元素是否相等。如果相等，则认为该元素已经存在，不会重复添加；如果不相等，则会采用某种策略（例如链地址法）解决哈希冲突，将新元素添加到哈希表中。
重要提示： 为了保证Set的唯一性，强烈建议重写自定义类的equals()和hashCode()方法，并且要保证：
- 如果
equals()方法返回true，则hashCode()方法必须返回相同的值。 - 如果
equals()方法返回false，则hashCode()方法最好返回不同的值（虽然不是强制要求，但可以提高性能）。
下面是一个简单的示例，展示了如何重写equals()和hashCode()方法：
import java.util.Objects;
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;
}
@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);
}
@Override
public String toString() {
return "Person{" +
"name='" + name + ''' +
", age=" + age +
'}';
}
}
public class SetExample {
public static void main(String[] args) {
Person p1 = new Person("Alice", 30);
Person p2 = new Person("Alice", 30);
System.out.println("p1.equals(p2): " + p1.equals(p2)); // 输出: true
System.out.println("p1.hashCode(): " + p1.hashCode()); // 输出: 某个哈希值
System.out.println("p2.hashCode(): " + p2.hashCode()); // 输出: 与p1.hashCode()相同的值
}
}在这个例子中，我们重写了Person类的equals()和hashCode()方法。equals()方法比较name和age是否相等，hashCode()方法根据name和age生成哈希码。这样，当两个Person对象的name和age都相同时，它们将被认为是相等的，并且具有相同的哈希码，从而保证了Set的唯一性。
2. HashSet：无序的狂野牛仔
HashSet是Set接口的一个实现类，它基于哈希表（实际上是HashMap）实现。HashSet的特点是：
- 无序性：
HashSet中的元素没有特定的顺序。你添加元素的顺序和元素在HashSet中的存储顺序可能并不一致。就像一个狂野的牛仔，自由奔放，不受约束。 - 快速查找： 由于基于哈希表实现，
HashSet在查找、添加和删除元素时具有很高的性能，时间复杂度通常为O(1)。 - 允许
null元素：HashSet允许添加一个null元素。 - 非线程安全：
HashSet不是线程安全的，如果在多线程环境下使用，需要进行同步处理。
下面是一个HashSet的使用示例：
import java.util.HashSet;
import java.util.Set;
public class HashSetExample {
public static void main(String[] args) {
Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
hashSet.add("Orange");
hashSet.add("Apple"); // 重复元素，不会被添加
hashSet.add(null); // 允许添加null元素
System.out.println("HashSet: " + hashSet); // 输出：HashSet: [null, Banana, Orange, Apple] (顺序可能不同)
boolean containsBanana = hashSet.contains("Banana");
System.out.println("Contains Banana: " + containsBanana); // 输出: Contains Banana: true
hashSet.remove("Banana");
System.out.println("HashSet after removing Banana: " + hashSet); // 输出: HashSet after removing Banana: [null, Orange, Apple] (顺序可能不同)
System.out.println("Size of HashSet: " + hashSet.size()); // 输出: Size of HashSet: 3
hashSet.clear();
System.out.println("HashSet after clearing: " + hashSet); // 输出: HashSet after clearing: []
}
}从上面的例子可以看出，HashSet中的元素是无序的，添加重复元素会被忽略，并且允许添加null元素。
HashSet的底层原理：HashMap的马甲
HashSet的底层实际上是使用HashMap来实现的。当你创建一个HashSet时，实际上是创建了一个HashMap，只不过HashMap的value全部使用同一个Object对象（PRESENT，一个静态的Object实例）作为占位符。
// HashSet的构造函数
public HashSet() {
map = new HashMap<>();
}
// HashSet的add方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// PRESENT，一个静态的Object实例
private static final Object PRESENT = new Object();因此，HashSet的性能很大程度上取决于HashMap的性能，而HashMap的性能又取决于哈希函数的质量和哈希冲突的解决策略。
3. TreeSet：秩序的优雅绅士
TreeSet也是Set接口的一个实现类，它基于红黑树（一种自平衡的二叉搜索树）实现。TreeSet的特点是：
- 有序性：
TreeSet中的元素是有序的。默认情况下，元素按照自然顺序（例如数字从小到大，字母按照字母表顺序）排序。你也可以通过提供一个Comparator来自定义排序规则。就像一个优雅的绅士，总是保持着井然有序的仪态。 - 快速查找： 由于基于红黑树实现，
TreeSet在查找、添加和删除元素时也具有较高的性能，时间复杂度通常为O(log n)，其中n是TreeSet中元素的数量。 - 不允许
null元素：TreeSet不允许添加null元素，否则会抛出NullPointerException。 - 非线程安全：
TreeSet不是线程安全的，如果在多线程环境下使用，需要进行同步处理。
下面是一个TreeSet的使用示例：
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;
public class TreeSetExample {
public static void main(String[] args) {
// 使用自然顺序排序
Set<String> treeSet1 = new TreeSet<>();
treeSet1.add("Banana");
treeSet1.add("Apple");
treeSet1.add("Orange");
treeSet1.add("Apple"); // 重复元素，不会被添加
System.out.println("TreeSet (natural order): " + treeSet1); // 输出: TreeSet (natural order): [Apple, Banana, Orange]
// 使用自定义Comparator排序
Set<String> treeSet2 = new TreeSet<>(Comparator.reverseOrder()); // 逆序排序
treeSet2.add("Banana");
treeSet2.add("Apple");
treeSet2.add("Orange");
System.out.println("TreeSet (reverse order): " + treeSet2); // 输出: TreeSet (reverse order): [Orange, Banana, Apple]
Set<Person> treeSet3 = new TreeSet<>(Comparator.comparing(Person::getAge).thenComparing(Person::getName)); //先按年龄升序，年龄相同按名字升序
treeSet3.add(new Person("Bob", 25));
treeSet3.add(new Person("Alice", 30));
treeSet3.add(new Person("Charlie", 25));
System.out.println("TreeSet (custom comparator): " + treeSet3); // 输出: TreeSet (custom comparator): [Person{name='Bob', age=25}, Person{name='Charlie', age=25}, Person{name='Alice', age=30}]
}
}从上面的例子可以看出，TreeSet中的元素是有序的，可以按照自然顺序排序，也可以通过提供Comparator来自定义排序规则。
TreeSet的底层原理：红黑树的守护
TreeSet的底层是使用TreeMap来实现的。TreeMap是一种基于红黑树的有序Map，可以保证元素的有序性。与HashSet类似，TreeSet也只是使用了TreeMap的key部分，value部分仍然使用同一个Object对象（PRESENT）作为占位符。
因此，TreeSet的性能很大程度上取决于TreeMap的性能，而TreeMap的性能又取决于红黑树的平衡性和操作效率。
4. HashSet vs TreeSet：性格大比拼
为了更直观地了解HashSet和TreeSet的区别，我们用一个表格来总结一下它们的特性：
| 特性 | HashSet |
TreeSet |
|---|---|---|
| 存储结构 | 哈希表（HashMap） |
红黑树（TreeMap） |
| 有序性 | 无序 | 有序（自然顺序或自定义Comparator） |
| 性能 | 查找、添加、删除：O(1) | 查找、添加、删除：O(log n) |
null元素 |
允许一个null元素 |
不允许null元素 |
| 线程安全 | 非线程安全 | 非线程安全 |
| 使用场景 | 不需要排序，对性能要求高的场景 | 需要排序，对性能要求不是特别高的场景 |
5. 选择哪个？ 这是一个问题
那么，在实际开发中，我们应该选择HashSet还是TreeSet呢？ 这取决于你的具体需求。
- 如果你不需要排序，并且对性能要求很高，那么
HashSet是更好的选择。 例如，你需要存储一组唯一的ID，并且需要快速查找某个ID是否存在。 - 如果你需要排序，并且对性能要求不是特别高，那么
TreeSet是更好的选择。 例如，你需要存储一组学生成绩，并且需要按照成绩从高到低排序。
总结：
HashSet和TreeSet是Java集合框架中两个重要的Set实现类。它们都保证元素的唯一性，但在元素存储和访问方式上却有着很大的不同。HashSet基于哈希表实现，具有无序性和快速查找的特点；TreeSet基于红黑树实现，具有有序性的特点。在实际开发中，你需要根据你的具体需求来选择合适的Set实现类。
希望这篇文章能够帮助你更好地理解HashSet和TreeSet的特性和使用场景。记住，选择合适的集合类，就像选择合适的武器，可以让你在编程战场上事半功倍，所向披靡！