并发容器的实现

容器

实现

使用场景

CopyOnWriteArrayList

内部是一个数组，这个数组是以原子方式被整体更新的。

写：每次修改操作，都会新建一个数组，复制原数组的内容到新数组，在新数组上进行需要的修改，然后以原子方式设置内部的数组引用，这就是写时复制。多个线程不能同时写，每个写操作都需要先获取锁。CopyOnWriteArrayList内部使用ReentrantLock。

读：先拿到当前引用的数组，然后直接访问该数组。在读的过程中，可能内部的数组引用已经被修改了，但不会影响读操作，它依旧访问原数组内容。读不需要锁，可以并行，读和写也可以并行。

CopyOnWriteArrayList不适用于数组很大且修改频繁的场景。它是以优化读操作为目标的，读不需要同步，性能很高，但在优化读的同时牺牲了写的性能。

对于绝大部分访问都是读，且有大量并发线程要求读，只有个别线程进行写，且只是偶尔写的场合，写时复制就是一种很好的解决方案。

CopyOnWriteArraySet

CopyOnWriteArraySet内部是通过CopyOnWriteArrayList实现的。

其成员声明为：private final CopyOnWriteArrayList<E> al;

性能比较低，不适用于元素个数特别多的集合。如果元素个数比较多，可以考虑ConcurrentHashMap或ConcurrentSkipListSet这两个类。

ConcurrentHashMap

特性

• 并发安全；
• 直接支持一些原子复合操作；
• 支持高并发，读操作完全并行，写操作支持一定程度的并行；
• 迭代不用加锁，不会抛出ConcurrentModificationException；
• 弱一致性。

实现

• 分段锁：将数据分为多个段，而每个段有一个独立的锁，每一个段相当于一个独立的哈希表，分段的依据也是哈希值，无论是保存键值对还是根据键查找，都先根据键的哈希值映射到段，再在段对应的哈希表上进行操作。采用分段锁，可以大大提高并发度，多个段之间可以并行读写。
• 读不需要锁。在对每个段的数据进行读写时，ConcurrentHashMap也不是简单地使用锁进行同步，内部使用了CAS。对于写操作，需要获取锁，不能并行，但是读操作可以，多个读可以并行，写的同时也可以读。

迭代器

• 在迭代器创建后，在迭代过程中，如果另一个线程对容器进行了修改，迭代会继续，不会抛出ConcurrentModificationException。

弱一致性

• ConcurrentHashMap的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。

元素多、较多写线程，对性能要求较高的场景。

Java中没有并发版的HashSet，但可以通过Collections.newSetFromMap方法基于ConcurrentHashMap构建一个。

ConcurrentSkipListMap

ConcurrentSkipListMap是基于SkipList实现的。并发版本为什么采用跳表而不是树呢？因为跳表更易于实现高效并发算法。

特性

• 没有使用锁，所有操作都是无阻塞的，所有操作都可以并行，包括写，多线程可以同时写。
• 与ConcurrentHashMap类似，迭代器不会抛出ConcurrentModificationException，是弱一致的，迭代可能反映最新修改也可能不反映，一些方法如putAll、clear不是原子的。
• 与ConcurrentHashMap类似，同样实现了ConcurrentMap接口，支持一些原子复合操作。
• 与TreeMap一样，可排序，默认按键的自然顺序，也可以传递比较器自定义排序，实现了SortedMap和NavigableMap接口。

注意：

ConcurrentSkipListMap的size方法与大多数容器实现不同，这个方法不是常量操作，它需要遍历所有元素，复杂度为O(N)，而且遍历结束后，元素个数可能已经变了。一般而言，在并发应用中，这个方法用处不大。

ConcurrentSkipListMap和ConcurrentSkipListSet基于跳表实现，有序，无锁非阻塞，完全并行，主要操作复杂度为O(log(N))。

ConcurrentSkipListSet

TreeSet是基于TreeMap实现的，与此类似，ConcurrentSkipListSet也是基于ConcurrentSkipListMap实现的。