一、并发容器概述：为什么需要并发容器？

1.1 从同步容器到并发容器的演进

同步容器（如Vector、Hashtable、Collections.synchronizedList）：

• 通过synchronized关键字实现线程安全

• 简单但性能差：容器级锁导致高并发下吞吐量严重下降

并发容器（JUC包）：

• 基于更精细的锁机制或无锁算法实现

• 读写分离、分段锁、CAS等优化手段

• 在高并发场景下性能表现优异

1.2 JUC并发容器全景图

并发容器主要分为四大类：

1. List并发容器：
   - CopyOnWriteArrayList → 代替Vector、synchronizedList

2. Set并发容器：
   - CopyOnWriteArraySet → 代替synchronizedSet
   - ConcurrentSkipListSet → 代替synchronizedSortedSet

3. Map并发容器：
   - ConcurrentHashMap → 代替Hashtable、synchronizedMap
   - ConcurrentSkipListMap → 代替synchronizedSortedMap

4. Queue并发容器：
   - ArrayBlockingQueue、LinkedBlockingQueue
   - ConcurrentLinkedQueue、PriorityBlockingQueue等

---

二、CopyOnWriteArrayList：读多写少的完美解决方案

2.1 核心原理：写时复制（Copy-On-Write）

工作原理：

1. 读操作：直接读取，无需加锁（因为数组被volatile修饰）

2. 写操作：

   • 加锁（ReentrantLock）

   • 复制原数组到新数组（长度+1）

   • 在新数组上执行修改

   • 将原数组引用指向新数组

   • 解锁

内存变化示意图：

写操作前：
原数组：[1, 2, 3, 4] ← 当前读取的数组

写操作中（添加元素5）：
原数组：[1, 2, 3, 4] ← 读操作仍使用
新数组：[1, 2, 3, 4, 5] ← 写操作在此进行

写操作完成后：
新数组：[1, 2, 3, 4, 5] ← 成为当前数组（原数组被GC回收）

2.2 源码关键实现

// CopyOnWriteArrayList.java
public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    // 核心：volatile保证可见性
    private transient volatile Object[] array;
    final transient ReentrantLock lock = new ReentrantLock();
    
    // 添加元素
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();      // 获取原数组
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);  // 复制数组
            newElements[len] = e;                // 在新数组上修改
            setArray(newElements);               // 替换引用
            return true;
        } finally {
            lock.unlock();
        }
    }
    
    // 获取元素（无锁！）
    public E get(int index) {
        return get(getArray(), index);  // 直接读取，无需同步
    }
}

2.3 实战应用：IP黑名单系统

public class IPBlacklistSystem {
    // 使用CopyOnWriteArrayList存储黑名单IP
    private static final CopyOnWriteArrayList<String> BLACKLIST = 
        new CopyOnWriteArrayList<>();
    
    static {
        // 初始化黑名单
        BLACKLIST.add("192.168.1.100");
        BLACKLIST.add("10.0.0.5");
        BLACKLIST.add("172.16.0.10");
    }
    
    // 检查IP是否在黑名单中（高频读操作）
    public static boolean isBlacklisted(String ip) {
        // 读操作无需加锁，性能极高
        return BLACKLIST.contains(ip);
    }
    
    // 添加黑名单IP（低频写操作）
    public static void addToBlacklist(String ip) {
        // 写操作会复制数组，但频率低，影响小
        if (!BLACKLIST.contains(ip)) {
            BLACKLIST.add(ip);
            System.out.println("已添加IP到黑名单: " + ip);
        }
    }
    
    // 处理用户请求
    public static void handleRequest(String ip) {
        if (isBlacklisted(ip)) {
            System.out.println("拒绝访问: " + ip);
        } else {
            System.out.println("允许访问: " + ip);
            // 处理业务逻辑...
        }
    }
    
    public static void main(String[] args) {
        // 模拟并发请求
        ExecutorService executor = Executors.newFixedThreadPool(10);
        
        // 1000个读请求
        for (int i = 0; i < 1000; i++) {
            final String ip = "192.168.1." + (i % 256);
            executor.submit(() -> handleRequest(ip));
        }
        
        // 偶尔的写操作（添加黑名单）
        executor.submit(() -> addToBlacklist("192.168.1.200"));
        
        executor.shutdown();
    }
}

2.4 优缺点分析

优点：

1. 读性能极高：完全无锁，适合读多写少场景

2. 线程安全：写操作通过锁+数组复制保证

3. 迭代安全：不会抛ConcurrentModificationException

4. 实现简单：基于数组复制，逻辑清晰

缺点：

1. 内存占用大：每次写操作都复制整个数组

2. 数据延迟：读操作可能读到旧数据（最终一致性）

3. 写性能差：复制数组开销大，不适合频繁写操作

2.5 适用场景

1. 黑白名单系统：读多写少，数据变更不频繁

2. 监听器列表：事件监听器列表，注册少触发多

3. 配置信息缓存：配置信息读取频繁，更新少

4. 日志收集：日志写入批量处理，读取统计

---

三、ConcurrentHashMap：高并发场景的Map首选

3.1 版本演进：从分段锁到CAS+synchronized

JDK 1.7：分段锁（Segment）

结构：Segment数组 + HashEntry数组 + 链表
锁粒度：Segment级别（默认16个Segment）
优势：减小锁竞争范围
缺点：内存占用大，并发度固定

JDK 1.8：CAS + synchronized

结构：Node数组 + 链表 + 红黑树（与HashMap相同）
锁粒度：单个链表头节点（更细粒度）
优势：内存更省，并发度更高，性能更好
实现：CAS无锁算法 + synchronized锁升级

3.2 核心数据结构（JDK 1.8）

// Node节点定义
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;           // volatile保证可见性
    volatile Node<K,V> next;  // volatile保证可见性
    
    // ... 方法实现
}

// 树节点定义（当链表过长时转为红黑树）
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // 红黑树父节点
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    TreeNode<K,V> prev;    // 前驱节点
    boolean red;           // 红色标记
}

3.3 实战应用：单词频率统计

public class WordFrequencyCounter {
    /**
     * 统计多个文件中单词出现的频率（并发安全版本）
     */
    public static Map<String, Long> countWordsConcurrent(List<File> files) 
            throws InterruptedException {
        // 使用ConcurrentHashMap保证线程安全
        ConcurrentHashMap<String, LongAdder> wordCount = new ConcurrentHashMap<>();
        
        CountDownLatch latch = new CountDownLatch(files.size());
        ExecutorService executor = Executors.newFixedThreadPool(10);
        
        // 并发处理每个文件
        for (File file : files) {
            executor.submit(() -> {
                try {
                    // 读取文件内容
                    List<String> words = readWordsFromFile(file);
                    
                    // 统计单词频率
                    for (String word : words) {
                        // 使用computeIfAbsent原子操作
                        wordCount.computeIfAbsent(word, k -> new LongAdder())
                                 .increment();
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                } finally {
                    latch.countDown();
                }
            });
        }
        
        // 等待所有任务完成
        latch.await();
        executor.shutdown();
        
        // 转换为普通Map返回
        Map<String, Long> result = new HashMap<>();
        wordCount.forEach((word, adder) -> result.put(word, adder.longValue()));
        
        return result;
    }
    
    /**
     * 使用merge方法更简洁的实现
     */
    public static Map<String, Integer> countWordsWithMerge(List<File> files) 
            throws InterruptedException {
        ConcurrentHashMap<String, Integer> wordCount = new ConcurrentHashMap<>();
        
        CountDownLatch latch = new CountDownLatch(files.size());
        ExecutorService executor = Executors.newFixedThreadPool(10);
        
        for (File file : files) {
            executor.submit(() -> {
                try {
                    List<String> words = readWordsFromFile(file);
                    for (String word : words) {
                        // 使用merge原子操作：如果key不存在则设为1，存在则累加
                        wordCount.merge(word, 1, Integer::sum);
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                } finally {
                    latch.countDown();
                }
            });
        }
        
        latch.await();
        executor.shutdown();
        return wordCount;
    }
    
    private static List<String> readWordsFromFile(File file) throws IOException {
        // 读取文件实现...
        return Collections.emptyList();
    }
}

3.4 ConcurrentHashMap高级API

public class ConcurrentHashMapAPIDemo {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        
        // 1. putIfAbsent：如果不存在则插入
        Integer prev1 = map.putIfAbsent("key1", 100);  // 返回null，插入成功
        Integer prev2 = map.putIfAbsent("key1", 200);  // 返回100，不插入
        
        // 2. computeIfAbsent：如果不存在则计算后插入
        map.computeIfAbsent("key2", k -> k.length());  // key2 -> 4
        
        // 3. computeIfPresent：如果存在则重新计算
        map.computeIfPresent("key2", (k, v) -> v * 2);  // key2 -> 8
        
        // 4. merge：合并值
        map.merge("key3", 1, Integer::sum);  // key3不存在，设为1
        map.merge("key3", 2, Integer::sum);  // key3存在，1+2=3
        
        // 5. search：并发搜索
        String result = map.search(1, (k, v) -> v > 2 ? k : null);
        
        // 6. reduce：并发归约
        int sum = map.reduceValuesToInt(1, Integer::intValue, 0, Integer::sum);
        
        // 7. forEach：并发遍历
        map.forEach(1, (k, v) -> System.out.println(k + "=" + v));
    }
}

3.5 性能优化：LongAdder vs AtomicLong

// ❌ 性能较差：频繁CAS竞争
ConcurrentHashMap<String, AtomicLong> map1 = new ConcurrentHashMap<>();
map1.computeIfAbsent(key, k -> new AtomicLong()).incrementAndGet();

// ✅ 性能优化：减少CAS竞争
ConcurrentHashMap<String, LongAdder> map2 = new ConcurrentHashMap<>();
map2.computeIfAbsent(key, k -> new LongAdder()).increment();

// LongAdder原理：内部维护多个Cell，分散竞争压力

3.6 扩容机制

// ConcurrentHashMap扩容条件
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    // 1. 新建2倍大小的数组
    // 2. 多线程协同迁移：每个线程负责一个区间
    // 3. 迁移期间读写操作可以并行：
    //    - 读操作：在老数组或新数组上查找
    //    - 写操作：如果正在迁移，协助迁移
}

扩容特点：

1. 渐进式扩容：不是一次性完成，避免长时间停顿

2. 多线程协助：写操作发现正在扩容会协助迁移

3. 读写不阻塞：扩容期间读写操作仍可进行

---

四、ConcurrentSkipListMap：有序高并发Map

4.1 跳表（Skip List）原理

什么是跳表：

• 基于有序链表的多层索引结构

• 时间复杂度：O(log n) 查找、插入、删除

• 空间复杂度：O(n)（比平衡树实现简单）

跳表结构：

Level 3: 1 --------------------------------> 9
Level 2: 1 ------------> 5 ------------> 9
Level 1: 1 ----> 3 ----> 5 ----> 7 ----> 9
Level 0: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9

跳表特性：

1. 多层结构，每层都是有序链表

2. 最底层（Level 0）包含所有元素

3. 上层元素是下层的子集

4. 随机确定节点的层数（抛硬币算法）

4.2 ConcurrentSkipListMap实战

public class ConcurrentSkipListMapDemo {
    public static void main(String[] args) {
        // 创建有序并发Map
        ConcurrentSkipListMap<Integer, String> skipListMap = 
            new ConcurrentSkipListMap<>();
        
        // 并发插入
        ExecutorService executor = Executors.newFixedThreadPool(5);
        for (int i = 0; i < 100; i++) {
            final int key = i;
            executor.submit(() -> {
                skipListMap.put(key, "Value-" + key);
            });
        }
        executor.shutdown();
        
        // 范围查询（跳表优势）
        System.out.println("前10个元素: " + skipListMap.headMap(10));
        System.out.println("大于90的元素: " + skipListMap.tailMap(90));
        System.out.println("50-60之间的元素: " + skipListMap.subMap(50, 60));
        
        // 获取最值（跳表优势）
        System.out.println("最小键: " + skipListMap.firstKey());
        System.out.println("最大键: " + skipListMap.lastKey());
        
        // 遍历（有序）
        for (Map.Entry<Integer, String> entry : skipListMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

4.3 跳表插入过程示例

// 模拟跳表插入算法
public class SkipListInsertExample {
    /**
     * 跳表插入步骤：
     * 1. 从最高层开始查找插入位置
     * 2. 记录每层的前驱节点
     * 3. 随机确定新节点的层数
     * 4. 在各层插入新节点
     */
    public void insert(Node newNode) {
        // 1. 随机层数（抛硬币）
        int level = randomLevel();
        
        // 2. 从最高层向下查找
        Node[] update = new Node[MAX_LEVEL];
        Node current = header;
        
        for (int i = MAX_LEVEL - 1; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key < newNode.key) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        // 3. 在各层插入
        for (int i = 0; i < level; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
    
    // 随机层数：抛硬币算法
    private int randomLevel() {
        int level = 1;
        while (Math.random() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }
}

4.4 ConcurrentSkipListMap vs ConcurrentHashMap

特性	ConcurrentHashMap	ConcurrentSkipListMap
有序性	无序	有序（默认升序）
时间复杂度	O(1) ~ O(log n)	O(log n)
内存占用	较低	较高（多层索引）
范围查询	不支持	支持（headMap、tailMap、subMap）
最值查询	不支持	支持（firstKey、lastKey）
适用场景	常规K-V存储	需要有序或范围查询

---

五、并发容器选型指南：电商场景实战

5.1 场景一：商品销量统计

需求特点：

• 频繁按商品ID进行get和set

• 商品ID数量相对稳定

• 高并发读写

方案对比：

// ❌ HashMap：线程不安全，高并发下数据错乱
Map<String, Integer> sales1 = new HashMap<>();

// ❌ Hashtable：全局锁，性能差
Map<String, Integer> sales2 = new Hashtable<>();

// ✅ ConcurrentHashMap：分段锁，性能好
Map<String, Integer> sales3 = new ConcurrentHashMap<>();

// 使用示例
sales3.compute(productId, (k, v) -> v == null ? 1 : v + 1);

最终选择：ConcurrentHashMap

5.2 场景二：用户浏览历史

需求特点：

• 每个用户浏览记录量大

• 频繁增删改查

• 需要按时间范围查询

方案对比：

// ❌ ConcurrentHashMap：红黑树平衡开销大
ConcurrentHashMap<Long, List<BrowseRecord>> history1;

// ✅ ConcurrentSkipListMap：跳表增删效率更高
ConcurrentSkipListMap<Long, BrowseRecord> history2;

// 范围查询示例（跳表优势）
history2.subMap(startTime, endTime);  // 查询时间范围内的记录

最终选择：ConcurrentSkipListMap

5.3 场景三：用户黑名单系统

需求特点：

• 冻结用户少，但查询频繁

• 读多写少

• 需要快速判断用户是否在黑名单中

方案对比：

// ❌ ArrayList：线程不安全
List<String> blacklist1 = new ArrayList<>();

// ❌ Vector：全局锁，性能差
List<String> blacklist2 = new Vector<>();

// ✅ CopyOnWriteArrayList：读无锁，性能好
List<String> blacklist3 = new CopyOnWriteArrayList<>();

// 使用示例
if (blacklist3.contains(userId)) {
    // 拒绝访问
}

最终选择：CopyOnWriteArrayList

5.4 选型决策树

开始
  ↓
是否需要有序或范围查询？
  ├─ 是 → 选择ConcurrentSkipListMap/ConcurrentSkipListSet
  ↓
  ├─ 否 → 读多写少？
  │    ├─ 是 → 选择CopyOnWriteArrayList/CopyOnWriteArraySet
  │    ↓
  │    └─ 否 → 选择ConcurrentHashMap
  ↓
是否是队列场景？
  ├─ 是 → 根据需求选择BlockingQueue实现类
  ↓
  └─ 否 → 完成选型

---

六、迭代器模式：Fail-Fast vs Fail-Safe

6.1 Fail-Fast（快速失败）

代表类：ArrayList、HashMap等java.util包中的集合

原理：

// ArrayList迭代器实现
private class Itr implements Iterator<E> {
    int expectedModCount = modCount;  // 记录修改次数
    
    public E next() {
        checkForComodification();  // 检查是否被修改
        // ... 其他逻辑
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();  // 快速失败
    }
}

特点：

• 迭代过程中检测到结构修改立即抛出异常

• 实现简单，能尽早发现并发问题

• 适用于单线程或正确同步的多线程环境

6.2 Fail-Safe（安全失败）

代表类：CopyOnWriteArrayList、ConcurrentHashMap等java.util.concurrent包中的集合

原理：

// CopyOnWriteArrayList迭代器实现
static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot;  // 迭代器创建时的数组快照
    
    COWIterator(Object[] elements) {
        snapshot = elements;  // 保存快照，后续修改不影响此迭代器
    }
    
    public E next() {
        // 直接从快照中读取，不检查修改
        return (E) snapshot[cursor++];
    }
}

特点：

• 迭代过程中允许集合被修改

• 基于快照机制，不会抛ConcurrentModificationException

• 读到的是旧数据（弱一致性）

• 内存开销较大

6.3 对比总结

特性	Fail-Fast	Fail-Safe
异常抛出	检测到修改立即抛出异常	不会抛出异常
数据一致性	强一致性	弱一致性（读到旧数据）
内存占用	正常	较大（需要复制数据）
适用场景	单线程或正确同步的多线程	高并发读多写少
性能影响	无额外开销	写操作有复制开销

---

七、性能测试与最佳实践

7.1 性能基准测试

public class ConcurrentContainerBenchmark {
    private static final int THREAD_COUNT = 100;
    private static final int OPERATIONS = 100000;
    
    public static void main(String[] args) throws Exception {
        // 测试不同Map的写性能
        testMapPerformance(new HashMap<>());           // 线程不安全，仅作参考
        testMapPerformance(new Hashtable<>());         // 同步Map
        testMapPerformance(new ConcurrentHashMap<>()); // 并发Map
        
        // 测试不同List的读性能
        testListReadPerformance(new ArrayList<>());    // 非同步
        testListReadPerformance(new Vector<>());       // 同步List
        testListReadPerformance(new CopyOnWriteArrayList<>()); // 写时复制
    }
    
    private static void testMapPerformance(Map<Integer, Integer> map) 
            throws InterruptedException {
        long start = System.currentTimeMillis();
        
        CountDownLatch latch = new CountDownLatch(THREAD_COUNT);
        ExecutorService executor = Executors.newFixedThreadPool(THREAD_COUNT);
        
        for (int i = 0; i < THREAD_COUNT; i++) {
            executor.submit(() -> {
                for (int j = 0; j < OPERATIONS; j++) {
                    map.put(j % 1000, j);
                }
                latch.countDown();
            });
        }
        
        latch.await();
        executor.shutdown();
        
        long end = System.currentTimeMillis();
        System.out.println(map.getClass().getSimpleName() + " 写操作耗时: " + 
                          (end - start) + "ms");
    }
}

预期结果：

• ConcurrentHashMap性能远优于Hashtable

• CopyOnWriteArrayList读性能最好，写性能最差

• 根据读写比例选择合适容器

7.2 最佳实践总结

1. 明确需求再选型：

   • 需要有序？→ ConcurrentSkipListMap

   • 读多写少？→ CopyOnWriteArrayList

   • 常规K-V存储？→ ConcurrentHashMap

2. 合理配置参数：

   // ConcurrentHashMap初始容量和并发级别
   Map<String, String> map = new ConcurrentHashMap<>(1000, 0.75f, 16);
   
   // CopyOnWriteArrayList初始容量
   List<String> list = new CopyOnWriteArrayList<>(new String[100]);

3. 使用高级API：

   • 优先使用computeIfAbsent、merge等原子操作

   • 避免先get后put的非原子操作

4. 监控与调优：

   • 监控容器大小和扩容频率

   • 根据负载调整并发级别

5. 避免常见陷阱：

   // ❌ 错误：非原子操作
   if (!map.containsKey(key)) {
       map.put(key, value);  // 可能被其他线程插入
   }
   
   // ✅ 正确：使用原子操作
   map.putIfAbsent(key, value);

---

八、总结与展望

8.1 核心要点回顾

1. CopyOnWriteArrayList：读多写少场景的首选，通过写时复制保证线程安全

2. ConcurrentHashMap：高并发Map的标准选择，JDK 8后性能大幅提升

3. ConcurrentSkipListMap：需要有序或范围查询时的选择，基于跳表实现

4. 选型是关键：根据具体业务场景（读写比例、有序性需求等）选择合适的容器