Java 容器之 Set

简介

Set 是 Java 容器框架中用于存储不重复元素的集合。它继承自 Collection 接口，通过内部机制保证元素的唯一性。Java 提供了多种 Set 实现：HashSet（无序、高性能）、LinkedHashSet（保持插入顺序）、TreeSet（有序、红黑树）和 EnumSet（枚举专用），各自适用于不同的场景。

Set 简介

Set 家族成员简介：

• Set 继承了 Collection 的接口。实际上 Set 就是 Collection，只是行为略有不同：Set 集合不允许有重复元素。
• SortedSet 继承了 Set 的接口。SortedSet 中的内容是排序的唯一值，排序的方法是通过比较器(Comparator)。
• NavigableSet 继承了 SortedSet 的接口。它提供了丰富的查找方法：如"获取大于/等于某值的元素"、“获取小于/等于某值的元素”等等。
• AbstractSet 是一个抽象类，它继承于 AbstractCollection，AbstractCollection 实现了 Set 中的绝大部分方法，为实现 Set 的实例类提供了便利。
• HashSet 类依赖于 HashMap，它实际上是通过 HashMap 实现的。HashSet 中的元素是无序的、散列的。
• TreeSet 类依赖于 TreeMap，它实际上是通过 TreeMap 实现的。TreeSet 中的元素是有序的，它是按自然排序或者用户指定比较器排序的 Set。
• LinkedHashSet 是按插入顺序排序的 Set。
• EnumSet 是只能存放 Emum 枚举类型的 Set。

Set 接口

Set 继承了 Collection 的接口。实际上，Set 就是 Collection，二者提供的方法完全相同。

Set 接口定义如下：

public interface Set<E> extends Collection<E> {}

SortedSet 接口

继承了 Set 的接口。SortedSet 中的内容是排序的唯一值，排序的方法是通过比较器(Comparator)。

SortedSet 接口定义如下：

public interface SortedSet<E> extends Set<E> {}

SortedSet 接口新扩展的方法：

• comparator - 返回 Comparator
• subSet - 返回指定区间的子集
• headSet - 返回小于指定元素的子集
• tailSet - 返回大于指定元素的子集
• first - 返回第一个元素
• last - 返回最后一个元素
• spliterator

NavigableSet 接口

NavigableSet 继承了 SortedSet。它提供了丰富的查找方法。

NavigableSet 接口定义如下：

public interface NavigableSet<E> extends SortedSet<E> {}

NavigableSet 接口新扩展的方法：

• lower - 返回小于指定值的元素中最接近的元素
• higher - 返回大于指定值的元素中最接近的元素
• floor - 返回小于或等于指定值的元素中最接近的元素
• ceiling - 返回大于或等于指定值的元素中最接近的元素
• pollFirst - 检索并移除第一个（最小的）元素
• pollLast - 检索并移除最后一个（最大的）元素
• descendingSet - 返回反序排列的 Set
• descendingIterator - 返回反序排列的 Set 的迭代器
• subSet - 返回指定区间的子集
• headSet - 返回小于指定元素的子集
• tailSet - 返回大于指定元素的子集

AbstractSet 抽象类

AbstractSet 类提供 Set 接口的核心实现，以最大限度地减少实现 Set 接口所需的工作。

AbstractSet 抽象类定义如下：

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {}

事实上，主要的实现已经在 AbstractCollection 中完成。

HashSet 类

HashSet 类依赖于 HashMap，它实际上是通过 HashMap 实现的。HashSet 中的元素是无序的、散列的。

HashSet 类定义如下：

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

HashSet 要点

• HashSet 通过继承 AbstractSet 实现了 Set 接口中的骨干方法。
• HashSet 实现了 Cloneable，所以支持克隆。
• HashSet 实现了 Serializable，所以支持序列化。
• HashSet 中存储的元素是无序的。
• HashSet 允许 null 值的元素。
• HashSet 不是线程安全的。

HashSet 原理

HashSet 是基于 HashMap 实现的。

// HashSet 的核心，通过维护一个 HashMap 实体来实现 HashSet 方法
private transient HashMap<E,Object> map;

// PRESENT 是用于关联 map 中当前操作元素的一个虚拟值
private static final Object PRESENT = new Object();
}

• HashSet 中维护了一个 HashMap 对象 map，HashSet 的重要方法，如 add、remove、iterator、clear、size 等都是围绕 map 实现的。
  • HashSet 类中通过定义 writeObject() 和 readObject() 方法确定了其序列化和反序列化的机制。
• PRESENT 是用于关联 map 中当前操作元素的一个虚拟值。

TreeSet 类

TreeSet 类依赖于 TreeMap，它实际上是通过 TreeMap 实现的。TreeSet 中的元素是有序的，它是按自然排序或者用户指定比较器排序的 Set。

TreeSet 类定义如下：

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {}

TreeSet 要点

• TreeSet 通过继承 AbstractSet 实现了 NavigableSet 接口中的骨干方法。
• TreeSet 实现了 Cloneable，所以支持克隆。
• TreeSet 实现了 Serializable，所以支持序列化。
• TreeSet 中存储的元素是有序的。排序规则是自然顺序或比较器（Comparator）中提供的顺序规则。
• TreeSet 不是线程安全的。

TreeSet 源码

TreeSet 是基于 TreeMap 实现的。

// TreeSet 的核心，通过维护一个 NavigableMap 实体来实现 TreeSet 方法
private transient NavigableMap<E,Object> m;

// PRESENT 是用于关联 map 中当前操作元素的一个虚拟值
private static final Object PRESENT = new Object();

• TreeSet 中维护了一个 NavigableMap 对象 map（实际上是一个 TreeMap 实例），TreeSet 的重要方法，如 add、remove、iterator、clear、size 等都是围绕 map 实现的。
• PRESENT 是用于关联 map 中当前操作元素的一个虚拟值。TreeSet 中的元素都被当成 TreeMap 的 key 存储，而 value 都填的是 PRESENT。

LinkedHashSet 类

LinkedHashSet 是按插入顺序排序的 Set。

LinkedHashSet 类定义如下：

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

LinkedHashSet 要点

• LinkedHashSet 通过继承 HashSet 实现了 Set 接口中的骨干方法。
• LinkedHashSet 实现了 Cloneable，所以支持克隆。
• LinkedHashSet 实现了 Serializable，所以支持序列化。
• LinkedHashSet 中存储的元素是按照插入顺序保存的。
• LinkedHashSet 不是线程安全的。

LinkedHashSet 原理

LinkedHashSet 有三个构造方法，无一例外，都是调用父类 HashSet 的构造方法。

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
    super(16, .75f, true);
}

需要强调的是：LinkedHashSet 构造方法实际上调用的是父类 HashSet 的非 public 构造方法。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

不同于 HashSet public 构造方法中初始化的 HashMap 实例，这个构造方法中，初始化了 LinkedHashMap 实例。

也就是说，实际上，LinkedHashSet 维护了一个双链表。由双链表的特性可以知道，它是按照元素的插入顺序保存的。所以，这就是 LinkedHashSet 中存储的元素是按照插入顺序保存的原理。

EnumSet 类

EnumSet 类定义如下：

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
    implements Cloneable, java.io.Serializable {}

EnumSet 要点

• EnumSet 继承了 AbstractSet，所以有 Set 接口中的骨干方法。
• EnumSet 实现了 Cloneable，所以支持克隆。
• EnumSet 实现了 Serializable，所以支持序列化。
• EnumSet 通过 <E extends Enum<E>> 限定了存储元素必须是枚举值。
• EnumSet 没有构造方法，只能通过类中的 static 方法来创建 EnumSet 对象。
• EnumSet 是有序的。以枚举值在 EnumSet 类中的定义顺序来决定集合元素的顺序。
• EnumSet 不是线程安全的。

HashSet vs. LinkedHashSet vs. TreeSet

特性	HashSet	LinkedHashSet	TreeSet
底层结构	哈希表（HashMap）	链表+哈希表	红黑树（TreeMap）
元素顺序	无序	插入顺序	自然序/比较器序
null 元素	允许 1 个	允许 1 个	不允许
时间复杂度	O(1)	O(1)	O(log n)
线程安全	不安全	不安全	不安全
适用场景	快速去重	去重且保持顺序	排序场景

典型应用场景

场景一：数据去重

快速去除列表中的重复元素：

List<String> names = Arrays.asList("Alice", "Bob", "Alice", "Charlie", "Bob");
Set<String> uniqueNames = new HashSet<>(names);
// 结果：[Alice, Bob, Charlie]

场景二：集合运算（交集、并集、差集）

利用 Set 的数学集合特性进行交并差运算：

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));

// 交集
Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // [4, 5]

// 并集
Set<Integer> union = new HashSet<>(set1);
union.addAll(set2); // [1, 2, 3, 4, 5, 6, 7, 8]

// 差集
Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2); // [1, 2, 3]

场景三：使用 TreeSet 实现范围查询

利用 NavigableSet 的丰富方法进行范围查询：

TreeSet<Integer> scores = new TreeSet<>(Arrays.asList(55, 72, 88, 91, 63, 45, 78));

// 查找大于等于 80 分的学生
NavigableSet<Integer> highScores = scores.tailSet(80, true); // [88, 91]

// 查找分数在 60-80 之间的
NavigableSet<Integer> midScores = scores.subSet(60, true, 80, false); // [63, 72, 78]

最佳实践

1. 默认选择 HashSet：如果没有特殊需求，HashSet 是最佳选择，O(1) 的时间复杂度最优。
2. 需要保持插入顺序时用 LinkedHashSet：适合需要按插入顺序输出的场景，如配置项管理。
3. 需要排序时用 TreeSet：当元素需要自然序或自定义排序时使用，注意时间复杂度为 O(log n)。
4. 枚举类型用 EnumSet：性能远优于 HashSet，底层用位向量实现。
5. 注意自定义对象的 hashCode 和 equals：使用 HashSet 时，必须正确覆写这两个方法，否则无法正确去重。
6. 并发环境使用 ConcurrentHashMap.newKeySet()：比 Collections.synchronizedSet 性能更好。

常见问题

Q1：HashSet 如何保证元素唯一性？

HashSet 基于 HashMap 实现。添加元素时，先计算 hashCode 确定存储位置，再用 equals 比较是否已存在。如果 hashCode 和 equals 判断相同，则不会重复添加。这就是为什么自定义对象必须正确覆写这两个方法。

Q2：TreeSet 可以存储 null 吗？

不可以。TreeSet 基于 TreeMap（红黑树），在插入时会调用 compareTo 或 Comparator 进行比较，null 会导致 NullPointerException。

Q3：HashSet、LinkedHashSet、TreeSet 如何选择？

• 只需去重，不关心顺序 → HashSet
• 需要保持插入顺序 → LinkedHashSet
• 需要自然序或自定义排序 → TreeSet
• 存储枚举类型 → EnumSet

参考资料

• Java 编程思想（Thinking in java） (opens new window)
• 《Effective Java》第 3 版 (opens new window)
• Java Set 官方文档 (opens new window)