Set

Set 接口概述

Set 是 Java 集合框架中的一个接口，它继承了 Collection 接口，并添加了一些独有的方法。

我们通常看作 Set 是没有重复元素的 Collection，或者说，Set是一个不允许重复元素的集合。

Set 源自数学中的 集合 概念——元素唯一、无序（多数情况下）、不可通过索引访问。

Set 接口本身并未定义新的方法，而是通过语义约束对 Collection 的行为进行了强化：任何尝试添加重复元素的操作都会被忽略（add() 返回 false）。这一特性就使得 Set 成为去重、成员存在性判断等场景的首选数据结构。

目前，Java 提供了多个 Set 的常用实现类，下面我会逐一深入分析，尽管这些实现类在底层数据结构、元素顺序和性能特征上各有不同，但它们都严格遵循 Set 接口的三大核心契约

  1. 元素唯一性：不允许存储重复元素（依赖 equals() 和 hashCode() 或 compareTo() 判断）；
  2. 无索引访问：不支持通过下标获取元素，遍历需依赖迭代器或增强 for 循环；
  3. 对 null 的有限支持：HashSet 和 LinkedHashSet 允许一个 null 元素，而 TreeSet 通常禁止（除非使用自定义比较器处理 null）。

Set 接口对于不允许重复元素使用 equals() 判断

HashSet

基本特性

我觉得 HashSet 的基本特性一句话就够了：高效存储唯一元素的利器

HashSet 作为 Set 的最经典实现，它拥有 Set 的基本特性，元素唯一，无序，允许至多一个 null 元素，而且它线程不安全，它的线程安全的版本为 ConcurrentHashMap，两者区别不大

emmm，只有是 LinkedHashSet 或 SortedSet 子类，才能保顺序

关于 HashSet 为什么能够允许 null，因为 HashMap 允许 key 为 null，HashSet 继承了这一特性，但是 Map 中 key 不能重复，所以最多只能允许一个 null

它非线程安全

image-20260205142644033

而且，对于 HashSet，官方有一段性能上的建议

image-20260205143127040

过大的 capacity 会导致迭代变慢，即便你的元素很少，合理设置初始容量可提升性能，大伙可以近似的认为 迭代时间 = 元素数量 + 桶的数量（capacity）

结构分析

HashSet 是 Set 接口最常用的实现类，内部使用 HashMap 作为底层数据结构。复用 HashMap，避免重复造轮子

image-20260205141959711
  • 所有元素作为 HashMap 的 key 存储，value 统一使用一个静态常量 PRESENT（ <E, Object>）

而 HashSet 也正是利用了 HashMap 的 O(1) 平均时间复杂度实现 add/remove/contains等各种各样的操作

对于其构造方法

  • 无参构造

    image-20260205142126635
    • 使用 HashMap 默认容量（16）和负载因子（0.75）

  • 从集合初始化

    image-20260205142204563
    • 调用 HashMap.newHashMap(int n)（JDK 19+ 新增的工厂方法），它的关键在于这样构造能够自动计算合适容量，避免频繁扩容，适合容器之间的转换

  • 指定初始容量 & 负载因子 初始化

    image-20260205142400199
    image-20260205142307569

  • JDK 19 新增，自动计算最优初始容量，避免太多的 rehash，它更高效、更简洁

    image-20260205142417236

    emmm，工厂构造也是构造））））））））

基本操作

核心方法实现基本都委托给了 HashMap，带 Hash 的东西牛就牛在了，在理想哈希分布下，也就是没有碰撞，所有操作的时间复杂度可以认为 ≈ O(1)

添加元素

以add(E e) 方法为例子，可以看到，它直接调用了 HashMap 的 add 方法，将元素作为 key，然后对应的 value 就是上面提到的哑值

image-20260205143814046

而且，能够去重的核心也在此处体现，因为它的去重依赖 HashMap 的 key 唯一性。而大伙都把元素存在了 HashSet 的 key 中，天然去重了

  • 如果 e 之前不存在，put() 返回 null → add() 返回 true
  • 如果 e 已存在，put() 返回旧的 value（即 PRESENT）→ add() 返回 false
移除元素

讲解 remove(Object o) 方法

image-20260205143448396

一样，调用了 HashMap 的删除方法，调用 map.remove(o) 删除 key 为 o 的条目，如果要删除的值存在，remove() 返回被删除的 value（即 PRESENT），通过比较 == PRESENT 判断是否真的删除了元素

这里用的是 == 而不是 .equals()一点毛病没有，因为 PRESENT 是单例（static final），引用唯一。

可以进行窥探，因为接下来的操作很类似，不再细说了，其他方法也间接体现这一设计

  • contains(o) → map.containsKey(o)（只关心 key）
  • iterator() → map.keySet().iterator()（只遍历 key）
  • size() → map.size()（key 的数量）
  • 序列化时只写入 map.keySet() 中的元素（value 不需要保存）
查找元素

HashSet 是如何进行哈希查找的，这里的哈希查找不要理解为我就在说它的 contains 方法，但是我会以这个为例子，也是在说整个类哈希容器的一个查找思路，简单总结就是

调用入口方法的时候

image-20260205145124541
image-20260205145130487

这里，在 HashMap 中，做了两件事情

  1. 调用 hash(key) → 计算扰动后的哈希值

    image-20260205145223640

    如果 key == null ，哈希值为 0，也是为什么 HashSet 允许一个 null 元素

    否则，调用 key.hashCode() 得到原始哈希值 h，执行 (h ^ (h >>> 16))， 高位参与低位运算，这就是哈希扰动

    为什么要做扰动？

    • HashMap 的桶数组长度通常是 2 的幂（如 16, 32, 64…）
    • 而索引计算公式是(n - 1) & hash（等价于 hash % n，但更快）
    • 如果原始 hashCode() 高位变化大、低位变化小（常见于某些对象），直接用低位会导致哈希冲突集中
    • 扰动后，高位信息混入低位，使分布更均匀，减少冲突

  2. 调用 getNode(hash, key) → 根据哈希值和 key 查找节点

    这是真正的查找核心：

    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
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        
        // 1. 检查 table 是否初始化且目标桶非空
        // O(1) 定位到桶
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            
            // 2. 检查第一个节点是否匹配，先比较hash值，再比较key
            if (first.hash == hash && // 哈希值相等（快速失败）
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;

            // 如果第一个节点不匹配，说明发生了哈希冲突,多个 key 映射到同一桶
            // 3. 如果有后续节点（链表或红黑树）
            if ((e = first.next) != null) {
                // 4. 如果是红黑树节点（TreeNode）,对每个节点重复步骤 2 的比较逻辑
                // 这就是 HashMap（从而 HashSet）在最坏情况下仍能保持较好性能的关键
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
                // 5. 否则是普通链表，遍历查找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null; // 未找到
    }
比较两个 HashSet

这个是我自己寻思出来的一个小问题，在 HashSet 自己的源码中貌似没有太多的进行展示

首先，集合相等 ≠ 引用相等

Set 接口的 equals() 方法语义由 数学集合相等 定义：

两个集合相等，当且仅当它们包含完全相同的元素（忽略顺序、重复、内部结构）

虽然 HashSet 自身未重写 equals()，但它继承自 AbstractSet，而 AbstractSet.equals() 的逻辑是：

image-20260205144858664

即使内部 HashMap 的桶分布不同，只要元素相同，equals() 就返回 true。

1
2
3
4
5
6
7
8
9
Set<String> set1 = new HashSet<>();
set1.add("a");
set1.add("b");

Set<String> set2 = new HashSet<>();
set2.add("b");
set2.add("a");

System.out.println(set1.equals(set2)); // true！顺序无关

迭代器

它的好多东西都是 HashMap 的，迭代器也一样，也说返回 HashMap 的 keySet 迭代器

image-20260205142738918

这里简单说一下，这个迭代器内部也会记录一个 modCount，也就是说，如果在迭代过程中集合被外部修改（非通过迭代器 remove()），会抛出 ConcurrentModificationException

所以说，HashSet 和 HashMap 的迭代器都是 Fail-Fast 的

这个部分等到 HashMap 再说

序列化机制

为什么 HashSet 还需要自定义序列化机制？

  • 因为 HashSet 通过一个 transient 的 HashMap 来实现，而且HashMap 的内部数组（table）也是 transient的，不会自动序列化

    image-20260205142930818

    虽然 HashSet 实现了 Serializable 接口。但是给你你就用？？底层 HashMap 的内部结构不会被序列化，如果直接使用默认序列化，性能直接爆炸了

  • 因此，HashSet 必须自定义序列化逻辑，只保存必要信息，并在反序列化时重建 HashMap。

它的序列化和反序列化的代码相对简单

序列化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void writeObject(ObjectOutputStream s) throws IOException {
    s.defaultWriteObject(); // 写入非 transient 字段（这里其实没有）
    
    // 1. 写入 HashMap 的 capacity（桶数组大小）
    s.writeInt(map.capacity());
    
    // 2. 写入 loadFactor（负载因子）
    s.writeFloat(map.loadFactor());
    
    // 3. 写入元素个数
    s.writeInt(map.size());
    
    // 4. 遍历所有 key（即 HashSet 的元素），逐个写入
    // 不保存 value（PRESENT），因为它是固定的。
    for (E e : map.keySet())
        s.writeObject(e);
}

反序列化：这是更复杂、也更安全的部分

  • 首先，读取并校验元数据

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int capacity = s.readInt();
    if (capacity < 0) throw new InvalidObjectException(...);

    float loadFactor = s.readFloat();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) 
        throw new InvalidObjectException(...);

    // 安全限制：clamp 到 [0.25, 4.0]
    loadFactor = Math.clamp(loadFactor, 0.25f, 4.0f);

    int size = s.readInt();
    if (size < 0) throw new InvalidObjectException(...);

    防止构造超大 capacity 或非法 loadFactor 导致 OOM 或异常行为。

  • 重新计算合理容量

    1
    2
    3
    4
    capacity = (int) Math.min(
        size * Math.min(1 / loadFactor, 4.0f),
        HashMap.MAXIMUM_CAPACITY
    );

    确保容量足够容纳 size 个元素，但不超过 HashMap 最大容量

  • 防御性编程

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

    在真正分配内存前，检查是否允许创建这么大数组，防住了CVE

  • 然后才是重建底层 Map 和 逐个添加元素，注意，重新添加元素是无序的，所以说，反序列化后的 HashSet 与原对象逻辑等价，但因为 rehash 内部哈希表结构可能不同，但是没关系，本来 HashSet 就无序

LinkedHashSet

基本特性

LinkedHashSet 作为有序且高效的哈希集合，底层结构是 哈希表+双向链表 的形式

LinkedHashSet 最核心的特性是维护元素的插入顺序，在 HashSet 存储结构的基础上多使用了双向链表记录添加元素的顺序，可按照添加的顺序遍历输出

实际上，LinkedHashSet 直接继承 HashSet，但通过特定的构造方法让底层使用 LinkedHashMap 来存储数据（HashSet 的 map 字段指向 LinkedHashMap 实例）。所有的有序操作都委托给 LinkedHashMap 完成。

Java 21 新增的 addFirst() 和 addLast() 方法可以主动改变元素位置，因此它存在一个重新插入的行为，如果元素已存在，重新插入不会改变其在集合中的位置，除非使用 addFirst/addLast

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");

// 重新插入已存在的元素 "B"
set.add("B");  // 返回 false，位置不变

// 遍历结果
System.out.println(set);  // [A, B, C]，B 的位置没有变化

// 使用 addFirst/addLast 会改变位置
set.addFirst("B");   // B 移动到头部
System.out.println(set);  // [B, A, C]

set.addLast("A");    // A 移动到尾部
System.out.println(set);  // [B, C, A]

而且，LinkedHashSet 在迭代遍历的时候，时间复杂度只与元素数量 n 相关，而与容量无关，对于频繁的遍历比HashMap效率高，但是插入和删除都是会因为遍历元素位置和额外维护双向链表的指针，会慢一些，是O(n)

LinkedHashSet 支持存储 null 元素，但是不允许重复，且 null 同样遵循插入顺序的规则。当然，不允许重复，所以最多只能有一个 null。

LinkedHashSet 是线程不安全的，在涉及到并发的时候，我们会使用 ConcurrentSkipListSet

LinkedHashSet 的初始容量和负载因子与 HashSet 定义一致。但有一个特殊之处，过高的初始容量对 LinkedHashSet 的迭代性能几乎没有负面影响，因为迭代走的是链表而非桶数组。而在 HashSet 中，过高的容量会拖慢迭代速度。

结构分析

LinkedHashSet 是 HashSet 的子类，底层使用了 LinkedHashMap，而且继承 HashSet，实现 SequencedSet、Cloneable、Serializable，分别代表可取首尾元素，可克隆，可序列化。

image-20260819143125286

然后，很容易发现LinkedHashSet 本身不定义任何新的字段，完全复用父类 HashSet 的 map 字段，所有状态都存储在父类中。因此，所有操作都是薄委托，几乎没有自己的逻辑。

image-20260819145002025

那么，实际上来说，LinkedHashSet 的数据结构是和 LinedHashMap 一样的，都是维护了一个hash表和双向链表，其中，每一个节点在 key 之外又维护了 before 和 after 两个属性，从而实现双向链表

img

来看 LinkedHashSet 的核心构造方法，所有构造方法都调用了 super(..., true)，这个 true 参数是关键！下面会提到。

1
2
3
4
// HashSet.java 中供 LinkedHashSet 使用的构造方法
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
// 1. 指定初始容量和负载因子
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

// 2. 指定初始容量，使用默认负载因子 0.75
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

// 3. 默认构造：容量16，负载因子0.75
public LinkedHashSet() {
    super(16, .75f, true);
}

// 4. 从集合构造
public LinkedHashSet(Collection<? extends E> c) {
    super(HashMap.calculateHashMapCapacity(Math.max(c.size(), 12)), .75f, true);
    addAll(c);
}

而这个 super() 调用了父类 HashSet 的无参构造器，即底层创建一个 HashSet 对象，但关键是，HashSet 的 map 字段实际上被初始化为 LinkedHashMap 实例，而不是 HashMap。

1
2
3
4
// HashSet.java 中供 LinkedHashSet 使用的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
 map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

其中，所有构造方法都调用 super(..., true)，这个 true 是一个 dummy 参数，用于区分是 HashSet 的普通构造还是 LinkedHashSet 的专用构造：

1
2
3
4
5
6
7
8
9
// HashSet.java
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);  // ← 普通 HashSet
}

// 供 LinkedHashSet 调用的构造
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);  // ← 专门为 LinkedHashSet 准备
}

通过一个 dummy 参数重载构造方法，让 LinkedHashSet 可以复用 HashSet 的代码，同时创建 LinkedHashMap 而不是 HashMap。很明显这是一种设计模式

那么，元素存储方式就和 HashSet 一样了，每个元素作为 LinkedHashMap 的 Key，所有 Key 共享同一个 PRESENT 对象作为 Value，双向链表是 LinkedHashMap 内部的 Entry 节点自带的 before/after 指针，记录 Node 元素的上一个元素和下一个元素，可以按照元素添加的顺序实现遍历

然后我们来看工厂方法 newLinkedHashSet()

1
2
3
4
5
6
public static <T> LinkedHashSet<T> newLinkedHashSet(int numElements) {
    if (numElements < 0) {
        throw new IllegalArgumentException("Negative number of elements: " + numElements);
    }
    return new LinkedHashSet<>(HashMap.calculateHashMapCapacity(numElements));
}
  • 它会为预期元素数量自动计算合适的初始容量，其实就是使用 HashMap.calculateHashMapCapacity() 计算容量，确保 numElements / loadFactor 足够大，这个算法看 HashMap 那边的

那么，LinkedHashSet 的 父类 HashSet 的 map 字段实际上被初始化为 LinkedHashMap 实例，而 HashSet 中初始化的其实是一个 HashMap 对象，这就必然涉及到一个向下转型，LinkedHashSet 中的map() 方法是类型转换关键

1
2
3
4
@SuppressWarnings("unchecked")
LinkedHashMap<E, Object> map() {
    return (LinkedHashMap<E, Object>) map;
}

它将父类 HashSet 的 HashMap 类型字段向下转型为 LinkedHashMap，使得可以调用 LinkedHashMap 特有的有序操作方法。这个方法封装了类型转换，让后续代码可以类型安全地使用 LinkedHashMap 的扩展功能。

而 SequencedSet 中涉及到的方法实现就很暴力了，所有方法都是薄委托，直接转发给底层 LinkedHashMap，可以看出这是一种委派模式的设计模式，所以说，LinkedHashSet 本身不实现任何存储逻辑，所有操作都委派给底层的 LinkedHashMap。

基本操作

要理解 LinkedHashSet 的操作，必须先理清它的完整委派链

1
2
3
4
5
6
7
8
9
用户调用 LinkedHashSet 方法
         ↓
LinkedHashSet (薄封装层)
         ↓ 继承自
HashSet (核心 Set 实现)
         ↓ 持有
LinkedHashMap (实际存储)
         ↓ 内部
Entry (节点) 包含 before/after 双向链表指针

那么，在这个基础上，LinkedHashSet 的一切操作都很好说了，都他喵的是委派给 LinkedHashMap 了，然后 LinkedHashMap 的父类还是 HashMap，所以，最后 LinkedHashSet 的大部分操作都说跟 HashMap 对齐的

image-20260819151708966

以remove(Object o) 操作为例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinkedHashSet.remove(Object o)
    │
    ▼ (继承自 HashSet)
HashSet.remove(Object o)
    │
    │  return map.remove(o) == PRESENT;
    ▼
LinkedHashMap.remove(Object key)
    │
    ▼ (继承自 HashMap.removeNode)
HashMap.removeNode(hash, key, null, false, true)
    │
    ├── 定位到节点 (通过哈希查找)
    │
    ├── 从桶中移除 (链表/树结构调整)
    │
    ├── afterNodeRemoval(node)  ← LinkedHashMap 重写了这里
    │       │
    │       └── 从双向链表中移除 (调整 before/after 指针)
    │
    └── 返回移除的节点 (其 value 为 PRESENT)

其中，LinkedHashMap 重写了remove() ，它让返回 true 的条件是 map.remove() 返回的值正好等于 PRESENT，因为所有 key 对应的 value 都是这个占位对象，要不然删不了

然后在看一个 LinkedHashSet 的操作吧，以下面这俩 get 元素方法为例子，这个委派跟上面的完全不一样，因为这个涉及到的是 SequencedSet 操作的委派链

image-20260819152207734

首先，这个map()指的就是 LinkedHashMap

image-20260819152246364

而 sequencedKeySet 就是 LinkedHashMap 的一个辅助方法，基本上是创建了一个 SequencedSet 对象然后进行各种顺序操作

image-20260819152313319

而什么 getFirst 和 addFirst 什么的都是这个 SequencedSet 接口的父接口 SequencedCollection 的 defalut 方法

image-20260819152422421

最后，他们会返回 LinkedKeySet 实例，这个迭代器又会回到 LinkedKeyIterator，然后进行在双向链表下的具体的操作

而 LinkedHashSet 的reversed() 反向视图操作比较有趣，基本上 JDK 中的集合，能不复制元素是绝对不会复制的，基本上都是原地操作，这个也不例外，方法也很简单，就是所有操作都映射到反向操作，不复制数据，只改变访问方向，而这样还自带操作传播，对视图的修改会直接反映到原集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// LinkedHashSet.java
public SequencedSet<E> reversed() {
    class ReverseLinkedHashSetView extends AbstractSet<E> 
            implements SequencedSet<E> {
        // 所有操作都映射到反向操作
        public void addFirst(E e) { LinkedHashSet.this.addLast(e); }
        public void addLast(E e) { LinkedHashSet.this.addFirst(e); }
        public E getFirst() { return LinkedHashSet.this.getLast(); }
        public E getLast() { return LinkedHashSet.this.getFirst(); }
        public E removeFirst() { return LinkedHashSet.this.removeLast(); }
        public E removeLast() { return LinkedHashSet.this.removeFirst(); }
        public SequencedSet<E> reversed() { return LinkedHashSet.this; }
        // ...
    }
    return new ReverseLinkedHashSetView();
}

最后神奇的 deepseek 总结如下

操作类别 方法 委派目标 时间复杂度 说明
基本集合操作 add() LinkedHashMap.put() O(1) 哈希查找 + 链表尾部插入
remove() LinkedHashMap.remove() O(1) 哈希查找 + 链表移除
contains() LinkedHashMap.containsKey() O(1) 纯哈希查找，不改变顺序
size() LinkedHashMap.size() O(1) 直接返回计数器
clear() LinkedHashMap.clear() O(n) 清空所有桶和链表
isEmpty() LinkedHashMap.isEmpty() O(1) 检查 size == 0
迭代操作 iterator() LinkedHashMap.keySet().iterator() O(n) 遍历双向链表
spliterator() Spliterators.spliterator() O(1) 返回延迟绑定 Spliterator
有序操作 (Java 21+) addFirst() LinkedHashMap.putFirst() O(1) 插入/移动到头部
addLast() LinkedHashMap.putLast() O(1) 插入/移动到尾部
getFirst() 直接访问 head O(1) 不改变顺序
getLast() 直接访问 tail O(1) 不改变顺序
removeFirst() HashMap.removeNode() + 链表调整 O(1) 移除头部节点
removeLast() HashMap.removeNode() + 链表调整 O(1) 移除尾部节点
反向视图 reversed() 返回内部视图类 O(1) 不复制数据

迭代器

那么一样，LinkedHashSet 的迭代器也是通过委派实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkedHashSet.iterator()
    │
    ▼ (继承自 HashSet)
HashSet.iterator()
    │
    │  return map.keySet().iterator();
    ▼
LinkedHashMap.keySet()  → 返回 LinkedKeySet 实例
    │
    ▼ (在 LinkedHashMap 中，keySet() 被重写了)
LinkedHashMap.LinkedKeySet.iterator()
    │
    │  return new LinkedKeyIterator(reversed);
    ▼
LinkedKeyIterator (继承 LinkedHashIterator)

那么，最后通过上面的源码分析其实也能知道，整个 LinkedHashSet 的迭代器也就是 LinkedKeyIterator，直接看就可以了

1
2
3
4
5
final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        LinkedKeyIterator(boolean reversed) { super(reversed); }
        public final K next() { return nextNode().getKey(); }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// LinkedHashMap 中的迭代器基类
abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;        // 下一个要返回的节点
    LinkedHashMap.Entry<K,V> current;     // 当前返回的节点（用于 remove）
    int expectedModCount;                 // 用于 fail-fast 检测
    boolean reversed;                     // 是否反向遍历（true=从头→尾，false=从尾→头）
    
    // 构造方法：根据 reversed 决定起点
    LinkedHashIterator(boolean reversed) {
        this.reversed = reversed;
        next = reversed ? tail : head;    // 关键！反向则从尾部开始
        expectedModCount = modCount;
        current = null;
    }
}

它的构造方法中是确定支持双向遍历起点的，而且注意到的是，虽然 LinkedHashSet 本身是插入序，但 reversed() 返回的视图会提供反向迭代器

那么，Linked 系列的迭代器其实有三种，只不过正好 LinkedHashSet 能使用且仅能使用一种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 1. Key 迭代器 - 返回键（LinkedHashSet 使用的就是这个，而且只有用这个才有意义）
final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
    LinkedKeyIterator(boolean reversed) { super(reversed); }
    public final K next() { return nextNode().getKey(); }  // 只返回 key
}

// 2. Value 迭代器 - 返回值
final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
    LinkedValueIterator(boolean reversed) { super(reversed); }
    public final V next() { return nextNode().value; }     // 返回 value
}

// 3. Entry 迭代器 - 返回完整的 Map.Entry
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
    LinkedEntryIterator(boolean reversed) { super(reversed); }
    public final Map.Entry<K,V> next() { return nextNode(); } // 返回完整节点
}

其中，fail-fast 机制依旧生效，对于并发修改会直接 fail

1
2
3
// 在每次 next() 和 remove() 时检查
if (modCount != expectedModCount)
    throw new ConcurrentModificationException();

TreeSet

基本特性

前面说到的 HashSet 负责高效去重，LinkedHashSet 在此基础上记录插入顺序，那么，如果我希望元素一直按照大小排列，还能够找到某个值的前一个、后一个元素呢？

这个时候就轮到 TreeSet 了。

我觉得 TreeSet 的核心可以概括为：按照比较规则去重，并始终维护排序顺序的集合。

它继承 AbstractSet，实现 NavigableSet、Cloneable 和 Serializable。底层通常是 TreeMap，而 TreeMap 使用红黑树组织节点，所以 add()、remove()、contains() 的时间复杂度为 O(log n)，这里默认单次比较的开销为 O(1)。

注意，这个“有序”和 LinkedHashSet 的“有序”不是一个意思。

1
2
3
TreeSet<Integer> set = new TreeSet<>();
Collections.addAll(set, 30, 10, 20, 10);
System.out.println(set); // [10, 20, 30]

元素的插入顺序是 30、10、20，但是遍历顺序是 10、20、30。TreeSet 维护的是比较器决定的顺序，不是添加顺序。

TreeSet 有两种比较方式：

  • 构造时没有提供比较器，就使用元素的 Comparable.compareTo()；
  • 提供了 Comparator，就使用 Comparator.compare()，元素不必再实现 Comparable。

而且，排序和去重用的是同一套比较规则：比较结果为 0，就认为这个位置已经有元素了，不会再调用 equals() 确认，也不会根据 hashCode() 分桶。

1
2
3
4
5
TreeSet<String> words = new TreeSet<>(Comparator.comparingInt(String::length));
System.out.println(words.add("AA")); // true
System.out.println(words.add("BB")); // false
System.out.println(words.contains("CC")); // true
System.out.println(words); // [AA]

emmm，"AA" 和 "BB" 明明不相等，为什么第二次添加失败了？因为这里比较的是长度，两者的比较结果为 0。contains("CC") 也会根据相同的规则找到 "AA"。

所以说，如果需要实现所谓业务要求“长度一样，但是内容不同的字符串也要保留”，比较器需要继续比较内容：

1
2
3
Comparator<String> byLengthThenText =
        Comparator.comparingInt(String::length)
                  .thenComparing(Comparator.naturalOrder());

更一般地说，比较规则应满足传递性、符号对称性等契约，而且最好与 equals() 一致，即 compare(a, b) == 0 与 a.equals(b) 表达同一种相等关系。否则 TreeSet 自身仍然按照比较规则工作，但跨实现的 Set 比较可能破坏对称性。

例如 BigDecimal("1.0") 与 BigDecimal("1.00") 的 compareTo() 为 0，equals() 却为 false。分别装入只含一个元素的 TreeSet 和 HashSet 后，两个方向的 equals() 可能得到不同结果，原因就在两种容器使用了不同的成员判断规则。

TreeSet 不是线程安全的。需要并发排序集合时，可以考虑后面的 ConcurrentSkipListSet；需要外部同步时，可以使用 Collections.synchronizedNavigableSet()，并在遍历期间持有同一个包装对象的锁。

关于 null，准确的说：自然排序不接受 null；自定义比较器能够处理 null 时，TreeSet 可以保存一个 null。

1
2
3
4
5
TreeSet<Integer> nullable = new TreeSet<>(
        Comparator.nullsFirst(Comparator.naturalOrder()));
nullable.add(null);
nullable.add(10);
System.out.println(nullable); // [null, 10]

最后，它没有索引，也没有 get(0)。即使元素排好了序，也不能把 TreeSet 当成一个能够按下标访问的 List。

结构分析

前面 HashSet 的“元素作为 key，value 使用占位对象”这个设计，在 TreeSet 中又出现了。

源码字段为 private transient NavigableMap<E,Object> m，占位对象为 private static final Object PRESENT = new Object()。元素都在 key 中，红黑树节点属于 TreeMap，TreeSet 自己没有再定义一套树节点。

为什么字段是 NavigableMap，而不是直接写 TreeMap？因为普通 TreeSet 使用 TreeMap，但是范围视图、逆序视图需要使用 TreeMap 的子映射视图。接口类型允许它们共享一套 Set 委派逻辑。

无参构造和比较器构造的代码很直接：

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

另外还有两个从集合构造的重载：

构造方法 元素来源 排序规则
TreeSet(Collection<? extends E> c) 遍历 c 添加元素 自然排序
TreeSet(SortedSet<E> s) 遍历 s 添加元素 保留 s 的比较器

这里要注意重载选择取决于编译期类型。同一个按降序排列的 TreeSet，如果通过 Collection<Integer> 变量传入，就会调用 Collection 构造方法，新集合恢复自然升序；通过 SortedSet<Integer> 变量传入，则会保留降序规则。

TreeMap 的 Entry 节点保存 key、value、left、right、parent 和 color。left/right 用于定位左右子树，parent 用于回溯以及调整结构，color 用于维护红黑树性质。

TreeSet 与 TreeMap 的红黑树结构

图中每个节点都保存一个集合元素，value 都是 PRESENT。树形只是一个满足红黑树性质的示意，实际形状由插入、删除顺序决定；相同元素的集合，不一定具有相同的内部树形。

红黑树并不是“左右子树高度必须一样”。它主要约束是：根为黑色；红节点的子节点为黑色；从一个节点到各个空叶子的路径包含相同数量的黑节点；空叶子按黑色处理。

这样可以限制最长路径与最短路径之间的差距，使树高保持在 O(log n)，避免普通二叉搜索树在递增插入时退化成链表。颜色维护与旋转不会改变中序遍历的结果，因此可以同时保留排序和较低的树高。

JDK 21 的接口关系也值得顺着看一下：

1
2
TreeSet → NavigableSet → SortedSet → SequencedSet → SequencedCollection
                                              ↘ Set

这意味着 TreeSet 也具备首尾访问和反向视图能力，但是它的位置由比较规则决定。addFirst() 和 addLast() 在 TreeSet 中直接抛出 UnsupportedOperationException，不能强行把一个大的元素放到最前面。

基本操作

添加元素：比较、定位、平衡

先看 TreeSet 的入口：

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

这个实现和 HashSet 很像，但是下面走的是 TreeMap 的 put()，不是 HashMap 的哈希插入。

TreeMap 的公开 put(key, value) 会调用私有的 put(key, value, true)。对照这个私有方法，可以把流程分成三步。

  1. 空树初始化：通过 addEntryToEmptyMap() 创建根节点，但在真正创建之前先调用 compare(key, key)。
  2. 沿比较结果查找：小于 0 进入左子树，大于 0 进入右子树，等于 0 返回原节点的 value。
  3. 挂接并平衡：找到空位置后调用 addEntry()，再调用 fixAfterInsertion()，最后更新 size 和 modCount。
1
2
3
4
5
6
private void addEntryToEmptyMap(K key, V value) {
    compare(key, key); // 先做类型（以及可能的 null）检查
    root = new Entry<>(key, value, null);
    size = 1;
    modCount++;
}

这里的 compare(key, key) 很容易被忽略。它提前校验类型和 null，即使集合为空，第一次添加不具备自然比较能力的对象，也不是先存进去，等第二次再报错。

对于比较结果为 0 的分支，源码只替换 value，保留原来的 key。TreeSet 的 value 又始终为 PRESENT，所以重复添加既不替换已有元素对象，也不会增加元素数量，add() 返回 false。

对于新节点，fixAfterInsertion() 先把它设为红色，再处理父节点为红色的情况。下面是完整的插入修复方法，父节点位于祖父节点左侧与右侧的分支采用镜像处理。

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
private void fixAfterInsertion(Entry<K,V> x) {
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK;
}

可以顺着这里理解两类调整。

叔节点为红色：把父节点和叔节点改为黑色，把祖父节点改为红色，再向上检查。此时重点是重新分配颜色。

叔节点为黑色：如果当前节点与父节点呈折线关系，先旋转父节点，把折线变成直线；随后重新着色并旋转祖父节点。最后整个方法保证根节点为黑色。

大伙不需要把旋转理解成重新排序。左旋、右旋调整的是节点之间的父子关系，中序遍历顺序仍然不变；TreeSet 的排序结果不会因为平衡操作而改变。

查找元素与邻近元素

contains(o) 委派给 m.containsKey(o)，底层继续按照比较结果定位节点，所以查找元素的规则和添加元素的规则一致。

但 TreeSet 真正比普通哈希集合多出来的能力，是导航操作：

方法 查找目标 在 [10, 20, 30, 40] 中查询 20
lower(e) 严格小于 e 的最大元素 10
floor(e) 小于等于 e 的最大元素 20
ceiling(e) 大于等于 e 的最小元素 20
higher(e) 严格大于 e 的最小元素 30

查找不到时返回 null。这里的“大于”和“小于”都由集合的比较器定义，使用降序比较器时，要按照降序规则理解这些关系。

以 TreeMap 的 getCeilingEntry() 为例，目标小于当前节点时，当前节点已经是候选值，还会继续向左寻找更接近的节点；目标大于当前节点时，向右寻找；如果不能继续向右，就通过 parent 回溯寻找适合的祖先。这些操作利用树的有序结构定位边界，不需要先遍历所有元素再排序。

first() 和 last() 返回比较规则下的首尾元素，空集合会抛出 NoSuchElementException。pollFirst() 和 pollLast() 则取出并删除首尾元素，空集合返回 null。

1
2
3
4
5
TreeSet<Integer> scores = new TreeSet<>(List.of(10, 20, 30, 40));
System.out.println(scores.ceiling(25)); // 30
System.out.println(scores.floor(25));   // 20
System.out.println(scores.pollFirst()); // 10，已经删除
System.out.println(scores);             // [20, 30, 40]

JDK 21 的 getFirst()/getLast() 继承 SortedSet 默认实现，分别调用 first()/last()；removeFirst()/removeLast() 先获取元素，再调用 remove。因此不要混淆它们与空集合返回 null 的 poll 方法，前者在空集合上会抛出异常。

允许 null 的 TreeSet 还有一个边界：pollFirst() 返回 null，既可能代表集合为空，也可能代表取出的元素本身就是 null。若业务需要区分，必须结合自己的访问约束处理。

移除元素：为什么会涉及后继节点
1
2
3
public boolean remove(Object o) {
    return m.remove(o)==PRESENT;
}

底层通过比较定位 Entry，找到后调用 TreeMap 的 deleteEntry()。它首先更新 modCount 和 size，随后区分节点是否有两个子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
modCount++;
size--;

// 如果待删节点有两个子节点，把后继节点的元素复制到 p，再让 p 指向后继节点
if (p.left != null && p.right != null) {
    Entry<K,V> s = successor(p);
    p.key = s.key;
    p.value = s.value;
    p = s;
} // p 有两个子节点

// 如果存在替代节点，就从它开始修复
Entry<K,V> replacement = (p.left != null ? p.left : p.right);

如果待删除节点有两个子节点，源码会取它的中序后继，将后继节点的 key 和 value 复制到当前节点，再把实际删除目标切换成后继节点。

这个后继是右子树中最靠左的节点，它最多只有一个子节点。这样原本复杂的“两子节点删除”，就转成了“至多一个子节点删除”。复制的是节点保存的引用，没有克隆元素对象。

接下来，有替代子节点时把它接到原节点的父节点；删除黑节点时调用 fixAfterDeletion() 修复黑高；删除没有子节点的黑叶子时，先把原节点当作临时替身参与修复，最后再断开它。

删除修复主要围绕兄弟节点进行：兄弟为红色时先旋转转成黑兄弟情形；兄弟和两个子节点都为黑色时，重新着色并向父节点继续处理；其他情况通过近侧、远侧子节点的颜色以及旋转补足缺失的黑高。源码左右两边采用镜像分支。

所以，TreeSet 的删除并不是简单地断开一个指针，它需要继续保证后续查找仍有 O(log n) 的树高。

范围视图和反向视图

源码定位：TreeSet.java:324–328。

1
2
3
4
5
public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) {
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

源码构造了一个新的 TreeSet 包装对象，但是传入的是 m.subMap()。新的包装对象，不等于新的元素副本。

TreeSet 范围视图与逆序视图共享数据 
1
2
3
4
5
6
7
TreeSet<Integer> all = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> middle = all.subSet(20, true, 40, false);
System.out.println(middle); // [20, 30]
middle.remove(30);
middle.add(25);
System.out.println(all);    // [10, 20, 25, 40, 50]
// middle.add(40);          // IllegalArgumentException，超出视图边界

headSet(to, inclusive) 表示上界之前的范围，tailSet(from, inclusive) 表示下界之后的范围。两个参数的 subSet(from, to) 默认是左闭右开，headSet(to) 默认不含上界，tailSet(from) 默认包含下界。

原集合中位于范围内的修改也会反映到视图中。视图的 clear() 清空的是这个范围，不会把原集合中范围之外的元素一起清掉。

descendingSet() 包装 m.descendingMap()，提供逆序视图。JDK 21 的 reversed() 继承自 NavigableSet，直接调用 descendingSet()。视图上的 first()、lower() 等操作，也按照视图自身的反向比较顺序解释。

批量添加与复制

TreeSet 的 addAll() 存在一条优化路径：目标为空、来源非空且是 SortedSet、目标底层确实是 TreeMap，并且双方比较器通过 Objects.equals() 判断相等时，调用 addAllForTreeSet()。

底层进一步使用 buildFromSorted()，按照有序输入直接构建树，避免每个元素都从根节点开始插入，构建开销为 O(n)。如果条件不满足，则退回逐个 add，不能笼统地说 TreeSet 的所有 addAll 都是 O(n)。

clone() 会创建新的 TreeMap，节点结构独立，但元素对象仍然共享，是浅拷贝。序列化时则保存比较器、元素数量和有序元素；反序列化使用 readTreeSet() 重建树，不是原样保存每一个节点的左右指针。如果自定义比较器不能序列化，序列化整个 TreeSet 也会受到影响。

迭代器

TreeSet 的正向迭代入口为 m.navigableKeySet().iterator()，逆向入口为 m.descendingKeySet().iterator()。对于完整的 TreeMap，最终使用 KeyIterator 和 DescendingKeyIterator；范围视图有自己的带边界迭代器。

TreeMap 的迭代器并没有把元素复制进数组，而是从首节点开始，通过后继节点沿中序顺序推进。

1
2
3
4
5
6
7
8
9
10
final Entry<K,V> nextEntry() {
    Entry<K,V> e = next;
    if (e == null)
        throw new NoSuchElementException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

当前节点有右子树时，后继就是右子树最左节点；没有右子树时，沿 parent 向上，寻找第一次从左侧回到的祖先。逆向迭代则使用 predecessor()，方向相反。

虽然一次回溯可能走 O(log n)，但完整遍历的结构访问总量为 O(n)，不需要对每个元素重新执行一次从根查找。

它仍然采用 Fail-Fast：迭代器创建时保存 expectedModCount，next() 和 remove() 对比实际 modCount。外部添加、删除元素可能导致 ConcurrentModificationException；通过另一个范围视图修改同一棵树，也属于外部结构修改。

1
2
3
4
5
6
7
8
TreeSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30));
Iterator<Integer> it = numbers.iterator();
while (it.hasNext()) {
    if (it.next() == 20) {
        it.remove(); // 使用当前迭代器删除
    }
}
System.out.println(numbers); // [10, 30]

再回头看“两子节点删除”，就能理解正向迭代器 remove() 中一个看似奇怪的处理：当 lastReturned 同时具有左右子节点时，先设置 next = lastReturned。因为删除方法会将后继元素复制到这个节点，如果仍然保持原来的 next，就可能跳过被复制过来的元素。

删除成功后，迭代器会同步自己的 expectedModCount，并把 lastReturned 清空，保证一次 next 最多对应一次 remove。逆向迭代器采用单独的删除实现，不需要照搬这个 next 修正。

还有一个很实际的问题：修改元素中参与比较的字段，不会自动重新排序，也不会触发 modCount。 对象可能停留在旧位置，导致 contains/remove 找不到它，甚至出现看上去顺序混乱的结果。正确做法是先删除，再修改，再重新添加；更稳妥的是使用比较字段不可变的对象。

Fail-Fast 只是尽力发现错误使用，不能作为线程同步保障。TreeSet 的 Spliterator 支持 DISTINCT、ORDERED、SORTED 等特征，完整集合的遍历可以利用有序结构分割，但是“支持 Stream”仍然不意味着可以在没有同步的情况下并发修改它。

CopyOnWriteArraySet

基本特性

前面的集合，读和写基本都围绕同一份底层结构进行。CopyOnWriteArraySet 换了一个思路：读取已经发布的数组，写入时构造新数组，再整体替换数组引用。

名字里的 Copy-On-Write，就是“写时复制”。不过它是在真正需要改变内容的写操作才会建立新的数组；重复添加、删除不存在的元素，都有提前返回的路径。

它继承 AbstractSet，实现 Serializable，底层持有 CopyOnWriteArrayList，是一个线程安全的 Set。元素去重依赖相等性判断，不依赖哈希值，也不支持自定义排序比较器。

虽然底层是 List，但对外仍然是 Set：没有公开的下标访问方法，也不能像 List 那样保存多个相等元素。

1
2
3
4
5
6
7
CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<>();
set.add("B");
set.add("A");
set.add("B");
set.add(null);
set.add(null);
System.out.println(set); // [B, A, null]

它允许一个 null，迭代按照元素添加顺序进行。重复添加不会改变位置；删除某元素后重新添加，它会出现在当前数组的尾部。对于同时进行的添加，顺序取决于写操作实际完成的先后，不能用线程启动顺序推断。

这个添加顺序，并不意味着它实现了 JDK 21 的 SequencedSet。CopyOnWriteArraySet 没有 addFirst、addLast 和 reversed 这一套接口能力。 不能因为底层 CopyOnWriteArrayList 支持序列操作，就认为 Set 自动暴露了这些方法。

它最适合的场景，是集合较小、读取和遍历很多、内容变动很少，例如事件监听器集合。广播事件时使用稳定的成员快照，比持续修改一个庞大集合更符合它的设计。

这里的“读取很多”也要拆开看：遍历数组很直接，但是 contains 需要逐个比较，时间复杂度是 O(n)。读路径不获取写锁，不等于查找是 O(1)。

如果元素很多，成员查询十分频繁，或者新增、删除十分频繁，数组扫描和复制都可能成为负担，不能仅凭“线程安全”就选择它。

结构分析

CopyOnWriteArraySet 自身的字段很简单：private finalCopyOnWriteArrayList<E> al。存储、加锁、数组发布和快照迭代，主要都由这个 al 完成。

无参构造创建一个空的 CopyOnWriteArrayList；从 Collection 构造时，如果来源恰好是 CopyOnWriteArraySet，就根据它的 al 创建新的 List 包装，否则创建空 List 再调用 addAllAbsent() 去重。

1
2
3
4
5
6
7
8
9
10
11
public CopyOnWriteArraySet(Collection<? extends E> c) {
    if (c.getClass() == CopyOnWriteArraySet.class) {
        @SuppressWarnings("unchecked") CopyOnWriteArraySet<E> cc =
            (CopyOnWriteArraySet<E>)c;
        al = new CopyOnWriteArrayList<E>(cc.al);
    }
    else {
        al = new CopyOnWriteArrayList<E>();
        al.addAllAbsent(c);
    }
}

这里使用 c.getClass() == CopyOnWriteArraySet.class，不是简单的 instanceof。这是源码针对精确实现类型选择的优化路径，不要自行把条件换成“所有子类都一样”。

CopyOnWriteArrayList 的两个关键字段如下，直接取自这份 JDK 21 源码：

源码定位：CopyOnWriteArrayList.java:107–111。

1
2
3
4
5
final transient Object lock = new Object();

/** 底层数组，只通过 getArray/setArray 访问。 */
private transient volatile Object[] array;

一个是保护写操作的普通 Object 锁，另一个是 volatile 数组引用。这份版本的写锁是 synchronized(lock)，不是某些旧版本分析中常见的 ReentrantLock。

数组本身存放的是元素引用。写入并没有深拷贝每个元素对象，只复制数组里的引用，所以两个版本的数组可能指向同一个元素对象。

CopyOnWriteArraySet 新旧数组与迭代快照

假设集合最初保存 [A, B]，迭代器拿到数组 V1。随后写线程添加 C，它在锁内复制 V1，得到 V2 [A, B, C]，最后把 array 指向 V2。

已经创建的迭代器仍然持有 V1；之后重新调用集合读取方法，会获取当时发布的数组引用。旧数组不会因为替换而被原地改写，但只要还有迭代器引用它，就不能被回收。

volatile 在这里保证数组引用发布的可见性及相关的先行发生关系。写线程在发布新数组之前对新数组内容的初始化，能够被随后读取这个引用的线程看到。

但 volatile 不会自动让“扫描、去重、复制、发布”这个复合过程变成原子操作。所以写操作还要使用锁，保证多个写线程不会基于同一份旧数组各自覆盖对方的结果。

大伙可以把两个机制分开理解：锁用于协调写线程，volatile 数组引用用于向读线程发布结果。两者解决的问题不同，缺一不可。

基本操作

添加元素：先查快照，锁内再校验

CopyOnWriteArraySet 的 add 入口没有调用 List 的普通 add，而是调用专门的 addIfAbsent：

源码定位：CopyOnWriteArraySet.java:260–262。

1
2
3
public boolean add(E e) {
    return al.addIfAbsent(e);
}

源码定位：CopyOnWriteArrayList.java:670–674。

1
2
3
4
5
public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOfRange(e, snapshot, 0, snapshot.length) < 0
        && addIfAbsent(e, snapshot);
}

第一步取出当前数组快照，在锁外调用 indexOfRange() 查找。如果快照里已经存在相等元素，直接返回 false，避免获取写锁和复制数组。

如果快照没有找到，再进入私有重载：

源码定位：CopyOnWriteArrayList.java:680–699。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private boolean addIfAbsent(E e, Object[] snapshot) {
    synchronized (lock) {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {
            // 针对输给其他 addXXX 操作的竞争做优化
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i]
                    && Objects.equals(e, current[i]))
                    return false;
            if (indexOfRange(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    }
}

这个方法中，snapshot != current 是关键。锁外扫描和获取锁之间，另一个线程可能已经添加了同一个元素，如果直接把新元素接在后面，就会出现重复。

所以它必须确认锁内看到的 current 是否还是旧快照。数组没有变化，就可以复用之前“不存在”的判断；数组已经变化，就检查公共前缀中引用变化的位置，并扫描新增加的区间。

为什么没有把所有位置都再比较一次？因为在两份数组的同一个位置，如果元素引用相同，之前的扫描已经排除了它；变化的位置和新增加的位置，才需要重新判断。这是优化重新校验的范围，不是取消重新校验。

最后，确认仍然不存在，才 Arrays.copyOf(current, len + 1)，将 e 放入末尾，再调用 setArray(newElements) 发布结果。

因此，单个 add 已经完成“仅在不存在时添加”的并发协调。没有必要先写一个外部 contains 再 add 来实现去重；外部的两次调用也不会合成一个原子操作。

重复元素仍保留原来的对象，不会因为传入了一个 equals 相等的新对象，就替换数组里的引用。这里的“不重复”也与 HashSet 的哈希定位不同：即使两个相等对象的 hashCode 实现有问题，这条成员查找路径也不使用 hashCode，不过对象本身依旧应该遵守 equals/hashCode 的通用契约。

查找元素：数组扫描，而不是哈希定位

contains(o) 由 Set 委派给 al.contains，List 再在一次获取的数组上调用 indexOfRange()。

对于 null，源码单独检查数组元素是否为 null；对于非 null，调用查找对象的 equals 与数组元素比较。所以 null 能够保存，但最多只能有一个。

1
2
3
CopyOnWriteArraySet<String> names = new CopyOnWriteArraySet<>(List.of("A", "B"));
System.out.println(names.contains("B")); // true
System.out.println(names.contains("C")); // false

一次 contains 的成员判断针对它取得的那个数组版本。在它扫描的同时，其他线程可以发布新数组，但是这次扫描不会半途把前一半换成新数组、后一半保留旧数组。

同样，toArray() 会返回数组副本，不能通过修改返回数组来改变集合内容；size() 读取当前数组长度，不需要逐个计数。

不过，多次调用仍然可能读到不同版本。比如先取得 size，再遍历，结果数量可能不同；线程安全不意味着一组独立调用共享同一个观察时刻。需要对一组成员执行稳定批处理时，应该明确保留一个快照。

删除元素：复制缺少目标的新数组

Set 的 remove(o) 委派给 al.remove。底层先在快照中寻找索引，找不到直接返回 false；找到后在锁内确认目标在当前数组中的位置，防止其他线程修改数组导致原索引失效。

下面是重新校验之后真正构建新数组的源码节选：

源码定位：CopyOnWriteArrayList.java:621–627。

1
2
3
4
5
6
7
Object[] newElements = new Object[len - 1];
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index + 1,
                 newElements, index,
                 len - index - 1);
setArray(newElements);
return true;

新数组长度减一，目标之前和之后的元素分别复制过去，再发布新数组。旧快照仍然包含目标元素，这也是为什么某个监听器从集合删除后，已经开始的那轮快照广播仍可能调用它。

1
2
3
4
5
CopyOnWriteArraySet<String> listeners = new CopyOnWriteArraySet<>(List.of("A", "B"));
Iterator<String> old = listeners.iterator();
listeners.remove("B");
old.forEachRemaining(System.out::println); // 仍然输出 A、B
System.out.println(listeners);            // [A]

这是它明确的快照语义，不能把 remove 返回之后还有旧迭代器输出目标，理解成删除没有生效。如果业务要求“注销后任何正在进行的回调都不能执行”，单靠这个容器不够，还需要业务层协调正在执行的任务。

批量添加：减少发布次数，但仍然需要去重

源码定位：CopyOnWriteArraySet.java:329–331。

1
2
3
public boolean addAll(Collection<? extends E> c) {
    return al.addAllAbsent(c) > 0;
}

底层 addAllAbsent() 在一次锁保护下完成两层去重：既检查候选元素是否已经在现有数组中，也检查它是否已经出现在本次接受的候选前缀中。

源码定位：CopyOnWriteArrayList.java:774–799。

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
public int addAllAbsent(Collection<? extends E> c) {
    Object[] cs = c.toArray();
    if (c.getClass() != ArrayList.class) {
        cs = cs.clone();
    }
    if (cs.length == 0)
        return 0;
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        int added = 0;
        // 在 cs 内部去重并压实元素
        for (int i = 0; i < cs.length; ++i) {
            Object e = cs[i];
            if (indexOfRange(e, es, 0, len) < 0 &&
                indexOfRange(e, cs, 0, added) < 0)
                cs[added++] = e;
        }
        if (added > 0) {
            Object[] newElements = Arrays.copyOf(es, len + added);
            System.arraycopy(cs, 0, newElements, len, added);
            setArray(newElements);
        }
        return added;
    }
}

最后把所有新元素一次接到新数组中，再一次发布。输入中存在重复元素，也不会因为它们“同一批到来”就绕过去重。

1
2
3
CopyOnWriteArraySet<String> letters = new CopyOnWriteArraySet<>(List.of("A"));
letters.addAll(List.of("B", "B", "A", "C"));
System.out.println(letters); // [A, B, C]

这样可以避免循环调用 add 时，每次成功添加都重新复制整个集合。但不要因此把 addAll 的复杂度写成 O(n)：如果集合原有 n 个元素，输入 m 个候选，逐个扫描现有数组并对候选去重，比较开销最坏可达到 O(mn + m²)，再加上最终数组复制。

也就是说，它优化的是写入的批量协调和数组发布次数，并没有使用哈希表消除线性去重成本。

条件删除、保留与清空

removeIf()、removeAll()、retainAll() 也会委派给 CopyOnWriteArrayList。其中批量删除使用 bulkRemove()：在锁内扫描，记录需要删除的位置，构建保留元素的新数组，再统一发布。

1
2
3
4
5
6
CopyOnWriteArraySet<Integer> values =
        new CopyOnWriteArraySet<>(List.of(1, 2, 3, 4));
values.removeIf(n -> n % 2 == 0);
System.out.println(values); // [1, 3]
values.retainAll(List.of(3, 5));
System.out.println(values); // [3]

相比在循环里多次调用集合 remove，removeIf 通常可以减少数组重建次数。它的扫描成本还要考虑谓词本身的执行成本；removeAll/retainAll 则要考虑传入集合 contains 的成本。

还有一个细节：快照迭代不会因为其他线程修改集合而抛出 ConcurrentModificationException，但并不代表这个类的所有方法都绝对不会抛出这个异常。

JDK 21 的 bulkRemove 会在谓词执行后检查数组引用是否变化。如果谓词重入修改了同一个集合，例如在 removeIf 的条件函数中再次 add，源码可能发现内部数组改变并抛出 ConcurrentModificationException。因此条件函数应专注于判断，不要在里面修改同一个集合。

clear() 则直接在锁内发布一个长度为 0 的新数组，不需要逐个 remove。对于集合本身，发布空数组的结构操作是常数级；旧数组与元素最终何时被回收，取决于是否还存在其他引用，以及后续垃圾回收。

迭代器

Set 的迭代器也是委派：iterator() 返回 al.iterator，后者创建 new COWIterator<E>(getArray(), 0)。

迭代器中最关键的两个字段是 private final Object[] snapshot 和 private int cursor。snapshot 在创建时确定，cursor 表示下一个要读取的位置，后续集合修改不会替换这个 snapshot。

下面是读取元素的源码：

源码定位：CopyOnWriteArrayList.java:1181–1185。

1
2
3
4
5
public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}

整个过程只有边界检查和数组访问，没有 expectedModCount 的对比，也不需要获取集合的写锁。

1
2
3
4
5
6
CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<>(List.of("A", "B"));
Iterator<String> it = set.iterator();
set.add("C");
set.remove("A");
it.forEachRemaining(System.out::println); // A、B
System.out.println(set);                 // [B, C]

这个迭代器是创建时的成员快照，不是 ConcurrentSkipListSet 那种可以在推进过程中观察后续修改的弱一致迭代器。

而且它不支持 iterator.remove：调用后直接抛出 UnsupportedOperationException。底层 COWIterator 虽然实现 ListIterator，但它的 remove、set、add 都不受支持；Set 对外返回的类型只是 Iterator。

如果要删除，使用集合自己的 remove 或 removeIf。遍历期间调用集合 remove 不会破坏当前快照，但每次实际删除可能产生一份新数组，而且当前快照后续仍可能返回已删除元素。

快照稳定的是元素引用和成员列表，不是元素对象的所有字段。 如果 A 是一个可变对象，旧数组和新数组都可能指向它；另一个线程修改 A 的字段，并不会被数组复制隔离，也不会自动获得由集合负责的对象级同步。

这也解释了写时复制的两个成本：每次成功新增或删除都需要 O(n) 数组复制；长时间存活的迭代器可能保留旧数组和其中的对象引用，多次写入又产生多个数组版本，使内存占用增大。不存在“复制之后马上释放旧数组”的保证。

它的 Spliterator 由数组快照构建，显式传入 IMMUTABLE 和 DISTINCT，并由数组工厂补充 SIZED、SUBSIZED。这里 IMMUTABLE 描述的是遍历所依赖的数组结构稳定，不代表集合永久不可修改，更不代表元素对象不可变。

操作 主要成本 需要写锁吗
size()/isEmpty() 读取数组及其长度，O(1) 不需要
contains() 线性相等性查找，O(n) 不需要
成功 add()/remove() 查找、校验和复制，O(n) 需要
重复 add、未命中的 remove 可能锁外扫描后直接返回，O(n) 不一定需要
创建 iterator 保存数组引用，O(1) 不需要
完整迭代 访问快照数组，O(n) 不需要
clear() 在锁内发布空数组，O(1) 结构操作 需要

这些复杂度默认 equals 和条件函数的单次调用成本为 O(1)，也不包含线程竞争等待与垃圾回收的耗时。选用它时，应该同时考虑读取方式、写入频率、集合规模和快照存活时间。

ConcurrentSkipListSet

基本特性

TreeSet 能够排序和导航，但是没有并发保护；CopyOnWriteArraySet 支持并发访问，但是频繁写入需要反复复制数组，也不提供排序和范围查询。

那么，如果需要多个线程共同维护一组有序、唯一的元素，并且内容经常变化，就可以看看 ConcurrentSkipListSet。

它继承 AbstractSet，实现 NavigableSet、Cloneable 和 Serializable，内部使用 ConcurrentSkipListMap。排序规则和 TreeSet 一样，可以是自然排序，也可以是在构造时传入的 Comparator。

它的名称已经把底层结构说出来了：Skip List，跳表。它不是给 TreeSet 的红黑树加一把锁，而是使用有序链表与多层索引，并通过 CAS 等机制协调结构修改。

在合理的随机索引分布下，add、remove、contains 等操作的期望时间复杂度为 O(log n)。这里是“期望”，不能把随机结构描述成红黑树那样由平衡性质约束的最坏树高保证；线程竞争产生的重试和比较器执行成本也会影响实际耗时。

1
2
3
ConcurrentSkipListSet<Integer> set = new ConcurrentSkipListSet<>();
Collections.addAll(set, 30, 10, 20, 10);
System.out.println(set); // 无并发修改时：[10, 20, 30]

它通过比较结果判断是否重复，compare/compareTo 返回 0 就视作同一个元素。因此，TreeSet 中说到的“比较规则最好与 equals 一致”“比较字段不应在集合内部直接改变”，这里同样适用。

ConcurrentSkipListSet 禁止 null。即使传入 Comparator.nullsFirst，也不能把 null 添加进去，因为底层方法会在比较器介入之前进行非空检查。

它的迭代器是弱一致的：可以与集合修改同时进行，不通过 modCount 检查来抛出 ConcurrentModificationException，也不会预先复制完整集合。可能观察到迭代开始之后的修改，具体结果取决于修改时机与迭代推进位置。

不过“线程安全”仍然有范围：单次操作得到协调，不等于一组方法调用成为原子事务。contains(e) 后再执行 remove(e)，两次调用之间其他线程可以修改集合；一次 addAll 涉及的所有元素，也不保证整体一次性对外出现。

最后，它维护排序顺序，不维护插入顺序。所以它不能直接满足 LinkedHashSet 的并发插入序需求；如果业务依赖插入序，就需要明确采用外部同步或其他专门设计。

结构分析

ConcurrentSkipListSet 的字段是 private final ConcurrentNavigableMap<E,Object> m。普通构造创建 ConcurrentSkipListMap，范围和逆序视图则使用这个 Map 的子映射视图。

元素仍然作为 Map 的 key 保存，不过这里统一的 value 是 Boolean.TRUE，没有像 HashSet、TreeSet 一样自己声明 PRESENT 对象。

从 SortedSet 构造时保留来源的比较器，从普通 Collection 构造时使用自然排序。对于没有比较器的集合，元素需要具备相互兼容的 Comparable 比较能力。

跳表可以先从“排序单链表”开始理解：普通链表查找一个元素，需要从头逐个比较；给链表增加一些能够跨过多个元素的索引，就可以先快速跳到附近，再下降到更细的层级继续定位。

ConcurrentSkipListSet 的基础链表与索引层

图中，最底层的 Node 链表保存完整的集合成员；上层 Index 节点只为部分 Node 提供索引。每个 Index 的 node 指向它对应的底层节点，right 指向同层右侧索引，down 指向下一层索引。

对照 JDK 21 源码，节点结构如下：

源码定位：ConcurrentSkipListMap.java:360–384。

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
static final class Node<K,V> {
    final K key; // 当前实现中不会脱离链表
    V val;
    Node<K,V> next;
    Node(K key, V value, Node<K,V> next) {
        this.key = key;
        this.val = value;
        this.next = next;
    }
}

/**
 * 索引节点表示跳表的各个层级。
 */
static final class Index<K,V> {
    final Node<K,V> node;  // 当前实现中不会脱离链表
    final Index<K,V> down;
    Index<K,V> right;
    Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
        this.node = node;
        this.down = down;
        this.right = right;
    }
}

这里有两个容易与旧资料混淆的点。

第一，Node 与 Index 是不同的对象：底层 Node 保存 key、val、next；Index 保存 node、down、right。不是简单地在每个底层节点里放一个“所有层的 next 数组”。

第二，这份源码中的 val、next、right 字段并没有直接声明为 volatile。实现通过 VarHandle 的比较交换操作和 acquire/release 等内存屏障安排访问顺序，不能仅凭字段声明就判断并发可见性，更不能拿旧版本的字段定义代替当前源码。

底层字段对应的 VarHandle 包括 NEXT、VAL、RIGHT、HEAD、ADDER，分别服务于基础链表、值、索引、头节点与计数器的原子协调。

索引高度采用随机方式生成。JDK 21 的 doPut 中，先检查 (lr & 0x3) == 0，也就是大约四分之一的新节点进入建立索引的路径；进入之后，再用随机位决定是否继续增加索引层。

所以，不要机械套用“每个底层节点都有一层索引，然后统一以二分之一概率晋升”的描述。图中层级只是便于讲解的一种可能结构，实际哪些节点拥有索引，由随机值、已有层高与并发状态共同决定。

更关键的是，索引是查找加速结构，底层有序链表才保存真实成员。如果节点已经成功接入基础链表，即使索引补充受到并发干扰，成员仍然存在，后续查找可以在较少索引的情况下继续定位。

基本操作

查找元素：先走索引，再定位底层节点

Set 的 contains 委派给 m.containsKey(o)，完整 Map 最终通过 doGet 寻找非 null 的值。

查找时，从 head 开始，看当前索引的 right。如果右侧索引对应的 key 仍然小于目标，就向右走；不能继续向右，就沿 down 下降，最后在基础链表中比较目标附近的节点。

图中查找 35 时，可以先利用 20、30 的索引缩小范围，再在底层找到 35，不需要从 10 一直逐个比较过来。

源码的 findPredecessor 按相似方式寻找严格小于目标的前驱。它还有一个额外工作：遇到对应 Node 的 val 已经为 null 的索引，就尝试把失效索引从当前层摘掉。

这意味着并发查找并非绝对只读所有结构，它可能顺手帮助清理已经删除的节点或索引。实际成员判断仍然以有效的底层节点和值为依据，不会把索引存在当作元素一定存在。

添加元素：putIfAbsent 与 CAS

源码定位：ConcurrentSkipListSet.java:242–244。

1
2
3
public boolean add(E e) {
    return m.putIfAbsent(e, Boolean.TRUE) == null;
}

与 TreeSet 的普通 put 不同，这里使用 putIfAbsent，表达“如果对应 key 不存在，就插入 Boolean.TRUE”。返回 null 说明本次新建了成员，Set 的 add 返回 true；返回已有值说明元素原来就存在，返回 false。

ConcurrentSkipListMap 的 putIfAbsent 最终调用 doPut(key, value, true)。这个 true 表示遇到有效的同 key 节点时保留旧值。

结合源码，可以把添加过程理解为：

  1. 检查 key 非 null，必要时通过 HEAD 的 CAS 初始化基础头节点与索引头。
  2. 从索引层下降，并在基础链表寻找目标位置；遇到删除节点则帮助清理，遇到标记节点等不稳定状态则重新定位。
  3. 如果比较结果为 0 且节点有效，直接返回原值；否则构造新 Node，并尝试更新前驱的 next。
  4. 基础插入成功后，按随机条件补充索引，再更新计数并返回。

下面是真正接入基础链表的源码节选：

源码定位：ConcurrentSkipListMap.java:652–657。

1
2
3
4
5
6
if (c < 0 &&
    NEXT.compareAndSet(b, n,
                       p = new Node<K,V>(key, value, n))) {
    z = p;
    break;
}

NEXT.compareAndSet(b, n, p) 的意思是：只有 b 的 next 仍然是预期的 n，才把它改成新节点 p；新节点的 next 指向 n。

如果另一线程已经修改了同一个位置，CAS 失败，当前线程不能直接覆盖对方的 next，而是重新检查或重新查找。CAS 成功接入新 Node，是新成员插入的关键生效位置；随机索引是在这个基础上补充的。

两个线程同时添加相同的元素，不会像“锁外 contains，然后无条件插入”那样都成功形成两个有效成员。竞争者需要重新观察链表，比较为 0 时返回已有值。

但这个保证是针对一次操作。某元素刚被另一线程删除后，又被重新添加，或者在多个操作之间发生其他变化，都属于正常的并发历史，不能用一次 add 的返回值推断它之后一直存在。

删除元素：逻辑删除、标记与脱链

源码定位：ConcurrentSkipListSet.java:260–262。

1
2
3
public boolean remove(Object o) {
    return m.remove(o, Boolean.TRUE);
}

底层 remove(key, value) 会调用 doRemove。找到比较为 0 的有效节点后，确认 value 匹配 Boolean.TRUE，然后尝试把节点的 val 从原值 CAS 成 null。

val 变成 null，表示这个数据节点已经被逻辑删除。 这一时刻，成员就不能再被当作有效元素；不必等所有链表指针和索引都清理完才生效。

但是，指针清理不能只写 b.next = n.next。如果另一个线程在被删除节点 n 后面插入了新节点，简单替换可能把新插入的路径一起丢掉，所以源码使用 marker 节点协调删除过程。

ConcurrentSkipListMap 的删除标记与脱链

先把 n 的 next 通过 CAS 指向一个 key、val 均为 null 的 marker，marker 再指向后继 f；随后尝试把前驱 b 的 next 从 n 改为 f，越过 n 与 marker。

这里可以直接看 unlinkNode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static <K,V> void unlinkNode(Node<K,V> b, Node<K,V> n) {
    if (b != null && n != null) {
        Node<K,V> f, p;
        for (;;) {
            if ((f = n.next) != null && f.key == null) {
                p = f.next;               // 已经被标记
                break;
            }
            else if (NEXT.compareAndSet(n, f,
                                        new Node<K,V>(null, null, f))) {
                p = f;                    // 添加标记节点
                break;
            }
        }
        NEXT.compareAndSet(b, n, p);
    }
}

如果其他线程已经建立 marker，就复用 marker 的后继；如果没有，则尝试创建。之后再尝试物理脱链。如果当前线程没能完成全部清理，其他线程在查找和更新时也可以帮助完成。

对应索引层还会继续清理失效索引，并在合适时机尝试降低无用的头部层高。逻辑删除、基础链表脱链和索引清理是不同阶段，不要求在一个全局锁中一次全部完成。

用户元素禁止 null，也让 val == null 可以用作内部删除状态；marker/header 的 null key 属于内部结构，不是集合允许保存的 null 元素。

导航、范围视图与反向访问

它提供与 TreeSet 相同的 lower、floor、ceiling、higher、first、last，以及 headSet、tailSet、subSet 和 descendingSet。

1
2
3
4
5
6
7
ConcurrentSkipListSet<Integer> all =
        new ConcurrentSkipListSet<>(List.of(10, 20, 30, 40));
System.out.println(all.floor(25));   // 20
System.out.println(all.ceiling(25)); // 30
NavigableSet<Integer> middle = all.subSet(20, true, 40, false);
middle.remove(30);
System.out.println(all); // 无并发修改时：[10, 20, 40]

这些范围同样是共享底层数据的视图，插入越界元素会抛出 IllegalArgumentException。默认区间仍为左闭右开，视图也继续使用底层的并发更新机制。

descendingSet() 和 JDK 21 的 reversed() 提供逆序视图。虽然拥有 SequencedSet 的接口能力，但是 addFirst/addLast 直接抛出 UnsupportedOperationException，排序位置不能由调用者任意指定。

首尾删除时要区分两组方法：pollFirst/pollLast 通过底层专门的取出并删除路径完成一次首尾移除，空集合返回 null；继承的 removeFirst/removeLast 是先 first/last 再 remove，空集合抛异常，而且这两步在并发情况下不是同一个原子操作。

例如某线程先取得 first 为 10，另一线程将 10 删除并插入 5，前一个线程随后 remove(10) 可能失败，但默认 removeFirst 仍会返回先前取得的 10。需要协调一次“取出并删除当前首元素”的任务时，应使用 pollFirst，而不是把默认首尾方法理解成同样的原子路径。

同理，多线程中 first() 之后再 remove(first)，不能拿来替代 pollFirst 的语义。

size：源码实现与旧注释需要分开看

这是本机 JDK 21.0.4 中一个很值得注意的细节。ConcurrentSkipListSet.size 的注释仍然说计数需要遍历，但是方法本身只是 return m.size()，必须继续追到实际 m 的实现。

完整 ConcurrentSkipListMap 的实现是：

源码定位：ConcurrentSkipListMap.java:1394–1399。

1
2
3
4
5
6
public int size() {
    long c;
    return ((baseHead() == null) ? 0 :
            ((c = getAdderCount()) >= Integer.MAX_VALUE) ?
            Integer.MAX_VALUE : (int) c);
}

getAdderCount 通过 LongAdder.sum 汇总计数。成功添加后 addCount(1)，成功删除后 addCount(-1)。完整集合的 size 没有遍历全部数据节点，它的成本主要来自计数器分片汇总，不能按旧注释直接写成 O(n)，也不宜理解成任何并发状态下都是单字段 O(1) 读取。

而 subSet/headSet/tailSet，甚至 descendingSet 的底层是 SubMap。SubMap.size 则真的会从范围起点开始扫描有效节点计数，范围内有 r 个节点时，其主要遍历成本为 O(r)，再加上定位范围起点的成本。

两个路径在同一个 Set 入口下具有不同实现，这是字段声明成接口之后需要继续追踪实际对象的原因。

无论哪条路径，都不要用 size 的结果做精确的并发限流判断：LongAdder 汇总不是原子快照，节点修改与计数更新也存在观察窗口；范围计数期间成员同样可能变化。if (size() < limit) add(e) 不能保证集合始终小于 limit。

批量操作与复制

addAll、removeAll、retainAll、clear 等批量操作，并不保证整批原子性。其他线程可以观察到部分元素已经变化、其他元素尚未变化的状态。

equals() 在这个类中被重写为双向 containsAll，避免先调用 size。不过两边的成员检查仍然不能在并发修改时形成同一时刻的完整快照，不能把 equals 当成并发状态一致性的证明。

clone 会重建一个新的 ConcurrentSkipListMap，底层结构独立，元素对象仍然共享。对于正在被其他线程修改的来源，复制过程也不能自动获得业务所需的事务快照。

迭代器

正向入口为 m.navigableKeySet().iterator()，逆向入口为 m.descendingKeySet().iterator()。完整映射的正向迭代最终使用 ConcurrentSkipListMap.KeyIterator，范围或逆向视图使用 SubMap 的迭代器。

正向迭代器基类 Iter 保存 lastReturned、next 和 nextValue，推进时沿基础链表的 next 继续查找，并跳过 val 为 null 的节点。

源码定位：ConcurrentSkipListMap.java:2122–2131。

1
2
3
4
5
6
7
8
9
10
final void advance(Node<K,V> b) {
    Node<K,V> n = null;
    V v = null;
    if ((lastReturned = b) != null) {
        while ((n = b.next) != null && (v = n.val) == null)
            b = n;
    }
    nextValue = v;
    next = n;
}

没有复制完整的节点序列，也没有记录 expectedModCount。所以，与 CopyOnWriteArraySet 的固定数组快照不同，它在推进过程中可能看到后来接入的节点；对于已经缓存为 next、之后又被删除的节点，也可能仍然返回其 key。

1
2
3
4
5
6
7
8
9
ConcurrentSkipListSet<Integer> set =
        new ConcurrentSkipListSet<>(List.of(10, 20, 30));
Iterator<Integer> it = set.iterator();
set.add(25);
set.remove(20);
while (it.hasNext()) {
    System.out.println(it.next());
}
// 修改时机影响结果，不应该给这段程序规定唯一输出。

“弱一致”并不意味着随机乱序。返回的元素仍遵循该迭代方向的比较顺序，但是它不承诺观察到所有新增元素，也不承诺只返回仍在集合中的元素，更不承诺整个结果对应某一个统一时刻。

它支持 iterator.remove。完整正向迭代器会取最后返回节点的 key，再调用 ConcurrentSkipListMap.this.remove(key)，最后清空 lastReturned。这个删除是按 key 再次执行的，不能把它理解成迭代器独占了当时那个物理节点；若其他线程已经删除并重新添加同 key 元素，当前删除可能影响重新添加后的成员。

同一个 Iterator 自身的 cursor/next 等状态没有因集合线程安全而自动变成可以由多个线程同时推进的安全协议，通常应由一个线程使用各自的迭代器。

正向遍历一般比逆向遍历更有效率，因为基础链表只有 next，没有 prev；逆向视图推进需要借助搜索找到更小元素。因此不能把“两种方向都支持”理解成它们有完全相同的成本。

完整集合的 key Spliterator 报告 CONCURRENT、NONNULL、DISTINCT、SORTED、ORDERED。CONCURRENT 表示支持并发修改下的遍历语义，不意味着提供不可变快照，也不意味着并行 Stream 中的一组业务操作天然原子。

还要继续区分视图：这份 JDK 21 源码中，范围和逆序视图使用 SubMapKeyIterator 作为 Spliterator，其 characteristics 只返回 DISTINCT、ORDERED、SORTED，没有报告 CONCURRENT 和 NONNULL。它的底层迭代仍是弱一致行为，但不能仅根据完整集合的注释推断每个视图报告完全相同的特征位。

EnumSet

基本特性

前面几个 Set，主要是在讨论“如何组织任意对象”。EnumSet 则利用了一个更具体的条件：元素全部来自同一种枚举类型，而且这个类型的所有可能值已经确定。

既然所有候选成员提前已知，就不一定要为每一个成员建立哈希节点或树节点了。我们可以给每一个枚举常量安排一个 bit，1 表示存在，0 表示不存在。

我觉得这就是 EnumSet 最核心的设计：用位向量表示枚举成员关系的专用集合。

1
2
3
4
5
6
7
enum Permission {
    READ, WRITE, EXECUTE, DELETE, ADMIN
}

EnumSet<Permission> permissions =
        EnumSet.of(Permission.EXECUTE, Permission.READ);
System.out.println(permissions); // [READ, EXECUTE]

插入 EXECUTE 在前，READ 在后，为什么遍历却先输出 READ？因为 EnumSet 按枚举常量的声明顺序遍历，对应 ordinal 从小到大。它不维护插入顺序，也不允许传入 Comparator 自定义顺序。

EnumSet 是抽象类，继承 AbstractSet，实现 Cloneable 和 Serializable。我们不能直接 new EnumSet，而是通过 noneOf、allOf、of、range、copyOf 等工厂方法创建。

它不接受 null，添加 null 会抛出 NullPointerException，但是 contains(null) 和 remove(null) 返回 false。不允许保存 null，不等于查询 null 时都必须抛异常。

同一个 EnumSet 只能保存对应枚举类型的元素。泛型通常在编译期限制类型，底层还会进行类型检查，防止原始类型等方式绕过泛型之后混入其他枚举。

它不是线程安全的。即使内部只是一个 long，也不能因此认为多个线程同时设置不同 bit 没有问题；elements |= mask 包含读取、计算、写回，竞争时可能丢失更新，而且字段没有为普通并发访问提供完整的同步协议。

如果共享可变 EnumSet，可以使用适当的外部锁，或者 Collections.synchronizedSet()，并按包装器要求同步遍历。另一个选择是业务上构造完整集合后，作为不再修改的配置安全发布。

EnumSet 的迭代器不会用 Fail-Fast 检测外部修改。官方总体语义为弱一致，而具体内部实现还需要再区分，后面会结合源码细说。

还有一点与 JDK 21 相关：虽然遍历顺序确定，但是 EnumSet 没有实现 SortedSet、NavigableSet 或 SequencedSet，不支持 lower/floor，也没有 addFirst/reversed。确定的遍历顺序，不会自动变成这些接口的完整能力。

结构分析

工厂方法如何选择内部实现

先看最基础的 noneOf：

源码定位：EnumSet.java:112–121。

1
2
3
4
5
6
7
8
9
10
public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {
    Enum<?>[] universe = getUniverse(elementType);
    if (universe == null)
        throw new ClassCastException(elementType + " not an enum");

    if (universe.length <= 64)
        return new RegularEnumSet<>(elementType, universe);
    else
        return new JumboEnumSet<>(elementType, universe);
}

getUniverse 取得这个枚举类型的完整常量数组。如果传入的 Class 不是枚举类型，就会抛出 ClassCastException；如果是枚举类型，则根据常量总数选择实现：

枚举类型中的常量总数 U 内部实现 成员存储结构
U <= 64 RegularEnumSet 一个 long
U > 64 JumboEnumSet 一个 long[]

注意，分界依据是枚举类型一共声明了多少个常量，不是这个集合当前存入多少个元素。如果某枚举声明 100 个常量，即使集合只保存一个元素，也使用 JumboEnumSet；不会等 size 达到 65 才升级结构。

两个类都是包内的具体实现，业务代码使用 EnumSet 即可，没有必要根据类名进行分支。

EnumSet 本身保存 elementType 和 universe。universe 不是集合当前元素数组，而是这个枚举类型的所有常量，它从 JDK 内部的缓存共享获取，便于通过 ordinal 反查枚举对象。

成员位向量只记录哪些常量被选择，不再为每次 add 单独申请一个成员节点。不过，集合对象、类型信息和 universe 引用仍然存在，不能把“一个 long 存成员”说成整个 EnumSet 对象只占 8 字节。

RegularEnumSet：一个 long 表示 64 个位置

RegularEnumSet 的核心字段为 private long elements = 0L。枚举常量的 ordinal 对应其 bit 位置，掩码为 1L << ordinal。

EnumSet 位向量与 JumboEnumSet 分组

图中按通常的二进制写法把高位画在左边，低位画在右边。Permission 的 READ.ordinal 为 0，EXECUTE.ordinal 为 2，因此 {READ, EXECUTE} 对应低五位 00101。

没有加入 WRITE，只是 bit 1 为 0，不需要创建“WRITE 不存在”的占位节点。两次添加 READ 也是反复将同一个 bit 置为 1，天然不会增加第二份成员。

long 的最高位为 1 时，数值在有符号表示中可能为负，但成员集合依旧正确。这里利用的是位模式，不是把 long 当成普通的非负数量。

恰好 64 个常量也仍然用 RegularEnumSet。 Java 的 long 移位只使用距离的低 6 位，位运算代码利用这一规则处理边界；不能看到“移动 64 位”就按照无限精度整数的规则推断结果。

JumboEnumSet：按 64 个常量一组

JumboEnumSet 使用 private long elements[]，并额外保存一个 size 计数器。构造数组长度为 (universe.length + 63) >>> 6，也就是向上取整的 U/64。

某常量的位置可以拆成：

1
2
3
数组下标 = ordinal >>> 6          // ordinal / 64
组内位置 = ordinal & 63           // ordinal % 64
位掩码   = 1L << ordinal          // long 移位会自动保留低 6 位距离

例如 ordinal 为 70，则位于 elements[1] 的 bit 6。ordinal 为 63 则位于 elements[0] 的最高位；ordinal 为 64，进入 elements[1] 的最低位。

JDK 源码直接写 1L << eOrdinal，没有显式 & 63，并不是忘了处理分组，而是使用了 Java 的移位规则。数组下标与组内 bit 必须结合起来看，不能单独看到相同的掩码就认为 6 与 70 会重复。

基本操作

添加元素：类型校验，然后置位

先看 RegularEnumSet.add：

源码定位：RegularEnumSet.java:161–167。

1
2
3
4
5
6
7
public boolean add(E e) {
    typeCheck(e);

    long oldElements = elements;
    elements |= (1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

它先调用 typeCheck，保存 oldElements，再把目标 bit 设为 1。新旧位向量不同，说明元素原来不存在，返回 true；新旧位向量相同，说明已经存在，返回 false。

这里没有 hashCode，没有 equals 的线性查找，也没有 Comparator。同一枚举类型中的常量具有确定且唯一的 ordinal，成员去重直接映射成同一个 bit。

typeCheck 的源码也很有意思：

源码定位：EnumSet.java:398–402。

1
2
3
4
5
final void typeCheck(E e) {
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        throw new ClassCastException(eClass + " != " + elementType);
}

为什么还检查 getSuperclass？因为枚举常量可以带自己的类体，这样这个常量的运行时类可能是对应枚举的匿名子类。它依旧是合法的同一枚举类型成员，不能只凭 getClass 与 elementType 不相等就拒绝。

调用 e.getClass() 时，如果 e 是 null，自然会抛出 NullPointerException。对于其他枚举类型，即使 ordinal 恰好也是 0，也会先被类型校验拒绝，不能误用相同的 bit。

JumboEnumSet 的添加流程相同，只是要先找到数组分组，并在真的新增时维护 size：

源码定位：JumboEnumSet.java:202–214。

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean add(E e) {
    typeCheck(e);

    int eOrdinal = e.ordinal();
    int eWordNum = eOrdinal >>> 6;

    long oldElements = elements[eWordNum];
    elements[eWordNum] |= (1L << eOrdinal);
    boolean result = (elements[eWordNum] != oldElements);
    if (result)
        size++;
    return result;
}

一个常量的添加仍然只操作一个数组位置，所以即使 U 超过 64，单元素 add 的结构成本也为 O(1)，并不会扫描整个 long[]。

查找与删除：测试 bit、清除 bit

RegularEnumSet.contains 先处理 null 和类型不匹配，再执行 (elements & mask) != 0。只有对应 bit 为 1，元素才在集合中。

删除则将目标 bit 清为 0：

源码定位：RegularEnumSet.java:175–185。

1
2
3
4
5
6
7
8
9
10
11
public boolean remove(Object e) {
    if (e == null)
        return false;
    Class<?> eClass = e.getClass();
    if (eClass != elementType && eClass.getSuperclass() != elementType)
        return false;

    long oldElements = elements;
    elements &= ~(1L << ((Enum<?>)e).ordinal());
    return elements != oldElements;
}

~mask 在目标位置为 0，在其他位置为 1，与 elements 按位与之后，只清除目标位置，保留其他成员。比较新旧值，判断是否真的删除。

JumboEnumSet 只清除对应数组分组的 bit，真正改变成员时再减少 size。

1
2
3
4
5
EnumSet<Permission> set = EnumSet.of(Permission.READ, Permission.EXECUTE);
System.out.println(set.contains(Permission.READ));  // true
System.out.println(set.remove(Permission.WRITE));   // false
System.out.println(set.remove(Permission.EXECUTE)); // true
System.out.println(set);                           // [READ]

RegularEnumSet.size 使用 Long.bitCount(elements)，统计置为 1 的 bit 数。JumboEnumSet.size 则直接返回维护的计数器，避免每次对所有分组重复统计。

contains/remove 对于不属于目标枚举类型的对象返回 false；add 则拒绝错误类型。对于不同操作，类型约束的处理方式不能简单统一成“总是抛异常”。

常用工厂：空集、全集、范围与复制
1
2
3
4
5
EnumSet<Permission> empty = EnumSet.noneOf(Permission.class);
EnumSet<Permission> all = EnumSet.allOf(Permission.class);
EnumSet<Permission> selected = EnumSet.of(Permission.READ, Permission.WRITE);
EnumSet<Permission> range = EnumSet.range(Permission.WRITE, Permission.DELETE);
System.out.println(range); // [WRITE, EXECUTE, DELETE]

noneOf 创建类型已知的空集；allOf 先 noneOf，再将有效成员位全部置为 1；of 从显式给出的枚举常量建立集合。

range 使用枚举声明顺序，两个端点都包含，from.ordinal 大于 to.ordinal 时抛出 IllegalArgumentException。这是一个新集合，不是像 TreeSet.subSet 那样共享数据的范围视图。

RegularEnumSet 的范围初始化直接生成连续 bit 掩码：

源码定位：RegularEnumSet.java:49–51。

1
2
3
void addRange(E from, E to) {
    elements = (-1L >>>  (from.ordinal() - to.ordinal() - 1)) << from.ordinal();
}

这里的无符号右移与左移合起来，产生 from 到 to 的连续 1。JumboEnumSet 则分别处理起始分组、完整的中间分组和结束分组，避免逐个枚举常量调用 add。

copyOf 也需要区分来源：如果来源本来就是 EnumSet，即使为空，也能从 elementType 知道类型并克隆；如果是普通 Collection，就需要从首个元素推断枚举类型，空 Collection 会抛出 IllegalArgumentException。

1
2
3
EnumSet<Permission> empty = EnumSet.noneOf(Permission.class);
EnumSet<Permission> copy = EnumSet.copyOf(empty); // 合法，类型已知
// EnumSet.copyOf(new ArrayList<Permission>());  // IllegalArgumentException

泛型中的 Permission 不会自动补给运行时类型信息。普通空 List 没有实际元素，EnumSet.copyOf 无法凭空知道应该选取哪个枚举 universe。

并集、交集、差集与补集

到了这里，就能理解 EnumSet 为什么适合权限、状态和选项组合：很多集合运算可以直接变成位运算。

对于同类型的 RegularEnumSet，源码走专门的批量路径：

集合操作 对应位运算 作用
addAll(other) elements |= other.elements 并集
retainAll(other) elements &= other.elements 交集
removeAll(other) elements &= ~other.elements 差集
containsAll(other) (other.elements & ~elements) == 0 other 是否为子集

例如 retainAll 的核心分支就是：

源码定位：RegularEnumSet.java:271–273。

1
2
3
long oldElements = elements;
elements &= es.elements;
return elements != oldElements;

这些运算可以一次处理一个 long 中的多个成员，不需要对每一个已存在元素重新定位。

对于同类型 JumboEnumSet，遍历各个 long 分组做同样的位运算，再在需要时重新统计 size，成本约为 O(w)，其中 w = ceil(U/64)。如果传入的是普通 Collection，而不是兼容的 EnumSet，就可能回退到通用逐元素路径。

所以要说准确：同类型 RegularEnumSet 之间的批量位运算是 O(1)，不能把任意来源、任意大小的 EnumSet 批量操作全部写成 O(1)。

1
2
3
4
5
6
7
8
9
10
11
EnumSet<Permission> a = EnumSet.of(Permission.READ, Permission.WRITE);
EnumSet<Permission> b = EnumSet.of(Permission.WRITE, Permission.EXECUTE);
EnumSet<Permission> union = a.clone();
union.addAll(b);
EnumSet<Permission> intersection = a.clone();
intersection.retainAll(b);
EnumSet<Permission> difference = a.clone();
difference.removeAll(b);
System.out.println(union);        // [READ, WRITE, EXECUTE]
System.out.println(intersection); // [WRITE]
System.out.println(difference);   // [READ]

complementOf 则先复制集合，再对副本做补集操作，原集合不变。补集的范围是这个枚举类型的所有常量，不是“所有 Java 对象”。

源码定位：RegularEnumSet.java:58–63。

1
2
3
4
5
6
void complement() {
    if (universe.length != 0) {
        elements = ~elements;
        elements &= -1L >>> -universe.length;  // 清除未使用的位
    }
}

为什么取反之后还要与一个掩码？因为 long 总共有 64 位，而枚举可能只有 5 个常量。单纯执行 ~elements 会把其余不存在枚举常量的高位也设为 1，所以必须清除无效位。

源码里的 -1L >>> -universe.length 利用了 long 移位距离低 6 位的规则：5 个常量对应保留低 5 位；64 个常量对应移位距离 0，保留全部 64 位。对于零常量枚举，外层 length 判断保证不会误生成一个有元素的集合。

不同枚举类型的 EnumSet 做批量操作时，也有专门分支：对方为空时，containsAll 为 true；添加另一个类型的非空集合会被拒绝；与不同类型求交则会清空当前成员。这些行为与数学集合操作和类型限制共同有关，不能忽略空集合这个边界。

克隆与序列化

RegularEnumSet 克隆后，long 成员状态自然独立；JumboEnumSet 还会克隆 long[]，避免两个集合共享可写的位数组。universe 中的枚举常量引用则继续共享，枚举常量本来就是同一个类型的固定对象。

序列化使用 EnumSet.SerializationProxy：保存 elementType 和当前成员数组，反序列化时重新调用 EnumSet.noneOf(elementType)，再逐个添加成员。

因此，序列化保存的是逻辑成员关系，而不是把 Regular/Jumbo 的内部位向量布局直接暴露出去。反序列化按照当时枚举类型的常量总数选择实现；EnumSet 自身的 readObject/readObjectNoData 则拒绝绕过代理的读取路径。

这一点也提醒大伙：ordinal 是内部位定位手段，不适合直接作为长期外部数据协议的成员标识。如果重新排列枚举常量，ordinal 就会变化；外部持久化更适合使用明确、稳定的业务标识。

迭代器

RegularEnumSet：保存一个 long 的成员快照

RegularEnumSet.iterator 创建自己的 EnumSetIterator。构造时执行 unseen = elements，把当前成员位保存到迭代器字段中，并不在每次 next 时重新读取集合的全部位向量。

其 next 的实现如下：

源码定位：RegularEnumSet.java:101–107。

1
2
3
4
5
6
7
public E next() {
    if (unseen == 0)
        throw new NoSuchElementException();
    lastReturned = unseen & -unseen;
    unseen -= lastReturned;
    return (E) universe[Long.numberOfTrailingZeros(lastReturned)];
}

unseen & -unseen 取得最低位的 1；从 unseen 中减掉这一位，就标记该成员已经遍历；Long.numberOfTrailingZeros() 得到它对应的 ordinal，再从 universe 取出枚举常量。

例如 unseen 为 00101，第一次提取 00001，返回 READ；随后 unseen 为 00100，第二次返回 EXECUTE。低位到高位，正好是枚举声明顺序。

1
2
3
4
5
6
EnumSet<Permission> set = EnumSet.of(Permission.READ, Permission.WRITE);
Iterator<Permission> it = set.iterator();
set.remove(Permission.READ);
set.add(Permission.EXECUTE);
it.forEachRemaining(System.out::println); // READ、WRITE
System.out.println(set);                 // [WRITE, EXECUTE]

在这个 RegularEnumSet 示例里，迭代器持有的是创建时的 long 快照，因此后续增删不改变 unseen；不会抛出 ConcurrentModificationException。这个更具体的行为要与 EnumSet 对外的总体弱一致契约区分开。

它支持 iterator.remove：从当前集合的 elements 中清除 lastReturned 对应的 bit，再将 lastReturned 设为 0。一轮 next 之前不能 remove，一次 next 之后也不能连续 remove 两次。

这里的 remove 会修改当前集合的成员位，不是只改迭代器快照；如果该成员已被其他代码删除，再次清除 bit 不会把别的成员一起删除。

JumboEnumSet：按分组推进的弱一致迭代

JumboEnumSet 不能只保存一个 long 就覆盖整个集合。它保存当前分组的 unseen、分组索引 unseenIndex，以及最后返回成员所在的分组。

构造时只读取 elements[0]。当前分组遍历完之后，hasNext 再读取下一个分组：

源码定位：JumboEnumSet.java:126–130。

1
2
3
4
5
public boolean hasNext() {
    while (unseen == 0 && unseenIndex < elements.length - 1)
        unseen = elements[++unseenIndex];
    return unseen != 0;
}

因此，已经读入 unseen 的分组具有局部快照行为，尚未读取的分组可能反映后续修改。它并没有在迭代器创建时 clone 整个 long[]，不能说所有 EnumSet 迭代器都保存完整创建时快照。

next 仍然提取当前 unseen 的最低位 1，但最终 ordinal 需要加上分组偏移：(lastReturnedIndex << 6) + Long.numberOfTrailingZeros(lastReturned)。

iterator.remove 清除对应分组的 bit，并比较新旧值；只有当前集合中的 bit 确实从 1 变为 0 时才减少 size，防止外部已经删除该成员后再次递减计数。

两个实现都不通过 modCount 做 Fail-Fast，也都支持迭代器删除。但不抛出并发修改异常，不等于线程安全。这些迭代特征首先描述了迭代行为，不能代替多个线程对可变 EnumSet 的同步。

RegularEnumSet 完整遍历只提取实际成员的置位 bit，成本为 O(n)；JumboEnumSet 除了返回 n 个成员，还要扫描分组，成本为 O(n + w)。这也说明，一个声明了很多常量、只保存少量成员的 JumboEnumSet，遍历成本还与枚举全集的分组数有关。

EnumSet 继承的 Set 默认 Spliterator 会带有 DISTINCT，但不会仅凭枚举声明顺序就自动报告 SortedSet 的 SORTED 特征。要区分“当前迭代器有确定顺序”和“实现了排序集合接口及对应的分割契约”。

Set 的常见问题与使用边界

Comparable 和 Comparator 的区别

Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：

  • Comparable 接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
  • Comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序

那么，它们的设计哲学完全不同，Comparable的定义是自然排序，Comparator的定义是定制排序。

一般我们需要对元素定义排序时，可以实现 Comparable.compareTo，或者提供 Comparator.compare；无序 Set 并不会因为元素实现 Comparable 就自动排序，但是当我们需要对某一个集合实现两种排序方式，我们可以重写compareTo()方法和使用自制的Comparator方法，因为Comparable<T>只能有一种排序规则，而Comparator<T>可以有多个排序规则，可以按需定义，而且Comparator<T>支持Lambda，Comparable<T>不支持

例如，对下面这样的一个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Student.java
public class Student {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() { return name; }
    public int getScore() { return score; }

    @Override
    public String toString() {
        return name + "(" + score + ")";
    }
}

  • 使用 Comparable：定义“自然排序”（比如按分数升序）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public class Student implements Comparable<Student> {
        // ... 上述字段和构造器 ...

        @Override
        public int compareTo(Student other) {
            // 按分数升序（注意：避免 o1 - o2，防止溢出！）
            return Integer.compare(this.score, other.score);
        }

        // ... toString() ...
    }

    Collections.sort(list); // 自动使用 compareTo()

  • 使用 Comparator：定义多种排序规则

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 1. 按姓名排序（Lambda）
    Comparator<Student> byName = (s1, s2) -> s1.getName().compareTo(s2.getName());

    // 2. 按分数降序（方法引用 + reversed）
    Comparator<Student> byScoreDesc = Comparator.comparingInt(Student::getScore).reversed();

    // 3. 先按分数降序，再按姓名升序（链式）
    Comparator<Student> complex = 
        Comparator.comparingInt(Student::getScore).reversed()
                  .thenComparing(Student::getName);

    // 使用
    List<Student> list = ...; // 同上

    list.sort(byName);         // 按姓名
    list.sort(byScoreDesc);    // 按分数降序
    list.sort(complex);        // 复合排序

    上述排序都不是自然排序，所以，当需要到其他的排序方法的时候，就需要Comparator，要不然你就得改 compareTo()

而且Comparator对处理 null 有自己的支持

1
Comparator.nullsLast(Comparator.naturalOrder()) // null 放最后

而且若元素实现了 Comparable，同时构造排序容器或调用排序方法时又显式传入 Comparator，则使用显式比较器的规则。

1
Collections.sort(list, myComparator); // 忽略 compareTo()

无序性和不可重复性的含义是什么

无序性不等于随机性 ，对于 HashSet，无序表示它没有承诺插入顺序或排序顺序。当前遍历会受哈希值、桶容量、插入删除历史、扩容以及内部节点形态等因素影响，即使元素的 hashCode 不变，也不能把某个观察到的顺序当作 API 保证。其他 Set 是否有序，需要看各自契约

不可重复性是指集合不能包含两个按照其成员判断规则相等的元素。HashSet/LinkedHashSet 要求相等对象具有相同的 hashCode；自定义值对象通常需要同时实现 equals 和 hashCode。TreeSet/ConcurrentSkipListSet 则实际按比较结果为 0 去重。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。

HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，默认遍历遵循插入顺序，但它不是队列，任意删除与 JDK 21 的首尾重定位也会影响顺序。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。

对于 HashSet 和 LinkedHashSet，比较它们的元素都是依赖 hashCode() + equals() 判断唯一性，而 TreeSet 是依赖 compareTo() 或 compare()，返回 0 视为重复

底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于去重并保留插入顺序的场景，TreeSet 用于支持对元素自定义排序规则的场景

HashSet的元素增删查的时间复杂度是 O(1)，LinkedHashSet也是O(1)，但是 LinkedHashSet因为要维护链表，使用起来要比 HashSet 慢一点，而且 TreeSet 因为红黑树平衡操作，所以是O(log n)

HashSet 和 LinkedHashSet 都允许一个 null；TreeSet 使用自然排序时不允许 null，使用能够处理 null 的比较器时可以允许一个 null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Set<String> hashSet = new HashSet<>();
Set<String> linkedHashSet = new LinkedHashSet<>();
Set<String> treeSet = new TreeSet<>();

// 插入相同元素（乱序）
Collections.addAll(hashSet, "Banana", "Apple", "Orange");
Collections.addAll(linkedHashSet, "Banana", "Apple", "Orange");
Collections.addAll(treeSet, "Banana", "Apple", "Orange");

System.out.println("HashSet:      " + hashSet);      
// 顺序不作保证；某次运行可能看到 [Apple, Orange, Banana]

System.out.println("LinkedHashSet: " + linkedHashSet); 
// 输出：[Banana, Apple, Orange] （插入顺序）

System.out.println("TreeSet:       " + treeSet);       
// 输出：[Apple, Banana, Orange] （字典序）

描述一下 HashSet 的去重原理

HashSet 是基于 HashMap 实现的，它利用哈希表（Hash Table）来存储元素，并通过对象的 hashCode() 和 equals() 方法来实现去重。

具体来说，HashSet 的去重原理如下：

  1. 底层结构 HashSet 内部封装了一个 HashMap，所有存入 HashSet 的元素实际上作为 HashMap 的 key 存储，而 value 则是一个固定的 Object 对象（通常是 PRESENT 哨兵对象）。由于 HashMap 的 key 本身不允许重复，这就天然保证了 HashSet 的元素唯一性。

  2. 插入过程中的去重逻辑 当调用 add(E e) 方法添加元素时：

    • 首先调用该元素的 hashCode() 方法，计算其哈希值；
    • 根据哈希值确定在底层哈希表（数组 + 链表/红黑树）中的存储位置（即桶 index）；
    • 如果该位置为空，则直接插入；
    • 如果该位置已有元素（发生哈希冲突），则遍历该位置上的链表或红黑树，依次调用 equals() 方法与新元素比较；
      • 若新元素与已有元素引用相同，或者新元素的 equals(已有元素) 返回 true，说明元素已存在，不插入；
      • 否则按对应桶的结构插入新节点。红黑树桶中还会结合哈希值、可比较性及内部规则寻找位置，不能概括成始终只做线性 equals 扫描。

  3. 为了保证 HashSet 正确去重，hashCode() 与 equals()必须遵守 Java 的通用约定：

    如果两个对象通过 equals() 判定为相等，那么它们的 hashCode() 必须相同； 反之，如果 hashCode() 相同，equals() 不一定为 true（即哈希冲突是允许的）。

  4. 如果只重写 equals() 而不重写 hashCode()，可能导致逻辑上相等的对象被存入 HashSet 多次，破坏去重语义。

也就是说，HashSet 的去重依赖于对象的 hashCode() 定位存储位置，再通过 equals() 精确判断是否重复，二者缺一不可。

自定义类的去重

定义一个Person类，包含id和name两个属性。要求在HashSet中存储Person对象时，能够正确去重。

在自定义类中重写hashCode和equals方法，确保HashSet能够正确判断两个对象是否相等就可以

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
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class Person {
    private int id;
    private String name;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

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

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

    @Override
    public String toString() {
        return "Person{id=" + id + ", name='" + name + "'}";
    }
}

public class PersonHashSetExample {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        set.add(new Person(1001, "A"));
        set.add(new Person(1001, "A"));

        System.out.println(set); // 输出 [Person{id=1001, name='A'}]
    }
}

那么这里再总结一下 Set 集合的去重机制

方法 描述
hashCode 计算对象的哈希值，用于快速定位存储位置。
equals 判断两个对象是否相等，用于在存储位置上进一步判断是否重复。

首先通过hashCode方法计算哈希值，然后通过equals方法判断是否相等。

为什么在修改Set集合中对象的属性值后，可能会导致删除失败？

因为修改属性值后，对象的哈希值可能会发生变化，导致Set集合无法找到该对象。

几种 Set 放在一起看

前面每一种实现，都在围绕“唯一成员”解决不同的问题。把它们放在一起，应该同时看去重规则、遍历顺序、更新成本和迭代语义，而不是只记一个底层结构名称。

实现 底层结构 成员判断 遍历顺序 null 线程安全 迭代器特点
HashSet HashMap 哈希定位与相等性 不保证 一个 否 Fail-Fast，支持 remove
LinkedHashSet LinkedHashMap 哈希定位与相等性 默认插入顺序，可首尾重定位 一个 否 Fail-Fast，支持 remove
TreeSet TreeMap 红黑树 比较结果为 0 比较顺序 取决于比较器 否 Fail-Fast，支持 remove
CopyOnWriteArraySet CopyOnWriteArrayList 数组 相等性扫描 添加顺序 一个 是 创建时数组快照，不支持 remove
ConcurrentSkipListSet ConcurrentSkipListMap 跳表 比较结果为 0 比较顺序 禁止 是 弱一致，支持 remove
EnumSet long / long[] 位向量 类型与 ordinal 定位 枚举声明顺序 添加禁止，查询/删除返回 false 否 无 Fail-Fast，支持 remove；具体快照行为按实现区分

这里的“线程安全”描述集合结构的操作协调，不代替元素对象的同步，也不把多个调用或批量操作自动变成事务。

实现 单元素新增/删除/查找 完整遍历 主要适用条件
HashSet 预期 O(1) O(n + capacity) 不需要顺序，频繁成员判断
LinkedHashSet 预期 O(1) O(n) 去重并保留插入顺序
TreeSet O(log n) O(n) 排序、邻近查询与范围视图
CopyOnWriteArraySet O(n)，成功更新还需复制 O(n)，遍历旧数组 较小集合，少更新，稳定成员快照
ConcurrentSkipListSet 期望 O(log n) 稳定集合的正向遍历 O(n)，逆向成本通常更高 并发排序和导航
EnumSet O(1) Regular O(n)，Jumbo O(n + w) 同一枚举类型，权限/选项组合

n 是当前成员数，capacity 是哈希桶容量，w 是枚举全集所需的 64 位分组数。复杂度默认比较、哈希、equals 的单次成本为 O(1)，不包含竞争重试、锁等待或垃圾回收；并发修改期间的完整遍历也不能直接套用固定 n 的精确耗时模型。

补充：工厂返回的 Set 与包装器

Set.of() 和 Set.copyOf() 返回不可修改的 Set，不允许 null，也不保证插入顺序。of 的输入包含重复元素时抛出 IllegalArgumentException；copyOf 接受 Collection，来源有重复元素时会去重。

JDK 21 的 copyOf 在不直接复用已有内部不可修改实现时，通过临时 HashSet 去重，再调用 of 创建结果：

1
2
3
4
5
6
7
8
9
static <E> Set<E> copyOf(Collection<? extends E> coll) {
    if (coll instanceof ImmutableCollections.AbstractImmutableSet) {
        return (Set<E>)coll;
    } else if (coll.isEmpty()) { // 对 coll 的隐式非空检查
        return Set.of();
    } else {
        return (Set<E>)Set.of(new HashSet<>(coll).toArray());
    }
}

因此 copyOf 得到的是独立的成员快照，来源集合后续增删不会自动反映到结果。已有内部不可修改实现可能直接返回，不必每次分配新的容器；成员对象依旧只是引用，不会被深拷贝。

这些工厂在 JDK 21 中使用 ImmutableCollections 内部实现：一两个元素可以使用 Set12，更多元素通常使用 SetN；SetN 使用数组中的开放寻址与线性探测处理位置冲突，不是给 HashSet 加一个只读开关。空集合还有共享的内部实例。

它们的迭代不应依赖某一次观察到的输出顺序。不可修改的结构也不能阻止元素对象自己的字段变化，因此参与 equals/hashCode 的状态仍然应该稳定。

Collections.unmodifiableSet(original) 则是另一个概念：它是原集合的只读包装视图，原集合后续变化仍然可见。它阻止通过包装器执行修改，不会把原集合变成独立快照。

对于并发哈希集合，ConcurrentHashMap.newKeySet() 返回可修改的 KeySetView，元素作为 key，value 使用 Boolean.TRUE；不允许 null，迭代采用弱一致语义。需要成员快速查询但不需要排序时，这是与 ConcurrentSkipListSet 不同的选择。这里不要将 ConcurrentHashMap 这个 Map 类直接写成“线程安全的 HashSet”。

Collections.newSetFromMap(map) 可以从一个空 Map 创建 Set 包装器，Map 的 key 作为成员，包装器共享该 Map 的状态。比如使用 IdentityHashMap 时，会按引用身份去重，而不是普通 equals；这种语义需要明确的业务目的，不能与普通值相等的 Set 随意混用。

最后，Collections.synchronizedSet(set) 只协调通过同一包装器执行的访问。迭代器不能靠每次 next 的单独加锁保障整个遍历，因此遍历必须同步包围在包装对象的锁内；如果原集合引用仍被其他代码直接修改，包装器也无法替它保护这些绕过访问。

一些 Set 的面试题

Comparable 和 Comparator 的区别

Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：

  • Comparable 接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
  • Comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序

那么，它们的设计哲学完全不同，Comparable的定义是自然排序，Comparator的定义是定制排序。

一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，但是当我们需要对某一个集合实现两种排序方式，我们可以重写compareTo()方法和使用自制的Comparator方法，因为Comparable<T>只能有一种排序规则，而Comparator<T>可以有多个排序规则，可以按需定义，而且Comparator<T>支持Lambda，Comparable<T>不支持

例如，对下面这样的一个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Student.java
public class Student {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() { return name; }
    public int getScore() { return score; }

    @Override
    public String toString() {
        return name + "(" + score + ")";
    }
}

  • 使用 Comparable：定义“自然排序”（比如按分数升序）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public class Student implements Comparable<Student> {
        // ... 上述字段和构造器 ...

        @Override
        public int compareTo(Student other) {
            // 按分数升序（注意：避免 o1 - o2，防止溢出！）
            return Integer.compare(this.score, other.score);
        }

        // ... toString() ...
    }

    Collections.sort(list); // 自动使用 compareTo()

  • 使用 Comparator：定义多种排序规则

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 1. 按姓名排序（Lambda）
    Comparator<Student> byName = (s1, s2) -> s1.getName().compareTo(s2.getName());

    // 2. 按分数降序（方法引用 + reversed）
    Comparator<Student> byScoreDesc = Comparator.comparingInt(Student::getScore).reversed();

    // 3. 先按分数降序，再按姓名升序（链式）
    Comparator<Student> complex = 
        Comparator.comparingInt(Student::getScore).reversed()
                  .thenComparing(Student::getName);

    // 使用
    List<Student> list = ...; // 同上

    list.sort(byName);         // 按姓名
    list.sort(byScoreDesc);    // 按分数降序
    list.sort(complex);        // 复合排序

    上述排序都不是自然排序，所以，当需要到其他的排序方法的时候，就需要Comparator，要不然你就得改 compareTo()

而且Comparator对处理 null 有自己的支持

1
Comparator.nullsLast(Comparator.naturalOrder()) // null 放最后

而且若同时存在 Comparable 和传入 ，Comparator 优先！

1
Collections.sort(list, myComparator); // 忽略 compareTo()

无序性和不可重复性的含义是什么

无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。也就是输出顺序与插入顺序不一致，但每次 JVM 运行中，只要哈希值不变，遍历顺序是确定的，除非你重写了 hashCode()

不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode() 方法。

比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。

HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。

对于 HashSet 和 LinkedHashSet，比较它们的元素都是依赖 hashCode() + equals() 判断唯一性，而 TreeSet 是依赖 compareTo() 或 compare()，返回 0 视为重复

底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景

HashSet的元素增删查的时间复杂度是 O(1)，LinkedHashSet也是O(1)，但是 LinkedHashSet因为要维护链表，使用起来要比 HashSet 慢一点，而且 TreeSet 因为红黑树平衡操作，所以是O(log n)

HashSet 和 LinkedHashSet 都允许一个 null，TreeSet不允许 null，会抛 NullPointerException

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Set<String> hashSet = new HashSet<>();
Set<String> linkedHashSet = new LinkedHashSet<>();
Set<String> treeSet = new TreeSet<>();

// 插入相同元素（乱序）
Collections.addAll(hashSet, "Banana", "Apple", "Orange");
Collections.addAll(linkedHashSet, "Banana", "Apple", "Orange");
Collections.addAll(treeSet, "Banana", "Apple", "Orange");

System.out.println("HashSet:      " + hashSet);      
// 输出：[Apple, Orange, Banana] （无序）

System.out.println("LinkedHashSet: " + linkedHashSet); 
// 输出：[Banana, Apple, Orange] （插入顺序）

System.out.println("TreeSet:       " + treeSet);       
// 输出：[Apple, Banana, Orange] （字典序）

描述一下 HashSet 的去重原理

HashSet 是基于 HashMap 实现的，它利用哈希表（Hash Table）来存储元素，并通过对象的 hashCode() 和 equals() 方法来实现去重。

具体来说，HashSet 的去重原理如下：

  1. 底层结构 HashSet 内部封装了一个 HashMap，所有存入 HashSet 的元素实际上作为 HashMap 的 key 存储，而 value 则是一个固定的 Object 对象（通常是 PRESENT 哨兵对象）。由于 HashMap 的 key 本身不允许重复，这就天然保证了 HashSet 的元素唯一性。

  2. 插入过程中的去重逻辑 当调用 add(E e) 方法添加元素时：

    • 首先调用该元素的 hashCode() 方法，计算其哈希值；
    • 根据哈希值确定在底层哈希表（数组 + 链表/红黑树）中的存储位置（即桶 index）；
    • 如果该位置为空，则直接插入；
    • 如果该位置已有元素（发生哈希冲突），则遍历该位置上的链表或红黑树，依次调用 equals() 方法与新元素比较；
      • 若存在某个已有元素 e.equals(newElement) 返回 true，说明元素已存在，不插入；
      • 否则，将新元素插入到该位置（链表尾部或树中）。

  3. 为了保证 HashSet 正确去重，hashCode() 与 equals()必须遵守 Java 的通用约定：

    如果两个对象通过 equals() 判定为相等，那么它们的 hashCode() 必须相同； 反之，如果 hashCode() 相同，equals() 不一定为 true（即哈希冲突是允许的）。

  4. 如果只重写 equals() 而不重写 hashCode()，可能导致逻辑上相等的对象被存入 HashSet 多次，破坏去重语义。

也就是说，HashSet 的去重依赖于对象的 hashCode() 定位存储位置，再通过 equals() 精确判断是否重复，二者缺一不可。

自定义类的去重

定义一个Person类，包含id和name两个属性。要求在HashSet中存储Person对象时，能够正确去重。

在自定义类中重写hashCode和equals方法，确保HashSet能够正确判断两个对象是否相等就可以

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
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class Person {
    private int id;
    private String name;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

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

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

    @Override
    public String toString() {
        return "Person{id=" + id + ", name='" + name + "'}";
    }
}

public class PersonHashSetExample {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();
        set.add(new Person(1001, "A"));
        set.add(new Person(1001, "A"));

        System.out.println(set); // 输出 [Person{id=1001, name='A'}]
    }
}

那么这里再总结一下 Set 集合的去重机制

方法 描述
hashCode 计算对象的哈希值，用于快速定位存储位置。
equals 判断两个对象是否相等，用于在存储位置上进一步判断是否重复。

首先通过hashCode方法计算哈希值，然后通过equals方法判断是否相等。

为什么在修改Set集合中对象的属性值后，可能会导致删除失败？

因为修改属性值后，对象的哈希值可能会发生变化，导致Set集合无法找到该对象。