java--线程安全集合 CopyOnWriteArrayList、ConcurrentHashMap、ConcurrentSkipListMap、BlockingQueue

ゞ浴缸里的玫瑰 2022-03-12 02:18 258阅读 0赞

# 概要 #

线程安全集合可以分为三大类：

>  *  从以前 jdk 传承下来的 Hashtable、Vector；
>  *  使用Collections装饰的线程安全集合，如：Collections.synchronizedCollection、Collections.synchronizedList、Collections.synchronizedMap、Collections.synchronizedSet 等；
>  *  java.util.concurrent.\* ；

## java.util.concurrent.\* ##

jdk 5 引入并发包 java.util.concurrent.\* （简称：juc），juc 下的线程安全集合类，可发现它们是有规律的，里面包含三类关键词：Blocking、CopyOnWrite、Concurrent，如下：

>  *  CopyOnWrite 开头的集合，采用了“写入时拷贝”的思想来提高并发度
>  *  Concurrent 开头的集合，支持并发（线程安全）
>  *  Blocking 开头的集合，支持阻塞操作
> 
> 基于 lock-free，在常见的多线程访问场景，一般可以提供较高吞吐量；
> 
> 往往提供 了较低的遍历一致性（弱一致性），如：当利用迭代器遍历时，如果容器发生修改，迭代器仍然可以搜索进行遍历；
> 
> 弱一致性的另外一个体是，size等操作准确性是有限的，未必是100%准确；
> 
> 与此同时，读取的性能具有一定的不确定性；
> 
> 与弱一致性对应的，就是同步容器常见的行为 “fail-fast”，也就是检测到容器在遍历过程中发生了修改，则抛出ConcurrentModificationException，不再继续遍历

## CopyOnWriteArrayList ##

CopyOnWriteArrayList 底层实现采用拷贝写入的思想，增删改操作会将底层数组拷贝一份，更改操作在新数组上执行，这时不影响其他线程的并发读，读写分离。

> 过程介绍：
> 
>  *  CopyOnWriteArrayList 支持多线程并发读取 (如：get, 遍历) ，只支持单线程写入 (如：add, remove)
>  *  当有修改操作发生时，会对原有的数组进行拷贝，拷贝出一个新的数组，修改操作在新的数组上发生，修改时加锁。
>  *  原有数组的查询操作不需要加锁保护，当修改线程执行完毕，再用新的数组替换原有数组。
>  *  把读写操作分离开，读不加锁，写加锁，用空间换取读不加锁
>  *  适合读多写少的场景

## ConcurrentHashMap ##

Hashtable 是锁住了整个map集合，而 ConcurrentHashMap，它只会锁住map集合中的一个桶，根据桶的多少，可以进一步提高并发度，只要读写操作落在不同的桶里，操作就可以并行执行

> **1.7 以前** 
> 
> 采用的是分段锁，过程如下：
> 
>  *  初始化时（不是懒惰初始化），会创建所有 segment 数组的元素，而且 segmen t数组不能扩容（默认大小为16（并行度）），占用内存多
>  *  put 操作会锁住 key 对应的 segment，元素放入 HashEntry 的数组+链表结构中，元素放入链表头
>  *  get 操作无锁，仅需保证可见性，扩容过程中，get 先发生从旧表中读取，get 发生后就从新表中读取
>  *  扩容会加锁，它发生在 put 方法内，因此要提前加锁
>  *  计算个数（size）前，先不加锁多次计算，前后两次结果一样，认为个数正确，计算超过三次将所有 segment 锁住，重新计算个数返回
>  *  数据结构 数组 segment + 数组 HashEntry + 链表 HashEntry，从图中首先是一个 segment 数组，每个 segment 的元素又是一个HashEntry 数组，Node 数组中又存放了链表
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70][]
> 
> **1.8 又做了修改**
> 
>  *  初始化数组时，使用 cas 来保证并发安全性，懒惰初始化
>  *  当容量小于64首先尝试扩容，当超过这个容量并且链表大于或等于8，会将链表树化，树化过程中会锁住链表头
>  *  put 操作会锁住链表头，新加的元素放入链表尾部
>  *  get 操作不需要加锁，仅需要用cas保证元素的可见性
>  *  扩容 以链表为单位扩容，当扩容时有多个线程来同时访问，这些线程会协助扩容
>  *  数据结构 数组 Node+链表 Node /红黑树 TreeNode
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 1][]

## ConcurrentSkipListMap ##

ConcurrentSkipListMap 类似于之前 LinkedHashMap ，都可以保持元素遍历的顺序和放入的顺序是一致的。

> 它们的不同之处：
> 
>  *  LinkedHashMap 非线程安全
>  *  ConcurrentSkipListMap 线程安全
>  *  LinkedHashMap 数据结构 数组+链表
>  *  ConcurrentSkipListMap 数据结构 跳跃表
> 
> 跳跃表结构如下，白色链表部分起到了快速定位底层链表的效果：
> 
> ![20190306083314647.png][]
> 
>  **查询操作**
> 
> 比如要查询 7，查找流程如下：
> 
>     第 4 层 1 --> NIL （有大于7的吗？no --> 向下）
>     第 3 层 1 --> 4  --> 6 --> NIL（有大于7的吗？no --> 向下）
>     第 2 层                     6 --> 9 （有大于7的吗？yes --> 向下）
>     第 1 层                     6 --> 7 （找到）
> 
> **插入操作**
> 
> 插入元素动态图如下：
> 
> ![20190306083422402.gif][]

## BlockingQueue 阻塞队列 ##

队列,它是先进先出的，经常用来实现生产消费模式，来解耦生产者、消费者线程。

其类如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 2][]

**阻塞队列演示**

import java.util.concurrent.BlockingQueue;
    import java.util.concurrent.LinkedBlockingDeque;
    
    public class TestBlockingQueue {
    
        public static void main(String[] args) throws InterruptedException {
            //创建队列，指定队列容量为5
            BlockingQueue<String> queue = new LinkedBlockingDeque<>(5);
    
            // 存放元素, 如果集合满了,put 方法会阻塞，也就是数据个数超过容量，队列就不能在装下数据，除非把队列里的元素出列
            queue.put("a");
            queue.put("b");
            queue.put("c");
            queue.put("d");
            queue.put("e");
    
            // 获取元素, 如果集合空了, take 方法会阻塞，没有数据可以拿，也就阻塞了
            System.out.println(queue.take());
            System.out.println(queue.take());
            System.out.println(queue.take());
            System.out.println(queue.take());
            System.out.println(queue.take());
            System.out.println(queue.take());
        }
    }

结果

![20190306191606349.PNG][]

结果中队列一直在等待取到第六个数据，队列中没有第六个数据，所以控制台一直是开启状态，没有结束编译。

## 线程安全控制的三个级别 ##

>  *  JVM 级别：通常以 cas 指令形式，是一种级别低的、细粒度的技术
>  *  低级使用程序类：锁定和原子类，使用 cas 作为并发原语，ReentrantLock 类提供与 synchronized 原语相同的锁定和内存语义
>  *  高级使用程序类：信号、互斥、屏障、交换程序等

## cas ##

cas 它是乐观锁(无锁并发)， 不断重试直到成功，体现的是乐观的精神，而 synchronized 它是悲观锁 , 同一时刻，只能有一个线程访问 synchronized 代码块的内容。

乐观锁应用场景：

>  *  原子操作类 例如 AtomicInteger,AtomicBoolean... 它们内部用的都是 cas 的无锁并发
>  *  适用于并发量较小，多cpu情况

## volatile 关键字 ##

配合 cas 编程时，共享变量的声明上必须用 volatile ，因为线程的工作区是独立的，当线程读取到主存的数据时，会缓存一份在线程里，对数据的修改在工作区内，修改完数据后新值还没有来得及更改到主存中，这时如果有人访问数据，访问的还是原来的值，因此要想读取主存中最新的结果，就必须加上 volatile 。（详情请见：[https://blog.csdn.net/grey\_mouse/article/details/84193844][https_blog.csdn.net_grey_mouse_article_details_84193844]）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70]: /images/20220312/bf68151a39d04e1ab29e27a3393f38a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 1]: /images/20220312/f4200b9b4dc64dca8fe519ce8f33d71d.png
[20190306083314647.png]: /images/20220312/9b49732736a644eb889e4ca3bdb2e709.png
[20190306083422402.gif]: /images/20220312/f125d0ef879746ea8436c7c439346233.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dyZXlfbW91c2U_size_16_color_FFFFFF_t_70 2]: /images/20220312/f728cc41ca7245549d6514dfe08316bd.png
[20190306191606349.PNG]: /images/20220312/9470e1166f1d46aeadc09795ce736de6.png
[https_blog.csdn.net_grey_mouse_article_details_84193844]: https://blog.csdn.net/grey_mouse/article/details/84193844