HashSet如何保证元素不重复

本文目录导读：

1. 底层数据结构
2. 添加元素时的唯一性校验流程
3. 必须遵守的契约：hashCode() 与 equals()
4. 举例说明
5. 核心保证机制

HashSet 在 Java 中保证元素不重复的核心机制是基于 HashMap 实现的，它利用哈希表（Hash Table）的特性，通过以下步骤来确保元素的唯一性：

底层数据结构

HashSet 内部维护了一个 HashMap 实例。

// HashSet 源码关键部分
private transient HashMap<E,Object> map;
// 一个虚拟的占位对象
private static final Object PRESENT = new Object();
public HashSet() {
    map = new HashMap<>();
}

当向 HashSet 添加元素时，实际上是将该元素作为 HashMap 的键（Key） 存入，而值（Value）则统一使用一个固定的虚拟对象 PRESENT。

添加元素时的唯一性校验流程

当调用 add(E e) 方法时，代码如下：

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

HashMap.put(key, value) 方法的核心逻辑：

1. 计算哈希值：调用 key.hashCode() 方法获取元素的哈希码。
2. 定位桶位置：根据哈希码计算元素在数组（table）中的索引位置。
3. 查找重复元素：
   • 如果在对应位置的链表或红黑树中,没有找到与该 key 哈希值相等且 equals() 返回 true 的节点，则将该 key-value 对插入，并返回 null。
   • 找到了 相同的 key（即 hashCode 相等且 equals() 返回 true），则用新 value 替换旧 value，并返回旧 value（即非 null）。

HashSet.add() 通过判断 map.put(e, PRESENT) == null 来决定是否添加成功：

• 返回 null：说明 HashMap 中原本没有这个 key，插入成功，HashSet 添加成功。
• 返回非 null（即 PRESENT）：说明 HashMap 中已有相同的 key，只是替换了 value，但 HashSet 认为元素已存在，添加失败。

必须遵守的契约：hashCode() 与 equals()

HashSet 判断两个元素是否相等的依据是两个方法的组合：

1. 先比较 hashCode()：
   • 如果两个对象的 hashCode() 不同，则直接判定为不同元素，不会调用 equals()。
2. 再比较 equals()：
   • 如果两个对象的 hashCode() 相同（发生了哈希冲突），则进一步调用 equals() 方法判断是否真正相等。
   • 只有当 equals() 返回 true 时，才认为是重复元素。

放入 HashSet 的自定义对象必须正确重写 hashCode() 和 equals() 方法，否则可能导致重复元素无法被识别的问题。

举例说明

Set<String> set = new HashSet<>();
set.add("apple");   // "apple".hashCode() 计算出索引，放入
set.add("banana");  // 不同 hash，直接放入
set.add("apple");   // 相同 hash，equals 比较返回 true，map.put 返回旧值，add 返回 false

set 中只有两个元素：["apple", "banana"]。

核心保证机制

HashSet 保证元素不重复的本质是 “HashMap的键不重复”，而 HashMap 依赖 hashCode() 和 equals() 的配合来完成去重。