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

面试考察点

面试官提出这个问题，核心是想考察你对 Java 集合框架设计的深入理解，而非仅仅记住一个 API。主要考察点包括：

对 Java 集合框架顶层设计的理解：Set 接口的 “不重复” 契约是如何通过底层数据结构实现的？它与 Map 接口有何精妙的关联？
对 equals() 和 hashCode() 方法契约的掌握：这是理解 HashSet 等实现类如何工作的基石。面试官想知道你是否清楚这两个方法如何协同工作来决定“唯一性”。
对具体实现类（如 HashSet, TreeSet）源码级机制的了解：例如，HashSet 如何处理哈希冲突？TreeSet 的 “唯一性” 依据又是什么？
理论与实践结合的能力：你是否能在实际编码中正确地重写 equals() 和 hashCode() 方法来使用 Set，避免常见陷阱？

核心答案

Set 保证元素不重复的核心机制因实现类而异，但底层都严格依赖于 equals() 和 hashCode() 方法（对于 TreeSet 则是 Comparable/Comparator）。

以 HashSet (最常用) 为例：它内部使用一个 HashMap 来存储元素。当你调用 add(e) 时，元素 e 实际上是作为 HashMap 的 Key 被放入的。HashMap 的 Key 必须是唯一的，其唯一性正是通过先比较 hashCode()，再比较 equals() 来严格保证的。因此，HashSet 间接继承了这套机制。
以 TreeSet 为例：它内部使用 TreeMap（红黑树）存储。其唯一性由元素的比较规则决定。当使用 Comparable 自然排序或自定义 Comparator 时，如果 compareTo() 或 compare() 返回 0，则认为两个元素 “相等”，新元素不会被加入。

一句话总结：Set 通过其底层实现（Map）的键唯一性机制来保证元素不重复，而该机制精确地依赖于 hashCode/equals 或比较器。

深度解析

原理/机制

HashSet 与 HashMap 的适配器模式： HashSet 的源码非常简单，它包含一个 HashMap 实例。所有元素作为该 HashMap 的键（Key）存储，而值（Value）则统一存储为一个名为 PRESENT 的静态空对象。
```
// 摘自 JDK 11 的 HashSet 源码
public class HashSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;
    // 虚拟值，与键关联
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // 关键在此！
    }
}
```
因此，HashSet 的“不重复”特性完全是由 HashMap 的“键唯一”特性保证的。
HashMap 的键唯一性判定流程（核心）：当向 HashMap（即 HashSet 底层）添加一个键 Key 时，会执行以下判定：

步骤 1：计算哈希码。调用 key.hashCode() 计算哈希值，通过扰动函数确定其在哈希表中的桶（bucket）位置。

步骤 2：检查桶内元素。
- 如果该桶为空，直接插入，认为元素“不重复”。
- 如果该桶非空（哈希冲突），则遍历该桶内的链表或红黑树节点，对每个已存在的键 k，进行如下判断：
  1. 先比较哈希值：如果 key.hashCode() 与 k.hashCode() 不同，则 key != k，继续检查下一个。
  2. 再比较相等性：如果哈希值相同，则调用 key.equals(k) 进行最终裁决。
    - 如果 equals() 返回 true，则认为 key 与 k 相同，新值会覆盖旧值（在 HashSet 中表现为 add 返回 false）。
    - 如果 equals() 返回 false，则视为哈希冲突，将 key 以链表或红黑树节点形式加入桶中。
这个 hashCode() 快速筛选 + equals() 最终裁决 的两步机制，是保证高效判重的关键。

代码示例

下面的例子展示了错误和正确的实践：

import java.util.HashSet;

public class SetUniquenessDemo {
    static class WrongPerson {
        String id;
        String name;
        // 构造器、getter/setter 省略...
        // **错误：只重写了 equals， 未重写 hashCode**
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            WrongPerson that = (WrongPerson) o;
            return id.equals(that.id); // 业务上认为 id 相同即为同一人
        }
        // 没有重写 hashCode()！将使用 Object 的默认实现（通常返回内存地址）
    }

    static class CorrectPerson {
        String id;
        String name;
        // 构造器、getter/setter 省略...
        // **正确：同时重写 equals 和 hashCode**
        @Override
        public boolean equals(Object o) { /* 同上，基于 id 比较 */ }

        @Override
        public int hashCode() {
            return id.hashCode(); // 必须使用 equals 方法中用于比较的相同字段！
        }
    }

    public static void main(String[] args) {
        HashSet<WrongPerson> wrongSet = new HashSet<>();
        WrongPerson wp1 = new WrongPerson("001", "Alice");
        WrongPerson wp2 = new WrongPerson("001", "Alice");
        wrongSet.add(wp1);
        wrongSet.add(wp2); // 由于 hashCode 不同，它们可能落入不同桶，equals 不会被调用，导致 Set 中存在两个“业务相同”的对象！
        System.out.println("WrongPerson Set size: " + wrongSet.size()); // 输出可能是 2

        HashSet<CorrectPerson> correctSet = new HashSet<>();
        CorrectPerson cp1 = new CorrectPerson("001", "Alice");
        CorrectPerson cp2 = new CorrectPerson("001", "Alice");
        correctSet.add(cp1);
        correctSet.add(cp2); // hashCode 相同，落入同一桶，再调用 equals 返回 true，判定为重复，添加失败
        System.out.println("CorrectPerson Set size: " + correctSet.size()); // 输出 1
    }
}

对比分析与最佳实践

HashSet vs TreeSet vs LinkedHashSet：
- HashSet：基于哈希表，判重依赖 hashCode() 和 equals()，性能最佳（O(1)平均），但元素无序。
- TreeSet：基于红黑树，判重依赖 compareTo()/compare() 是否返回0，元素自然有序或按比较器排序，性能为 O(log n)。
- LinkedHashSet：继承 HashSet，但同时维护一个链表来记录插入顺序，判重机制与 HashSet 相同，能提供可预测的迭代顺序。
最佳实践与常见误区：
1. 必须同时重写 equals() 和 hashCode()：这是使用 HashSet、HashMap 等哈希集合类的铁律。且必须保证：如果 equals() 返回 true，则两个对象的 hashCode() 返回值必须相等（反之则不一定）。
2. 用于计算 hashCode() 和 equals() 的字段应是不可变的：如果字段可变，对象放入集合后修改了这些字段，会导致 hashCode 变化，从而无法在集合中正确找到该对象，引发内存泄漏和逻辑错误。
3. 使用 IDE 或 Objects 工具类生成：手动实现容易出错，推荐使用 IDE 自动生成或 Objects.hash(field1, field2...) 和 Objects.equals()。
4. TreeSet 的判重陷阱：TreeSet 仅依赖于比较器，即使两个对象的 equals() 返回 false，只要比较器认为它们相等（返回0），也会被视作重复。这可能导致与 HashSet 行为不一致。

总结

Set 保证元素不重复的本质，是将其作为底层 Map 的键来存储，并严格遵循由 hashCode() 和 equals()（或比较器）共同定义的对象相等性契约；理解并正确实现这个契约，是高效、无误使用 Set 及相关集合类的关键。

发布于2026年01月23日|17:20:01