Java并发容器大合集

• JUC包中List接口的实现类：CopyOnWriteArrayList
  • CopyOnWriteArrayList是线程安全的ArrayList
    
• JUC包中Set接口的实现类：CopyOnWriteArraySet、ConcurrentSkipListSet
  • CopyOnWriteArraySet是线程安全的Set，它内部包含了一个CopyOnWriteArrayList，因此本质上是由CopyOnWriteArrayList实现的。
    
  • ConcurrentSkipListSet相当于线程安全的TreeSet。它是有序的Set。它由ConcurrentSkipListMap实现。
    

• ConcurrentHashMap：线程安全的HashMap。采用分段锁实现高效并发。
• ConcurrentSkipListMap：线程安全的有序Map。使用跳表实现高效并发。

• ConcurrentLinkedQueue：线程安全的无界队列。底层采用单链表。支持FIFO。
• ConcurrentLinkedDeque：线程安全的无界双端队列。底层采用双向链表。支持FIFO和FILO。
• ArrayBlockingQueue：数组实现的阻塞队列。
• LinkedBlockingQueue：链表实现的阻塞队列。
• LinkedBlockingDeque：双向链表实现的双端阻塞队列。

• PS：CopyOnWriteArraySet有CopyOnWriteArrayList实现。

• 适用于读操作远远多于写操作，并且数据量较小的情况。
• 修改容器的代价是昂贵的，因此建议批量增加addAll、批量删除removeAll。

1. 使用volatile修饰数组引用：确保数组引用的内存可见性。
2. 对容器修改操作进行同步：从而确保同一时刻只能有一条线程修改容器（因为修改容器都会产生一个新的容器，增加同步可避免同一时刻复制生成多个容器，从而无法保证数组数据的一致性）
3. 修改时复制容器：确保所有修改操作都作用在新数组上，原本的数组在创建过后就用不变化，从而其他线程可以放心地读。

// 添加集合中不存在的元素

int addAllAbsent(Collection<? extends E> c)

// 该元素若不存在则添加

boolean addIfAbsent(E e)

• CopyOnWriteArrayList拥有内部类：COWIterator，它是ListIterator的子类。
  
• 当调用iterator函数时返回的是COWIterator对象。
  
• COWIterator不允许修改容器，你若调用则会抛出UnsupportedOperationException。
  

• 数据一致性问题
  • 由于迭代的是容器当前的快照，因此在迭代过程中容器发生的修改并不能实时被当前正在迭代的线程感知。
• 内存占用问题
  • 由于修改容器都会复制数组，从而当数组超大时修改容器效率很低。
  • PS：因此写时复制容器适合存储小容量数据。

• ConcurrentHashMap内部包含了Segment数组，而每个Segment又继承自ReentrantLock，因此它是一把可重入的锁。
  
• Segment内部拥有一个HashEntry数组，它就是一张哈希表。HashEntry是单链表的一个节点，HashEntry数组存储单链表的表头节点。

V putIfAbsent(K key, V value)

• 它是一个有序的Map，相当于TreeMap。
• TreeMap采用红黑树实现排序，而ConcurrentHashMap采用跳表实现有序。

• 它是一个有序的、线程安全的Set，相当于线程安全的TreeSet。
• 它内部拥有ConcurrentSkipListMap实例，本质上就是一个ConcurrentSkipListMap，只不过仅使用了Map中的key。

• ArrayBlockingQueue是一个 数组实现的 线程安全的 有限 阻塞队列。

• ArrayBlockingQueue继承自AbstractQueue，并实现了BlockingQueue接口。
• ArrayBlockingQueue内部由Object数组存储元素，构造时必须要指定队列容量。
• ArrayBlockingQueue由ReentrantLock实现队列的互斥访问，并由notEmpty、notFull这两个Condition分别实现队空、队满的阻塞。
• ReentrantLock分为公平锁和非公平锁，可以在构造ArrayBlockingQueue时指定。默认为非公平锁。
  

// 在队尾添加指定元素，若队已满则等待指定时间

boolean offer(E e, long timeout, TimeUnit unit)

// 获取并删除队首元素，若队为空则阻塞等待

E take()

// 添加指定元素，若队已满则一直等待

void put(E e)

// 获取队首元素，若队为空，则等待指定时间

E poll(long timeout, TimeUnit unit)

• 队满阻塞：当添加元素时，若队满，则调用notFull.await()阻塞当前线程；当移除一个元素时调用notFull.signal()唤醒在notFull上等待的线程。
• 队空阻塞：当删除元素时，若队为空，则调用notEmpty.await()阻塞当前线程；当队首添加元素时，调用notEmpty.signal()唤醒在notEmpty上等待的线程。

• LinkedBlockingQueue是一个 单链表实现的、线程安全的、无限 阻塞队列。
  

• LinkedBlockingQueue继承自AbstractQueue，实现了BlockingQueue接口。
  
• LinkedBlockingQueue由单链表实现，因此是个无限队列。但为了方式无限膨胀，构造时可以加上容量加以限制。
  
• LinkedBlockingQueue分别采用读取锁和插入锁控制读取/删除 和 插入过程的并发访问，并采用notEmpty和notFull两个Condition实现队满队空的阻塞与唤醒。
  

• 队满阻塞：若要插入元素，首先需要获取putLock；在此基础上，若此时队满，则调用notFull.await()，阻塞当前线程；当移除一个元素后调用notFull.signal()唤醒在notFull上等待的线程；最后，当插入操作完成后释放putLock。
• 队空阻塞：若要删除/获取元素，首先要获取takeLock；在此基础上，若队为空，则调用notEmpty.await()，阻塞当前线程；当插入一个元素后调用notEmpty.signal()唤醒在notEmpty上等待的线程；最后，当删除操作完成后释放takeLock。

• 它是一个 由双向链表实现的、线程安全的、 双端 无限 阻塞队列。

• 它是一个由单链表实现的、线程安全的、无限 队列。

• 它仅仅继承了AbstractQueue，并未实现BlockingQueue接口，因此它不是阻塞队列，仅仅是个线程安全的普通队列。

• head、tail、next、item均使用volatile修饰，保证其内存可见性，并未使用锁，从而提高并发效率。
• PS：它究竟是怎样在不使用锁的情况下实现线程安全的？