其他并发容器 ⭐

// ConcurrentLinkedQueue 内部节点结构（简化版）
private static class Node<E> {
    volatile E item;       // 存储的元素值，volatile 保证可见性
    volatile Node<E> next; // 指向下一个节点的引用，volatile 保证可见性
}

// 队列整体结构示意
head                                              tail
  |                                                 |
  v                                                 v
[sentinel] --> [node1: "A"] --> [node2: "B"] --> [node3: "C"] --> null
 (item=null)

// CAS 操作的语义（伪代码，实际由 CPU 原子执行）
boolean compareAndSwap(Object target, long offset, Object expected, Object newValue) {
    // 1. 读取 target 对象在 offset 偏移处的当前值
    Object currentValue = getValueAt(target, offset);
    
    // 2. 比较当前值是否等于预期值
    if (currentValue == expected) {
        // 3. 如果相等，说明没有其他线程修改过，将新值写入
        setValueAt(target, offset, newValue);
        return true;   // CAS 成功
    }
    
    // 4. 如果不相等，说明已经被其他线程抢先修改了
    return false;       // CAS 失败
}
// 关键：步骤 1~3 是由 CPU 保证的原子操作，不可能被中间打断

// ConcurrentLinkedQueue.offer() 简化实现
public boolean offer(E e) {
    // 1. 空值检查，ConcurrentLinkedQueue 不允许 null 元素
    if (e == null) throw new NullPointerException();
    
    // 2. 创建新节点（此时 next 为 null）
    final Node<E> newNode = new Node<>(e);
    
    // 3. 从 tail 开始，循环尝试将新节点链接到队尾
    //    t: 当前尝试的尾节点引用
    //    p: 实际遍历指针
    for (Node<E> t = tail, p = t;;) {
        // 4. 获取 p 的下一个节点
        Node<E> q = p.next;
        
        if (q == null) {
            // 5. q == null 说明 p 确实是链表的最后一个节点
            //    尝试 CAS 将 p.next 从 null 改为 newNode
            if (NEXT.compareAndSet(p, null, newNode)) {
                // 6. CAS 成功！新节点已经链接到链表尾部
                //    检查是否需要更新 tail 指针（hop 策略）
                if (p != t) {
                    // 7. p 和 t 不同，说明 tail 已经落后了，尝试更新
                    //    即使这里 CAS 失败也没关系，其他线程会帮忙更新
                    TAIL.compareAndSet(this, t, newNode);
                }
                return true;  // 入队成功
            }
            // 8. CAS 失败：说明其他线程抢先链接了节点，重新循环
        }
        else if (p == q) {
            // 9. p == q 说明遇到了"自链接"节点（已被移除的节点）
            //    需要从 head 重新开始遍历
            p = (t != (t = tail)) ? t : head;
        }
        else {
            // 10. q != null 且 p != q，说明 p 不是真正的尾节点
            //     向后移动 p，追赶真正的尾节点
            p = (p != t && t != (t = tail)) ? t : q;
        }
    }
}

// ConcurrentLinkedQueue.poll() 简化实现
public E poll() {
    // 定义重启标签，用于特殊情况下从头开始
    restartFromHead:
    for (;;) {
        // 1. 从 head 开始遍历
        for (Node<E> h = head, p = h, q;;) {
            // 2. 获取当前节点 p 的元素值
            E item = p.item;
            
            // 3. 如果 item 不为 null，尝试 CAS 将其置为 null（逻辑删除）
            if (item != null && ITEM.compareAndSet(p, item, null)) {
                // 4. CAS 成功，item 已被"摘取"
                if (p != h) {
                    // 5. 如果 p 和 h 不同，说明 head 指针落后了
                    //    更新 head，同时尝试跳过已失效的节点
                    updateHead(h, ((q = p.next) != null) ? q : p);
                }
                return item;  // 返回出队的元素
            }
            // 6. item 为 null 或 CAS 失败
            else if ((q = p.next) == null) {
                // 7. 没有下一个节点了，队列为空
                updateHead(h, p);
                return null;  // 返回 null 表示队列为空
            }
            else if (p == q) {
                // 8. 遇到自链接节点，从 head 重新开始
                continue restartFromHead;
            }
            else {
                // 9. 移动 p 到下一个节点继续尝试
                p = q;
            }
        }
    }
}

// 出队前：队列中有 A, B, C 三个元素
head                                                    tail
  |                                                       |
  v                                                       v
[sentinel] --> [node1: item=A] --> [node2: item=B] --> [node3: item=C] --> null
 
// 执行 poll() 后：node1 的 item 被 CAS 置为 null，head 前移
                    head                                tail
                      |                                   |
                      v                                   v
[sentinel] --> [node1: item=null] --> [node2: item=B] --> [node3: item=C] --> null
               (逻辑已删除)
 
// sentinel 和 node1 最终变为垃圾，被 GC 回收

import java.util.concurrent.ConcurrentLinkedQueue;
 
public class NonBlockingQueueDemo {
    public static void main(String[] args) throws InterruptedException {
        // 1. 创建一个非阻塞的并发队列
        ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
 
        // 2. 生产者线程：快速入队 100 个元素
        Thread producer = new Thread(() -> {
            for (int i = 0; i < 100; i++) {
                // offer() 永远不会阻塞，直接返回 true
                queue.offer("msg-" + i);
            }
            System.out.println("Producer finished.");
        });
 
        // 3. 消费者线程：循环尝试出队
        Thread consumer = new Thread(() -> {
            int count = 0;                       // 已消费计数
            while (count < 100) {
                // poll() 不会阻塞，队列为空时返回 null
                String msg = queue.poll();
                if (msg != null) {
                    count++;                     // 成功消费一个
                    // 处理消息...
                }
                // msg == null 时，线程不阻塞，立即进入下一轮循环
                // 这就是典型的"忙等待(busy-wait)"或"自旋等待(spin-wait)"
                // 在实际应用中，可加入 Thread.yield() 或短暂 sleep 以减少 CPU 空转
            }
            System.out.println("Consumer finished. Consumed: " + count);
        });
 
        producer.start();   // 启动生产者
        consumer.start();   // 启动消费者
        producer.join();    // 等待生产者完成
        consumer.join();    // 等待消费者完成
    }
}

while (true) {
    String item = queue.poll();
    if (item != null) process(item);
}

while (!queue.isEmpty()) {
    String item = queue.poll();
    process(item);
}

while (true) {
    String item = queue.poll();
    if (item != null) process(item);
    else Thread.yield();
}

for (String item : queue) {
    process(item);
    queue.remove(item);
}

// ConcurrentLinkedDeque 内部节点的简化结构
// 实际源码位于 java.util.concurrent.ConcurrentLinkedDeque.Node
static final class Node<E> {
    // 前驱节点指针，指向链表中当前节点的前一个节点
    volatile Node<E> prev;
    // 当前节点实际存储的数据元素
    volatile E item;
    // 后继节点指针，指向链表中当前节点的后一个节点
    volatile Node<E> next;
}

// 以 offerLast（尾部插入）为例，展示 CAS 无锁插入的核心逻辑（简化版）
public boolean offerLast(E e) {
    // 创建新节点，不允许 null 元素
    final Node<E> newNode = new Node<>(Objects.requireNonNull(e));
 
    // 自旋重试，直到成功将新节点链接到链表尾部
    restartFromTail:
    for (;;) {
        // 从 tail 指针开始寻找真正的尾节点
        // （tail 可能并非指向实际的最后一个节点——这是一种"松弛"优化）
        Node<E> t = tail;
        Node<E> p = t;
 
        for (;;) {
            // q 是 p 的后继节点
            Node<E> q = p.next;
 
            if (q == null) {
                // p 确实是最后一个节点（p.next == null）
                // 将新节点的 prev 设置为 p
                newNode.prev = p;
 
                // 通过 CAS 将 p.next 从 null 改为 newNode
                if (p.casNext(null, newNode)) {
                    // CAS 成功！新节点已链接到链表尾部
                    // 尝试更新 tail 指针（允许失败，属于"松弛"策略）
                    if (p != t) {
                        casTail(t, newNode);
                    }
                    return true; // 插入成功
                }
                // CAS 失败：说明有其他线程抢先插入了节点，重新循环
            } else {
                // p 不是最后一个节点，继续向后遍历
                p = q;
            }
        }
    }
}

import java.util.concurrent.ConcurrentLinkedDeque;
 
public class ConcurrentLinkedDequeDemo {
    public static void main(String[] args) {
        // 创建一个线程安全的双端队列
        ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();
 
        // === 头部操作 ===
        deque.addFirst("B");       // 从头部插入 "B" -> [B]
        deque.offerFirst("A");     // 从头部插入 "A" -> [A, B]
 
        // === 尾部操作 ===
        deque.addLast("C");        // 从尾部插入 "C" -> [A, B, C]
        deque.offerLast("D");      // 从尾部插入 "D" -> [A, B, C, D]
 
        // === 查看操作（不移除元素）===
        System.out.println("头部元素: " + deque.peekFirst());  // 输出: A
        System.out.println("尾部元素: " + deque.peekLast());   // 输出: D
 
        // === 删除操作 ===
        String head = deque.pollFirst();  // 移除并返回头部元素 "A" -> [B, C, D]
        String tail = deque.pollLast();   // 移除并返回尾部元素 "D" -> [B, C]
 
        System.out.println("移除的头部: " + head);  // 输出: A
        System.out.println("移除的尾部: " + tail);  // 输出: D
        System.out.println("剩余队列: " + deque);   // 输出: [B, C]
 
        // === 当作栈使用（LIFO）===
        deque.push("X");            // 等价于 addFirst("X") -> [X, B, C]
        String top = deque.pop();   // 等价于 removeFirst() -> [B, C]
        System.out.println("栈顶弹出: " + top);    // 输出: X
 
        // === 队列为空时的安全操作 ===
        deque.clear();                          // 清空队列
        System.out.println(deque.pollFirst());  // 输出: null（安全返回，不抛异常）
        System.out.println(deque.pollLast());   // 输出: null（安全返回，不抛异常）
 
        // deque.removeFirst();  // ⚠️ 这里会抛 NoSuchElementException！
    }
}

import java.util.concurrent.ConcurrentLinkedDeque;
 
public class DualRoleDemo {
    public static void main(String[] args) {
 
        // ====== 场景一：作为 FIFO 队列使用 ======
        // 等价于 ConcurrentLinkedQueue 的行为
        ConcurrentLinkedDeque<String> fifoQueue = new ConcurrentLinkedDeque<>();
 
        // 生产者从尾部入队
        fifoQueue.offerLast("任务1");   // [任务1]
        fifoQueue.offerLast("任务2");   // [任务1, 任务2]
        fifoQueue.offerLast("任务3");   // [任务1, 任务2, 任务3]
 
        // 消费者从头部出队（先进先出）
        System.out.println(fifoQueue.pollFirst()); // 输出: 任务1
        System.out.println(fifoQueue.pollFirst()); // 输出: 任务2
        System.out.println(fifoQueue.pollFirst()); // 输出: 任务3
 
        // ====== 场景二：作为 LIFO 栈使用 ======
        // push/pop 方法操作头部，天然形成栈的行为
        ConcurrentLinkedDeque<String> lifoStack = new ConcurrentLinkedDeque<>();
 
        // push 等价于 addFirst，将元素压入栈顶
        lifoStack.push("帧A");   // [帧A]
        lifoStack.push("帧B");   // [帧B, 帧A]
        lifoStack.push("帧C");   // [帧C, 帧B, 帧A]
 
        // pop 等价于 removeFirst，从栈顶弹出（后进先出）
        System.out.println(lifoStack.pop()); // 输出: 帧C
        System.out.println(lifoStack.pop()); // 输出: 帧B
        System.out.println(lifoStack.pop()); // 输出: 帧A
 
        // ====== 场景三：Work-Stealing 模式 ======
        // 所有者线程从自己的队列尾部取任务（LIFO，利用缓存局部性）
        // 其他空闲线程从队列头部"偷"任务（FIFO，减少竞争）
        ConcurrentLinkedDeque<String> workQueue = new ConcurrentLinkedDeque<>();
 
        workQueue.offerLast("子任务1");  // 添加到尾部
        workQueue.offerLast("子任务2");
        workQueue.offerLast("子任务3");
 
        // 所有者线程：从尾部取（最近添加的，缓存更热）
        String ownWork = workQueue.pollLast();    // 子任务3
        System.out.println("所有者处理: " + ownWork);
 
        // 窃取线程：从头部偷（最早添加的，与所有者不竞争）
        String stolenWork = workQueue.pollFirst(); // 子任务1
        System.out.println("窃取线程处理: " + stolenWork);
    }
}

import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.CountDownLatch;
 
public class ConcurrentDequeStressTest {
    public static void main(String[] args) throws InterruptedException {
        // 共享的线程安全双端队列
        ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();
        // 用于等待所有线程完成
        int threadCount = 4;
        CountDownLatch latch = new CountDownLatch(threadCount);
 
        // 线程1：从头部插入 0~999
        Thread headProducer = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                deque.offerFirst(i);  // 每次插入到头部
            }
            latch.countDown(); // 标记本线程已完成
        }, "HeadProducer");
 
        // 线程2：从尾部插入 1000~1999
        Thread tailProducer = new Thread(() -> {
            for (int i = 1000; i < 2000; i++) {
                deque.offerLast(i);   // 每次插入到尾部
            }
            latch.countDown();
        }, "TailProducer");
 
        // 线程3：从头部消费
        Thread headConsumer = new Thread(() -> {
            int consumed = 0;
            // 持续消费直到两个生产者都完成
            while (consumed < 500) {
                Integer val = deque.pollFirst(); // 从头部取
                if (val != null) {
                    consumed++;
                }
                // pollFirst 返回 null 说明队列暂时为空，自旋重试
            }
            System.out.println("HeadConsumer 共消费: " + consumed + " 个元素");
            latch.countDown();
        }, "HeadConsumer");
 
        // 线程4：从尾部消费
        Thread tailConsumer = new Thread(() -> {
            int consumed = 0;
            while (consumed < 500) {
                Integer val = deque.pollLast();  // 从尾部取
                if (val != null) {
                    consumed++;
                }
            }
            System.out.println("TailConsumer 共消费: " + consumed + " 个元素");
            latch.countDown();
        }, "TailConsumer");
 
        // 启动所有线程
        headProducer.start();
        tailProducer.start();
        headConsumer.start();
        tailConsumer.start();
 
        // 等待所有线程完成
        latch.await();
 
        // 生产了 2000 个，消费了 1000 个，应剩余 1000 个
        System.out.println("队列剩余元素数量: " + deque.size());
        // 输出: 队列剩余元素数量: 1000
    }
}

// ⚠️ 错误的并发模式——基于 size() 做判断
if (deque.size() > 0) {
    // 在这一瞬间，另一个线程可能已经把最后一个元素取走了！
    String element = deque.pollFirst(); // 可能返回 null！
}
 
// ✅ 正确的并发模式——直接操作并检查返回值
String element = deque.pollFirst();
if (element != null) {
    // 安全地使用 element
    processElement(element);
}

import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedDeque;
 
public class WeakConsistentIteratorDemo {
    public static void main(String[] args) {
        ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();
        deque.addLast("A");
        deque.addLast("B");
        deque.addLast("C");
 
        // 正向迭代（从头到尾）
        Iterator<String> ascIter = deque.iterator();
        // 降序迭代（从尾到头）
        Iterator<String> descIter = deque.descendingIterator();
 
        // 在迭代过程中，其他线程修改队列不会抛异常
        // 但迭代器可能看到也可能看不到这些修改
        System.out.print("正向遍历: ");
        while (ascIter.hasNext()) {
            System.out.print(ascIter.next() + " "); // A B C
        }
 
        System.out.print("\n降序遍历: ");
        while (descIter.hasNext()) {
            System.out.print(descIter.next() + " "); // C B A
        }
    }
}

// CopyOnWriteArrayList 核心字段（JDK 17+）
public class CopyOnWriteArrayList<E> implements List<E> {
    // 用于写操作的独占锁，保证同一时刻只有一个线程在修改
    final transient Object lock = new Object();
    // 底层存储数组，volatile 保证读线程能立即看到最新引用
    private transient volatile Object[] array;
 
    // 获取当前数组的引用（读操作的入口）
    final Object[] getArray() {
        return array;                  // 直接返回引用，无锁
    }
 
    // 将内部数组引用指向新数组（写操作完成后调用）
    final void setArray(Object[] a) {
        array = a;                     // volatile 写，对所有读线程立即可见
    }
}

// ===== 读操作：get() =====
public E get(int index) {
    // getArray() 返回 volatile 引用，获取当前最新的数组快照
    // 注意：这里没有任何 synchronized、Lock、CAS 操作
    return elementAt(getArray(), index);
}
 
// 内部辅助方法，从数组中按下标取元素
@SuppressWarnings("unchecked")
static <E> E elementAt(Object[] a, int index) {
    return (E) a[index];            // 直接数组下标访问，O(1) 时间复杂度
}
 
// ===== 读操作：size() =====
public int size() {
    return getArray().length;        // 直接返回数组长度，无锁
}
 
// ===== 读操作：contains() =====
public boolean contains(Object o) {
    Object[] es = getArray();        // 获取当前数组快照
    return indexOfRange(o, es, 0, es.length) >= 0;  // 线性扫描
}
 
// ===== 读操作：iterator() =====
public Iterator<E> iterator() {
    // 创建迭代器时，将当前数组快照传入
    // 后续迭代永远基于这个快照，不会看到之后的修改
    return new COWIterator<E>(getArray(), 0);
}

// ===== 对比：synchronizedList 的 get() =====
// 来自 Collections.SynchronizedList 的实现
public E get(int index) {
    synchronized (mutex) {           // 每次读都要获取锁！
        return list.get(index);      // 锁竞争是性能瓶颈
    }
}
// 在高并发读场景下，所有读线程互相阻塞，吞吐量极低
 
// ===== 对比：CopyOnWriteArrayList 的 get() =====
public E get(int index) {
    return elementAt(getArray(), index);  // 零锁竞争，零阻塞
}
// 100 个线程同时读，没有任何等待

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
 
public class COWReadDemo {
    public static void main(String[] args) throws InterruptedException {
        // 创建 COW 列表，初始包含三个元素
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("Java");            // 添加初始元素
        list.add("Python");          // 添加初始元素
        list.add("Go");             // 添加初始元素
 
        // 在主线程创建迭代器 —— 此刻快照为 [Java, Python, Go]
        Iterator<String> snapshot = list.iterator();
 
        // 启动子线程在迭代期间修改列表
        Thread writer = new Thread(() -> {
            list.add("Rust");        // 写操作创建新数组 [Java, Python, Go, Rust]
            list.remove("Python");   // 再次创建新数组 [Java, Go, Rust]
            System.out.println("Writer done. Current list: " + list);
        });
        writer.start();              // 启动写线程
        writer.join();               // 等待写线程完成
 
        // 主线程继续用之前的迭代器遍历
        System.out.print("Snapshot iterator sees: ");
        while (snapshot.hasNext()) {
            System.out.print(snapshot.next() + " ");
            // 输出: Java Python Go
            // 注意: Rust 不会出现，Python 不会消失！
            // 因为迭代器持有的是创建时刻的旧数组快照
        }
        System.out.println();
 
        // 重新获取迭代器，可以看到最新状态
        System.out.print("Fresh iterator sees: ");
        for (String s : list) {      // 增强 for 循环会调用 iterator()
            System.out.print(s + " ");
            // 输出: Java Go Rust —— 这是最新的数组
        }
    }
}

// JDK 17+ 源码（简化版）
public boolean add(E e) {
    synchronized (lock) {                      // ① 获取独占锁，同一时刻只有一个线程能写
        Object[] es = getArray();              // ② 获取当前数组引用
        int len = es.length;                   // ③ 记录当前数组长度
        // ④ 创建长度 +1 的新数组，并将旧数组内容完整复制过去
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;                           // ⑤ 在新数组的末尾位置放入新元素
        setArray(es);                          // ⑥ volatile 写：将引用指向新数组
        return true;                           // ⑦ 返回添加成功
    }                                          // ⑧ 释放锁
}

public E set(int index, E element) {
    synchronized (lock) {                      // 获取独占锁
        Object[] es = getArray();              // 获取当前数组
        E oldValue = elementAt(es, index);     // 取出旧值（用于返回）
 
        if (oldValue != element) {             // 判断新旧值是否相同（优化）
            int len = es.length;               // 记录数组长度
            // 完整复制旧数组（即使只改一个元素也要全量复制）
            es = es.clone();
            es[index] = element;               // 在新数组中替换目标位置的值
        } else {
            // 如果新值和旧值是同一个对象，仍然执行 setArray
            // 这是为了保证 volatile 写语义（happens-before）
            // 确保此次操作之前的所有修改对其他线程可见
        }
        setArray(es);                          // volatile 写，发布新数组
        return oldValue;                       // 返回被替换的旧值
    }
}

public E remove(int index) {
    synchronized (lock) {                      // 获取独占锁
        Object[] es = getArray();              // 获取当前数组
        int len = es.length;                   // 当前长度
        E oldValue = elementAt(es, index);     // 记录被删除的元素
        int numMoved = len - index - 1;        // 计算需要移动的元素数量
 
        Object[] newElements;
        if (numMoved == 0) {
            // 删除的是最后一个元素，直接 copyOf 截断
            newElements = Arrays.copyOf(es, len - 1);
        } else {
            // 创建长度减 1 的新数组
            newElements = new Object[len - 1];
            // 复制 index 之前的部分
            System.arraycopy(es, 0, newElements, 0, index);
            // 复制 index 之后的部分（跳过被删除的元素）
            System.arraycopy(es, index + 1, newElements, index, numMoved);
        }
        setArray(newElements);                 // volatile 写，发布新数组
        return oldValue;                       // 返回被删除的元素
    }
}

import java.util.concurrent.CopyOnWriteArrayList;
 
public class EventBus {
    // 监听器列表使用 COW，确保遍历时线程安全
    private final CopyOnWriteArrayList<EventListener> listeners
            = new CopyOnWriteArrayList<>();
 
    // 注册监听器 —— 写操作，偶尔发生
    public void register(EventListener listener) {
        listeners.add(listener);                 // 加锁 + 复制，低频操作
    }
 
    // 注销监听器 —— 写操作，偶尔发生
    public void unregister(EventListener listener) {
        listeners.remove(listener);              // 加锁 + 复制，低频操作
    }
 
    // 触发事件 —— 读操作（遍历），高频操作
    public void fireEvent(Event event) {
        // 增强 for 循环底层调用 iterator()，获取快照
        // 遍历过程中无锁，即使其他线程同时注册/注销也不会出问题
        for (EventListener listener : listeners) {
            listener.onEvent(event);             // 无锁遍历，高性能
        }
        // 不会抛出 ConcurrentModificationException！
    }
}

public class WhitelistService {
    // 白名单使用 COW 列表，读操作零开销
    private final CopyOnWriteArrayList<String> whitelist
            = new CopyOnWriteArrayList<>();
 
    // 初始化：批量加载（addAll 内部也是加锁 + 复制一次）
    public void init(List<String> initialList) {
        whitelist.addAll(initialList);
    }
 
    // 高频读：每个请求都要检查白名单
    public boolean isAllowed(String ip) {
        return whitelist.contains(ip);           // 无锁 O(n) 扫描
    }
 
    // 低频写：管理员手动添加
    public void addToWhitelist(String ip) {
        whitelist.addIfAbsent(ip);               // COW 特有方法，避免重复
    }
}

// 假设列表中有 N 个元素
list.add(newElement);
// 内部实际执行:
// 1. 分配 new Object[N + 1]          → 堆内存分配
// 2. System.arraycopy(old, 0, new, 0, N)  → O(N) 的内存拷贝
// 3. new[N] = newElement
// 4. array = new（volatile 写）
// 5. old 数组等待 GC 回收
 
// 如果连续 add 10 次，就会创建 10 个临时数组！
// 每次大小依次为: N+1, N+2, N+3, ..., N+10
// 总内存拷贝量: N×10 + (1+2+...+10) = 10N + 55 次元素复制

// ❌ 错误做法：10次独立写入 = 10次数组复制
for (String item : newItems) {
    cowList.add(item);               // 每次都复制整个数组！
}
 
// ✅ 正确做法：1次批量写入 = 1次数组复制
cowList.addAll(newItems);            // 只复制一次，高效得多

public class StaleReadDemo {
    private static final CopyOnWriteArrayList<String> list
            = new CopyOnWriteArrayList<>(List.of("v1"));
 
    public static void main(String[] args) {
        // Reader 线程：获取快照后慢慢处理
        Thread reader = new Thread(() -> {
            Iterator<String> it = list.iterator();  // ① 获取快照 ["v1"]
            sleep(2000);                             // ② 模拟慢处理
            while (it.hasNext()) {
                // ③ 输出 "v1"，即使此时 list 已变成 ["v2"]
                System.out.println("Reader sees: " + it.next());
            }
        });
 
        // Writer 线程：1秒后修改数据
        Thread writer = new Thread(() -> {
            sleep(1000);                             // 等待1秒
            list.set(0, "v2");                       // 将 "v1" 改为 "v2"
            System.out.println("Writer updated to v2");
        });
 
        reader.start();
        writer.start();
    }
 
    // 时间线:
    // T=0s: Reader 获取快照 ["v1"]
    // T=1s: Writer 修改为 ["v2"]
    // T=2s: Reader 遍历快照，依然输出 "v1" ← 过时数据！
}

// ❌ 误区1: 以为迭代器能看到最新修改
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
Iterator<String> it = list.iterator();   // 快照: ["A"]
list.add("B");                           // 新数组: ["A", "B"]
it.forEachRemaining(System.out::println); // 只输出 "A"，不会输出 "B"
 
// ❌ 误区2: 以为迭代器支持 remove()
Iterator<String> it2 = list.iterator();
it2.next();
it2.remove();   // 抛出 UnsupportedOperationException！
                // COW 迭代器是只读快照，不支持修改操作
 
// ❌ 误区3: 用于高频写场景
// 下面的代码在循环中不断 add，每次都触发数组复制
// 如果 list 有 10000 个元素，每次 add 都要拷贝 10000+个元素
for (int i = 0; i < 100000; i++) {
    list.add("item-" + i);  // 灾难性性能！时间复杂度 O(N²)
}

// JDK 源码简化展示
public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
 
    // 唯一的内部字段：一个 CopyOnWriteArrayList
    private final CopyOnWriteArrayList<E> al;
 
    // 无参构造器：直接创建一个空的 CopyOnWriteArrayList
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
 
    // 带集合参数的构造器：先创建列表，再利用 addAllAbsent 完成去重
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 如果源本身就是 CopyOnWriteArraySet，已经无重复，直接拷贝
            @SuppressWarnings("unchecked")
            CopyOnWriteArraySet<E> cc = (CopyOnWriteArraySet<E>) c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        } else {
            al = new CopyOnWriteArrayList<E>();
            // addAllAbsent：只添加列表中尚不存在的元素（核心去重方法）
            al.addAllAbsent(c);
        }
    }
}

// CopyOnWriteArraySet.add() 源码
public boolean add(E e) {
    // 如果元素不存在才添加，返回 true 表示添加成功
    // 如果元素已存在，什么都不做，返回 false
    return al.addIfAbsent(e);
}

// CopyOnWriteArrayList.addIfAbsent() 源码简化
public boolean addIfAbsent(E e) {
    // 先拿到当前数组的快照（无锁读取，因为 array 是 volatile 的）
    Object[] snapshot = getArray();
    // indexOf：线性扫描整个数组，看 e 是否已存在
    // 如果找到了（>= 0），直接返回 false，不做任何修改
    // 如果没找到（返回 -1），进入加锁的 addIfAbsent 重载版本
    return indexOfRange(e, snapshot, 0, snapshot.length) < 0
        && addIfAbsent(e, snapshot);
}
 
private boolean addIfAbsent(E e, Object[] snapshot) {
    // 加锁：保证写操作的互斥
    synchronized (lock) {
        // 重新获取当前数组（可能在等锁期间被其他线程修改了）
        Object[] current = getArray();
        int len = current.length;
        // 如果 snapshot 和 current 不是同一个引用，说明数组被改过
        if (snapshot != current) {
            // 需要重新检查：只扫描新增的部分 + 确认旧部分
            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;
                }
            }
            // 检查 current 中超出 snapshot 长度的新增部分
            if (indexOfRange(e, current, common, len) >= 0) {
                return false;
            }
        }
        // 确认不存在后，执行标准的写时复制
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;  // 在末尾放入新元素
        setArray(newElements); // volatile 写，对所有读线程可见
        return true;
    }
}

// CopyOnWriteArraySet.contains() 源码
public boolean contains(Object o) {
    // 直接委托给 CopyOnWriteArrayList 的 contains
    // 内部就是从头到尾遍历数组做 equals 比较
    return al.contains(o);
}
 
// CopyOnWriteArraySet.size() 源码
public int size() {
    return al.size(); // 直接返回内部数组的长度
}
 
// CopyOnWriteArraySet.remove() 源码
public boolean remove(Object o) {
    return al.remove(o); // 委托：先找到元素索引，再写时复制删除
}

// 演示快照迭代器的行为
CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<>();
set.add("A");            // 添加元素 A
set.add("B");            // 添加元素 B
set.add("C");            // 添加元素 C
 
// 获取迭代器——此刻对底层数组拍了一个"快照"
Iterator<String> it = set.iterator();
 
// 在迭代期间，另一个线程（或当前线程）修改了 set
set.add("D");            // 新增 D
set.remove("A");         // 删除 A
 
// 迭代器仍然遍历的是快照：A, B, C
while (it.hasNext()) {
    System.out.print(it.next() + " "); // 输出: A B C
}
 
// 直接遍历 set 看到的是最新数据
System.out.println(set);  // 输出: [B, C, D]

CopyOnWriteArraySet<Integer> set = new CopyOnWriteArraySet<>();
set.addAll(List.of(1, 2, 3, 4, 5));   // 批量添加，内部调用 addAllAbsent
 
// removeIf：原子性地移除满足条件的元素（Java 8+）
// 内部会加锁，一次性完成判断与删除
set.removeIf(n -> n % 2 == 0);        // 移除所有偶数
System.out.println(set);               // 输出: [1, 3, 5]
 
// retainAll：保留交集
set.retainAll(List.of(1, 5, 7));       // 只保留 1 和 5
System.out.println(set);               // 输出: [1, 5]

// 场景1：事件监听器注册表
// - 元素数量少（通常几个到几十个监听器）
// - 注册/注销（写）极少发生
// - 事件触发时遍历（读）极其频繁
// - 遍历过程中不希望被干扰
private final CopyOnWriteArraySet<EventListener> listeners = new CopyOnWriteArraySet<>();
 
public void addListener(EventListener l) {
    listeners.add(l);       // 写操作：低频，加锁+复制
}
 
public void removeListener(EventListener l) {
    listeners.remove(l);    // 写操作：低频
}
 
public void fireEvent(Event e) {
    // 读操作：高频，无锁遍历，快照保证不会 ConcurrentModificationException
    for (EventListener l : listeners) {
        l.onEvent(e);       // 安全地遍历每个监听器
    }
}

// 场景2：白名单/黑名单
// - IP 地址白名单：几十个条目，很少更新，每个请求都要检查
private final CopyOnWriteArraySet<String> whitelist = new CopyOnWriteArraySet<>();
 
public boolean isAllowed(String ip) {
    return whitelist.contains(ip);  // 无锁读，但 O(n)，小集合可接受
}
 
public void allow(String ip) {
    whitelist.add(ip);  // 低频写操作
}

// ❌ 反例1：大量元素
// 10 万个元素，每次 add 都要复制 10 万个元素的数组，且 contains 要扫描 10 万次
CopyOnWriteArraySet<String> largeSet = new CopyOnWriteArraySet<>(); // 千万别这么用
 
// ❌ 反例2：写操作频繁
// 高频写入会导致大量数组复制，GC 压力巨大
for (int i = 0; i < 100000; i++) {
    set.add(UUID.randomUUID().toString()); // 每次都复制整个数组！
}
// 这种场景应该用 ConcurrentHashMap.newKeySet() 或 ConcurrentSkipListSet

// 如果你需要线程安全的大规模 Set，推荐这样做：
// 方案 A：基于 ConcurrentHashMap（无序，O(1) 查找）
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
 
// 方案 B：基于 ConcurrentSkipListMap（有序，O(log n) 查找）
Set<String> sortedConcurrentSet = new ConcurrentSkipListSet<>();

// ConcurrentSkipListMap 的类继承体系
public class ConcurrentSkipListMap<K, V>
    extends AbstractMap<K, V>                // 继承 AbstractMap，获得 Map 基本骨架
    implements ConcurrentNavigableMap<K, V>, // 并发 + 可导航（支持范围查询）
               Cloneable,                    // 支持克隆
               Serializable                  // 支持序列化
{
    // ...
}

Level 3:  HEAD ---------------------------------------------------------> 50 --------------------------> NIL
              |                                                            |
Level 2:  HEAD ----------------------> 20 --------------------------------> 50 -----------> 70 ----------> NIL
              |                         |                                   |                |
Level 1:  HEAD --------> 10 ---------> 20 -----------> 35 ---------------> 50 -----------> 70 --> 80 ---> NIL
              |           |             |                |                   |                |      |
Level 0:  HEAD --> 5 --> 10 --> 15 --> 20 --> 25 --> 35 --> 40 --> 45 --> 50 --> 60 --> 70 --> 80 --> 90 -> NIL

// ===== 1. 数据节点 Node：最底层链表的节点 =====
static final class Node<K, V> {
    final K key;                    // 键，不可变
    V val;                          // 值，通过 CAS 更新
    Node<K, V> next;                // 指向同层下一个节点的引用
}
 
// ===== 2. 索引节点 Index：上层索引链表的节点 =====
static final class Index<K, V> {
    final Node<K, V> node;          // 持有对底层数据节点的引用
    final Index<K, V> down;         // 向下指针：指向下一层的索引节点
    Index<K, V> right;              // 向右指针：指向同层右侧的索引节点
}
 
// ===== 3. 头索引节点 HeadIndex：每一层的入口 =====
static final class HeadIndex<K, V> extends Index<K, V> {
    final int level;                // 当前索引层的层级编号
}

/**
 * 为新插入的节点随机生成层级
 * 使用 ThreadLocalRandom 生成随机数，以位运算判断层级
 */
private int randomLevel() {
    int level = 1;                                   // 至少在 Level 0（底层链表）
    int rnd = ThreadLocalRandom.current().nextInt();  // 获取一个随机整数
    // 当最低位连续为 0 时，层级递增（概率约 1/2 晋升）
    while (((rnd >>>= 1) & 1) != 0) {                // 右移一位，检查最低位
        ++level;                                      // 层级 +1
    }
    return level;                                     // 返回最终层级
}

// ===== 方式一：Key 实现 Comparable 接口，使用自然排序 =====
ConcurrentSkipListMap<Integer, String> map1 = 
    new ConcurrentSkipListMap<>();                    // Integer 天然实现了 Comparable
map1.put(30, "Thirty");                               // 插入 key=30
map1.put(10, "Ten");                                  // 插入 key=10
map1.put(20, "Twenty");                               // 插入 key=20
System.out.println(map1);                             // 输出: {10=Ten, 20=Twenty, 30=Thirty}
                                                      // 按 key 升序排列
 
// ===== 方式二：通过 Comparator 自定义排序规则 =====
ConcurrentSkipListMap<String, Integer> map2 = 
    new ConcurrentSkipListMap<>(                      // 构造函数传入 Comparator
        Comparator.comparingInt(String::length)       // 按字符串长度排序
            .thenComparing(Comparator.naturalOrder())  // 长度相同按字典序
    );
map2.put("Java", 1);                                  // 长度 4
map2.put("Go", 2);                                    // 长度 2
map2.put("C", 3);                                     // 长度 1
map2.put("Rust", 4);                                  // 长度 4
System.out.println(map2);                             // 输出: {C=3, Go=2, Java=1, Rust=4}

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
map.put(10, "A");                                     // 构造测试数据
map.put(20, "B");
map.put(30, "C");
map.put(40, "D");
map.put(50, "E");
 
// ===== 边界查询 =====
map.firstKey();                                       // 10  → 最小 key
map.lastKey();                                        // 50  → 最大 key
map.firstEntry();                                     // 10=A → 最小键值对
map.lastEntry();                                      // 50=E → 最大键值对
 
// ===== 近邻查询 =====
map.lowerKey(30);                                     // 20  → 严格小于 30 的最大 key
map.floorKey(30);                                     // 30  → 小于或等于 30 的最大 key
map.ceilingKey(25);                                   // 30  → 大于或等于 25 的最小 key
map.higherKey(30);                                    // 40  → 严格大于 30 的最小 key
 
// ===== 范围视图（极其实用！）=====
map.headMap(30);                                      // {10=A, 20=B}       → key < 30
map.headMap(30, true);                                // {10=A, 20=B, 30=C} → key <= 30
map.tailMap(30);                                      // {30=C, 40=D, 50=E} → key >= 30
map.subMap(20, true, 40, false);                      // {20=B, 30=C}       → 20 <= key < 40
 
// ===== 降序视图 =====
NavigableMap<Integer, String> desc = map.descendingMap(); // {50=E, 40=D, 30=C, 20=B, 10=A}

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
map.put(40, "D");
 
NavigableMap<Integer, String> sub = map.subMap(15, true, 35, true);
// sub 现在是 {20=B, 30=C}
 
sub.put(25, "X");                                     // 向视图中插入（key=25 在范围内）
System.out.println(map);                              // {10=A, 20=B, 25=X, 30=C, 40=D}
                                                      // 原 Map 也出现了 25=X！
 
map.put(22, "Y");                                     // 向原 Map 插入（key=22 在子范围内）
System.out.println(sub);                              // {20=B, 22=Y, 25=X, 30=C}
                                                      // 视图也看得到 22=Y！
 
sub.put(50, "Z");                                     // key=50 超出范围 [15, 35]
// 抛出 IllegalArgumentException: key out of range

/**
 * 简化版 put 流程伪代码（真实源码更复杂）
 * 展示 CAS 如何保证无锁插入的线程安全
 */
V doPut(K key, V value) {
    for (;;) {                                        // 外层无限重试循环（CAS 典型模式）
        // Step 1: 在底层链表中找到插入位置
        Node<K,V> b = findPredecessor(key);           // 找到 key 的前驱节点 b
        Node<K,V> n = b.next;                         // b 的后继节点 n
 
        // Step 2: 在链表中遍历，找到精确的插入位置
        for (;;) {                                    // 内层循环：沿链表向右扫描
            if (n != null) {
                int cmp = compare(key, n.key);        // 比较 key 与当前节点
                if (cmp > 0) {                        // key 更大，继续右移
                    b = n;                            // 前驱变为当前节点
                    n = n.next;                       // 后继变为下一个
                    continue;                         // 继续内层循环
                }
                if (cmp == 0) {                       // key 已存在
                    // CAS 更新值：期望旧值，设为新值
                    if (n.casValue(n.val, value))     // 原子替换 value
                        return n.val;                 // CAS 成功，返回旧值
                    break;                            // CAS 失败，外层重试
                }
            }
            // Step 3: 找到位置 (b, n) 之间，创建新节点
            Node<K,V> z = new Node<>(key, value, n);  // 新节点的 next 指向 n
            // CAS 将 b.next 从 n 改为 z
            if (!b.casNext(n, z))                     // 原子修改前驱的 next 指针
                break;                                // CAS 失败，外层重试（有人抢先插入了）
            
            // Step 4: 随机决定是否建立索引层
            int rnd = ThreadLocalRandom.current().nextInt();
            if ((rnd & 0x80000001) == 0) {            // 大约 50% 概率
                int level = 1;
                while (((rnd >>>= 1) & 1) != 0)      // 每一位为 1 就升一层
                    ++level;
                addIndex(key, z, level);              // 为新节点建立索引
            }
            return null;                              // 插入成功，返回 null（无旧值）
        }
    }
}

原始状态:        10 ---next---> 20 ---next---> 30
 
Step 1 逻辑删除:  10 ---next---> 20(val=null) ---next---> 30
                               ↑ 值被 CAS 为 null，但节点仍在链表中
 
Step 2 追加标记:  10 ---next---> 20(val=null) ---next---> [MARKER] ---next---> 30
                               ↑ Marker 是一个特殊节点，阻止在 20 之后插入
 
Step 3 物理摘除:  10 ---next--------------------------------------------> 30
                  ↑ CAS 把 10.next 从 20 直接改为 30
                    20 和 MARKER 变为垃圾，等待 GC 回收

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
 
// 迭代过程中可以安全地修改 map，不会抛 ConcurrentModificationException
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry);                        // 遍历当前快照视图
    if (entry.getKey() == 2) {
        map.put(4, "D");                              // 并发插入新元素
        map.remove(3);                                // 并发删除已有元素
    }
    // 新插入的 4="D" 可能出现也可能不出现在本次遍历中
    // 已删除的 3="C" 可能仍被遍历到，也可能不会
}

ConcurrentSkipListMap<String, Integer> map = new ConcurrentSkipListMap<>();
 
// putIfAbsent：仅当 key 不存在时插入，原子操作
map.putIfAbsent("counter", 0);                        // 原子性地"检查并插入"
 
// computeIfAbsent：key 不存在时通过函数计算新值，原子操作
map.computeIfAbsent("score", k -> {                   // k = "score"
    return expensiveComputation();                    // 仅在 key 不存在时执行
});
 
// merge：原子性地合并旧值和新值
map.merge("counter", 1, Integer::sum);                // counter 不存在 → 设为 1
map.merge("counter", 1, Integer::sum);                // counter 存在(=1) → 1+1=2
map.merge("counter", 1, Integer::sum);                // counter 存在(=2) → 2+1=3
 
// replace：原子性地替换
map.replace("counter", 3, 100);                       // 仅当 value==3 时替换为 100
 
// compute：无论 key 是否存在，都进行计算
map.compute("counter", (k, v) -> {                    // v = 当前值（可能为 null）
    return (v == null) ? 1 : v + 1;                   // 原子性地递增
});

// ===== 场景一：并发环境下的排行榜/积分榜 =====
// key = 分数（倒序），value = 用户ID
ConcurrentSkipListMap<Integer, Set<String>> leaderboard = 
    new ConcurrentSkipListMap<>(Comparator.reverseOrder()); // 降序排列
 
// 多线程并发更新积分
leaderboard.computeIfAbsent(950, k -> ConcurrentHashMap.newKeySet())
    .add("user_001");                                 // 原子性地添加用户到对应分数段
 
// O(log n) 快速获取 Top 10
leaderboard.entrySet().stream()
    .limit(10)                                        // 取前 10 名（已经是降序）
    .forEach(System.out::println);
 
 
// ===== 场景二：按时间戳排序的事件队列 =====
ConcurrentSkipListMap<Long, Event> eventTimeline = new ConcurrentSkipListMap<>();
 
// 多线程并发写入事件
eventTimeline.put(System.nanoTime(), new Event("login"));
 
// 高效查询某个时间范围内的事件
long oneHourAgo = System.currentTimeMillis() - 3600_000;
NavigableMap<Long, Event> recentEvents = 
    eventTimeline.tailMap(oneHourAgo);                // O(log n) 定位起点
 
 
// ===== 场景三：缓存中的 TTL 过期管理 =====
ConcurrentSkipListMap<Long, String> expiryIndex = new ConcurrentSkipListMap<>();
// key = 过期时间戳，value = 缓存 key
 
// 清理过期条目——只需取出 headMap 即可
long now = System.currentTimeMillis();
NavigableMap<Long, String> expired = expiryIndex.headMap(now); // 所有已过期的
expired.forEach((ts, cacheKey) -> {                   // 遍历并清理
    cache.remove(cacheKey);                           // 从主缓存中移除
});
expired.clear();                                      // 从过期索引中批量删除

// ConcurrentSkipListSet 的核心源码结构
public class ConcurrentSkipListSet<E>
        extends AbstractSet<E>                  // 继承 AbstractSet，获得集合通用方法
        implements NavigableSet<E>,             // 实现 NavigableSet，支持导航操作
                   Cloneable,                   // 支持克隆
                   java.io.Serializable {       // 支持序列化
 
    // 唯一的核心字段：内部委托的 ConcurrentSkipListMap
    // 集合元素作为 Map 的 key，value 全部填充 Boolean.TRUE
    private final ConcurrentNavigableMap<E, Object> m;
 
    // 构造方法：创建一个新的 ConcurrentSkipListMap 作为后端存储
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap<E, Object>();  // 使用自然排序
    }
 
    // 带比较器的构造方法
    public ConcurrentSkipListSet(Comparator<? super E> comparator) {
        m = new ConcurrentSkipListMap<E, Object>(comparator);  // 使用自定义排序
    }
 
    // 从已有集合构造
    public ConcurrentSkipListSet(Collection<? extends E> c) {
        m = new ConcurrentSkipListMap<E, Object>();  // 先创建空 Map
        addAll(c);                                    // 再逐个添加元素
    }
 
    // 从已有 SortedSet 构造，保留其比较器
    public ConcurrentSkipListSet(SortedSet<E> s) {
        m = new ConcurrentSkipListMap<E, Object>(s.comparator());  // 复用比较器
        addAll(s);                                                  // 逐个添加
    }
 
    // 内部使用的私有构造方法，直接接收一个 Map 实例
    // 用于 subSet/headSet/tailSet 等子视图操作
    ConcurrentSkipListSet(ConcurrentNavigableMap<E, Object> m) {
        this.m = m;  // 直接引用传入的子 Map
    }
}