算法与数据结构（3），并发结构
本来已经合上电脑了，躺在床上，翻来覆去睡不着，索性，不睡了，起床，听听歌，更新简书，这可能是这一系列的最后一篇，脚趾的伤也好的差不多了，下个礼拜就要全身心找工作了。
并发List
Vector和CopyOnWriteArrayList是两个线程安全的List实现ArrayList不是线程安全的。因此，应该尽量避免在多线程环境中使用ArrayList。如果因为某些原因必须，则需要使用Collections.synchronizedList( )进行包装。
CopyOnWriteArrayList的内部实现与Vector不同，从字面中可以看出Copy-On-Write就是CopyOnWriteArrayList的实现机制。即当对象进行写操作时，复制该对象；若进行的时读操作，则直接返回结果，操作过程中不进行同步。
CopyOnWriteArrayList很好利用了对象的不变性，在没有对象进行写操作之前由于对象未发生改变，因此不需要加锁。而在视图改变对象时，总是先获取对象的一个副本，然后对副本进行修改，最后将副本写回。
这种实现方式的核心思想是减少锁竞争，从而提高并发时的读取性能，但是它却一定程度上牺牲了写的性能。
get( )方法如下：
/** The array, accessed only via getArray/setArray. */
private volatile transient Object[] array;//内置数组被关键字volatile修饰
/**
* {@inheritDoc}
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
return get(getArray(), index);
}
/**
* Gets the array. Non-private so as to also be accessible
* from CopyOnWriteArraySet class.
*/
final Object[] getArray() {
return array;
}
可以看到，作为一个线程安全的实现，CopyOnWriteArrayList的get( )没有任何锁操作，而对比Vector的get( )实现：
/**
* Returns the element at the specified position in this Vector.
*
* @param index index of the element to return
* @return object at the specified index
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
* @since 1.2
*/
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
Vector使用了同步关键字synchronized所有的get( )操作都必须先等待对象锁的释放，才能进行。在高并发的情况下，大量的锁竞争会降低系统性能。
虽然CopyOnWriteArrayList的读操作性能优越，但是，基于CopyOnWriteArrayList的写操作却不能尽如人意。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
final ReentrantLock lock = this.lock; //使用了锁
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); //进行一次内置数组的复制
newElements[len] = e; //修改副本
setArray(newElements); //写回副本
return true;
} finally {
lock.unlock();
}
}
在每一次add( )方法中，CopyOnWriteArrayList都进行一次自我复制，同时add( )操作也申请了锁，并不像get( )那样。相对的，Vector的add( )方法则要快捷的多。
/**
* Appends the specified element to the end of this Vector.
*
* @param e element to be appended to this Vector
* @return {@code true} (as specified by {@link Collection#add})
* @since 1.2
*/
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1); //内置数组是否需要扩容
elementData[elementCount++] = e;
return true;
}
因此，在高并发且以读为主的应用场景中，CopyOnWriteArrayList要优于Vector。但是当写操作很频繁时，CopyOnWriteArrayList的效率并不高，可以考虑优先使用Vector。
并发Map
在多线程环境中使用Map，一般也可以使用Collections.synchronizedMap( )进行包装。
但是在高并发情况下，这个Map的性能表示不是最优的。因为被包装后的Map，在进行读写操作时都要等待锁的释放。
在高并发的环境中，可以使用ConcurrentHashMap，写操作的效率比同步HashMap快了将近一倍，ConcurrentHashMap之所以有如此之高的吞吐量，得益于其内部实现了锁桶的锁分离机制，在读写整张Entry数组表的时候，不需要像HashMap那样锁住整张表，而是只锁当前需要用到的桶，原来只能一个线程进入，现在却能同时16（默认16个桶）个写线程进入，并发性的提升是显而易见的。同时，ConcurrentHashMap的get( )操作是无锁的。这些都为ConcurrentHashMap在多线程并发下的高性能提供了保证。
ConcurrentHashMap是专门为线程设计的HashMap。它的get( )操作时无锁的，它的put( )操作的锁粒度又小于同步HashMap。因此它的整体性能优于同步的HashMap。
并发Queue
Queue是一种特殊的线性结构队列，只允许从队列的头部移除元素，或者从队列的尾端添加元素，以一种FIFO（先进先出）的方式管理数据。
add( )，和remove( )方法。
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full"); //队列已满，抛出异常
}
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException(); //队列为空，抛出异常
}
由此可见，应该尽量避免使用add( )，和remove( )方法。而使用offer( )来加入元素，使用poll( )来获取并移出元素。
并发队列，有两种实现，一个是以ConcurrentLinkedQueue为代表的高性能队列，一个是以BlockingQueue为代表的阻塞队列。
ConcurrentLinkedQueue是一个适用于高并发场景下的队列。它通过无锁方式，实现了高并发状态下的高性能。
与ConcurrentLinkedQueue相比BlockingQueue的主要功能不是在于提升高并发时的队列功能，而在于简化多线程间的数据共享。
BlockingQueue的典型使用场景是生产-消费者模式中，生产者总是将产品放入BlockingQueue队列中，而消费者从队列中取出产品消费，从而实现数据共享。
BlockingQueue提供一种读写阻塞等待的机制，即如果消费者速度过快，则BlockingQueue可能被清空，此时，消费线程再试图从BlockingQueue读取数据时就会被阻塞。反之，如果生产线程过快，则BlockingQueue可能会被装满，此时，生产线程再试图向BlockingQueue队列中装入数据时，便会阻塞等待。
BlockingQueue的工作模式
BlockingQueue提供了两种主要实现：
-
ArrayBlockingQueue：它是一种基于数组的阻塞队列实现，在ArrayBlockingQueue内部还维护了一个定长的数组，用于缓存队列中的数据对象。此外，ArrayBlockingQueue内部还存着两个整型变量，分别标识着队列头部和尾部在数组中的位置。
-
LinkedBlockingQueue：这是一个基于链表的阻塞队列，ArrayBlockingQueue类似，内部也维持着一个数据缓冲队列（该队列由一个链表构成），当生产者往队列中放入一个数据时，队列会从生产者手中获取数据，并缓存在队列内部，而生产者立即返回；只有当队列缓冲区达到最大值缓存容量时，才会阻塞生产者队列，直到消费者从队列中消费掉一个数据，生产者线程才能被唤醒。
并发Deque
Deque是一种双端队列，允许在队列的头部或者尾部进行出队和入队操作。
由于Deque这个接口日常工作中很少用到，这里只做简单介绍。
LinkedList，ArrayDeque和LinkedBlockingDeque都实现了Deque接口。其中，LinkedList使用链表实现了双端队列，ArrayDeque使用数组实现了双端队列。通常情况下ArrayDeque是基于数组实现的，所以拥有高效的随机访问性能，因此ArrayDeque具有更好的遍历性。但是当队列大小变化较大时，ArrayDeque需要重新分配内存并进行数组复制，在这种情况下，基于链表的LinkedList没有内存调整和数组复制的负担，性能表现会较好。但是，无论，ArrayDeque还是LinkedList，他们都不是线程安全的。
在AsyncTask的源代码中
private static class SerialExecutor implements Executor {
final ArrayDeque<Runnable> mTasks = new ArrayDeque<Runnable>();
Runnable mActive;
/*ArrayDeque不是线程安全的，execute需要用关键字synchronized 修饰*/
public synchronized void execute(final Runnable r) {
mTasks.offer(new Runnable() {
public void run() {
try {
r.run();
} finally {
scheduleNext();
}
}
});
if (mActive == null) {
scheduleNext();
}
}
protected synchronized void scheduleNext() {
if ((mActive = mTasks.poll()) != null) {
THREAD_POOL_EXECUTOR.execute(mActive);
}
}
}
LinkedBlockingDeque是一个线程安全的双端队列。在内部是现中，LinkedBlockingDeque使用链表结构。每一个队列节点都维护一个前驱节点和一个后驱节点。LinkedBlockingDeque并没有进行读写锁的分离，因此同一时间只能有一个线程对其进行访问。因此，在高并发应用中，它的性能表现要远低于LinkedBlockingQueue，更低于ConcurrentLinkedQueue。
片尾TIP：
private SparseArray<String> sparseArray = new SparseArray<String>();
private SparseIntArray sparseIntArray = new SparseIntArray();
private SparseBooleanArray sparseBooleanArray = new SparseBooleanArray();
private LongSparseArray<String> longSparseArray = new LongSparseArray<String>();
public void Test() {
sparseArray.put(1, "1");
sparseIntArray.put(2, 2);
sparseBooleanArray.put(3, true);
longSparseArray.put(4, "4");
}
使用优化后的数据集合，可以避免掉基本数据类型转换成对象数据类型时浪费的时间。
数据结构这个系列，暂且告一段落，最后，我想把这段话送给大家。
