Set 核心特性：唯一性的代价与收益
从一个疑问开始
Set 为什么能保证元素不重复？
答案藏在 equals 方法里——但如果每次添加都要遍历整个集合比较，时间复杂度岂不是 O(n)？为什么 HashSet 的 add 操作是 O(1)？
理解这个矛盾，就理解了 Set 的设计精髓。
Set 的契约：什么算「重复」
Set 不关心元素是什么，只关心两个元素是否「相等」。这个相等由你决定。
java
public interface Set<E> extends Collection<E> {
// 添加元素，如果已存在则忽略
boolean add(E e);
// 判断是否包含
boolean contains(Object o);
// ...
}关键点：Set 只用 equals 判断相等。但 HashSet 还多了一个条件——hashCode 必须配合。
去重的两把钥匙：hashCode 和 equals
为什么需要两把钥匙
假设只用 equals：
java
// 只用 equals：每次添加都要遍历
public boolean add(String s) {
for (String existing : elementData) {
if (s.equals(existing)) {
return false; // 重复，忽略
}
}
// 插入... O(n)
}10 万元素，每次添加都要比较 10 万次，性能无法接受。
引入 hashCode 做「预筛选」：
添加 "hello" 时：
1. 计算 hashCode() = 31（假设）
2. 只在 hashCode = 31 的桶里比较 equals
3. 如果该桶只有 1 个元素，只需比较 1 次这把钥匙把 O(n) 变成了 O(1)。
hashCode 和 equals 的契约
相等的对象必须有相等的 hashCode
java
public class Student {
private String name;
private int 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 age == student.age && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
}不遵守契约的后果
java
Set<Student> set = new HashSet<>();
Student s1 = new Student("张三", 20);
Student s2 = new Student("张三", 20);
System.out.println(s1.equals(s2)); // true（业务上相等）
System.out.println(s1.hashCode()); // 假设 9967
System.out.println(s2.hashCode()); // 假设 9967
set.add(s1);
System.out.println(set.contains(s2)); // true ✅ 两个都在同一桶
// 错误的 hashCode 实现：
// s1.hashCode() = 100
// s2.hashCode() = 200
set.add(s1);
set.contains(s2); // false ❌ 分布在不同桶，找不到！Set 的三种有序性
这是最容易混淆的点。Set 的「有序」有两种完全不同含义：
| 有序类型 | 含义 | 实现类 |
|---|---|---|
| 无序 | 遍历顺序不确定 | HashSet |
| 插入有序 | 遍历顺序 = 插入顺序 | LinkedHashSet |
| 排序有序 | 遍历顺序 = 自然顺序/自定义顺序 | TreeSet |
java
Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
Set<String> tree = new TreeSet<>();
List.of("c", "a", "b").forEach(s -> {
hash.add(s);
linked.add(s);
tree.add(s);
});
System.out.println("HashSet: " + hash); // 无序，如 [a, b, c]
System.out.println("LinkedHashSet: " + linked); // [c, a, b] 保持插入顺序
System.out.println("TreeSet: " + tree); // [a, b, c] 字母排序Set vs List：什么时候选 Set
java
// 选 List：如果需要按索引访问，允许重复
List<String> names = new ArrayList<>();
names.get(5); // ✅ O(1) 随机访问
// 选 Set：如果需要去重
Set<String> uniqueNames = new HashSet<>();
uniqueNames.add("张三");
uniqueNames.add("李四");
uniqueNames.add("张三"); // 自动忽略
System.out.println(uniqueNames.size()); // 2
// 选 List + Set 组合：既要访问又要去重
List<String> allNames = new ArrayList<>(new HashSet<>(rawData));Set 的 null 元素
| 实现类 | null 支持 |
|---|---|
| HashSet | ✅ 允许一个 null |
| LinkedHashSet | ✅ 允许一个 null |
| TreeSet | ❌ 不允许（抛出 NullPointerException） |
java
TreeSet<String> tree = new TreeSet<>();
tree.add(null); // NullPointerException！TreeSet 不允许 null 是因为它需要比较元素来确定顺序。没有比较规则，null 无法放入红黑树。
Set 的批量操作
java
Set<String> set1 = new HashSet<>(Arrays.asList("a", "b", "c"));
Set<String> set2 = new HashSet<>(Arrays.asList("b", "c", "d"));
// 交集
set1.retainAll(set2);
System.out.println(set1); // [b, c]
// 并集（addAll 自动去重）
Set<String> union = new HashSet<>(set1);
union.addAll(set2);
// 差集：属于 set1 但不属于 set2
Set<String> diff = new HashSet<>(set1);
diff.removeAll(set2);常见误区
误区 1：HashSet 遍历顺序等于插入顺序
错。HashSet 的遍历顺序取决于 hashCode 分布，和插入顺序无关。
java
Set<Integer> set = new HashSet<>();
set.add(3); set.add(1); set.add(2);
System.out.println(set); // 可能是 [1, 2, 3]，也可能不是如果需要保持插入顺序，用 LinkedHashSet。
误区 2：对象放入 Set 后可以修改字段
java
Set<Student> set = new HashSet<>();
Student s = new Student("张三", 20);
set.add(s);
// ❌ 修改了影响 hashCode 的字段！
s.setName("李四");
set.contains(s); // false！对象「消失」了
set.remove(s); // 移不出永远不要修改已入 Set 的对象的 key 字段。
误区 3：自定义对象天然去重
java
Set<Person> set = new HashSet<>();
set.add(new Person("张三", 20));
set.add(new Person("张三", 20)); // ❌ 添加成功！
System.out.println(set.size()); // 2Java 不知道你的「相等」规则。必须重写 hashCode 和 equals。
总结
| 要点 | 说明 |
|---|---|
| 去重原理 | hashCode 定位桶 + equals 比较 |
| 无序 Set | HashSet，O(1) 操作 |
| 插入有序 | LinkedHashSet，保留插入顺序 |
| 排序有序 | TreeSet，按自然顺序/比较器排序 |
| null 元素 | HashSet/LinkedHashSet 允许一个，TreeSet 不允许 |
| 对象去重 | 必须重写 hashCode 和 equals |
选型口诀：无排序需求用 HashSet，需要插入顺序用 LinkedHashSet，需要排序用 TreeSet。