HashSet 是如何保证元素不重复的？

2025年阅读约 7 分钟面试指南 · Java面试

Java 面试集合

深入解析HashSet的去重原理，从HashMap底层到hashCode和equals的配合，分初级、中级、高级三个层次全面讲解。

一句话总结

HashSet 底层是 HashMap（元素作 key，PRESENT 作 value），去重依赖 hashCode() + equals()。先比 hashCode（不同则不是重复），再比 equals（true 才判重）。重写 equals 必须重写 hashCode，否则两个 equals 为 true 的对象 hash 不同，去重失效。TreeSet 底层是 TreeMap，通过 compareTo/compare 判重。

初级理解

HashSet 底层就是一个 HashMap：元素作为 HashMap 的 key，value 是一个固定的 PRESENT 对象（new Object()）。

HashSet 的去重依赖于 HashMap 的 key 不重复特性，而 HashMap 判断 key 是否重复依赖两个方法：

1. hashCode()：先比较 hash 值，hash 不同则一定不是同一个 key

2. equals()：hash 相同后再比较 equals，equals 返回 true 才认为是同一个 key

// HashSet 的 add 方法本质 public boolean add(E e) { return map.put(e, PRESENT) == null; // PRESENT = new Object() }

判断流程：hashCode 不同 → 不是重复；hashCode 相同 → equals 比较 → equals 为 true → 重复，不添加。

中级深入

为什么重写 equals 必须重写 hashCode？如果只重写 equals 不重写 hashCode，两个 equals 为 true 的对象可能 hash 值不同，导致 HashMap/HashSet 认为它们是不同的 key，破坏了"相等对象必须有相等 hash 值"的约定。

class Person { String name; // 只重写 equals，没重写 hashCode @Override public boolean equals(Object o) { return name.equals(((Person) o).name); } } Set<Person> set = new HashSet<>(); Person p1 = new Person("张三"); Person p2 = new Person("张三"); set.add(p1); set.add(p2); // p2 也添加成功了！因为 hashCode 不同 System.out.println(set.size()); // 2，去重失败！

正确做法：同时重写 equals 和 hashCode，保证 equals 相等的对象 hashCode 也相等。

高级拓展

HashSet 的 add 方法为什么返回 boolean？返回 true 表示添加成功（元素之前不存在），false 表示元素已存在（去重生效）。

LinkedHashSet 的去重原理：继承 HashSet，底层是 LinkedHashMap（HashMap + 双向链表），在保证去重的同时维护插入顺序。

TreeSet 的去重原理：底层是 TreeMap（红黑树），通过 Comparable.compareTo() 或 Comparator.compare() 判断是否重复（返回 0 即重复），不依赖 hashCode 和 equals。

// TreeSet 按自然顺序排序 + 去重 Set<Integer> treeSet = new TreeSet<>(); treeSet.add(3); treeSet.add(1); treeSet.add(2); treeSet.add(2); // 重复，不添加 System.out.println(treeSet); // [1, 2, 3]，自动排序

面试加分项：能说出 HashSet 底层是 HashMap、TreeSet 底层是 TreeMap，以及为什么重写 equals 必须重写 hashCode。

实战场景

场景：用 HashSet 去重 + Lombok 的正确姿势

// 反例：Lombok @Data 只生成 getter/setter/equals/hashCode/toString // 如果字段很多，equals/hashCode 计算开销大 @Data public class User { private Long id; private String name; private String email; private Date createTime; } // 正例：只基于业务主键生成 equals/hashCode @Getter @Setter public class User { private Long id; private String name; private String email; private Date createTime; @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof User)) return false; return Objects.equals(id, ((User) o).id); } @Override public int hashCode() { return Objects.hash(id); } }

面试模拟

Q：HashSet 怎么判断两个元素是否重复？

A：分两步：1) hashCode() 比较 hash 值，不同则一定不重复；2) hash 相同再调用 equals()，返回 true 才判重。这要求 equals 相等的对象 hashCode 必须相等（Object 规范），否则去重失效。

Q：HashSet、LinkedHashSet、TreeSet 有什么区别？

A：HashSet：基于 HashMap，无序，O(1)；LinkedHashSet：基于 LinkedHashMap，维护插入顺序，O(1)；TreeSet：基于 TreeMap（红黑树），按自然顺序或 Comparator 排序，O(log n)。选型：需要去重+排序→TreeSet，需要去重+保持插入顺序→LinkedHashSet，只需去重→HashSet。