Java 的基础容器主要有 List、Set、Queue、Map 四个大类，但是大家熟知的基础容器类 ArrayList、LinkedList、HashMap 都是非线程安全的，在多个线程场景中使用这些基础容器会出现线程安全问题。为了解决线程安全问题，Java 提供了一系列的同步容器。这些容器基本分为两大类：基于 synchronized 实现和 JUC 提供的基于 CAS 操作实现的。

基于 synchronized 的同步容器类

Java 同步容器类通过 Synchronized 来实现同步的容器，比如 Vector、HashTable 以及 SynchronizedList 等容器。线程安全的同步容器类主要有 Vector、Stack、HashTable 等。另外，Java 还提供了一组包装方法，将一个普通的基础容器包装成一个线程安全的同步容器。例如通过 Collections.synchronized 包装方法能将一个普通的 SortedSet 容器包装成一个线程安全的 SortedSet 同步容器。

HashTable

  1. public class Hashtable<K,V> extends Dictionary<K,V>
  2.     implements Map<K,V>, Cloneable, java.io.Serializable {
  4.     public synchronized V put(K key, V value) { }
  6.     public synchronized V get(Object key) { }
  8.     public synchronized boolean contains(Object value) { }
  10.     public synchronized void clear() { }
  12. }

可以看到，对于这类容器类来说，保证线程安全的做法就是将每个方法加上 synchronized 关键字。

通过 synchronizedSortedSet 静态方法包装出一个同步容器

  1. public class SynchronizedSortedSet_Test {
  3.     public static void main(String[] args) throws InterruptedException {
  5.         TreeSet<String> elementSet = new TreeSet<>();
  7.         // 将 elementSet 包装成为一个同步容器
  8.         SortedSet<String> sortSet = Collections.synchronizedSortedSet(elementSet);
  10.         CountDownLatch countDownLatch = new CountDownLatch(50);
  11.         for (int i = 0; i < 50; i++) {
  12.             final int finalIndex = i;
  13.             new Thread(() -> {
  14.                 if (finalIndex != 0 && (finalIndex % 15 == 0)) {
  15.                     // 代码1
  16.                     sortSet.forEach(s -> System.out.println(finalIndex + "=========: " + s));
  17.                 } else {
  18.                     // 代码2
  19.                     sortSet.add("_" + finalIndex + "_");
  20.                 }
  21.                 countDownLatch.countDown();
  22.             }).start();
  23.         }
  24.         countDownLatch.await();
  25.         System.out.println("------------------------------");
  26.         System.out.println(elementSet);
  27.     }
  28. }

若将代码1和代码2处的 sortSet 替换为 elementSet，则抛出 java.util.ConcurrentModificationException。可见，java.util.Collections.synchronizedSortedSet() 静态方法包装出是容器是线程安全的。

java.util.Collections 提供的同步包装方法

  1. public static <T> Collection<T> synchronizedCollection(Collection<T> c)
  2.     将基础Collection容器包装成线程安全的Collection容器
  4. public static <T> List<T> synchronizedList(List<T> list)
  5.     将基础List包装成线程安全的列表容器
  7. public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
  8.     将基础Map容器包装成线程安全的容器
  10. public static <K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m)
  13. public static <T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s)
  16. public static <T> Set<T> synchronizedSet(Set<T> s)
  19. public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
  22. public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)

小结

基于 synchronized 关键字实现的同步容器类都是在方法上添加 synchronized 关键字来实现线程同步的。synchronized 在线程没有发生争用的场景下处于偏向锁的状态，其性能是非常高的。但是，一旦发生了线程争用，synchronized 会由偏向锁膨胀成重量级锁，在抢占和释放时发生 CPU 内核态与用户态切换，所以削弱了并发性，降低了吞吐量，而且会严重影响性能。

JUC 高并发容器类

JUC 高并发容器是基于非阻塞算法（或者无锁编程算法）实现的容器类，无锁编程算法主要通过 CAS（Compare And Swap）+Volatile 组合实现，通过 CAS 保障操作的原子性，通过 volatile 保障变量内存的可见性。无锁编程算法的主要优点如下：

  1. 开销较小：不需要在内核态和用户态之间切换进程
  2. 读写不互斥：只有写操作需要使用基于CAS机制的乐观锁，读读操作之间可以不用互斥

List

UC 包中的高并发 List 主要有 CopyOnWriteArrayList，对应的基础容器为 ArrayList。

CopyOnWriteArrayList 相当于线程安全的 ArrayList，它实现了List接口。在读多写少的场景中，其性能远远高于 ArrayList 的同步包装容器。

Set

JUC 包中的 Set主要有 CopyOnWriteArraySet 和 ConcurrentSkipListSet。

  • CopyOnWriteArraySet 继承自 AbstractSet 类，对应的基础容器为 HashSet。其内部组合了一个 CopyOnWriteArrayList 对象，它的核心操作是基于 CopyOnWriteArrayList 实现的
  • ConcurrentSkipListSet 是线程安全的有序集合，对应的基础容器为 TreeSet。它继承自 AbstractSet，并实现了 NavigableSet 接口。ConcurrentSkipListSet 是通过 ConcurrentSkipListMap 实现的。

Map

JUC 包中 Map 主要有 ConcurrentHashMap 和 ConcurrentSkipListMap。

  • ConcurrentHashMap 对应的基础容器为 HashMap。JDK 6 中的 ConcurrentHashMap 采用一种更加细粒度的“分段锁”加锁机制，JDK 8 中采用 CAS 无锁算法
  • ConcurrentSkipListMap 对应的基础容器为 TreeMap。其内部的 Skip List（跳表）结构是一种可以代替平衡树的数据结构，默认是按照 Key 值升序的

Queue

JUC 包中的 Queue 的实现类包括三类：单向队列、双向队列和阻塞队列。

  • ConcurrentLinkedQueue 是基于列表实现的单向队列，按照 FIFO（先进先出）原则对元素进行排序。新元素从队列尾部插入，而获取队列元素则需要从队列头部获取
  • ConcurrentLinkedDeque 是基于链表的双向队列，但是该队列不允许 null 元素。作为双向队列， ConcurrentLinkedDeque 可以当作“栈”来使用，并且高效地支持并发环境
  • ArrayBlockingQueue 是基于数组实现的可阻塞的 FIFO 队列
  • LinkedBlockingQueue 是基于链表实现的可阻塞的 FIFO 队列
  • PriorityBlockingQueue 是按优先级排序的队列
  • DelayQueue 是按照元素的 Delay 时间进行排序的队列
  • SynchronousQueue 是无缓冲等待队列