一、同步容器

   在Java中，同步容器主要包括2类：

　　1）Vector、Stack、HashTable

　　2）Collections类中提供的静态工厂方法创建的类

　　Vector实现了List接口，Vector实际上就是一个数组，和ArrayList类似，但是Vector中的方法都是synchronized方法，即进行了同步措施。

　　Stack也是一个同步容器，它的方法也用synchronized进行了同步，它实际上是继承于Vector类。

       HashTable实现了Map接口，它和HashMap很相似，但是HashTable进行了同步处理，而HashMap没有。

Collections类是一个工具提供类，注意，它和Collection不同，Collection是一个顶层的接口。在Collections类中提供了大量的方法，比如对集合或者容器进行排序、查找等操作。最重要的是，在它里面提供了几个静态工厂方法来创建同步容器类，如：

Collectinons.synchronizedList()

Collections.synchronizedSet()

Collections.synchronizedMap()

Collections.synchronizedSortedSet()

Collections.synchronizedSortedMap()

缺点：

1、通过同步方法将访问操作串行化，导致并发环境下效率低下

2、复合操作（迭代、条件运算如没有则添加等）非线程安全，需要客户端代码来实现加锁

二、并发容器

理解基本的线程安全工具。

理解传统集合框架并发编程中Map存在的问题，清楚简单同步方式的不足。

梳理并发包内，尤其是ConcurrentHashMap采取了哪些方法来提高并发表现。

最好能掌握ConcurrentHashMap自身的演进。

   1）ConcurrentHashMap

      为什么需要ConcurrentHashMap？

      Hashtable或者同步包装版本，只是在方法前加synchronized，导致所有的并发操作都要竞争同一把锁，一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操作的效率。只是适合在非高度并发的场景下。

      早期ConcurrentHashMap，其实是基于：

        * 分离锁，也就是将内部进行分段（Segment），里面则是HashEntry的数组，和HashMap类似，哈希相同的条目也是以链表形式存储。

        * HashEntry内部使用volatile的value字段来保证可见性，也利用了不可变对象的机制以改进利用Unsafe提供的底层能力去直接完成部分操作，以优化性能。

      ConcurrentHashMap最关键的是要理解一个概念：Segment，Segment是什么呢？Segment本身就相当于一个HashMap对象。同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。

单一的Segment结构如下：

像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个，共同保存在一个名为segments的数组当中。

因此整个ConcurrentHashMap的结构如下：

可以说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。

ConcurrentHashMap优势就是采用了[锁分段技术]，每一个Segment就好比一个自治区，读写操作高度自治，Segment之间互不影响。

并发读写的几种情形：

Case1：不同Segment的并发写入

不同Segment的写入是可以并发执行的。

Case2：同一Segment的一写一读

同一Segment的写和读是可以并发执行的。

Case3：同一Segment的并发写入

Segment的写入是需要上锁的，因此对同一Segment的并发写入会被阻塞。

由此可见，ConcurrentHashMap当中每个Segment通过继承ReentrantLock来进行加锁，各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

ConcurrentHashMap读写详细过程：

Get方法：

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象

3.再次通过hash值，定位到Segment当中数组的具体位置。

Put方法：

1.为输入的Key做Hash运算，得到hash值。

2.通过hash值，定位到对应的Segment对象

3.获取可重入锁

4.再次通过hash值，定位到Segment当中数组的具体位置。

5.插入或覆盖HashEntry对象。

6.释放锁。

从上述步骤可以看出，ConcurrentHashMap在读写时都需要二次定位，首先定位到Segment，之后定位到Segment内的具体数组下标。

Size方法：

既然每个Segment都各自加锁，那么在调用Size方法的时候，怎么解决一致性的问题呢？

Size方法的目的是统计ConcurrentHashMap的总元素数量， 自然需要把各个Segment内部的元素数量汇总起来。

但是，如果在统计Segment元素数量的过程中，已统计过的Segment瞬间插入新的元素，这时候该怎么办呢？

ConcurrentHashMap的Size方法是一个嵌套循环，大体逻辑如下：

1.遍历所有的Segment。

2.把Segment的元素数量累加起来。

3.把Segment的修改次数累加起来。

4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。

5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。

6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。

7.释放锁，统计结束。

为什么这样设计呢？这种思想和乐观锁悲观锁的思想如出一辙。

为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数(最多3次)，才无奈转为悲观锁，锁住所有Segment保证强一致性。

ConcurrentHashMap在jdk1.7和jdk1.8的区别：

* 总体结构上，它的内部存储变得和HashMap结构非常相似，同样是大的桶数组，然后内部也是一个个所谓的链表结构，同步的粒度要更细致一些。

* 其内部仍然有Segment定义，但仅仅是为了保证序列化时的兼容性而已，不再有任何结构上的用处。

* 因为不再使用Segment，初始化操作大大简化，修改为lazy-load形式，这样可以避免初始开销，解决了老版本很多人抱怨的这一点。

* 数据存储利用volatile保证可见性。

* 使用CAS等操作，在特定场景进行无锁并发操作。

* 使用Unsafe、LongAdder之类的底层手段，进行极端情况的优化。

Java 7中的ConcurrentHashMap的底层数据结构仍然是数组和链表。与HashMap不同的是，ConcurrentHashMap最外层不是一个大的数组，而是一个Segment的数组。每个Segment包含一个与HashMap数据结构差不多的链表数组。结构如下：

Java 7为实现并行访问，引入了Segment这一结构，实现了分段锁，理论上最大并发度与Segment个数相等。Java 8为进一步提高并发性，摒弃了分段锁的方案，而是直接使用一个大的数组，采用Node + CAS + Synchronized来保证并发安全进行实现。同时为了提高哈希碰撞下的寻址性能，Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(long(N))）。

可以理解为，Java8相当于把Segment分段锁更细粒度了，每个数组元素就是原来的一个Segment，那并发读就由原来的Segment数变为数组长度了。然后用到了CAS乐观锁，所以能支持更高的并发。

Java8的ConcurrentHashMap结构如下：

对于put操作，如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。在同步逻辑上为什么使用的是synchronized，而不是通常建议的ReentrantLock之类？现在JDK中，synchronized已经被不断优化，可以不再过分担心性能差异，另外，相比ReentrantLock，它可以减少内存消耗，这是个非常大的优势。如果该put操作使得当前链表长度超过一定阈值，则将该链表转换为树，从而提高寻址效率。

对于读操作，由于数组被volatile关键字修饰，因此不用担心数组的可见性问题。同时每个元素是一个Node实例（Java 7中每个元素是一个HashEntry），它的Key值和hash值都由final修饰，不可变更，无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰，可见性也有保障。

2）CopyOnWriteArrayList和CopyOnWriteArraySet

   CopyOnWriteArrayList是Java并发包中提供的一个并发容器，它是个线程安全且读操作无锁的ArrayList，写操作则通过创建底层数组的新副本来实现，是一种读写分离的并发策略，我们也可以称这种容器为"写时复制器"，Java并发包中类似的容器还有CopyOnWriteArraySet。

实现原理

　　我们都知道，集合框架中的ArrayList是非线程安全的，Vector虽是线程安全的，但由于简单粗暴的锁同步机制，性能较差。而CopyOnWriteArrayList则提供了另一种不同的并发处理策略（当然是针对特定的并发场景）。

很多时候，我们的系统应对的都是读多写少的并发场景。CopyOnWriteArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

优缺点分析

　　了解了CopyOnWriteArrayList的实现原理，分析它的优缺点及使用场景就很容易了。

　　优点：

　　读操作性能很高，因为无需任何同步措施，比较适用于读多写少的并发场景。Java的list在遍历时，若中途有别的线程对list容器进行修改，则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想，遍历和修改操作分别作用在不同的list容器，所以在使用迭代器进行遍历时候，也就不会抛出ConcurrentModificationException异常了

　　缺点：

缺点也很明显，一是内存占用问题，毕竟每次执行写操作都要将原容器拷贝一份，数据量大时，对内存压力较大，可能会引起频繁GC；二是无法保证实时性，Vector对于读写操作均加锁同步，可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因，写和读分别作用在新老不同容器上，在写操作执行过程中，读不会阻塞但读取到的却是老容器的数据。

3）阻塞队列

      使用非阻塞队列的时候有一个很大问题就是：它不会对当前线程产生阻塞，那么在面对类似消费者-生产者的模型时，就必须额外地实现同步策略以及线程间唤醒策略，这个实现起来就非常麻烦。但是有了阻塞队列就不一样了，它会对当前线程产生阻塞，比如一个线程从一个空的阻塞队列中取元素，此时线程会被阻塞直到阻塞队列中有了元素。当队列中有元素后，被阻塞的线程会自动被唤醒（不需要我们编写代码去唤醒）。这样提供了极大的方便性。

       阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作是：在队列为空时，获取元素的线程会等待队列变为非空。当队列满时，存储元素的线程会等待队列可用。阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。阻塞队列就是生产者存放元素的容器，而消费者也只从容器里拿元素。阻塞队列用Condition接口的await和signal方法实现。

当队列中没有数据的情况下，消费者端的所有线程都会被自动阻塞（挂起），直到有数据放入队列：

当队列中填满数据的情况下，生产者端的所有线程都会被自动阻塞（挂起），直到队列中有空的位置，线程被自动唤醒：

阻塞队列种类：

ArrayBlockingQueue：基于数组实现的一个阻塞队列，维护了一个定长数组，以便缓存队列中的数据对象，在创建ArrayBlockingQueue对象时必须制定容量大小。并且可以指定公平性与非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。

LinkedBlockingQueue：基于链表实现的一个阻塞队列，其内部也维持着一个数据缓冲队列（该队列由一个链表构成）。当生产者往队列中放入一个数据时，队列会从生产者手中获取数据，并缓存在队列内部，而生产者立即返回；只有当队列缓冲区达到最大值缓存容量时（LinkedBlockingQueue可以通过构造函数指定该值），才会阻塞生产者队列，直到消费者从队列中消费掉一份数据，生产者线程会被唤醒，反之对于消费者这端的处理也基于同样的原理。作为开发者，我们需要注意的是，如果构造一个LinkedBlockingQueue对象，而没有指定其容量大小，LinkedBlockingQueue会默认一个类似无限大小的容量（Integer.MAX_VALUE），这样的话，如果生产者的速度一旦大于消费者的速度，也许还没有等到队列满阻塞产生，系统内存就有可能已被消耗殆尽了。

ArrayBlockingQueue和LinkedBlockingQueue是两个最普通也是最常用的阻塞队列，一般情况下，在处理多线程间的生产者消费者问题，使用这两个类足矣。

PriorityBlockingQueue：以上2种队列都是先进先出队列，而PriorityBlockingQueue却不是，它会按照元素的优先级对元素进行排序，按照优先级顺序出队，每次出队的元素都是优先级最高的元素。注意，此阻塞队列为无界阻塞队列，即容量没有上限，前面2种都是有界队列。

DelayQueue：基于PriorityQueue，一种延时阻塞队列，DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取到该元素。DelayQueue也是一个无界队列，因此往队列中插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。

SynchronousQueue：一种无缓冲的等待队列，每个删除操作都要等待插入操作，反之每个插入操作也都要等待删除操作。类似于无中介的直接交易，相对于有缓冲的BlockingQueue来说，少了一个中间经销商的环节（缓冲区），如果有经销商，生产者直接把产品批发给经销商，而无需在意经销商最终会将这些产品卖给那些消费者，由于经销商可以库存一部分商品，因此相对于直接交易模式，总体来说采用中间经销商的模式会吞吐量高一些（可以批量买卖）；但另一方面，又因为经销商的引入，使得产品从生产者到消费者中间增加了额外的交易环节，单个产品的及时响应性能可能会降低。

阻塞队列实现原理：

看它的两个关键方法的实现：put()和take()：

public void put(E e) throws InterruptedException {

    if (e == null) throw newNullPointerException();

    final E[] items =this.items;

    final ReentrantLock lock= this.lock;

   lock.lockInterruptibly();

    try {

        try {

            while (count ==items.length)

               notFull.await();

        } catch(InterruptedException ie) {

           notFull.signal(); // propagate to non-interrupted thread

            throw ie;

        }

        insert(e);

    } finally {

        lock.unlock();

    }

}

private void insert(E x) {

    items[putIndex] = x;

    putIndex =inc(putIndex);

    ++count;

    notEmpty.signal();

}

从put方法的实现可以看出，它先获取了锁，并且获取的是可中断锁，然后判断当前元素个数是否等于数组的长度，如果相等，则调用notFull.await()进行等待，如果捕获到中断异常，则唤醒线程并抛出异常。当被其他线程唤醒时，通过insert(e)方法插入元素，最后解锁。

下面是take()方法的实现：

public E take() throws InterruptedException {

    final ReentrantLock lock= this.lock;

    lock.lockInterruptibly();

    try {

        try {

            while (count ==0)

               notEmpty.await();

        } catch(InterruptedException ie) {

           notEmpty.signal(); // propagate to non-interrupted thread

            throw ie;

        }

        E x = extract();

        return x;

    } finally {

        lock.unlock();

    }

}

private E extract() {

final E[] items = this.items;

E x = items[takeIndex];

items[takeIndex] = null;

takeIndex = inc(takeIndex);

--count;

notFull.signal();

return x;

}

跟put方法实现很类似，只不过put方法等待的是notFull信号，而take方法等待的是notEmpty信号。在take方法中，如果可以取元素，则通过extract方法取得元素。

从这里大家应该明白了阻塞队列的实现原理，事实它和我们用Object.wait()、Object.notify()和非阻塞队列实现生产者-消费者的思路类似，只不过它把这些工作一起集成到了阻塞队列中实现。

4）EnumMap和EnumSet

   EnumMap是专门为枚举类型量身定做的Map实现。虽然使用其它的Map实现（如HashMap）也能完成枚举类型实例到值得映射，但是使用EnumMap会更加高效：它只能接收同一枚举类型的实例作为键值，并且由于枚举类型实例的数量相对固定并且有限，所以EnumMap使用数组来存放与枚举类型对应的值。这使得EnumMap的效率非常高。与HashMap的主要不同，一是构造方法需要传递类型参数，二是保证顺序。

EnumMap的基本实现原理，内部有两个数组，长度相同，一个表示所有可能的键，一个表示对应的值，值为null表示没有该键值对，键都有一个对应的索引，根据索引可直接访问和操作其键和值，效率很高。

EnumSet是使用位向量实现的，什么是位向量呢？就是用一个位表示一个元素的状态，用一组位表示一个集合的状态，每个位对应一个元素，而状态只可能有两种。

EnumSet是一个抽象类，它没有定义使用的向量长度，它有两个子类，RegularEnumSet和JumboEnumSet。RegularEnumSet使用一个long类型的变量作为位向量，long类型的位长度是64，而JumboEnumSet使用一个long类型的数组。如果枚举值个数小于等于64，则静态工厂方法中创建的就是RegularEnumSet，大于64的话就是JumboEnumSet。

5）Collections.sort()和Arrays.sort()

   总结一下Arrays.sort()方法，如果数组长度大于等于286且连续性好的话，就用归并排序，如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序，如果长度小于47的话就用插入排序。

再来看看Collections.sort()，一路点进去，发现会进到Arrays里了，来看看又有什么选择：

public static void sort(T[] a, Comparator c) {

    if (c == null) {

        sort(a);

    } else {

        if(LegacyMergeSort.userRequested)

           legacyMergeSort(a, c);

        else

            TimSort.sort(a,0, a.length, c, null, 0, 0);

    }

}

会发现如果LegacyMergeSort.userRequested为true的话就会使用归并排序，可以通过下面代码设置为true

System.setProperty("java.util.Arrays.useLegacyMergeSort","true");

不过方法legacyMergeSort的注释上有这么一句话，说明以后传统归并可能会被移除了。

/** To be removed in a future release. */

如果不为true的话就会用一个叫TimSort的排序算法。

参考书目：《Java编程思想》、《Java核心技术卷一》、《Effective Java》