跳转至

Java 中的 HashSet 内部是如何工作的？

一、结论

HashSet 内部就是一个 HashMap：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

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

所有元素作为 HashMap 的 key，value 都是同一个 PRESENT 对象。

二、工作流程

add(e)

  1. 把 e 作为 key，PRESENT 作为 value 调 map.put(e, PRESENT)。
  2. 如果 key 不存在，put 返回 null，add 返回 true。
  3. 如果 key 已存在，put 返回旧 value，add 返回 false。

contains(e)

直接 map.containsKey(e)。

remove(e)

map.remove(e)。

三、为什么用同一个 PRESENT

HashSet 只需要 key 集合，不需要 value。但 HashMap 必须有 value，所以用一个共享的 Object 占位，不占额外内存。

四、特性

  • 无序：不保证遍历顺序。
  • 允许 null：一个 null。
  • 非线程安全：多线程用 CopyOnWriteArraySet 或 Collections.synchronizedSet。
  • O(1) 添加/查找。

五、为什么不允许重复

HashMap 的 key 不能重复（equals/hashCode 判断），所以 HashSet 也不允许重复。

六、相关

  • LinkedHashSet：内部是 LinkedHashMap，保留插入顺序。
  • TreeSet：内部是 TreeMap，按 key 排序。
  • ConcurrentHashMap.newKeySet()：并发安全的 Set。

高频追问