同步类容器和并发类容器

一.为什么会出现同步容器？

在Java的集合容器框架中，主要有四大类别：List、Set、Queue、Map。

注意Collection和Map是顶层接口，而List、Set、Queue接口则分别继承了Collection接口，分别代表数组、集合和队列这三大类容器。

像ArrayList、LinkedList都是实现了List接口，HashSet实现了Set接口，而Deque（双向队列，允许在队首、队尾进行入队和出队操作）继承了Queue接口，PriorityQueue实现了Queue接口。另外LinkedList（实际上是双向链表）同时也实现了Deque接口。

但以上容器都是非线程安全的。如果有多个线程并发地访问这些容器时，就会出现问题。因此，在编写程序时，必须要求程序员手动地在访问到这些容器的地方进行同步处理，这样导致在使用这些容器的时候非常地不方便。所以，Java提供了同步容器供用户使用。

二.Java中的同步类容器

在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类中提供了大量的方法，比如对集合或者容器进行排序、查找等操作。最重要的是，在它里面提供了几个静态工厂方法来创建同步容器类，如下图所示：

这些同步容器都是通过synchronized进行同步来实现线程安全的，那么很显然，这必然会影响到执行性能。

而且虽然他们都是线程安全的，但这并不说明在任何情况下都可以线程安全，看你怎么用了，例如下面的这个例子：

public class Test {
    static Vector<Integer> vector = new Vector<Integer>();
    public static void main(String[] args) throws InterruptedException {
        while(true) {
            for(int i=0;i<10;i++)
                vector.add(i);
            Thread thread1 = new Thread(){
                public void run() {
                    for(int i=0;i<vector.size();i++)
                        vector.remove(i);
                };
            };
            Thread thread2 = new Thread(){
                public void run() {
                    for(int i=0;i<vector.size();i++)
                        vector.get(i);
                };
            };
            thread1.start();
            thread2.start();
            while(Thread.activeCount()>10)   {
                 
            }
        }
    }
}

运行结果是在执行过程中会出现数组下标越界的运行时异常。也许有朋友会问：Vector是线程安全的，为什么还会报这个错？很简单，对于Vector，虽然能保证每一个时刻只能有一个线程访问它，但是不排除这种可能，当某个线程在某个时刻执行这句时：

for(int i=0;i<vector.size();i++)

     vector.get(i);

假若此时vector的size方法返回的是10，i的值为9，在他要获取下标为9的元素时，有另外一个线程先执行了这句：

for(int i=0;i<vector.size();i++)

     vector.remove(i);

将下标为9的元素删除了，在删除过程中因为有锁，所以之前的那个线程无法执行vector.get(i);处于阻塞状态，等这个线程把下标为9的元素删除了之后获取到锁再执行。那么通过get方法访问下标为9的元素肯定就会出问题了。说明这是程序逻辑本身存在线程安全问题，因此为了保证线程安全，必须在方法调用端做额外的同步措施，如下面所示：

public class Test {
    static Vector<Integer> vector = new Vector<Integer>();
    public static void main(String[] args) throws InterruptedException {
        while(true) {
            for(int i=0;i<10;i++)
                vector.add(i);
            Thread thread1 = new Thread(){
                public void run() {
                    synchronized (Test.class) {   //进行额外的同步
                        for(int i=0;i<vector.size();i++)
                            vector.remove(i);
                    }
                };
            };
            Thread thread2 = new Thread(){
                public void run() {
                    synchronized (Test.class) {
                        for(int i=0;i<vector.size();i++)
                            vector.get(i);
                    }
                };
            };
            thread1.start();
            thread2.start();
            while(Thread.activeCount()>10)   {
                 
            }
        }
    }
}

三.Java中的并发类容器

为了解决同步类容器的性能问题，在Java 1.5之后提供了并发容器，位于java.util.concurrent目录下，这个目录俗称并发包。

3.1、ConcurrentMap

ConcurrentMap接口下有两个重要的实现：ConcurrentHashMap、ConcurrentSkipListMap。ConcurrentHashMap把整个哈希表分成多个segment，每个segment一把锁，主要通过锁分段技术减小了锁的粒度，降低了冲突，从而提高了并发性。在实际的应用中，散列表一般是读多写少。ConcurrentHashMap 就针对读操作做了大量的优化，运用了很多并发技巧，如不可变对象和使用volatile保证内存可见性，这样，在大多数情况下读操作甚至无需加锁也能获得正确的值。ConcurrentHashMap的concurrencyLevel（默认值为16）表示并发级别，这个值用来确定Segment的个数，Segment的个数是大于等于concurrencyLevel的第一个2的n次方的数。比如，如果concurrencyLevel为12，13，14，15，16这些数，则Segment的数目为16(2的4次方)。理想情况下ConcurrentHashMap的真正的并发访问量能够达到concurrencyLevel，因为有concurrencyLevel个Segment，假如有concurrencyLevel个线程需要访问Map，并且需要访问的数据都恰好分别落在不同的Segment中，则这些线程能够无竞争地自由访问（因为他们不需要竞争同一把锁），达到同时访问的效果。这也是为什么这个参数起名为“并发级别”的原因。该值设置过高会照成空间的浪费，设置过低会降低并发性。这种对调优的把握是要通过对底层实现的深刻理解和不断的实践积累才能获取的。

3.2、CopyOnWirte容器

Cope-On-Write简称COW，是一种用于程序设计中的优化策略，称为写时复制，理解起来很简单，就是执行修改操作时进行底层数组复制，使得修改操作在新的数组上进行，不妨碍原数组的并发读操作，复制修改完成后把原数组引用指向新数组。这样做的好处是可以并发的读而不需要加锁，因为当前容器不会添加任何元素，所以也是一种读写分离的思想。但正是因为写时复制，所以不能保证数据的实时性，而只能保证最终一致性。

在concurrent包下实现CopyOnWrite机制的容器有两种，CopyOnWriteArrayList和CopyOnWriteArraySet。

CopyOnWriteArrayList中有一个Object数组array用来存放数据，对于set()、add()、remove()等修改数据的操作会加上重入锁ReentrantLock，等修改操作完成替换掉array的引用之后才释放锁，从而保证写操作的线程安全，而针对读操作没有任何锁。

CopyOnWriteArraySet其实就是一个CopyOnWriteArrayList，不过就是在方法中避免重复数据而已，甚至这些避免重复数据的函数也是在CopyOnWriteArrayList中定义的，CopyOnWriteArraySet中只是包含一个CopyOnWriteArrayList的属性，然后在方法上做个包装，除了equals方法外，其他当前类中的所有函数都是调用的CopyOnWriteArrayList的方法，所以严格来讲可以使用一个CopyOnWriteArrayList作为具有Set特性的写时复制数组（不过就是没有继承AbstractSet）。

根据CopyOnWirte容器的实现原理可知，CopyOnWirte容器保证读写分离，十分适合读多写少的场景，但不适合写多的场景。

3.3、线程安全队列

在并发编程中我们有时候需要使用线程安全的队列。如果我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现，而非阻塞的实现方式则可以使用循环CAS的方式来实现。java.util.concurrent.atomic包相关类就是CAS的实现。

ConcurrentLinkedQueue是一个适用于高并发场景下的非阻塞的队列，通过无锁的方式(采用CAS操作)，实现了高并发状态下的高性能，通常ConcurrentLinkedQueue的性能优于BlockingQueue。ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素，该队列不允许NULL元素。

阻塞队列当队列是空的时候，再想获取元素就会阻塞进入等待状态，所以非常适合生产者-消费者模式。阻塞队列BlockingQueue接口JDK提供了7种实现：

• ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列。
• LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列。
• PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列。
• DelayQueue：一个使用优先级队列实现的无界阻塞队列。
• SynchronousQueue：一个不存储元素的阻塞队列。
• LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
• LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。