网站公告

本次更新：没啥更新的

“钱塘江上潮信起，今日方知我是我”

朕知道了
Noctiflorous Garden

外观

HashSet ​

字数: 0 字 时长: 0 分钟

1. HashSet 概述 ​

HashSet 是 Java 中 Set 接口最常用的实现类之一。

它最大的特点就是：

text
元素不能重复

并且：

text
不保证元素的遍历顺序

HashSet 的底层实际上是：

text
HashMap

可以简单理解为：

text
HashSet
    ↓
HashMap
    ↓
Set 中的元素作为 HashMap 的 Key

而 HashMap 的：

text
Key 不能重复

所以 HashSet 自然而然也就实现了：

text
元素不能重复

HashSet 的类定义：

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

继承关系：

text
Collection
    ↑
   Set
    ↑
HashSet

2. HashSet 基本使用 ​

来看一个简单的例子：

java
Set<String> set = new HashSet<>();

set.add("张无忌");
set.add("赵敏");
set.add("周芷若");
set.add("张无忌");

System.out.println(set);

虽然：

java
"张无忌"

添加了两次，但最终 HashSet 中只会保存一份。

因为：

text
HashSet
    ↓
不允许重复元素

需要注意：

HashSet 不保证元素的遍历顺序。

所以不要依赖：

text
插入顺序

来判断 HashSet 的输出顺序。

3. HashSet 的底层结构 ​

HashSet 中有一个非常重要的字段：

java
private transient HashMap<E, Object> map;

也就是说：

text
HashSet
    ↓
内部维护一个 HashMap

HashSet 中的元素：

text
E

会被保存为 HashMap 的：

text
Key

那 HashMap 的 Value 放什么？

HashSet 定义了一个固定对象：

java
private static final Object PRESENT =
        new Object();

所以整个结构可以理解为：

text
HashSet 元素
    ↓
HashMap Key


PRESENT
    ↓
HashMap Value

例如：

java
set.add("张无忌");

底层实际上类似于：

java
map.put(
        "张无忌",
        PRESENT
);

因此：

text
HashSet

本质上可以理解为：

只使用 HashMap 的 Key，而不关心 Value。

4. 构造方法 ​

4.1 无参构造 ​

创建 HashSet：

java
HashSet<String> set =
        new HashSet<>();

底层：

java
public HashSet() {

    map =
            new HashMap<>();
}

也就是说：

text
new HashSet()
    ↓
new HashMap()

4.2 指定初始容量 ​

也可以指定初始容量：

java
HashSet<String> set =
        new HashSet<>(16);

对应源码：

java
public HashSet(
        int initialCapacity) {

    map =
            new HashMap<>(
                    initialCapacity
            );
}

本质仍然是把参数传给：

java
HashMap

4.3 指定初始容量和负载因子 ​

java
HashSet<String> set =
        new HashSet<>(
                16,
                0.75f
        );

源码：

java
public HashSet(
        int initialCapacity,
        float loadFactor) {

    map =
            new HashMap<>(
                    initialCapacity,
                    loadFactor
            );
}

所以 HashSet 的：

text
容量

负载因子

扩容

本质上都依赖底层：

text
HashMap

5. add() ​

HashSet 中最重要的方法就是：

java
add()

源码非常简单：

java
public boolean add(
        E e) {

    return map.put(
            e,
            PRESENT
    ) == null;
}

可以看到：

text
HashSet.add(e)
    ↓
HashMap.put(e, PRESENT)

也就是说：

text
HashSet 元素
    ↓
HashMap Key

而：

text
PRESENT

只是一个固定的占位对象。

5.1 为什么不能添加重复元素 ​

假设：

java
set.add("张无忌");

底层：

java
map.put(
        "张无忌",
        PRESENT
);

第一次添加：

text
HashMap 中不存在这个 Key
    ↓
插入成功

再次添加：

java
set.add("张无忌");

还是：

java
map.put(
        "张无忌",
        PRESENT
);

因为 HashMap 中：

text
Key 唯一

所以不会再创建一个新的 "张无忌"。

而是：

text
找到原来的 Key
    ↓
更新 Value

但由于 Value 本身始终都是：

java
PRESENT

所以从 HashSet 的角度来看：

text
什么都没有发生

这就是 HashSet：

text
不能保存重复元素

的根本原因。

6. HashSet 如何判断元素是否重复 ​

既然 HashSet 底层使用的是：

text
HashMap

那么判断元素是否重复，本质上也就是：

HashMap 判断 Key 是否相同的过程。

整个过程可以简单理解为：

text
元素
    ↓
hashCode()
    ↓
计算 hash
    ↓
计算数组下标
    ↓
找到对应桶
    ↓
比较 Key

最终还会结合：

text
hashCode()

equals()

判断元素是否相同。

所以对于自定义对象，如果希望 HashSet 正确判断重复元素，就需要正确处理：

java
hashCode()

和：

java
equals()

例如：

java
class User {

    private String name;

    private int age;
}

如果希望：

text
name 和 age 相同

的两个 User 被认为是同一个元素，就应该按照这个规则重写：

text
equals()

hashCode()

否则即使两个对象中的数据完全一样：

java
new User("张无忌", 20)

new User("张无忌", 20)

HashSet 也可能把它们当成两个不同对象。

所以：

HashSet 的去重不是简单依靠 hashCode，而是依赖底层 HashMap 对 Key 的判断逻辑。

7. contains() ​

判断 HashSet 中是否存在某个元素：

java
set.contains(
        "张无忌"
);

源码：

java
public boolean contains(
        Object o) {

    return map.containsKey(o);
}

可以看到：

text
HashSet.contains()
    ↓
HashMap.containsKey()

因为 HashSet 中的元素本来就是：

text
HashMap 的 Key

所以只需要判断：

text
Key 是否存在

即可。

8. remove() ​

删除元素：

java
set.remove(
        "张无忌"
);

源码：

java
public boolean remove(
        Object o) {

    return map.remove(o)
            == PRESENT;
}

本质：

text
HashSet.remove()
    ↓
HashMap.remove()
    ↓
根据 Key 删除键值对

如果删除成功：

text
返回 PRESENT

那么：

java
map.remove(o) == PRESENT

结果就是：

text
true

9. iterator() ​

HashSet 也可以使用迭代器进行遍历：

java
Iterator<String> iterator =
        set.iterator();

while (
        iterator.hasNext()
) {

    System.out.println(
            iterator.next()
    );
}

HashSet 的 iterator()：

java
public Iterator<E> iterator() {

    return map
            .keySet()
            .iterator();
}

可以看到：

text
HashSet.iterator()
    ↓
HashMap.keySet()
    ↓
iterator()

还是在遍历：

text
HashMap 的 Key

这再次说明：

text
HashSet 中的元素
=
HashMap 中的 Key

10. null 元素 ​

HashSet 可以保存：

java
null

例如：

java
Set<String> set =
        new HashSet<>();

set.add(null);
set.add(null);

System.out.println(set);

最终只会保留一个：

text
null

原因还是因为底层 HashMap：

text
允许一个 null Key

所以：

text
HashSet

也允许保存：

text
一个 null 元素

重复添加：

java
null

仍然不会产生多个元素。

11. 常用方法对应关系 ​

HashSet 的很多核心操作实际上都是直接调用 HashMap：

HashSetHashMap
add(e)put(e, PRESENT)
contains(o)containsKey(o)
remove(o)remove(o)
iterator()keySet().iterator()
size()size()
isEmpty()isEmpty()
clear()clear()

整体关系：

text
HashSet
    ↓
HashMap


元素
    ↓
Key


Value
    ↓
PRESENT

12. 小结 ​

HashSet 是 Set 接口最常用的实现之一。

它最重要的特点：

text
元素不能重复

不保证遍历顺序

允许一个 null

底层实现：

text
HashSet
    ↓
HashMap

其中：

text
HashSet 元素
    ↓
HashMap Key


HashMap Value
    ↓
固定的 PRESENT 对象

所以 HashSet 的：

text
添加

删除

查找

去重

本质上都依赖：

text
HashMap

核心源码关系：

text
add()
    ↓
map.put(e, PRESENT)


contains()
    ↓
map.containsKey(o)


remove()
    ↓
map.remove(o)


iterator()
    ↓
map.keySet().iterator()

因此理解 HashSet 最重要的一句话就是：

HashSet 本质上是利用 HashMap 的 Key 唯一性，实现了元素不可重复的 Set。

Noctiflorous Garden · MIT License

© 2024 Kerwim · 冀ICP备2024088775号-1 · Built in silence. Running against entropy.