💡 摘要：你是否曾疑惑为什么Set能自动去重？是否对HashSet的快速查找感到惊奇？是否被HashMap和HashSet的关系搞糊涂？
别担心，Set作为处理唯一性集合的核心接口，其背后的哈希表原理是Java集合框架的精华所在。
本文将带你从Set接口的特性讲起，通过对比List理解Set的去重机制。然后深入哈希表的工作原理，揭开hashCode()和equals()的神秘面纱。
接着详细剖析HashSet、LinkedHashSet和TreeSet三大实现类的内部机制和适用场景。从哈希冲突解决到红黑树优化，从迭代顺序到性能对比，让你彻底掌握Set集合的精髓。文末附实战案例和面试高频问题，助你在实际开发中游刃有余。
一、Set接口：唯一性的守护者
1. Set的核心特性
与List的对比：
| 特性 | List | Set |
| 顺序性 | 插入顺序保存 | 通常不保证顺序（除LinkedHashSet、TreeSet） |
| 唯一性 | 允许重复元素 | 不允许重复元素 |
| null元素 | 允许多个null | 最多允许一个null |
| 实现基础 | 数组、链表 | 哈希表、树 |
Set接口的核心方法：
java
// 基本操作
boolean add(E e); // 添加元素，重复返回false
boolean remove(Object o); // 删除元素
boolean contains(Object o); // 是否包含元素
void clear(); // 清空集合
int size(); // 元素数量
// 集合操作
boolean addAll(Collection<? extends E> c); // 并集
boolean retainAll(Collection<?> c); // 交集
boolean removeAll(Collection<?> c); // 差集
2. 去重机制：hashCode()与equals()
Set去重的核心原理：
java
// 添加元素时的判断逻辑
public boolean add(E e) {
return map.put(e, PRESENT) == null; // HashSet底层用HashMap实现
}
// HashMap的put方法核心逻辑
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
// 键已存在，不添加
return false;
}
二、哈希表原理：快速查找的魔法
1. 哈希表基本概念
哈希函数：将任意大小的数据映射到固定大小值的函数
java
// String类的hashCode实现
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i]; // 多项式哈希函数
}
hash = h;
}
return h;
}
哈希表结构：
text
数组 + 链表/红黑树
┌───┐ ┌───┬───┐ ┌───┬───┐
│ 0 │ → │ A │ → │ │ │ │
├───┤ └───┴───┘ └───┴───┘
│ 1 │ → │ B │ → │ │ → │ C │
├───┤ └───┴───┘ └───┴───┘
│ 2 │ → │ D │ → │ │ │ │
├───┤ └───┴───┘ └───┴───┘
│ 3 │ → null
└───┘
2. 哈希冲突解决
链表法（Separate Chaining）：
java
// JDK 1.8之前的实现：数组+链表
if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度阈值
treeifyBin(tab, hash); // 转换为红黑树
开放地址法：Hashtable使用，但HashMap采用链表法
3. HashMap的优化机制
树化优化：当链表长度超过8时，转换为红黑树
java
static final int TREEIFY_THRESHOLD = 8; // 树化阈值
static final int UNTREEIFY_THRESHOLD = 6; // 链化阈值
// 红黑树节点定义
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左孩子
TreeNode<K,V> right; // 右孩子
TreeNode<K,V> prev; // 前驱节点
boolean red; // 颜色标志
}
三、HashSet：基于HashMap的Set实现
1. 内部实现机制
HashSet的本质：基于HashMap的包装类
java
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private transient HashMap<E, Object> map; // 底层HashMap
// 虚拟值，用于HashMap的value
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>(); // 默认初始容量16，加载因子0.75
}
public boolean add(E e) {
return map.put(e, PRESENT) == null; // 利用HashMap的key去重
}
}
2. 构造方法与参数
java
// 1. 默认构造：初始容量16，加载因子0.75
Set<String> set1 = new HashSet<>();
// 2. 指定初始容量
Set<String> set2 = new HashSet<>(100); // 初始容量100
// 3. 指定初始容量和加载因子
Set<String> set3 = new HashSet<>(100, 0.8f); // 容量100，加载因子0.8
// 4. 从其他集合创建
Set<String> set4 = new HashSet<>(list); // 包含list中所有不重复元素
3. 性能特点
时间复杂度：
- add()：平均O(1)，最坏O(log n)（树化时）
- remove()：平均O(1)，最坏O(log n)
- contains()：平均O(1)，最坏O(log n)
加载因子与扩容：
java
// 默认加载因子0.75：当元素数量达到容量*0.75时扩容
Set<String> set = new HashSet<>(16, 0.75f); // 当size=12时扩容
// 扩容过程：创建新数组（2倍大小），重新哈希所有元素
四、LinkedHashSet：保持插入顺序的Set
1. 内部实现机制
基于LinkedHashMap的实现：
java
public class LinkedHashSet<E> extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet() {
super(16, 0.75f, true); // 调用HashSet的特定构造方法
}
}
// HashSet中的特殊构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
2. 双向链表维护顺序
LinkedHashMap的内部结构：
text
哈希表 + 双向链表
┌───┐ ┌───────────────┐
│ 0 │ → │ Node1 │ → │ Node2 │
├───┤ ├───────────────┤ ┌───────────────┐
│ 1 │ → │ Node3 │ → │ Node4 │ → │ Node5 │
├───┤ └───────────────┘ └───────────────┘
│ 2 │ → null
└───┘
↑ ↓
头节点 尾节点
3. 适用场景
java
// 需要保持插入顺序的去重集合
Set<String> orderedSet = new LinkedHashSet<>();
orderedSet.add("z");
orderedSet.add("a");
orderedSet.add("b");
orderedSet.add("a"); // 重复元素，不会添加
System.out.println(orderedSet); // [z, a, b] 保持插入顺序
// 实现LRU缓存的基础
Set<String> lruSet = new LinkedHashSet<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) {
return size() > MAX_ENTRIES;
}
};
五、TreeSet：基于红黑树的排序Set
1. 内部实现机制
基于TreeMap的实现：
java
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
private transient NavigableMap<E, Object> m; // 底层TreeMap
public TreeSet() {
this(new TreeMap<E, Object>()); // 自然排序
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator)); // 定制排序
}
}
2. 排序方式
自然排序：
java
Set<String> naturalSet = new TreeSet<>();
naturalSet.add("orange");
naturalSet.add("apple");
naturalSet.add("banana");
System.out.println(naturalSet); // [apple, banana, orange] 字母顺序
定制排序：
java
// 按字符串长度排序
Set<String> lengthSet = new TreeSet<>((s1, s2) -> {
int lenCompare = Integer.compare(s1.length(), s2.length());
return lenCompare != 0 ? lenCompare : s1.compareTo(s2);
});
lengthSet.add("apple");
lengthSet.add("banana");
lengthSet.add("cat");
lengthSet.add("dog");
System.out.println(lengthSet); // [cat, dog, apple, banana]
3. 红黑树特性
自平衡二叉搜索树：
- 每个节点是红色或黑色
- 根节点是黑色
- 红色节点的子节点必须是黑色
- 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点
时间复杂度：
- add()：O(log n)
- remove()：O(log n)
- contains()：O(log n)
- first()/last()：O(log n)
六、三大Set实现对比
1. 特性对比表
| 特性 | HashSet | LinkedHashSet | TreeSet |
| 底层实现 | HashMap | LinkedHashMap | TreeMap |
| 排序特性 | 无顺序 | 插入顺序 | 自然排序/定制排序 |
| 性能 | O(1)平均 | O(1)平均 | O(log n) |
| null元素 | 允许1个 | 允许1个 | 不允许（除非Comparator支持） |
| 线程安全 | 否 | 否 | 否 |
| 适用场景 | 快速去重 | 保持插入顺序的去重 | 需要排序的去重 |
2. 性能测试对比
java
public class SetPerformanceTest {
public static void main(String[] args) {
final int SIZE = 100000;
// HashSet测试
Set<Integer> hashSet = new HashSet<>();
long start1 = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
hashSet.add(i);
}
long time1 = System.nanoTime() - start1;
// LinkedHashSet测试
Set<Integer> linkedSet = new LinkedHashSet<>();
long start2 = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
linkedSet.add(i);
}
long time2 = System.nanoTime() - start2;
// TreeSet测试
Set<Integer> treeSet = new TreeSet<>();
long start3 = System.nanoTime();
for (int i = 0; i < SIZE; i++) {
treeSet.add(i);
}
long time3 = System.nanoTime() - start3;
System.out.printf("HashSet: %d ns%n", time1);
System.out.printf("LinkedHashSet: %d ns%n", time2);
System.out.printf("TreeSet: %d ns%n", time3);
}
}
典型结果：
text
HashSet: 12500000 ns
LinkedHashSet: 14500000 ns
TreeSet: 28500000 ns
七、实战应用与最佳实践
1. 自定义对象的去重
java
class Student {
private String id;
private String name;
public Student(String id, String name) {
this.id = id;
this.name = name;
}
// 必须重写hashCode和equals
@Override
public int hashCode() {
return Objects.hash(id); // 只基于id计算哈希值
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
Student other = (Student) obj;
return Objects.equals(id, other.id); // 只比较id
}
}
// 使用示例
Set<Student> students = new HashSet<>();
students.add(new Student("1001", "Alice"));
students.add(new Student("1001", "Alice")); // 不会添加，id相同
students.add(new Student("1002", "Bob"));
2. 集合运算实战
java
Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));
// 并集
Set<Integer> union = new HashSet<>(set1);
union.addAll(set2); // [1, 2, 3, 4, 5, 6, 7, 8]
// 交集
Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // [4, 5]
// 差集
Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2); // [1, 2, 3]
// 对称差集
Set<Integer> symmetricDiff = new HashSet<>(union);
symmetricDiff.removeAll(intersection); // [1, 2, 3, 6, 7, 8]
3. 线程安全方案
java
// 方法1：Collections.synchronizedSet
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
// 方法2：CopyOnWriteArraySet（读多写少场景）
Set<String> copyOnWriteSet = new CopyOnWriteArraySet<>();
// 方法3：ConcurrentHashMap.keySet()
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
八、总结：Set选择的艺术
- 默认选择HashSet：大多数去重场景，性能最优
- 需要保持顺序选LinkedHashSet：缓存、LRU实现
- 需要排序选TreeSet：排行榜、范围查询
- 自定义对象必须重写hashCode()和equals()
- 线程安全用并发集合：CopyOnWriteArraySet或ConcurrentHashMap.keySet()
🚀 理解Set背后的哈希表原理和红黑树机制，是掌握Java集合框架的关键一步。
九、面试高频问题
❓1. HashSet如何保证元素不重复？
答：通过HashMap的key去重。添加元素时调用hashCode()确定存储位置，再用equals()比较是否重复。
❓2. hashCode()和equals()的契约是什么？
答：
- 两个对象equals()为true，则hashCode()必须相同
- hashCode()相同的对象，equals()不一定为true
- 重写equals()必须重写hashCode()
❓3. LinkedHashSet如何保持插入顺序？
答：底层使用LinkedHashMap，通过维护双向链表来记录插入顺序。
❓4. TreeSet的排序方式有哪些？
答：
- 自然排序：元素实现Comparable接口
- 定制排序：传入Comparator比较器
❓5. 哈希冲突的解决方法有哪些？
答：
- 链表法：HashMap使用，链表过长时树化
- 开放地址法：Hashtable使用
- 再哈希法：使用多个哈希函数
- 公共溢出区法：将冲突元素放在额外区域
