并发中的安全集合

像HashMap、ArrayList之类的集合在并发操作下很容易出错，或者说它们是线程不安全的。但在开发中我们难免用到这些集合，因此我们必须对这些集合进行一定的设计。

但在并发操作中使用集合，这种操作是很寻常的，几乎大部分使用者都会面临这个问题。所以JDK已经提前帮我们设计了一些并发中线程安全的集合。JDK提供的这些容器大部分在java.util.concurrent包中。

• ConcurrentHashMap：这是一个高效的并发HashMap。你可以理解为一个线程安全的HashMap，通过分段锁技术（在Java 8及以后版本中使用了更精细的锁机制）减少了锁的粒度，提高了并发性能。它允许在读取时不加锁，且写操作的锁粒度更小，从而支持更高的并发度。
• CopyOnWriteArrayList：这是一个List，从名字看就是和ArrayList是一族的。在读多写少的场合，这个List的性能非常好，远远好于Vector。
• CopyOnWriteArraySet：基于CopyOnWriteArrayList实现的线程安全Set集合，同样适用于读多写少的情况。
• ConcurrentLinkedQueue：高效的并发队列，使用链表实现。可以看做一个线程安全的LinkedList。
• BlockingQueue：虽然严格来说不是一个集合，但它是一个线程安全的队列，用于在多线程间进行数据传输。它有多种实现，如ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue等，支持阻塞等待队列操作。
• ConcurrentSkipListMap：跳表的实现。这是一个Map，使用跳表的数据结构进行快速查找。

除了以上并发包中的专有数据结构外，java.util下的Vector是线程安全的（虽然性能和上述专用工具没得比），另外Collections工具类可以帮助我们将任意集合包装成线程安全的集合。

线程安全的Map

下面介绍两种创建线程安全的map，一种是通过Collections工具类，另一种则是直接构建。

• 工具类

public static Map m = Collections.synchronizedMap(new HashMap());

这个包装的Map可以满足线程安全的要求。但是，它在多线程环境中的性能表现并不算太好。无论是对Map的读取或者写入，都需要获得mutex的锁

一个更加专业的并发HashMap是ConcurrentHashMap。它位于java.util.concurrent包内。它专门为并发进行了性能优化，因此，更加适合多线程的场合。

• 直接创建

import java.util.concurrent.ConcurrentHashMap;

public class WordCountExample {

    public static void main(String[] args) throws InterruptedException {
        // 创建一个ConcurrentHashMap来存储单词及其出现次数
        ConcurrentHashMap<String, Integer> wordCounts = new ConcurrentHashMap<>();

        // 定义一个任务，用于统计文本中的单词出现次数
        Runnable countingTask = () -> {
            String text = "Hello world! Welcome to the Java programming world. Hello again!";
            String[] words = text.split("\\W+"); // 使用正则表达式分割单词

            for (String word : words) {
                // 使用ConcurrentHashMap的putIfAbsent和computeIfPresent方法来安全地增加计数
                wordCounts.putIfAbsent(word, 1);
                wordCounts.computeIfPresent(word, (k, v) -> v + 1);
            }
        };

        // 创建并启动多个线程来执行统计任务
        Thread thread1 = new Thread(countingTask);
        Thread thread2 = new Thread(countingTask);

        thread1.start();
        thread2.start();

        // 等待所有线程完成
        thread1.join();
        thread2.join();

        // 打印最终的单词计数结果
        System.out.println("Word counts:");
        wordCounts.forEach((word, count) -> 
            System.out.println("Word: " + word + ", Count: " + count));
    }
}

在这个例子中，我们创建了一个ConcurrentHashMap实例wordCounts来统计文本中每个单词的出现次数。通过启动两个线程并执行相同的统计任务，模拟了多线程环境下的并发操作。ConcurrentHashMap的putIfAbsent方法保证了如果键不存在，则插入键值对；而computeIfPresent方法则在键存在时更新其值，这两个方法都是原子操作，确保了在多线程环境下的线程安全性。最后，我们打印出每个单词及其出现次数，展示了并发处理后的结果。

ConcurrentHashMap

在Java中，ConcurrentHashMap 是线程安全的哈希表实现，1.7和1.8版本在设计和实现上有显著差异。以下是两者的核心特点和主要改动：

Java 7的ConcurrentHashMap结构是分段的数组，每个Segment相当于一个小的HashTable，每个Segment里面是数组加链表的结构。锁的粒度是Segment，所以当多个线程访问不同的Segment时，不会冲突。默认的并发级别是16，也就是有16个Segment，可以同时支持16个线程并发写。这样设计的好处是减少锁的竞争，但可能如果并发级别设置不合适，或者多个线程访问同一个Segment的话，还是会有竞争。

总结下就是：

Java 7 中-ConcurrentHashMap的特点

1. 分段锁（Segment Locking）：
   • 数据结构由多个 Segment（默认16个）组成，每个 Segment 继承自 ReentrantLock，类似独立的哈希表。
   • 每个 Segment 内部是 数组+链表 结构，锁的粒度是 Segment 级别。
   • 不同 Segment 的并发操作互不影响，但同一 Segment 的写操作会竞争同一把锁。
2. 并发度（Concurrency Level）：
   • 初始化时指定并发度（默认16），即 Segment 的数量，决定了最大并发线程数。
3. 查询弱一致性：
   • 迭代器和读操作可能无法反映最新的修改，但保证最终一致性。
4. 扩容机制：
   • 仅针对单个 Segment 扩容，但扩容期间该 Segment 会阻塞写操作。

在Java 1.8版本中，ConcurrentHashMap的锁机制与之前的版本有所不同。在1.8版本中，ConcurrentHashMap摒弃了分段锁（Segment）的设计，转而采用更细粒度的锁机制，即锁的是Node（数组中的桶或节点）。这意味着在操作数据时，锁的粒度更小，从而减少了锁竞争的可能性，提高了并发性能

Java 8，ConcurrentHashMap做了很多优化。首先，结构上不再用Segment，而是直接用Node数组，每个Node可以是链表或者红黑树。当链表长度超过阈值（默认是8）时，链表会转成红黑树，这样在查询的时候效率更高，尤其是在哈希冲突严重的情况下。同时，扩容机制也改进了，支持多线程一起扩容。

在扩容时，它会通过CAS操作设置sizeCtl和transferIndex等变量来协调多个线程进行并发扩容。

具体来说，当某个线程发现需要扩容时，它会尝试获取扩容任务。如果此时已经有其他线程在进行扩容，该线程会帮助一起完成扩容任务。扩容过程中，会将原数组分组，每组分配给不同的线程进行元素迁移，每个线程负责一组或多组的元素转移工作。这样可以充分利用多核CPU的优势，提高扩容的效率。

在并发控制方面，Java 8用了CAS操作和synchronized。比如，插入元素的时候，如果该位置没有节点，就用CAS来添加；如果有节点，则用synchronized锁住头节点，然后进行操作。这样锁的粒度更细，只锁住单个桶，而不是整个Segment，这样并发度更高了。

关于链表 和 红黑树 之间的转换条件，如下文：

数组总长度 ≥ 64，同时链表长度 ≥8，便将链表转换为红黑树。

如果某一方的条件不满足，比如若此时数组长度小于 MIN_TREEIFY_CAPACITY（默认 64），会优先触发扩容而非树化

退化条件

当红黑树节点数 ≤6 时，会退化为链表（UNTREEIFY_THRESHOLD），避免资源浪费

Java 8（JDK 1.8）的改进

1. 数据结构优化：
   • 废弃分段锁，改为 数组+链表+红黑树 结构（与 HashMap 一致）。
   • 当链表长度超过阈值（默认8）时，链表转为红黑树，降低查询时间复杂度（从 O(n) 到 O(logn)）。
2. 锁粒度细化：
   • 使用 CAS（Compare-And-Swap） 和 synchronized 替代 ReentrantLock。
   • 锁的粒度细化到 单个桶（Bucket）的头节点，并发度显著提高（理论上接近哈希表长度）。
3. 并发扩容支持：
   • 多线程协同扩容：线程在插入时发现正在扩容，会帮助迁移数据。
   • 采用 ForwardingNode 标记迁移状态，避免重复迁移。
4. 高效的统计与API：
   • size() 方法通过 CounterCell 分段计数（类似 LongAdder），减少竞争。
   • 新增函数式API（如 forEach、compute），支持原子更新操作。