HashSet 与 HashMap 关系

面试官问："HashSet 底层是怎么实现的？"

候选人小张答："HashSet 底层用的是 HashMap。"

面试官追问："具体是怎么用 HashMap 实现的？"

小张说不上来。

【面试官心理】 HashSet 依赖 HashMap 实现是 Java 集合框架的经典设计。能说出 HashSet 用 HashMap 存储元素作为 key、固定 value 作为占位符的候选人，说明对 JDK 源码有过研究。

一、HashSet 的本质 🔴

1.1 源码结构

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

    // HashSet 内部持有一个 HashMap
    private transient HashMap<E, Object> map;

    // HashMap 的 value 固定为一个占位符
    private static final Object PRESENT = new Object();

    // 构造函数
    public HashSet() {
        map = new HashMap<>();
    }

    // 构造函数：指定初始容量
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    // 构造函数：指定初始容量和负载因子
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    // add 方法
    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // 添加成功返回 true
    }

    // 其他方法都是委托给 map
}

1.2 为什么 value 是固定对象

// HashSet 只关心 key（元素本身）
// value 没有实际用途，只需要一个占位符

private static final Object PRESENT = new Object();

// add 操作：
// map.put(e, PRESENT) → 如果 key 已存在，返回旧 value（PRESENT）
// add 返回 map.put() == null → 已存在返回 false

// remove 操作：
// map.remove(e) → 返回 PRESENT 表示删除成功
// 因为 key 是元素，value 总是 PRESENT

1.3 所有操作都委托给 HashMap

// HashSet 的每个方法都是委托给 HashMap

public int size() {
    return map.size();
}

public boolean isEmpty() {
    return map.isEmpty();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

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

public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

public void clear() {
    map.clear();
}

二、HashSet vs HashMap 对比 🔴

2.1 核心区别

维度	HashSet	HashMap
存储内容	单个元素	键值对
内部结构	HashMap（键=元素，值=占位符）	哈希桶数组
唯一性保证	元素的 hashCode 和 equals	Key 的 hashCode 和 equals
null 支持	可以有一个 null 元素	key 可以有一个 null，value 可以有多个 null
添加方法	`add(E e)`	`put(K k, V v)`
取出方法	不能直接取出，只能遍历	`get(K k)`
时间复杂度	O(1) 均摊（和 HashMap 相同）	O(1) 均摊

2.2 等价关系

// HashSet 和 HashMap 的等价操作

// 添加元素
set.add(e) == map.put(e, PRESENT)

// 删除元素
set.remove(e) == (map.remove(e) == PRESENT)

// 检查是否存在
set.contains(e) == map.containsKey(e)

// 获取大小
set.size() == map.size()

// 是否为空
set.isEmpty() == map.isEmpty()

2.3 ❌ 错误示范

候选人原话："HashSet 和 HashMap 是两个完全不同的实现。"

问题诊断：

没有看过 HashSet 的源码
不理解集合框架的设计模式

面试官内心 OS："HashSet 源码只有几十行，readability 很高。这个候选人肯定没看过。"

【面试官心理】 HashSet 依赖 HashMap 实现是 JDK 的经典设计模式。理解这一点，说明候选人对集合框架有深入理解。

三、HashSet 的构造方法 🟡

3.1 四种构造方法

// 1. 默认构造函数
HashSet() {
    map = new HashMap<>();
}

// 2. 指定初始容量
HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

// 3. 指定初始容量和负载因子
HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

// 4. 使用已有集合初始化
HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16));
    addAll(c);
}

3.2 LinkedHashSet

// LinkedHashSet 同样依赖 LinkedHashMap
public class LinkedHashSet<E>
        extends HashSet<E>
        implements Set<E> {

    public LinkedHashSet() {
        super(16, 0.75f, true); // accessOrder = true
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2 * c.size(), 11), 0.75f, true);
        addAll(c);
    }
}

// HashSet 的这个构造函数接受 accessOrder 参数
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

3.3 TreeSet

// TreeSet 依赖 TreeMap
public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, Serializable {

    private transient NavigableMap<E, Object> m;

    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E, Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E, Object>());
    }

    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

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

四、自定义对象作为 HashSet 元素 🟡

4.1 必须重写 hashCode 和 equals

// 如果要用自定义对象作为 HashSet 的元素
// 必须重写 hashCode() 和 equals()

public class Person {
    private String name;
    private int age;

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
}

4.2 ❌ 错误示范

// ❌ 没有重写 hashCode 和 equals
public class Person {
    private String name;
    private int age;
    // ...
}

HashSet<Person> set = new HashSet<>();
Person p1 = new Person("Alice", 25);
Person p2 = new Person("Alice", 25);

set.add(p1);
set.add(p2);

System.out.println(set.size()); // 2！不是 1！
// 因为 p1 和 p2 的 hashCode 不同（默认是 Object 的地址）

4.3 常见坑点

// ❌ 坑点 1：hashCode 返回固定值
public class BadPerson {
    public int hashCode() {
        return 1; // 所有对象的 hashCode 都相同
    }
}
// 后果：所有元素都在同一个桶，退化为链表
// 性能退化为 O(n)

// ❌ 坑点 2：equals 逻辑错误
public class WrongPerson {
    public boolean equals(Object o) {
        return true; // 总是返回 true
    }
}
// 后果：所有对象都被认为是相等的
// set.add 永远返回 false（第二个元素开始）

// ✅ 正确做法
public class GoodPerson {
    private String name;
    private int age;

    public int hashCode() {
        return Objects.hash(name, age);
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
}

⚠️

自定义对象作为 HashSet 的元素时，必须同时重写 hashCode() 和 equals()，并且保持一致性：相等的对象必须有相同的 hashCode。

五、生产选型 🟡

5.1 Set 类型选择

// 需要去重 + 不需要顺序 → HashSet（O(1)）
Set<String> unique = new HashSet<>();
unique.add("a");
unique.add("b");
unique.add("a"); // 被忽略

// 需要去重 + 需要插入顺序 → LinkedHashSet（O(1)）
Set<String> insertOrder = new LinkedHashSet<>();
insertOrder.add("a");
insertOrder.add("b");
insertOrder.add("c");
// 遍历顺序：a -> b -> c

// 需要去重 + 需要排序 → TreeSet（O(log n)）
Set<String> sorted = new TreeSet<>();
sorted.add("banana");
sorted.add("apple");
sorted.add("cherry");
// 遍历顺序：apple -> banana -> cherry

// 需要去重 + 多线程安全 → CopyOnWriteArraySet
// 或 Collections.newSetFromMap(new ConcurrentHashMap<>())
Set<String> concurrent = Collections.newSetFromMap(
    new ConcurrentHashMap<>());

5.2 性能对比

类型	时间复杂度	是否有序	线程安全
HashSet	O(1) 均摊	否	否
LinkedHashSet	O(1) 均摊	插入顺序	否
TreeSet	O(log n)	自然顺序/自定义	否
CopyOnWriteArraySet	O(n)	否	是
ConcurrentHashMap	O(1) 均摊	否	是

5.3 最佳实践

// 场景 1：去重
List<Integer> numbers = Arrays.asList(1, 2, 3, 2, 1, 4);
Set<Integer> unique = new HashSet<>(numbers);
// unique = {1, 2, 3, 4}

// 场景 2：去重并保持顺序
List<Integer> numbers = Arrays.asList(1, 2, 3, 2, 1, 4);
Set<Integer> unique = new LinkedHashSet<>(numbers);
// unique = {1, 2, 3, 4}（保持插入顺序）

// 场景 3：性能敏感
Set<String> cache = new HashSet<>(expectedSize);

// 场景 4：需要排序
Set<String> sorted = new TreeSet<>(Comparator.reverseOrder());

// 场景 5：多线程
Set<String> threadSafe = Collections.newSetFromMap(
    new ConcurrentHashMap<>());

六、源码扩展 🟢

6.1 Clone 方法

// HashSet 的 clone 是浅拷贝
public Object clone() {
    try {
        HashSet<E> result = (HashSet<E>) super.clone();
        result.map = (HashMap<E, Object>) map.clone();
        return result;
    } catch (CloneNotSupportedException e) {
        throw new InternalError(e);
    }
}

// 注意：clone 后，HashSet 的底层 HashMap 会被复制
// 但 HashMap 中的 key 和 value 对象是共享的（浅拷贝）

6.2 序列化

// HashSet 的序列化
// 只序列化 HashMap 的 key（PRESENT 不需要序列化）
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    s.defaultWriteObject();
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());
    s.writeInt(map.size());

    for (E e : map.keySet())
        s.writeObject(e);
}

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    int capacity = s.readInt();
    float loadFactor = s.readFloat();
    int size = s.readInt();

    map = ((HashMap<E, Object>) (capacity >= 0 ?
        new HashMap<>(capacity, loadFactor) :
        (HashMap<K,V>) new java.util.LinkedHashMap<>(capacity, loadFactor)));

    for (int i = 0; i < size; i++) {
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

6.3 Iterator

// HashSet 的迭代器委托给 HashMap
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

// 所以 HashSet 的迭代顺序取决于底层的 HashMap
// HashSet → HashMap → HashMap.Node → 迭代

七、面试高频追问 🟡

7.1 第一层追问

面试官："HashSet 的 contains 操作时间复杂度是多少？"

候选人：...

正确回答：O(1) 均摊。因为 HashSet 的 contains 委托给 HashMap 的 containsKey，而 HashMap 的 containsKey 是 O(1) 均摊。

7.2 第二层追问

面试官："HashSet 的 add 操作怎么保证元素不重复？"

候选人：...

正确回答：HashSet 的 add 委托给 HashMap 的 put。HashMap 要求 key 唯一，底层通过 hashCode 定位桶，再通过 equals 比较 key。所以：

hashCode 决定在哪个桶
equals 决定是否相同

7.3 第三层追问

面试官："HashSet 和 HashMap 的内部结构有什么关系？"

候选人：...

正确回答：

HashSet 内部持有一个 HashMap
HashSet 的元素作为 HashMap 的 key
HashMap 的 value 是一个固定的占位符（PRESENT）
所有操作都委托给 HashMap

7.4 第四层追问

面试官："LinkedHashSet 和 HashSet 的区别是什么？"

候选人：...

正确回答：

LinkedHashSet 继承 HashSet
LinkedHashSet 底层用 LinkedHashMap 代替 HashMap
LinkedHashSet 按插入顺序遍历，HashSet 无序

【学习小结】 HashSet 核心要点：

底层依赖 HashMap，元素作为 key，PRESENT 作为固定 value
所有操作都委托给 HashMap
去重依赖 hashCode 和 equals
自定义对象作为元素必须重写 hashCode 和 equals
选型：HashSet（无序）→ LinkedHashSet（插入顺序）→ TreeSet（排序）

#HashSet 与 HashMap 关系

#一、HashSet 的本质 🔴

#1.1 源码结构

#1.2 为什么 value 是固定对象

#1.3 所有操作都委托给 HashMap

#二、HashSet vs HashMap 对比 🔴

#2.1 核心区别

#2.2 等价关系

#2.3 ❌ 错误示范

#三、HashSet 的构造方法 🟡

#3.1 四种构造方法

#3.2 LinkedHashSet

#3.3 TreeSet

#四、自定义对象作为 HashSet 元素 🟡

#4.1 必须重写 hashCode 和 equals

#4.2 ❌ 错误示范

#4.3 常见坑点

#五、生产选型 🟡

#5.1 Set 类型选择

#5.2 性能对比

#5.3 最佳实践

#六、源码扩展 🟢

#6.1 Clone 方法

#6.2 序列化

#6.3 Iterator

#七、面试高频追问 🟡

#7.1 第一层追问

#7.2 第二层追问

#7.3 第三层追问

#7.4 第四层追问

HashSet 与 HashMap 关系

一、HashSet 的本质 🔴

1.1 源码结构

1.2 为什么 value 是固定对象

1.3 所有操作都委托给 HashMap

二、HashSet vs HashMap 对比 🔴

2.1 核心区别

2.2 等价关系

2.3 ❌ 错误示范

三、HashSet 的构造方法 🟡

3.1 四种构造方法

3.2 LinkedHashSet

3.3 TreeSet

四、自定义对象作为 HashSet 元素 🟡

4.1 必须重写 hashCode 和 equals

4.2 ❌ 错误示范

4.3 常见坑点

五、生产选型 🟡

5.1 Set 类型选择

5.2 性能对比

5.3 最佳实践

六、源码扩展 🟢

6.1 Clone 方法

6.2 序列化

6.3 Iterator

七、面试高频追问 🟡

7.1 第一层追问

7.2 第二层追问

7.3 第三层追问

7.4 第四层追问