线程安全的集合

1 同步容器类

同步容器类实现线程安全的方式是： 将他们的状态封装起来,并对每个公有方法都进行同步，使得每次只有一个线程能访问容器的状态。

1.1 同步容器类的问题

• 同步容器类都是线程安全的，但在某些情况下可能需要额外的客户端加锁来保护复合操作。
• 由于同步容器类要遵守同步策略(支持客户端加锁)，因此可能会创建一些新的操作，只要我们知道应该使用哪一个锁，那么这些新操作就与容器的其他操作一样是原子操作。

1.2 迭代器与 ConcurrentModificationException

• 及时失败(fail-fast)：在设计同步容器类的迭代器时并没有考虑到并发修改的问题，当发现容器在迭代过程中被修改时（通过计数器），就会抛出ConcurrentModificationException异常
• 避免出现ConcurrentModificationException的方法:
  1. 迭代过程持有容器的锁
  2. "克隆"容器，并在副本上迭代(克隆过程仍需要对容器加锁)

1.3 隐藏迭代器

封装对象的同步机制(同步代码)有助于确保实施同步策略(eg:用synchronizedSet包装HashSet)

• 标准容器的toString方法将隐式迭代容器，并在每个元素上调用toString来生成容器内容的格式化表示
• 容器的containsAll，hashCode和equals等方法也会间接地执行迭代操作

2 Concurrent 集合

• 同步容器将所有对容器的状态访问都串行化，严重降低并发性，当多个线程访问锁时，吞吐量将严重降低
• 同步容器是synchronizedXXX这类，仅仅给容器提供同步，效率很低
• 并发容器是针对多个线程并发访问设计的，ConcurrentMap，CopyOnWriteList(遍历操作较多的情况下代理同步的List)，ConcurrentQueue(传统先进先出队列)，BlockingQueue(扩展Queue,提供可阻塞操作)，BlockingDeque(可阻塞双端队列)

用并发容器来代替同步容器，可以极大地提高伸缩性并降低风险

java.util.concurrent包中 ConcurrentHashMap、ConcurrentSkipListMap、ConcurrentSkipListSet 和 ConcurrentLinkedQueue。这些集合使用复杂的算法，通过允许并发地访问数据结构的不同部分来使竞争极小化。

集合返回弱一致性的迭代器，这意味着迭代器不一定能反映出它们被构造之后的所有的修改，但是，它们不会将同一个值返回两次，也不会抛出 CocurrentModificationException 异常。

2.1 ConcurrentHashMap

ConcurrentHashSet 是其适配器。

• ConcurrentHashMap使用分段锁(Lock Strip)来实现更大程度的共享，写锁读不锁
• ConcurrentHashMap带来的结果是，在并发访问的环境下实现更高的吞吐量，而在单线程环境中值损失非常小的性能
• ConcurrentHashMap返回的迭代器具有弱一致性(Weakly Consistent)
• 用ConcurrentHashMap代替同步Map能进一步提高代码的可伸缩性，只有当应用程序需要加锁Map进行独占访问时，才应放弃使用ConcurrentHashMap

1）原子更新

1.8为 ConcurrentHashMap 提供更方便完成原子更新的方法。

• compute：提供一个键值和一个计算新值的函数
• computeIfPresent
• computeIfAbsent

2）批操作

1.8提供为 ConcurrentHashMap 提供一个批操作，即使有其它线程正在处理映射，这些操作也能安全执行，得到一个近似值。 有三种：搜索（search），规约（reduce），foreach

3 CopyOnWriteArrayList

CopyOnWrite 容器即写时复制的容器。写元素时先复制一个新容器，往新容器里写，然后将原容器引用指向新容器。

• CopyOnWriteArrayList用于替代同步List，在某些情况下它提供了更好的并发性能，并且在迭代期间不需要对容器进行加锁或复制
• 在每次修改时，它都会创建并重新发布一个新的容器副本，从而实现可变性
• 仅当迭代操作远远多于修改操作时，才应该使用"写入时复制"容器
• CopyOnWrite 容器可无锁并发读，只保证数据的最终一致性。
• CopyOnWriteArrayList 和 CopyOnWriteArraySet 是 CopyOnWrite 容器，读多写少时一般用 CopyOnWriteArrayList 类替代 ArrayList 。

4 并行数组算法

1.8中 Arrays 类提供了大量并行化操作。

• Arrays.parallelSort 方法：可以对基本类型或对象数组排序
• parallelSetAll 方法：用由一个函数计算得到的值填充一个数组
• parallelPrefix 方法：会用对应一个给定结合操作的前缀的累加结果替换各个数组元素

5 较早的线程安全集合

Java SE 1.2中，Vector 和 Hashtable 被弃用了。

任何集合类通过使用同步包装器变成线程安全的：

List<E> synchArrayList = Collections.synchronizedList(new ArrayList<E>());
Map<K, V> synchHashMap = Collections.synchronizedMap(new HashMap<K, V>());