并发容器

Java 5.0提供了多种并发容器类来改进同步容器的性能。同步容器将所有对容器状态的访问都串行化，以实现它们的线程安全性。这种方法的代价是严重降低并发性，当多个线程竞争容器的锁时，吞吐量将严重减低。

另一方面，并发容器是针对多个线程并发访问设计的。在Java 5.0 中增加了Concurrent-HashMap,用来替代同步且基于散列的Map,以及CopyOnWriteArrayList,用于在遍历操作为主要操作的情况下代替同步的List。在新的ConcurrentMap接口中增加了对一些常见复合操作的支持，例如“若没有则添加”、替换以及有条件删除等。

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

Java 5.0增加了两种新的容器类型:Queue和BlockingQueue。Queue 用来临时保存一组等待处理的元素。它提供了几种实现，包括：ConcurrentLinkedQueue，这是一个传统的先进先出队列，以及PriorityQueue，这是一个(非并发的)优先队列。Queue 上的操作不会阻塞，如果队列为空，那么获取元素的操作将返回空值。虽然可以用List 来模拟Queue的行为——事实上,正是通过LinkedList来实现Queue的,但还需要一个Queue 的类,因为它能去掉List的随机访问需求，从而实现更高效的并发。

BlockingQueue 扩展了Queue，增加了可阻塞的插入和获取等操作。如果队列为空，那么获取元素的操作将一直阻塞，直到队列中出现一个可用的元素。如果队列已满(对于有界队列来说)，那么插入元素的操作将一直阻塞，直到队列中出现可用的空间。在“生产者-消费者”这种设计模式中，阻塞队列是非常有用的，

正如ConcurrentHashMap用于代替基于散列的同步Map, Java 6 也引入了Concurrent-SkipListMap 和ConcurrentSkipListSet,分别作为同步的SortedMap和SortedSet的并发替代品(例如用synchronizedMap包装的TreeMap或TreeSet)。

ConcurrentHashMap

同步容器类在执行每个操作期间都持有一个锁。在一些操作中，例如HashMap. get 或List.contains，可能包含大量的工作：当遍历散列桶或链表来查找某个特定的对象时，必须在许多元素上调用equals(而equals 本身还包含一定的计算量)。在基于散列的容器中，如果hashCode 不能很均匀地分布散列值，那么容器中的元素就不会均匀地分布在整个容器中。某些情况下，某个糟糕的散列函数还会把一个散列表变成线性链表。当遍历很长的链表并且在某些或者全部元素上调用equals方法时，会花费很长的时间，而其他线程在这段时间内都不能访问该容器。

与HashMap一样,ConcurrentHashMap也是一个基于散列的Map,但它使用了一种完全不同的加锁策略来提供更高的并发性和伸缩性。ConcurrentHashMap并不是将每个方法都在同一个锁上同步并使得每次只能有一个线程访问容器，而是使用一种粒度更细的加锁机制来实现更大程度的共享，这种机制称为分段锁。在这种机制中，任意数量的读取线程可以并发地访问Map，执行读取操作的线程和执行写入操作的线程可以并发地访问Map,并且一定数量的写入线程可以并发地修改Map。ConcurrentHashMap带来的结果是,在并发访问环境下将实现更高的吞吐量，而在单线程环境中只损失非常小的性能。

ConcurrentHashMap与其他并发容器一起增强了同步容器类：它们提供的迭代器不会抛出ConcurrentModificationException,因此不需要在迭代过程中对容器加锁。ConcurrentHashMap 返回的迭代器具有弱一致性(Weakly Consistent)，而并非“及时失败”。弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有的元素，并可以(但是不保证)在迭代器被构造后将修改操作反映给容器。

尽管有这些改进，但仍然有一些需要权衡的因素。对于一些需要在整个Map上进行计算的方法，例如size 和isEmpty，这些方法的语义被略微减弱了以反映容器的并发特性。由于size 返回的结果在计算时可能已经过期了，它实际上只是一个估计值，因此允许size 返回一个近似值而不是一个精确值。虽然这看上去有些令人不安，但事实上size 和isEmpty 这样的方法在并

发环境下的用处很小，因为它们的返回值总在不断变化。因此，这些操作的需求被弱化了，以换取对其他更重要操作的性能优化,包括get、put、containsKey和remove等。

在ConcurrentHashMap 中没有实现对Map加锁以提供独占访问。在Hashtable 和synchronized-Map 中，获得Map的锁能防止其他线程访问这个Map。在一些不常见的情况中需要这种功能，例如通过原子方式添加一些映射，或者对Map 迭代若干次并在此期间保持元素顺序相同。然而，总体来说这种权衡还是合理的，因为并发容器的内容会持续变化。

与Hashtable 和synchronizedMap相比,ConcurrentHashMap有着更多的优势以及更少的劣势,因此在大多数情况下，用ConcurrentHashMap来代替同步Map能进一步提高代码的可伸缩性。只有当应用程序需要加锁Map以进行独占访问时，才应该放弃使用ConcurrentHashMap。

  额外的原子Map 操作

由于ConcurrentHashMap不能被加锁来执行独占访问，因此我们无法使用客户端加锁来创建新的原子操作，例如4.4.1节中对Vector 增加原子操作“若没有则添加”。但是，一些常见的复合操作，例如“若没有则添加”、“若相等则移除(Remove-If-Equal)”和“若相等则替换(Replace-If-Equal)”等,都已经实现为原子操作并且在ConcurrentMap的接口中声明,如程序清单5-7所示。如果你需要在现有的同步Map 中添加这样的功能，那么很可能就意味着应该考虑使用ConcurrentMap了。

public interface ConcurrentMap<K,V>extends Map<K,V>{

//仅当K没有相应的映射值时才插入

V putIfAbsent (K key,v value);

//仅当K被映射到V时才移除

boolean remove(K key,V value);

//仅当K被映射到oldValue 时才替换为newValue

boolean replace(K key,v oldValue,V newValue);

//仅当K被映射到某个值时才替换为newValue

V replace(K key,V newValue);

}

CopyOnWriteArrayList用于替代同步List,在某些情况下它提供了更好的并发性能,并且在迭代期间不需要对容器进行加锁或复制。(类似地，CopyOnWriteArraySet的作用是替代同步Set。)

“写入时复制(Copy-On-Write)”容器的线程安全性在于，只要正确地发布一个事实不可        

或者需要依赖于同步Map 带来的一些其他作用。

变的对象，那么在访问该对象时就不再需要进一步的同步。在每次修改时，都会创建并重新发布一个新的容器副本，从而实现可变性。“写入时复制”容器的迭代器保留一个指向底层基础数组的引用，这个数组当前位于迭代器的起始位置，由于它不会被修改，因此在对其进行同步时只需确保数组内容的可见性。因此，多个线程可以同时对这个容器进行迭代，而不会彼此干扰或者与修改容器的线程相互干扰。“写入时复制”容器返回的迭代器不会抛出ConcurrentModificationException,并且返回的元素与迭代器创建时的元素完全一致,而不必考虑之后修改操作所带来的影响。

显然，每当修改容器时都会复制底层数组，这需要一定的开销，特别是当容器的规模较大时。仅当迭代操作远远多于修改操作时，才应该使用“写入时复制”容器。这个准则很好地描述了许多事件通知系统：在分发通知时需要迭代已注册监听器链表，并调用每一个监听器，在大多数情况下，注册和注销事件监听器的操作远少于接收事件通知的操作。