避免锁：读-复制-更新
最快的锁是根本没有锁。问题在于没有锁的情况下，我们是否允许对共享数据结构的并发读写进行访问。答案当然是不可以。假设进程 A 正在对一个数字数组进行排序，而进程 B 正在计算其平均值，而此时你进行 A 的移动，会导致 B 会多次读到重复值，而某些值根本没有遇到过。
然而，在某些情况下，我们可以允许写操作来更新数据结构，即便还有其他的进程正在使用。窍门在于确保每个读操作要么读取旧的版本，要么读取新的版本，例如下面的树
上面的树中，读操作从根部到叶子遍历整个树。加入一个新节点 X 后，为了实现这一操作，我们要让这个节点在树中可见之前使它"恰好正确"：我们对节点 X 中的所有值进行初始化，包括它的子节点指针。然后通过原子写操作，使 X 称为 A 的子节点。所有的读操作都不会读到前后不一致的版本
在上面的图中，我们接着移除 B 和 D。首先，将 A 的左子节点指针指向 C 。所有原本在 A 中的读操作将会后续读到节点 C ，而永远不会读到 B 和 D。也就是说，它们将只会读取到新版数据。同样，所有当前在 B 和 D 中的读操作将继续按照原始的数据结构指针并且读取旧版数据。所有操作均能正确运行，我们不需要锁住任何东西。而不需要锁住数据就能够移除 B 和 D 的主要原因就是 读-复制-更新(Ready-Copy-Update,RCU)，将更新过程中的移除和再分配过程分离开。
Java 并发工具包
JDK 1.5 提供了许多种并发容器来改进同步容器的性能，同步容器将所有对容器状态的访问都串行化，以实现他们之间的线程安全性。这种方法的代价是严重降低了并发性能，当多个线程争抢容器锁的同时，严重降低吞吐量。
下面我们就来一起认识一下 Java 中都用了哪些并发工具
Java 并发工具综述
在 Java 5.0 中新增加了 ConcurrentHashMap 用来替代基于散列的 Map 容器；新增加了 CopyOnWriteArrayList 和 CopyOnWriteArraySet 来分别替代 ArrayList 和 Set 接口实现类；还新增加了两种容器类型，分别是 Queue 和 BlockingQueue， Queue 是队列的意思，它有一些实现分别是传统的先进先出队列 ConcurrentLinkedQueue以及并发优先级队列 PriorityQueue。Queue 是一个先入先出的队列，它的操作不会阻塞，如果队列为空那么获取元素的操作会返回空值。PriorityQueue 扩展了 Queue，增加了可阻塞的插入和获取等操作。如果队列为空，那么获取元素的操作将一直阻塞，直到队列中出现一个可用的元素为止。如果队列已满，那么插入操作则一直阻塞，直到队列中有可用的空间为止。
Java 6.0 还引入了 ConcurrentSkipListMap 和 ConcurrentSkipListSet 分别作为同步的 SortedMap 和 SortedSet 的并发替代品。下面我们就展开探讨了，设计不到底层源码，因为本篇文章主要目的就是为了描述一下有哪些东西以及用了哪些东西。
ConcurrentHashMap
我们先来看一下 ConcurrentHashMap 在并发集合中的位置
可以看到，ConcurrentHashMap 继承了 AbstractMap 接口并实现了 ConcurrentMap 和 Serializable 接口，AbstractMap 和 ConcurrentMap 都是 Map 的实现类，只不过 AbstractMap 是抽象实现。
ConcurrentHashMap 和 Hashtable 的构造非常相似，只不过 Hashtable 容器在激烈竞争的场景中会表现出效率低下的现象，这是因为所有访问 Hashtable 的线程都想获取同一把锁，如果容器里面有多把锁，并且每一把锁都只用来锁定一段数据，那么当多个线程访问不同的数据段时，就不存在竞争关系。这就是 ConcurreentHashMap 采用的 分段锁 实现。在这种锁实现中，任意数量的读取线程可以并发的访问 Map，执行读取操作的线程和执行写入的线程可以并发的访问 Map，并且在读取的同时也可以并发修改 Map。
ConcurrentHashMap 分段锁实现带来的结果是，在并发环境下可以实现更高的吞吐量，在单线程环境下只损失非常小的性能。
你知道 HashMap 是具有 fail-fast 机制的，也就是说它是一种强一致性的集合，在数据不一致的情况下会抛出 ConcurrentModificationException 异常，而 ConcurrentHashMap 是一种 弱一致性 的集合，在并发修改其内部结构时，它不会抛出 ConcurrentModificationException 异常，弱一致性能够容忍并发修改。
在 HashMap 中，我们一般使用的 size、empty、containsKey 等方法都是标准方法，其返回的结果是一定的，包含就是包含，不包含就是不包含，可以作为判断条件；而 ConcurrentHashMap 中的这些方法只是参考方法，它不是一个 精确值，像是 size、empty 这些方法在并发场景下用处很小，因为他们的返回值总是在不断变化，所以这些操作的需求就被弱化了。
在 ConcurrentHashMap 中没有实现对 Map 加锁从而实现独占访问。在线程安全的 Map 实现 Hashtable 和 Collections.synchronizedMap 中都实现了独占访问，因此只能单个线程修改 Map 。ConcurrentHashMap 与这些 Map 容器相比，具有更多的优势和更少的劣势，只有当需要独占访问的需求时才会使用 Hashtable 或者是 Collections.synchronizedMap ，否则其他并发场景下，应该使用 ConcurrentHashMap。
ConcurrentMap
ConcurrentMap 是一个接口，它继承了 Map 接口并提供了 Map 接口中四个新的方法，这四个方法都是 原子性 方法，进一步扩展了 Map 的功能。
public interface ConcurrentMap<K, V> extends Map<K, V> { // 仅当 key 没有相应的映射值时才插入 V putIfAbsent(K key, V value); // 仅当 key 被映射到 value 时才移除 boolean remove(Object key, Object value); // 仅当 key 被映射到 value 时才移除 V replace(K key, V value); // 仅当 key 被映射到 oldValue 时才替换为 newValue boolean replace(K key, V oldValue, V newValue); }
ConcurrentNavigableMap
java.util.concurrent.ConcurrentNavigableMap 类是 java.util.NavigableMap 的子类，它支持并发访问，并且允许其视图的并发访问。
什么是视图呢？视图就是集合中的一段数据序列，ConcurrentNavigableMap 中支持使用 headMap、subMap、tailMap 返回的视图。与其重新解释一下 NavigableMap 中找到的所有方法，不如看一下 ConcurrentNavigableMap 中添加的方法
- headMap 方法：headMap 方法返回一个严格小于给定键的视图
- tailMap 方法：tailMap 方法返回包含大于或等于给定键的视图。
- subMap 方法：subMap 方法返回给定两个参数的视图
ConcurrentNavigableMap 接口包含一些可能有用的其他方法
- descendingKeySet()
- descendingMap()
- navigableKeySet()
更多关于方法的描述这里就不再赘述了，读者朋友们可自行查阅 javadoc
ConcurrentSkipListMap
ConcurrentSkipListMap 是线程安全的有序的哈希表，适用于高并发的场景。
ConcurrentSkipListMap 的底层数据结构是基于跳表实现的。ConcurrentSkipListMap 可以提供 Comparable 内部排序或者是 Comparator 外部排序，具体取决于使用哪个构造函数。
ConcurrentSkipListSet
ConcurrentSkipListSet 是线程安全的有序的集合，适用于高并发的场景。ConcurrentSkipListSet 底层是通过 ConcurrentNavigableMap 来实现的，它是一个有序的线程安全的集合。
ConcurrentSkipListSet有序的，基于元素的自然排序或者通过比较器确定的顺序；
ConcurrentSkipListSet是线程安全的；
CopyOnWriteArrayList
CopyOnWriteArrayList 是 ArrayList 的变体，在 CopyOnWriteArrayList 中，所有可变操作比如 add、set 其实都是重新创建了一个副本，通过对数组进行复制而实现的。
CopyOnWriteArrayList 其内部有一个指向数组的引用，数组是不会被修改的，每次并发修改 CopyOnWriteArrayList 都相当于重新创建副本，CopyOnWriteArrayList 是一种 fail-safe 机制的，它不会抛出 ConcurrentModificationException 异常，并且返回元素与迭代器创建时的元素相同。
每次并发写操作都会创建新的副本，这个过程存在一定的开销，所以，一般在规模很大时，读操作要远远多于写操作时，为了保证线程安全性，会使用 CopyOnWriteArrayList。
类似的，CopyOnWriteArraySet 的作用也相当于替代了 Set 接口。
BlockingQueue
BlockingQueue 译为 阻塞队列，它是 JDK 1.5 添加的新的工具类，它继承于 Queue 队列，并扩展了 Queue 的功能。
BlockingQueue 在检索元素时会等待队列变成非空，并在存储元素时会等待队列变为可用。BlockingQueue 的方法有四种实现形式，以不同的方式来处理。
- 第一种是
抛出异常 特殊值：第二种是根据情况会返回 null 或者 false阻塞：第三种是无限期的阻塞当前线程直到操作变为可用后超时：第四种是给定一个最大的超时时间，超过后才会放弃
BlockingQueue 不允许添加 null 元素，在其实现类的方法 add、put 或者 offer 后时添加 null 会抛出空指针异常。BlockingQueue 会有容量限制。在任意时间内，它都会有一个 remainCapacity，超过该值之前，任意 put 元素都会阻塞。
BlockingQueue 一般用于实现生产者 - 消费者 队列，如下图所示
BlockingQueue 有多种实现，下面我们一起来认识一下这些容器。
其中 LinkedBlockingQueue 和 ArrayBlockingQueue 是 FIFO 先入先出队列，二者分别和 LinkedList和 ArrayList 对应，比同步 List 具有更好的并发性能。PriorityBlockingQueue 是一个优先级排序的阻塞队列，如果你希望按照某种顺序而不是 FIFO 处理元素时这个队列将非常有用。正如其他有序的容器一样，PriorityBlockingQueue 既可以按照自然顺序来比较元素，也可以使用 Comparator 比较器进行外部元素比较。SynchronousQueue 它维护的是一组线程而不是一组队列，实际上它不是一个队列，它的每个 insert 操作必须等待其他相关线程的 remove 方法后才能执行，反之亦然。
LinkedBlockingQueue
LinkedBlockingQueue 是一种 BlockingQueue 的实现。
它是一种基于链表的构造、先入先出的有界阻塞队列。队列的 head 也就是头元素是在队列中等待时间最长的元素；队列的 tail也就是队尾元素是队列中等待时间最短的元素。新的元素会被插入到队尾中，检索操作将获取队列中的头部元素。链表队列通常比基于数组的队列具有更高的吞吐量，但是在大多数并发应用程序中，可预测的性能较差。
ArrayBlockingQueue
ArrayBlockingQueue 是一个用数组实现的有界队列，此队列顺序按照先入先出的原则对元素进行排序。
默认情况下不保证线程公平的访问队列，所谓公平访问队列指的是阻塞的线程，可以按照阻塞的先后顺序访问，即先阻塞线程先访问队列。非公平性是对先等待的线程是非公平的。有可能先阻塞的线程最后才访问队列。
PriorityBlockingQueue
PriorityBlockingQueue 是一个支持优先级的阻塞队列，默认情况下的元素采取自然顺序生序或者降序，也可以自己定义 Comparator 进行外部排序。但需要注意的是不能保证同优先级元素的顺序。
DelayQueue
DelayQueue 是一个支持延时获取元素的无阻塞队列，其中的元素只能在延迟到期后才能使用，DelayQueue 中的队列头是延迟最长时间的元素，如果没有延迟，则没有 head 头元素，poll 方法会返回 null。判断的依据就是 getDelay(TimeUnit.NANOSECONDS) 方法返回一个值小于或者等于 0 就会发生过期。
TransferQueue
TransferQueue 继承于 BlockingQueue，它是一个接口，一个 BlockingQueue 是一个生产者可能等待消费者接受元素，TransferQueue 则更进一步，生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费，新添加的transfer 方法用来实现这种约束。
TransferQueue 有下面这些方法：两个 tryTransfer 方法，一个是非阻塞的，另一个是带有 timeout 参数设置超时时间的。还有两个辅助方法 hasWaitingConsumer 和 getWaitingConcusmerCount。
LinkedTransferQueue
一个无界的基于链表的 TransferQueue。这个队列对任何给定的生产者进行 FIFO 排序，head 是队列中存在时间最长的元素。tail 是队列中存在时间最短的元素。
BlockingDeque
与 BlockingQueue 相对的还有 BlockingDeque 和 Deque，它们是 JDK1.6 被提出的，分别对 Queue 和 BlockingQueue 做了扩展。
Deque 是一个双端队列，分别实现了在队列头和队列尾的插入。Deque 的实现有 ArrayDeque、ConcurrentLinkedDeque，BlockingDeque 的实现有 LinkedBlockingDeque 。
阻塞模式一般用于生产者 - 消费者队列，而双端队列适用于工作密取。在工作密取的设计中，每个消费者都有各自的双端队列，如果一个消费者完成了自己双端队列的任务，就会去其他双端队列的末尾进行消费。密取方式要比传统的生产者 - 消费者队列具有更高的可伸缩性，这是因为每个工作密取的工作者都有自己的双端队列，不存在竞争的情况。
ArrayDeque
ArrayDeque 是 Deque 的可动态调整大小的数组实现，其内部没有容量限制，他们会根据需要进行增长。ArrayDeque 不是线程安全的，如果没有外部加锁的情况下，不支持多线程访问。ArrayDeque 禁止空元素，这个类作为栈使用时要比 Stack 快，作为 queue 使用时要比 LinkedList 快。
除了 remove、removeFirstOccurrence、removeLastOccurrence、contains、interator.remove 外，大部分的 ArrayDeque 都以恒定的开销运行。
“注意：ArrayDeque 是 fail-fast 的，如果创建了迭代器之后，却使用了迭代器外部的 remove 等修改方法，那么这个类将会抛出 ConcurrentModificationException 异常。
ConcurrentLinkedDeque
ConcurrentLinkedDeque 是 JDK1.7 引入的双向链表的无界并发队列。它与 ConcurrentLinkedQueue 的区别是 ConcurrentLinkedDeque 同时支持 FIFO 和 FILO 两种操作方式，即可以从队列的头和尾同时操作(插入/删除)。ConcurrentLinkedDeque 也支持 happen-before 原则。ConcurrentLinkedDeque 不允许空元素。
LinkedBlockingDeque
LinkedBlockingDeque 是一个由链表结构组成的双向阻塞队列，即可以从队列的两端插入和移除元素。双向队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。LinkedBlockingDeque 把初始容量和构造函数绑定，这样能够有效过度拓展。初始容量如果没有指定，就取的是 Integer.MAX_VALUE，这也是 LinkedBlockingDeque 的默认构造函数。
