高并发下用的容器类

参考博客：https://www.cnblogs.com/daoqidelv/p/6753162.html

java cocurrent包提供了很多并发容器，在提供并发控制的前提下，通过优化，提升性能

为什么JUC需要提供并发容器？

1. java.util包中的大部分容器都是非线程安全的，若要在多线程中使用容器，你可以使用Collections提供的包装函数：synchronizedXXX，将普通容器变成线程安全的容器。但该方法仅仅是简单地给容器使用同步，效率很低。因此并发大师Doug Lea提供了java.util.concurrent包，提供高效的并发容器。并且为了保持与普通的容器的接口一致性，仍然使用util包的接口，从而易于使用、易于理解。

2.使用工具类Collections将非线程安全容器包装成线程安全容器。以下代码是Collections.synchronizedMap(Map<K,V> m)将原始Map包装为线程安全的SynchronizedMap，但是实际上最终操作时，仍然是在被包装的原始m上进行，只是SynchronizedMap的所有方法都加上了synchronized锁控制。

为了提供高效地并发容器，java 5在java.util.cocurrent包中引入了并发容器。

JUC并发容器

本节对juc常用的几个并发容器进行代码分析，重点看下这些容器是如何高效地实现并发控制的。在进行具体的并发容器介绍之前，我们提前搞清楚CAS理论是什么东西。因为在juc并发容器的很多地方都使用到了CAS，他比加锁处理更加高效

CAS

CAS是一种无锁的非阻塞算法，全称为：Compare-and-swap（比较并交换），大致思路是：先比较目标对象现值是否和旧值一致，如果一致，则更新对象为新值；如果不一致，则表明对象已经被其他线程修改，直接返回。算法实现的伪码如下：

function cas(p : pointer to int, old : int, new : int) returns bool {
    if *p ≠ old {
        return false
    }
    *p ← new
    return true
}

List和Set

JUC包中List接口的实现类：CopyOnWriteArrayList

CopyOnWriteArrayList是线程安全的ArrayList

CopyOnWriteArrayList提供高效地读取操作，使用在读多写少的场景。CopyOnWriteArrayList读取操作不用加锁，且是安全的；写操作时，先copy一份原有数据数组，再对复制数据进行写入操作，最后将复制数据替换原有数据，从而保证写操作不影响读操作。

// 添加集合中不存在的元素
int addAllAbsent(Collection<? extends E> c)
// 该元素若不存在则添加
boolean addIfAbsent(E e)

JUC包中Set接口的实现类：CopyOnWriteArraySet、ConcurrentSkipListSet

CopyOnWriteArraySet是线程安全的Set，它内部包含了一个CopyOnWriteArrayList，因此本质上是由CopyOnWriteArrayList实现的

ConcurrentSkipListSet相当于线程安全的TreeSet。它是有序的Set。它由ConcurrentSkipListMap实现。

Map

ConcurrentHashMap：线程安全的HashMap。采用分段锁实现高效并发

ConcurrentSkipListMap：线程安全的有序Map。使用跳表实现高效并发

Queue

ConcurrentLinkedQueue：线程安全的无界队列。底层采用单链表。支持FIFO

ConcurrentLinkedQueue使用链表作为数据结构，它采用无锁操作，可以任务是高并发环境下性能最好的队列。

ConcurrentLinkedQueue是非阻塞线程安全队列，无界，故不太适合做生产者消费者模式，而LinkedBlockingQueue是阻塞线程安全队列，可以做到有界，通常用于生产者消费者模式。

ConcurrentLinkedDeque：线程安全的无界双端队列。底层采用双向链表。支持FIFO和FILO

ArrayBlockingQueue：数组实现的阻塞队列

// 在队尾添加指定元素，若队已满则等待指定时间
boolean offer(E e, long timeout, TimeUnit unit)
// 获取并删除队首元素，若队为空则阻塞等待
E take()
// 添加指定元素，若队已满则一直等待
void put(E e)
// 获取队首元素，若队为空，则等待指定时间
E poll(long timeout, TimeUnit unit)

LinkedBlockingQueue：链表实现的阻塞队列

LinkedBlockingDeque：双向链表实现的双端阻塞队列