5.1 同步容器类（Synchronized Collections）
同步容器类包括Vector和Hashtable、这些类实现线程安全的方式是：将它们的状态封装起来，并对每个公有方法都进行同步，使得每次只有一个线程能访问容器的状态。
List接口一共有三个实现类，分别是ArrayList、Vector和LinkedList。
ArrayList是最常用的List实现类，内部是通过数组实现的，它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一个线程能够写Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问ArrayList慢。
LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。
5.1.1 同步容器类的
同步容器类都是线程安全的，但在某些情况下需要额外的客户端加锁来保护符合操作。
常见的复合操作包括：迭代（反复访问元素，知道遍历容器中所有元素），跳转（根据指定顺序找到当前元素的下个元素）以及条件运算：例如“若没有则添加”。在同步容器类中，这些复合操作在没有客户端加锁的情况下仍然是线程安全的，但当其他线程并发地修改容器时，它们可能会表现出意料之外的行为。
Vector中定义的两个方法：getLast和deleteLast，它们都会执行“先检查再运行”操作，每个方法首先都获得数组的大小，然后通过结果来获取或删除最后一个元素
// 5-1 Vector上可能导致混乱结果的复合操作
public static Object getLast(Vector list) {
int lastIndex = list.size() - 1;
return list.get(lastIndex);
}
public static void deleteLast(Vector list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
}如果线程A在包含10个元素的Vector上调用removeLast，同时线程B调用getLast，这个时候就会出现下面的情况，并抛出ArrayIndexOutOfBoundsException。
由于同步容器类要遵守同步策略，即支持客户端加锁，因此可能会创建一些新的操作，只要我们知道应该使用哪一个锁，那么新操作就与容器的其他操作一样都是原子操作。同步容器类通过自身的锁来保护它的每个方法。
通过获得容器类的锁，我们可以使getLast和deleteLast称为原子操作，并确保Vector的大小在调用size和get之间不会发生变化。
// 5-2 在使用客户端加锁的Vector上的复合操作
public static Object getLast(Vector list) {
synchronized (list) { //获得容器类的锁，从客户端得到
int lastIndex = list.size() - 1;
return list.get(lastIndex);
}
}
public static void deleteLast(Vector list) {
synchronized (list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
}
}在调用size和相应的get之间，Vector的长度可能发生变化，这种风险在对Vector中的元素进行迭代时仍会出现。
// 5-3 可能抛出ArrayIndexOutOfBoundsException的迭代操作
for (int i = 0; i < vector.size(); i++)
doSomething(vector.get(i));在单线程中，在调用size和get之间诶呦线程会修改Vector，但在多线程时则不是。
我们可以通过在客户端加锁来解决不可靠迭代的问题，但要牺牲一些伸缩性
// 5-4 带有客户端加锁的迭代
synchronized (vector) {
for (int i = 0; i < vector.size(); i++)
doSomething(vector.get(i));
}通过在迭代期间持有Vector的锁，可以防止其他线程在迭代期间修改Vector。然而，这会导致其他线程在迭代期间无法访问它，因此降低了并发性。
5.1.2 迭代器与ConcurrentModificationException
对容器类进行迭代的标准方式都是使用迭代器（Iterator）。
如果有其他线程并发地修改容器，那么即使是使用迭代器也无法避免在迭代期间对容器加锁。迭代器没有考虑到并发修改的问题，它们表现出的行为是“及时失败（fail-fast）”，这意味着当它们发现容器在迭代过程中被修改时，就会抛出一个Concurrentmodificationexception（并发修改异常）。
下面的代码说明了如何使用for-each循环语法对List容器进行迭代。
javac将生成使用Iterator的代码，仿佛调用hasNext和next来迭代List对象。
// 5-5 通过Iterator来迭代List
List<Widget> widgetList
= Collections.synchronizedList(new ArrayList<Widget>());
...
// 可能抛出ConcurrentModificationException
for (Widget w : widgetList)
doSomething(w);与迭代Vector一样，要想避免出现ConcurrentModificationException，就必须在迭代过程持有容器的锁。
然而，有时候我们并不希望在迭代期间对容器加锁。例如，某些线程在可以访问容器之前，必须等待迭代过程结束，如果容器的规模很大，或者在每个元素上执行操作的事件很长，那么这些线程将长时间等待。
如果不希望在迭代期间对容器加锁，一种替代方法就是“克隆”容器、，并在副本上进行迭代。
由于副本被封闭在线程中，因此其他线程并不会在迭代期间对其修改，这样就避免了抛出ConcurrentModificationException（在克隆过程中仍然需要对容器加锁）。
在克隆容器时存在显著的性能开销。
5.1.3 隐藏迭代器
在某些情况下，迭代器会隐藏起来。
HiddenIterator中的字符串连接隐藏着迭代操作。编译器将字符串的连接操作转换为调用StringBuilder，append（Object），而这个方法又会调用容器的toString方法，标准容器的toString方法将迭代容器，并在每个元素上调用toString来生成容器内容的格式化表示。
// 5-6 隐藏在字符串连接中的迭代操作（不要这么做）
public class HiddenIterator {
@GuardedBy("this") private final Set<Integer> set = new HashSet<Integer>();
public synchronized void add(Integer i) {
set.add(i);
}
public synchronized void remove(Integer i) {
set.remove(i);
}
public void addTenThings() {
Random r = new Random();
for (int i = 0; i < 10; i++)
add(r.nextInt());
System.out.println("DEBUG: added ten elements to " + set);//执行隐藏的迭代操作
}
}addTenThings方法可能会抛出ConcurrentModificationException，因为在生成调式信息的过程中，toString对容器进行迭代。
真正的问题在于HiddenIterator不是线程安全的。在使用println中的set之前必须首先获取HiddenIterator
的锁。如果HiddenIterator用synchronizedSet来包装HashSet，并对同步代码进行封装，就不会发生这种错误。
正如封装对象的状态有助于维持不变性条件一样，封装对象的同步机制同样有助于确保实施同步策略。
容器的hashCode和equals等方法也会间接地执行迭代操作，当容器作为另一个容器的元素或键值时，就会出现这种情况。同样，containsAll，removeAll和retainAll等方法，以及把容器作为参数的构造函数，都会对容器进行迭代，这些间接的迭代操作都可能抛出ConcurrentModificationException。
5.2 并发容器（Concurrent Collections）
Java提供了多种并发容器来改进同步容器的性能。
同步容器将所有的容器状态的访问都串行化，以实现它们的线程安全性。这种方法的代价是严重降低并发性，当多个线程竞争容器的锁时，吞吐量将严重减低。
并发容器是针对多个线程并发访问设计的。例如ConcurrentHashMap，用来替代同步且基于散列的Map，以及CopyOnWriteArrayList，用在遍历操作为主要操作的情况下代替同步的List。
通过并发容器来替代同步容器，可以极大地提高伸缩性并减低风险。
Queue用来临时保存一组等待处理的元素。它提供了几种实现：包括
ConcurrentLinkedQueue，这是传统的先进先出队列
PriorityQueue，这是一个（非并发）优先队列
Queue上的操作不会阻塞，如果队列为空，那么获取元素的操作将返回空值。
BlockingQueue（阻塞队列）扩展了Queue，增加了可阻塞的插入和获取等操作。
如果队列为空，那么获取元素的操作将一直阻塞，直到队列中出现一个可用的元素。
如果队列已满（对于有界队列），插入元素操作将阻塞，直到队列中出现可用的空间。
在“生产者-消费者”这种设计模式中，阻塞队列是十分有用的。
Java还引入了ConcurrentSkipListMap和ConcurrentSkipListSet，分别作为同步的SortedMap和SortedSet的并发代替品。
5.2.1 ConcurrentHashMap
同步容器类在执行每个操作期间都持有一个锁。
在一些操作中，例如HashMap.get或List.contains，可能包含大量的工作：当遍历散列（Hash）桶或链表来查找某个特定的对象时，必须在许多元素上调用equals（而equals本身还包含一定的计算量）。在基于散列（Hash）的容器中，如果hashCode不能均匀地分布散列值，那么容器中的元素就不会均匀地分布在整个容器中。在某些情况下，某个糟糕的散列函数还会把一个散列表编程线性链表。当遍历很长的链表并且某些或者全部元素上调用equals方法时，会花费很长的时间而其他线程在期间不能访问该容器。
ConcurrentHashMap也是几个基于散列的Map，但它使用了一种完全不同的加锁策略来提供更高的并发性和伸缩性。
ConcurrentHashMap并不是将每个方法都在同一个锁上同步并使得每次只能有一个线程访问容器，而是使用一种粒度更细（finer-grained）的加锁机制来实现更大程度的共享，这种机制被称为分段锁（Lock Striping）
在这种机制中，任意数量的线程可以并发地访问Map，执行读取操作的线程和执行写入操作的线程可以并发地访问Map，并且一定数量的写入线程可以并发地修改Map。
ConcurrentHashMap带来的结果时候，在并发访问环境下将实现更高的吞吐量，而在单线程环境中只损失非常小的性能。
并发容器增强了同步容器类，它们提供的迭代器不会抛出ConcurrentModificationException，因此不需要在迭代过程中对容器加锁。
ConcurrentHashMap返回的迭代器具有弱一致性（weakly consistent），而非“及时失败”。弱一致性的迭代器可以容忍并发的修改，当创建迭代器时会遍历已有额元素，并可以（但不保证）在迭代器被构造后将修改操作反映给容器。
某些操作如szie，isEmpty的需求被弱化，以换取对其他更重要操作的性能优化，包括get，put，containKey和remove等。
在ConcurrentHashMap中没有实现对Map加锁以提供独占访问。
5.2.2 额外的原子Map操作（Additional Atomic Map Operations）
由于ConcurrentHashMap不能被加锁来执行独占访问，因此我们无法使用客户端加锁来创建新的原子操作。
一些常见的复合操作，如“若没有则添加”，“若相等则移除”，“若相等则替换”等都已经实现为原子操作并且在ConcurrentMap的接口中声明。如果你需要在现有的Map中添加这样的功能，那么很可能就意味着应该考虑使用ConcurrentMap。
// 5-7 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);
}5.2.3 CopyOnWriteArrayList
CopyOnWriteArrayList用于替代同步List，在某些情况下它提供了更好的并发性能，并且在迭代期间不需要对容器进行加锁或复制（CopyOnWriteArraySet的作用是替代同步Set）
“写入时复制（Copy-On-Write）”容器的线程安全性在于，只要正确发布一个事实不变的对象，那么在访问该对象时就不再需要进一步的同步。
在每次修改时，都会创建并重新发布一个新的容器副本，从而实现可变性。
“写入时复刻”容器的迭代器保留一个指向底层基础数组的引用，这个数组当前位于迭代器的其实位置，由于它不会被修改，因此在其对进行同步时只需确保数组内容的可见性。因此，多个线程可以同时这个容器进行迭代，而不会彼此干扰或与修改容器的线程互相干扰。
“写入时复制”容器返回的迭代器不会抛出ConcurrentModificationException。
每当修改容器时都会复制底层数组，这需要一定开销，特别是容器规模较大时。
仅当迭代操作远远多于修改操作时，才应该使用“写入时复制”容器。
5.3 阻塞队列和生产者-消费者模式
阻塞队列提供了可阻塞的put和take方法，以及支持定时的offer和poll方法。如果队列已经满了，put方法将阻塞直到空间可用；如果队列为空，那么take方法将会阻塞直到有元素可用。队列可以有界也可以*，*队列put永远不会阻塞。
阻塞队列支持生产者-消费者这种设计模式。该模式将“找出需要完成的工作”与“执行工作”这两个过程分离开来，并吧工作放入一个“待完成”列表中以便在随后处理，而不是找出后立即处理。
生产者-消费者模式能简化开发过程，因为它消除了生产者类和消费者类之间的代码依赖性。此外，该模式还将生产数据的过程与使用数据的过程解耦开以简化工作负载的管理，因为这两个过程在处理数据的速率上有所不同。
在基于阻塞对象构建的生产者-消费者设计中，当数据生成时，生产者把数据放入队列，而当消费者准备处理数据时，将从队列中获取数据。生产者不需要知道消费者的标识或数量，或者它们是否唯一的生产者，而只需将数据放入队列即可。同样，消费者也不需要知道生产者是谁，或者工作来自何处。BlockingQueue简化了生产者-消费者设计的设计过程，它支持任意数量的生产者和消费者。
阻塞队列还提供了一个offer方法，如果数据项不能被添加到队列中，那么将返回一个失败状态。
在构建高可靠的应用程序时，有界队列是一种强大的资源管理工具：它们能抑制并防止生产过多的工作项，使应用程序在负荷过载的情况下变得更加健壮。
虽然生产者-消费者模式能够将生产者和消费者的代码彼此解耦开来，但它们的行为仍然会通过共享工作队列间接耦合在一起。
在类库中还包含了BlockingQueue的多种实现，其中：
LinkedBlockingQueue和ArrayBlockingQueue是FIFO，二者分别与LinkedList和ArrayList类似，但比同步List拥有更好的并发性能。
PriorityBlockingQueue是一个按优先级排序的队列，当你希望按照某种顺序而不是FIFO来处理元素时，这个队列将非常有用。
最后一个BlockingQueue实现是SynchronousQueue,事实上它并不是一个真正的队列，因为它不会为队列中元素维护存储空间。与其他队列不同的是，它维护一组线程，这些线程在等待这把元素加入或移出队列。
如果以洗盘子为比喻，就相当于没有盘架来暂时存放洗好的盘子，而是将洗好的盘子直接放入下一个空闲的烘干机中。
这种实现队列由于可以直接交付工作，从而降低了将数据从生产者移动到消费者的延迟（在传统的队列中，在一个工作单元可以交付之前，必须通过串行方式首先完成入队列【Enqueue】或者出队列【Dequeue】等操作。）直接交付方式还会将更多关于人物状态的信息反馈给生产者。当交付被接受时，它就知道消费者已经得到了人物，而不是简单地把任务放入队列。
因为SynchronousQueue没有存储功能，因此put和take会一直阻塞，知道有另一个线程已经准备好参与到交付过程中。仅当有足够的消费者，并且总是有一个消费者准备好获取交付的工作时，才适合使用同步队列。
5.3.1 示例：桌面搜索（Desktop Search）
有一种类型的程序适合被分解为生产者和消费者，例如代理程序，它将扫描本地驱动上的文件并建立索引以便随后进行搜索，类似与某些桌面搜索程序或Windows索引服务。
下面的FileCrawler中给出了一个生产者任务，即在某个文件层次结构中搜索符合索引标准的文件，并将它们的名称放入工作队列。
其中的crawl扫描文件并将符合fileFilter条件的文件放入数组中。
implement Runnable是面向接口，扩展性等方面比extends Thread好，因为java只能单继承，而可以实现多接口。实现方式的好处：避免了单继承的局限性
注意：Runnable接口没有抛出异常，那么实现它的类只能是try-catch不能throws***重点内容*
public class FileCrawler implements Runnable{
//mplement Runnable是面向接口，扩展性等方面比extends Thread好，因为java只能单继承，而可以实现多接口
private final BlockingQueue<File> fileQueue; //省去初始化过程
private final FileFilter fileFilter;
private final File root;
//...
@Override
public void run() { //重写run方法
try{
crawl(root);
}catch (InterruptedException e) { //如果队列满则阻塞
// 恢复被中断的状态，终结被阻塞状态。
Thread.currentThread().interrupt();
}
}
private void crawl(File root) throws InterruptedException{
File[] entries=root.listFiles(fileFilter); //列出符合过滤器的文件列表
if(entries!=null){
for(File entry:entries)
if(entry.isDirectory()) //判断是否是文件夹，是则递归继续扫描
crawl(entry);
else if (!alreadyIndexed(entry)) //判断是否已在队列中,这方法理解就好，这里没列出
fileQueue.put(entry);
}
}
}在Indexer中还给出了一个消费者任务，即从队列中取出文件名并对它们建立索引。
// 5-8 桌面搜索应用中消费者任务
public class Indexer implements Runnable{
private final BlockingQueue<File> queue; //阻塞队列
public Indexer(BlockingQueue<File> queue){ //获得阻塞队列
this.queue=queue;
}
public void run(){ //重写run方法
try{
while(true) //一直循环，取出文件名并对它们建立索引，这里省去建立索引的函数
indexFile(queue.take());
}catch(InterruptedException e){ //如果queue为空则阻塞
// 恢复被中断的状态，终结被阻塞状态。
Thread.currentThread().interrupt();
}
}
}生产者-消费者模式提供了一种适合线程的方法将桌面搜索问题分解为更简单的组件。将文件遍历与建立索引等功能分解为独立的操作，比将所有功能都放到一个操作中实现有这更高的代码可读性和可重用性：每个操作只需完成一个任务，并且阻塞队列将负责所有的控制流。
因此每个功能的代码更加简单和清晰。
生产者-消费者模式带来许多性能优势。
下面的代码启动了多个爬虫程序和索引建立程序，每个程序都在各自的线程中运行。
消费者线程永远不会退出，因而程序无法停止，这将在后面的课程解决这个问题。
// 5-9 启动桌面搜索
public static void startIndexing(File[] roots){
BlockingQueue<File> queue=new LinkedBlockingQueue<File>(BOUND); //新建一个共享的队列
FileFilter filter=new FileFilter() { //创建一个文件过滤器
@Override
public boolean accept(File pathname) {
return true;
}
};
for(File root:roots) //启动多个爬虫程序
new Thread(new FileCrawler(queue,filter,root)).start();
for(int i=0;i<N_CONSUMERS;i++) //启动多个索引建立程序
new Thread(new Indexer(queue)).start();
}5.3.2 串行线程封闭（Serial Thread Confinement）
各种阻塞队列都包含了足够的内部同步机制，从而安全地将对象从生产者线程发布到消费者线程。
核心思想 ：
通过将多个并发的任务存入队列实现任务的串行化，并为这些串行化的任务创建唯一的一个工作线程进行处理。
本质：
使用一个开销更小的锁（队列锁）去替代另一个可能开销更大的锁（非线程安全对象引用的锁）
在生产者-消费者模式中，所有生产者，消费者有一个共享的工作队列
对于可变对象，生产者-消费者这种设计与阻塞队列一起，促进了串行线程封闭，从而将对象所有从生产者交付给消费者。线程封闭对象只能由对个线程拥有，但可以通过安全地发布该对象来“转移”所有权。在转移所有权后，也只有另一个线程能获得这个对象的访问权限，并且发布对象的线程不会再访问它。
这种安全的发布确保了对象状态对于新的所有者来说是可见的，并且由于最初的所有者不会再访问它，因此对象被封闭在新的线程中。新的所有者线程可以对该对象做任意修改，因为它具有独占的访问权。
对象池利用了串行线程封闭，将对象“租借”给一个请求线程。只要对象池包含足够的内部同步来安全地发布池中的对象，并且只要客户代码本身不会发布池中的对象，或者在将对象返回给对象池后就不再使用它了，那么就可以安全地在线程之间传递所有权。
5.3.3 双端队列与工作密取（Deques and Work Stealing）
Deque和BlockingDeque这两种容器类型，分别对Queue和BlockingQueue进行了扩展。Deque是一个双端队列，实现了在队列头和队列尾的高效插入和移除。具体实现包括ArrayDeque和LinkedBlockingDeque。
阻塞队列使用与生产者-消费者模式，而双端队列适用与工作密取（Working Stealing）。在生产者-消费者模式中，所有消费者有一个共享的工作队列，而在工作密取设计中，每个消费者都有*各自的双端队列。如果一个消费者完成了自己双端队列中的全部工作，那么它可以从其他消费者双端队列末尾秘密地获取工作。
密取工作模式比传统的生产者-消费者模式具有更高的可伸缩性，这是因为工作者线程不会在单个共享的任务队列上发生竞争。这是因为工作者线程不会在单个共享的任务队列上发生竞争。在大多数情况下，它们都只是访问自己的双端队列，从而极大地减少了竞争。当工作者线程需要访问另一个队列时，它UI从队列的尾部而不是头部获取工作，因此进一步降低了队列上的竞争程度。
工作密取非常适用于既是生产者也是消费者问题-当执行某个工作时可能导致出现更多的工作。
例如，在网页爬虫程序处理一个页面时，通常会发现有更多的页面需要处理。类似的还有许多搜索图的算法，例如在垃圾回收阶段对堆进行标记，都可以通过工作密取机制来实现高效并行。
当一个工作线程找到新的任务单元时，它会将其放到自己队列的末尾（或者在工作共享设计模式中，放入其他工作者线程的队列中）。当双端队列为空时，它在另一个线程的队列队尾查找新的任务，从而确保每个线程都保持忙碌状态。