并发集合和阻塞队列

 

一、阻塞队列BlockingQueue

       BlockingQueue 是线程安全的java阻塞队列，主要应用于生产者消费者模式、消息传递、并行任务执行和相关并发设计的大多数常见使用上下文。

   BlockingQueue 可以是限定容量的。它在任意给定时间都可以有一个 remainingCapacity，超出此容量，便无法无阻塞地 put 附加元素。没有任何内部容量约束的 BlockingQueue 总是报告 Integer.MAX_VALUE 的剩余容量。

   BlockingQueue 方法以四种形式出现，对于不能立即满足但可能在将来某一时刻可以满足的操作，这四种形式的处理方式不同：第一种是抛出一个异常，第二种是返回一个特殊值（null 或 false，具体取决于操作），第三种是在操作可以成功前，无限期地阻塞当前线程，第四种是在放弃前只在给定的最大时间限制内阻塞。下表中总结了这些方法：

 

 

 

 

	抛出异常	特殊值	阻塞	超时
插入	add(e)	offer(e)	put(e)	offer(e, time, unit)
移除	remove()	poll()	take()	poll(time, unit)
检查	element()	peek()	不可用	不可用

 

 

阻塞队列包含以下实现：

1. ArrayBlockingQueue

        一个以数组为基础的有界阻塞队列，此队列按照先进先出原则对元素进行排序。队列头部元素是队列中存在时间最长的元素，队列尾部是存在时间最短的元素，新元素将会被插入到队列尾部。队列从头部开始获取元素。

       ArrayBlockingQueue是“有界缓存区”模型的一种实现，一旦创建了这样的缓存区，就不能再改变缓冲区的大小。ArrayBlockingQueue的一个特点是，必须在创建的时候指定队列的大小。当缓冲区已满，则需要阻塞新增的插入操作，同理，当缓冲区已空需要阻塞新增的提取操作。

       ArrayBlockingQueue是使用的是循环队列方法实现的，对ArrayBlockingQueue的相关操作的时间复杂度，可以参考循环队列进行分析。

 

2.LinkedBlockingQueue

        一种通过链表实现的阻塞队列，支持先进先出。队列的头部是队列中保持时间最长的元素，队列的尾部是保持时间最短的元素。新元素插入队列的尾部。可选的容量设置可以有效防止队列过于扩张造成系统资源的过多消耗，如果不指定队列容量，队列默认使用Integer.MAX_VALUE。LinkedBlockingQueue的特定是，支持无限（理论上）容量。

 

3.PriorityBlockingQueue

        PriorityBlockingQueue是一种基于优先级进行排队的*队列。队列中的元素按照其自然顺序进行排列，或者根据提供的Comparator进行排序，这与构造队列时，提供的参数有关。

        使用提取方法时，队列将返回头部，具有最高优先级（或最低优先级，这与排序规则有关）的元素。如果多个元素具有相同的优先级，则同等优先级间的元素获取次序无特殊说明。

       优先级队列使用的是一种可扩展的数组结构，一般可以认为这个队列是*的。当需要新添加一个元素时，如果此时数组已经被填满，优先队列将会自动扩充当前数组（一般认为是，先分配一个原数组一定倍数空间的数组，之后将原数组中的元素拷贝到新分配的数组中，释放原数组的空间）。

       如果使用优先级队列的iterator变量队列时，不保证遍历次序按照优先级大小进行。因为优先级队列使用的是堆结构。如果需要按照次序遍历需要使用Arrays.sort(pq.toArray())。

       在PriorityBlockingQueue的实现过程中聚合了PriorityQueue的一个实例，并且优先队列的操作完全依赖与PriorityQueue的实现。在PriorityQueue中使用了一个一维数组来存储相关的元素信息。一维数组使用最小堆算法进行元素添加。

 

4.DelayQueue

       一个*阻塞队列，只有在延时期满时才能从中提取元素。如果没有元素到达延时期，则没有头元素。

 

 

二、并发集合

       在多线程程序中使用的集合类，与普通程序中使用的集合类是不同的。因为有可能多个线程同时访问或修改同一集合，如果使用普通集合，很可能造成相应操作出现差错，甚至崩溃。Java提供了用于线程访问安全的集合。

 

1.ConcurrentMap

        ConcurrentMap接口在Map接口的基础上提供了一种线程安全的方法访问机制。ConcurrentMap接口额外提供了多线程使用的四个方法，这四个方法实际是对Map已有方法的一个组合，并对这种组合提供一种原子操作。

        包含ConcurrentNavigableMap<K,V>  子接口，ConcurrentHashMap, ConcurrentSkipListMap两个实现类。

 

2.ConcurrentSkipListSet

        一个基于 ConcurrentSkipListMap 的可缩放并发 NavigableSet 实现。set 的元素可以根据它们的自然顺序进行排序，也可以根据创建 set 时所提供的 Comparator 进行排序，具体取决于使用的构造方法。

 

3.CopyOnWriteArrayList ，CopyOnWriteArraySet

        CopyOnWriteArrayList是ArrayList的一个线程安全的变体，其中对于所有的可变操作都是通过对底层数组进行一次新的复制来实现的。

       由于可变操作需要对底层的数据进行一次完全拷贝，因此开销一般较大，但是当遍历操作远远多于可变操作时，此方法将会更有效，这是一种被称为“快照”的模式，数组在迭代器生存期内不会发生更改，因此不会产生冲突。创建迭代器后，迭代器不会反映列表的添加、移除或者更改。CopyOnWriteArraySet与CopyOnWriteArrayList相似，只不过是Set类的一个变体。

 

4.Collections线程封装

       Collections提供了synchronizedCollection、synchronizedList、synchronizedMap、

synchronizedSet、synchronizedSortedMap、synchronizedSortedMap等方法可以完成多种集合的线程安全的包装，如果在并发度不高的情况下，可以考虑使用这些包装方法，不过由于Concurrent相关的类的出现，已经不这么提倡使用这些封装了，这些方法有些人称他们为过时的线程安全机制。

 

总结

         提供线程安全的集合简单概括分为三类，首先，对于并发性要求很高的需求可以选择以Concurrent开头的相应的集合类，这些类主要包括ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentSkipListMap、ConcurrentSkipSet。其次对于可变操作次数远远小于遍历的情况，可以使用CopyOnWriteArrayList和CopyOnWriteArraySet类。最后，对于并发规模比较小的并行需求可以选择Collections类中的相应方法对已有集合进行封装。