Java HashSet 去重的底层原理

HashSet 的去重功能基于两个核心机制：哈希算法和 equals() 方法。其底层实现依赖于 HashMap，具体原理如下：

1. 底层数据结构

• HashSet 内部使用 HashMap 存储元素
• 每个元素作为 HashMap 的 key
• Value 统一使用静态常量 PRESENT（占位对象）

// 源码示例
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT) == null;  // 核心添加逻辑
}

2. 去重流程

当调用 add() 方法时：

1. 计算哈希值

   • 调用元素的 hashCode() 方法获取哈希值
   • 通过哈希算法确定桶位置：
     $$ \text{index} = (n - 1) \ &\ \text{hash} $$ （其中 $n$ 是哈希表长度）

2. 检查桶内冲突

   • 若目标桶为空：直接插入新节点
   • 若桶非空（哈希冲突）：
     • 遍历桶内链表/红黑树
     • 使用 equals() 逐项比较元素

3. 重复判定标准
   满足以下任一条件即判定重复： $$ \begin{cases} \text{相同对象引用} \quad (==) \ \text{或} \ \text{hashCode() 相等} \ \land \ \text{equals() 返回 true} \end{cases} $$

3. 关键特性

• 时间复杂度：
  • 无冲突时：$O(1)$
  • 最坏情况（全冲突）：$O(\log n)$（Java 8+ 红黑树优化）
• 依赖关系：

  graph LR
  A[add元素] --> B[计算hashCode]
  B --> C{桶位置}
  C -->|空| D[直接插入]
  C -->|非空| E[遍历比较equals]
  E -->|相等| F[拒绝添加]
  E -->|不相等| G[链式插入]
  

4. 重写规范

使用自定义类时必须同时重写：

@Override
public int hashCode() {
    // 保证相同对象返回相同哈希值
    return Objects.hash(field1, field2); 
}

@Override
public boolean equals(Object o) {
    // 实现严谨的值相等逻辑
    if (this == o) return true;
    if (!(o instanceof MyClass)) return false;
    MyClass obj = (MyClass) o;
    return field1 == obj.field1 
        && Objects.equals(field2, obj.field2);
}

5. 典型踩坑场景

• 未重写 hashCode()：
  相同内容对象被分配到不同桶，去重失效
• 重写不一致：
  equals() 返回 true 但 hashCode() 不同，导致重复元素共存
• 可变对象问题：
  修改已存入 HashSet 的对象的字段，可能破坏哈希一致性

📌 最佳实践：

1. 优先使用 String、Integer 等不可变类
2. 自定义类需严格遵循 hashCode/equals 契约
3. 避免在集合内修改对象的关键字段