网站公告

本次更新：没啥更新的

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

朕知道了
Noctiflorous Garden

外观

Set ​

字数: 0 字 时长: 0 分钟

1. Set ​

Set 是 Java 集合框架中用于保存不重复元素的接口。

和 List 相比，最大的区别是：

text
List
    ↓
元素可以重复
支持索引


Set
    ↓
元素不能重复
没有索引

需要注意：

Set 本身并不等于“无序”。

不同实现的顺序规则不同：

text
HashSet
    ↓
不保证迭代顺序


LinkedHashSet
    ↓
维护插入顺序


TreeSet
    ↓
按照排序规则保存

常见实现：

text
Set
├── HashSet
├── LinkedHashSet
└── TreeSet

1.1 HashSet ​

HashSet 是最常见的 Set 实现之一。

主要特点：

text
元素不能重复

不保证元素的迭代顺序

没有下标

查找、添加、删除通常比较快

HashSet 底层基于：

java
HashMap

实现。

可以简单理解：

text
HashSet 中的元素
    ↓
作为 HashMap 的 key


HashMap 的 value
    ↓
使用一个固定对象占位

核心源码思想类似：

java
private transient HashMap<E, Object> map;

private static final Object PRESENT =
        new Object();

public HashSet() {

    map =
            new HashMap<>();
}

public boolean add(
        E element) {

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

public boolean remove(
        Object object) {

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

所以：

java
set.add("kerwim");

本质上类似：

java
map.put(
        "kerwim",
        PRESENT
);

1.1.1 HashSet 基本使用 ​

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

// 添加元素
set.add("kerwim");
set.add("kevin");
set.add("牛马");

// 判断元素是否存在
boolean exists =
        set.contains(
                "kerwim"
        );

// 删除元素
set.remove(
        "kevin"
);

// 遍历
for (String value : set) {

    System.out.println(
            value
    );
}

Set 没有：

java
get(index)

所以不能像 List 一样：

java
// 不存在
// set.get(0);

1.1.2 HashSet 如何去重 ​

例如：

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

set.add("牛马");
set.add("kevin");
set.add("kerwim");
set.add("牛马");

System.out.println(
        set.size()
);

结果：

text
3

第二次添加：

java
"牛马"

不会再次进入集合。

原因是：

text
HashSet
    ↓
使用 HashMap 的 key 保存元素
    ↓
Map 的 key 不能重复

这里不能简单理解成：

text
hashCode 一样
    ↓
就是同一个元素

因为：

text
不同对象

可能拥有相同：

java
hashCode()

也就是：

text
哈希冲突

HashSet 判断元素是否重复，本质依赖底层 HashMap 对 key 的判断逻辑，通常会结合：

text
hashCode()

equals()

所以自定义对象放入 HashSet 时，通常需要正确实现：

java
equals()

hashCode()

1.1.3 HashSet 的使用场景 ​

HashSet 最典型的用途就是：

text
去重

例如：

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

words.add("Java");
words.add("Spring");
words.add("Java");

System.out.println(
        words.size()
);

结果：

text
2

所以如果业务只关心：

text
元素是否存在

元素是否重复

而不关心顺序，HashSet 很合适。

1.2 LinkedHashSet ​

LinkedHashSet 继承自：

java
HashSet

但它底层实际上利用：

java
LinkedHashMap

来保存元素。

可以简单理解：

text
LinkedHashSet
    ↓
HashSet 的去重能力
+
LinkedHashMap 的顺序维护能力

因此它最明显的特点是：

元素不重复，并且按照插入顺序进行迭代。

例如：

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

set.add("kerwim");
set.add("kevin");
set.add("牛马");

for (String value : set) {

    System.out.println(
            value
    );
}

输出顺序：

text
kerwim
kevin
牛马

1.2.1 LinkedHashSet 基本使用 ​

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

// 添加元素
set.add("kerwim");
set.add("kevin");
set.add("牛马");

// 删除
set.remove(
        "kevin"
);

// Set 没有 set(index, value)
// 修改通常需要删除旧值，再添加新值
set.remove(
        "牛马"
);

set.add(
        "纯牛马"
);

// 查询
boolean exists =
        set.contains(
                "kerwim"
        );

System.out.println(
        exists
);

由于 Set 没有：

text
索引

所以不存在：

java
set.set(
        1,
        "value"
);

如果需要“修改”一个元素，一般是：

text
删除旧元素
    ↓
添加新元素

1.2.2 LinkedHashSet 的特点 ​

可以简单记：

text
HashSet
    ↓
不重复
不保证顺序


LinkedHashSet
    ↓
不重复
保持插入顺序

因此：

java
LinkedHashSet

适合：

text
既需要去重

又希望保留原来的插入顺序

的场景。

1.3 TreeSet ​

TreeSet 是一个：

可以自动排序的 Set 实现。

它底层基于：

java
TreeMap

实现。

可以简单理解：

text
TreeSet 中的元素
    ↓
作为 TreeMap 的 key


TreeMap
    ↓
红黑树

所以 TreeSet 具有：

text
元素不重复

没有索引

自动排序

这些特点。

1.3.1 TreeSet 基本使用 ​

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

set.add("欧阳锋");
set.add("周芷若");
set.add("张无忌");

System.out.println(
        set
);

// 删除
set.remove(
        "周芷若"
);

// 修改
set.remove(
        "欧阳锋"
);

set.add(
        "小昭"
);

// 查询
System.out.println(
        set.contains(
                "张无忌"
        )
);

TreeSet 同样没有：

text
直接修改元素

这种操作。

一般也是：

text
remove()
    ↓
add()

1.3.2 TreeSet 的排序规则 ​

TreeSet 可以通过两种方式决定元素顺序：

text
自然排序
Comparable

或者：

text
自定义排序
Comparator

例如整数：

java
Set<Integer> set =
        new TreeSet<>();

set.add(30);
set.add(10);
set.add(20);

System.out.println(
        set
);

结果：

text
[10, 20, 30]

因为：

java
Integer

本身实现了：

java
Comparable<Integer>

所以可以进行自然排序。

也可以传入：

java
Comparator

自定义顺序：

java
Set<Integer> set =
        new TreeSet<>(
                Comparator.reverseOrder()
        );

set.add(30);
set.add(10);
set.add(20);

System.out.println(
        set
);

结果：

text
[30, 20, 10]

1.3.3 TreeSet 如何判断重复 ​

HashSet 主要依赖：

text
hashCode()

equals()

而 TreeSet 是否认为两个元素重复，核心取决于排序比较结果。

也就是：

text
compareTo()

或者：

text
Comparator.compare()

如果比较结果为：

text
0

TreeSet 会认为两个元素在排序意义上是：

text
相同元素

因此不会同时保存。

所以：

text
HashSet
    ↓
HashMap
    ↓
hashCode + equals


TreeSet
    ↓
TreeMap
    ↓
Comparable / Comparator

这是两者很重要的区别。

1.3.4 TreeSet 与 null ​

普通使用自然排序的：

java
TreeSet

不能加入：

java
null

例如：

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

set.add(null);

通常会抛出：

text
NullPointerException

因为：

text
TreeSet

需要对元素进行比较排序，而：

text
null

无法参与自然排序。

2. 小结 ​

三个常见 Set 实现可以直接这样记：

实现底层实现顺序主要特点
HashSetHashMap不保证顺序去重、查询快
LinkedHashSetLinkedHashMap插入顺序去重 + 保持顺序
TreeSetTreeMap排序顺序去重 + 自动排序

核心关系：

text
HashSet
    ↓
HashMap


LinkedHashSet
    ↓
LinkedHashMap


TreeSet
    ↓
TreeMap

选择时可以简单记：

text
只需要去重
    ↓
HashSet


去重 + 保持插入顺序
    ↓
LinkedHashSet


去重 + 排序
    ↓
TreeSet

Set 本身没有：

text
索引

所以不能像 List 一样通过：

java
get(index)

访问元素。

一句话概括：

Set 的核心是“不重复”，HashSet 负责普通去重，LinkedHashSet 在去重基础上维护插入顺序，TreeSet 在去重基础上提供排序。

Noctiflorous Garden · MIT License

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