Java 集合框架：Java 中的 Set 集合（HashSet & LinkedHashSet & TreeSet）特点与实现解析

大家好，我是栗筝i，这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 017 篇文章，在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验，并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时，本专栏的所有文章，也都会准备充足的代码示例和完善的知识点梳理，因此也十分适合零基础的小白和要准备工作面试的同学学习。当然，我也会在必要的时候进行相关技术深度的技术解读，相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。

–

相较于 List 集合与 Map 集合，Set 集合可以讨论的点其实很少，这主要的原因是因为无论是哪一种 Set 集合的实现类其实都是基于 Map 集合的，而如果深究其原理，其实就是去深究 Map 的实现，而我不打算对 Map 的解读放在 Set 的章节…

当然除了主要实现之外，Set 也是有很多值得我们关注的特点的，比如他的无序性，对并发流、序列化以及非序列化的实现，以及主要实现类 HashSet、TreeSet、LinkedHashSet 三者的区别，只是由于可能真正值得关注的点不是很多，所以我在本系列中将整个 Set 压缩为了一篇文章。

---

---

1、Set 集合介绍

1.1、Set 接口概述

Set 是 java.util 包下集合框架中一个接口，它是 Collection 接口的一个子接口，表示不允许包含重复元素的集合。Set 集合的特点是集合内的元素无序，且每个元素都是唯一的。这意味着即使试图添加两个相等的对象（依据 .equals() 方法判断相等），Set 集合只会保存一个对象。

Set集合的特点：

• 无序性：Set 集合中的元素不按任何特定顺序排列，无法通过索引访问元素，即集合内部的元素顺序可能随时间和操作发生变化；
• 唯一性：Set 集合不允许包含重复的元素。判断元素是否重复的标准是基于元素的 .equals() 方法。如果两个对象在 .equals() 方法下判断为相等，则 Set 集合中只会存储其中一个；
• 最大容量：理论上，Set 集合可以无限增长，直到受到可用内存限制为止。

1.2、实现类 HashSet

HashSet 是 Java 集合框架中一个实现 Set 接口的类，它使用哈希表（内部一般采用 HashMap）作为底层数据结构，主要用于存储不重复的元素集合。

HashSet 集合有以下特点：

• 唯一性；
• 无序性；
• 高效性：由于基于哈希表实现，HashSet 插入、删除和查找元素的平均时间复杂度为 O(1)，前提是哈希函数能够良好地分散冲突。
• 允许存储 null 值：HashSet 允许存储一个 null 元素，但仅能存储一个，因为 null 的哈希码固定为 0。

1.3、实现类 TreeSet

TreeSet 同样是 Java 集合框架中实现 Set 接口的一个重要类，它基于红黑树（Red-Black Tree）数据结构，提供了一个有序的、不包含重复元素的集合。

相比于 HashSet，TreeSet 性能稍逊，但在需要排序功能时非常有用。

TreeSet集合有以下特点：

• 唯一性
• 有序性：TreeSet中的元素是有序的，排序规则既可以是元素本身的自然排序（元素类实现了 Comparable 接口），也可以是由客户端提供的 Comparator 来决定。
• 自平衡：由于基于红黑树实现，TreeSet 在插入、删除和查找操作后都能保持树的平衡，从而确保这些操作的时间复杂度接近 O(log n)。

1.4、实现类 LinkedHashSet

LinkedHashSet 继承自 HashSet 并实现了 Set 接口。LinkedHashSet 集合是一种哈希表和链表的组合，它具有以下特点：

1. 无序性：与 HashSet 类似，LinkedHashSet 也不允许集合中有重复的元素。
2. 有序性：与 HashSet 不同的是，LinkedHashSet 维护了一个双向链表，使得迭代它时可以按照插入顺序访问集合中的元素。
3. 性能：LinkedHashSet 在大多数情况下提供与 HashSet 相同的时间和空间复杂度，即添加、删除和查找元素的时间复杂度为 O(1)。

当你需要一个不允许重复元素的集合，并且希望迭代时能够按照元素的插入顺序进行时，可以使用 LinkedHashSet。LinkedHashSet 可以作为 HashMap 的键集合，因为它提供了快速的查找和迭代性能。

1.5、三种 Set 集合对比

总的来说，这三种集合各有优劣，选择时需根据具体需求考虑，如性能要求、是否需要排序或保持顺序等。

• HashSet：在需要高效地进行添加、删除、查找操作且不关心元素顺序时最为适用。
• TreeSet：适用于需要对元素进行排序和范围查询的场景，尽管性能稍逊，但提供了额外的有序操作方法。
• LinkedHashSet：当既需要快速操作元素，又需要保持插入顺序时，是最佳选择。

---

2、HashSet 底层实现

HashSet<E> 继承自 AbstractSet<E>，实现了 Set<E>, Cloneable 和 java.io.Serializable 接口。Cloneable 使其支持克隆，Serializable 使其支持序列化。

2.1、HashSet 构造函数实现

HashSet 类在 Java 集合框架中提供了多个构造函数，用于创建不同的 HashSet 实例。

package java.util;

import ...

public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    // 底层使用 HashMap 实现
    private transient HashMap<E,Object> map;

    // 用于与 HashMap 中的 key 关联的虚拟值
    private static final Object PRESENT = new Object();

    /**
     * 构造一个新的空集合，底层 HashMap 的默认初始容量为 16，负载因子为 0.75
     */
    public HashSet() {
        map = new HashMap<>();
    }

    /**
     * 构造一个包含指定集合中元素的新集合。底层 HashMap 的负载因子为 0.75，
     * 初始容量足以包含指定集合中的元素。
     *
     * @param c 要放入此集合的元素的集合
     * @throws NullPointerException 如果指定的集合为 null
     */
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    /**
     * 构造一个新的空集合，底层 HashMap 实例具有指定的初始容量和负载因子。
     *
     * @param      initialCapacity   哈希映射的初始容量
     * @param      loadFactor        哈希映射的负载因子
     * @throws     IllegalArgumentException 如果初始容量小于 0，或负载因子非正
     */
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    /**
     * 构造一个新的空集合，底层 HashMap 实例具有指定的初始容量和默认负载因子 0.75。
     *
     * @param      initialCapacity   哈希表的初始容量
     * @throws     IllegalArgumentException 如果初始容量小于 0
     */
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    /**
     * 构造一个新的空的 LinkedHashSet。仅由 LinkedHashSet 使用的包私有构造函数。
     * 底层 HashMap 实例是具有指定初始容量和负载因子的 LinkedHashMap。
     *
     * @param      initialCapacity   哈希映射的初始容量
     * @param      loadFactor        哈希映射的负载因子
     * @param      dummy             忽略（用于区分其他 int, float 构造函数）
     * @throws     IllegalArgumentException 如果初始容量小于 0，或负载因子非正
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
  
    // 省略其他方法和实现细节
  	...
  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

从这部分代码我们可以看出：

• HashSet 主要通过 HashMap 实现其所有功能，所有元素作为 HashMap 的键存储，而 PRESENT 常量对象作为所有键的值。
• 多个构造函数提供了不同的初始化方式，满足不同场景下的使用需求。
• 包私有构造函数 HashSet(int initialCapacity, float loadFactor, boolean dummy) 专为 LinkedHashSet 设计，用于支持按插入顺序访问元素。

2.2、HashSet 主要方法实现

从 HashSet 具体的方法实现，我们可以进一步看出 HashSet 通过 HashMap 实现其所有主要功能，通过 HashMap 的键值特性，确保集合中的元素不重复。由于底层采用哈希表存储，HashSet 提供了快速的元素添加、删除和查找操作。

此外 HashSet 也主要实现了部分流方法，用于实现序列化、反序列化和并行流操作：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    // 底层使用 HashMap 实现
    private transient HashMap<E,Object> map;

    // 用于与 HashMap 中的 key 关联的虚拟值
    private static final Object PRESENT = new Object();
  
    // 省略其他方法和实现细节
  	...

    // 返回该集合的迭代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    /**
     * 返回集合中的元素数量（基数）。
     *
     * @return 集合中的元素数量（基数）
     */
    public int size() {
        return map.size();
    }

    /**
     * 如果此集合不包含任何元素，则返回 true。
     *
     * @return 如果此集合不包含任何元素，则返回 true
     */
    public boolean isEmpty() {
        return map.isEmpty();
    }

    /**
     * 如果此集合包含指定的元素，则返回 true。
     * 更正式地讲，当且仅当此集合包含一个元素 e 满足 (o==null ? e==null : o.equals(e)) 时，返回 true。
     *
     * @param o 测试在此集合中的存在的元素
     * @return 如果此集合包含指定的元素，则返回 true
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    /**
     * 如果指定元素尚未存在于集合中，则将其添加到集合中。
     * 更正式地讲，如果此集合不包含元素 e2 满足 (e==null ? e2==null : e.equals(e2))，则将指定元素 e 添加到此集合中。
     * 如果此集合已经包含该元素，则此调用不更改集合并返回 false。
     *
     * @param e 要添加到集合中的元素
     * @return 如果集合中尚不包含指定元素，则返回 true
     */
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    /**
     * 如果集合中存在指定的元素，则将其从集合中移除。
     * 更正式地讲，如果此集合包含一个元素 e 满足 (o==null ? e==null : o.equals(e))，则将其移除。
     * 如果此集合包含该元素，则返回 true（即此调用改变了集合）。
     *
     * @param o 要从集合中移除的元素
     * @return 如果集合中包含指定的元素，则返回 true
     */
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    /**
     * 从此集合中移除所有元素。此调用返回后集合将为空。
     */
    public void clear() {
        map.clear();
    }

    /**
     * 返回此 HashSet 实例的浅表副本：元素本身不被克隆。
     *
     * @return 此集合的浅表副本
     */
    @SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    /**
     * 将此 HashSet 实例的状态保存到一个流中（即，序列化它）。
     *
     * @serialData 发出支持 HashMap 实例的容量（int）及其负载因子（float），
     *             然后是集合的大小（它包含的元素数量）（int），
     *             以及所有的元素（每个是 Object），顺序不定。
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // 写出所有默认的序列化内容
        s.defaultWriteObject();

        // 写出 HashMap 的容量和负载因子
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // 写出大小
        s.writeInt(map.size());

        // 写出所有元素，顺序不定
        for (E e : map.keySet())
            s.writeObject(e);
    }

    /**
     * 从流中重构 HashSet 实例（即，反序列化它）。
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 读取并忽略流字段（当前为零）
        s.readFields();
        // 读取容量并验证非负
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("非法容量: " + capacity);
        }

        // 读取负载因子并验证正值且非 NaN
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("非法负载因子: " + loadFactor);
        }
        // 将负载因子限制在 0.25 到 4.0 范围内
        loadFactor = Math.min(Math.max(0.25f, loadFactor), 4.0f);

        // 读取大小并验证非负
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("非法大小: " + size);
        }
        // 根据大小和负载因子设置容量，确保 HashMap 至少填充 25%，并限制最大容量
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // 构造支持的 HashMap 将在添加第一个元素时懒惰地创建一个数组，
        // 因此在构造前进行检查。调用 HashMap.tableSizeFor 计算实际分配大小。
        // 检查 Map.Entry[].class，因为它是最接近实际创建的公共类型。

        SharedSecrets.getJavaOISAccess()
                     .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));

        // 创建支持的 HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // 以适当的顺序读取所有元素
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

    /**
     * 创建一个晚绑定且快速失败的 Spliterator 对象，遍历此集合中的元素。
     *
     * Spliterator 报告 SIZED 和 DISTINCT 特性。
     * 重写实现应记录额外特性值的报告。
     *
     * @return 一个遍历此集合中元素的 Spliterator
     * @since 1.8
     */
    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183

---

3、TreeSet 底层实现

TreeSet 类实现了 NavigableSet 接口，提供了一组按顺序存储的集合元素。它使用一个 NavigableMap 来存储元素，默认情况下是 TreeMap。

3.1、TreeSet 构造方法实现

TreeSet 提供了多个构造函数，以支持不同的初始化方式：

• 无参构造函数：创建一个空的 TreeSet，按自然顺序排序；
• 带比较器参数的构造函数：按指定的比较器排序；
• 带集合参数的构造函数：使用指定集合的元素构造 TreeSet，按自然顺序排序；
• 带排序集参数的构造函数：使用指定排序集的元素和顺序构造 TreeSet。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * 底层使用的 NavigableMap 实例。
     */
    private transient NavigableMap<E,Object> m;

    // 作为在底层 Map 中与元素关联的虚拟值
    private static final Object PRESENT = new Object();

    /**
     * 构造一个由指定的 NavigableMap 支持的集合。
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    /**
     * 构造一个新的空的树集，按照元素的自然顺序排序。
     * 插入集合的所有元素必须实现 {@link Comparable} 接口。
     * 此外，所有元素必须是相互可比较的：{@code e1.compareTo(e2)} 
     * 不能对集合中的任何元素 {@code e1} 和 {@code e2} 抛出 
     * {@code ClassCastException} 异常。如果用户尝试添加违反此约束的元素
     * （例如，用户尝试将字符串元素添加到整数元素的集合中），
     * {@code add} 调用将抛出 {@code ClassCastException} 异常。
     */
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    /**
     * 构造一个新的空的树集，按照指定的比较器排序。
     * 插入集合的所有元素必须是由指定的比较器相互可比较的：
     * {@code comparator.compare(e1, e2)} 不能对集合中的任何元素 
     * {@code e1} 和 {@code e2} 抛出 {@code ClassCastException} 异常。
     * 如果用户尝试添加违反此约束的元素，
     * {@code add} 调用将抛出 {@code ClassCastException} 异常。
     *
     * @param comparator 用于排序此集合的比较器。
     *        如果 {@code null}，将使用元素的自然顺序。
     */
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    /**
     * 构造一个包含指定集合中的元素的新树集，
     * 按照元素的自然顺序排序。插入集合的所有元素必须实现 
     * {@link Comparable} 接口。此外，所有元素必须是相互可比较的：
     * {@code e1.compareTo(e2)} 不能对集合中的任何元素 {@code e1} 和 
     * {@code e2} 抛出 {@code ClassCastException} 异常。
     *
     * @param c 其元素将构成新集合的集合
     * @throws ClassCastException 如果 {@code c} 中的元素不是 
     *         {@link Comparable}，或不是相互可比较的
     * @throws NullPointerException 如果指定的集合为 null
     */
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * 构造一个包含指定排序集的相同元素并使用相同顺序的新树集。
     *
     * @param s 其元素将构成新集合的排序集
     * @throws NullPointerException 如果指定的排序集为 null
     */
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

3.2、TreeSet 特色方法实现

TreeSet 提供了灵活的集合操作和导航功能的操作，使其成为功能强大的有序集合。这些特点使 TreeSet 在需要有序和高效查找的场景中尤为有用

/**
 * 返回此集合中的第一个（最低）元素。
 *
 * @throws NoSuchElementException 如果此集合为空
 */
public E first() {
    return m.firstKey();
}

/**
 * 返回此集合中的最后一个（最高）元素。
 *
 * @throws NoSuchElementException 如果此集合为空
 */
public E last() {
    return m.lastKey();
}

/**
 * 返回一个新的集合，包含从 fromElement（包含或不包含，根据 fromInclusive）到 toElement（包含或不包含，根据 toInclusive）范围内的元素。
 *
 * @param fromElement 起始元素
 * @param fromInclusive 是否包含起始元素
 * @param toElement 结束元素
 * @param toInclusive 是否包含结束元素
 * @return 包含指定范围内元素的新集合
 */
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement, boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive, toElement, toInclusive));
}

/**
 * 返回一个新的集合，包含从集合开头到指定元素（包含或不包含，根据 inclusive）的所有元素。
 *
 * @param toElement 结束元素
 * @param inclusive 是否包含结束元素
 * @return 包含从开头到指定元素的新集合
 */
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

/**
 * 返回一个新的集合，包含从指定元素（包含或不包含，根据 inclusive）到集合末尾的所有元素。
 *
 * @param fromElement 起始元素
 * @param inclusive 是否包含起始元素
 * @throws ClassCastException 如果指定元素的类型不允许
 * @throws NullPointerException 如果 fromElement 为 null 且集合使用自然顺序，或其比较器不允许 null 元素
 * @throws IllegalArgumentException 如果起始元素不合法
 * @since 1.6
 * @return 包含从指定元素到末尾的新集合
 */
public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
    return new TreeSet<>(m.tailMap(fromElement, inclusive));
}

/**
 * 返回一个新的集合，包含从 fromElement（包含）到 toElement（不包含）范围内的元素。
 *
 * @param fromElement 起始元素
 * @param toElement 结束元素
 * @return 包含指定范围内元素的新集合
 */
public SortedSet<E> subSet(E fromElement, E toElement) {
    return subSet(fromElement, true, toElement, false);
}

/**
 * 返回一个新的集合，包含从集合开头到指定元素（不包含）的所有元素。
 *
 * @param toElement 结束元素
 * @throws ClassCastException 如果指定元素的类型不允许
 * @throws NullPointerException 如果 toElement 为 null 且集合使用自然顺序，或其比较器不允许 null 元素
 * @throws IllegalArgumentException 如果结束元素不合法
 * @return 包含从开头到指定元素的新集合
 */
public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

/**
 * 返回一个新的集合，包含从指定元素（包含）到集合末尾的所有元素。
 *
 * @param fromElement 起始元素
 * @throws ClassCastException 如果指定元素的类型不允许
 * @throws NullPointerException 如果 fromElement 为 null 且集合使用自然顺序，或其比较器不允许 null 元素
 * @throws IllegalArgumentException 如果起始元素不合法
 * @return 包含从指定元素到末尾的新集合
 */
public SortedSet<E> tailSet(E fromElement) {
    return tailSet(fromElement, true);
}

/**
 * 返回此集合中元素的逆序迭代器。
 *
 * @return 逆序迭代器
 */
public Iterator<E> descendingIterator() {
    return m.descendingKeySet().iterator();
}

/**
 * 返回一个新的集合，包含此集合中元素的逆序视图。
 *
 * @since 1.6
 * @return 逆序视图的新集合
 */
public NavigableSet<E> descendingSet() {
    return new TreeSet<>(m.descendingMap());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113