Android 多线程探索（四）— 同步集合
前言
Android JDK 提供了一系列线程安全的集合，避免多线程环境下由于线程安全导致的各种问题。
一、程序之中的优化策略 — CopyOnWriteArrayList
Copy - On - Write 是一种用于程序设计中的优化策略，其基本思路是：从多个线程共享同一个列表，当某个线程想要修改这个列表的元素时，会把列表中的元素 Copy 一份，然后进行修改，修改完成之后再将新的元素设置给这个列表，这是一种延时懒惰策略。这样做的好处是我们可以对 CopyOnWrite 容器进行并发的读、而不需要加锁，因为当前容器不会添加、移除任何元素。所以，CopyOnWrite 容器也是一种读写分离的思想，读和写不同的容器。
以下代码是向 CopyOnWriteArrayList 中 add 方法的实现：
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (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();
}
}
添加完元素之后，直接让列表的内部数组成员指向新的数组。
/**
* Sets the array.
*/
final void setArray(Object[] a) {
array = a;
}
从上述程序可以发现，在添加的时候进行了加锁操作，否则多线程写的时候会 Copy 出 N 个副本出来。复制一份之后将新的元素设置到元素数组的 len 位置，然后再把最新的元素数组设置给该列表。
读的时候不需要加锁，如果读的时候有多个线程正在向 CopyOnWriteArrayList 添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的元素数组。读的代码如下：
public E get(int index) {
return get(getArray(), index);
}
通过这种写时拷贝的原理可以将读、写分离，使并发场景下对列表的操作效率得到提高，但它的问题是，在添加、移除元素时占用的内存空间翻了一倍，因此，这是以空间换时间，相似的列表还有 CopyOnWriteArraySet。
二、提高并发效率 — ConcurrentHashMap
我们知道，HashTable 是 HashMap 的线程安全实现，但 HashTable 容器使用 synchronized 来保证线程安全，在线程竞争激烈的情况下，HashTable 的效率非常低下。因为，当一个线程访问 HashTable 的同步方法时，其他线程访问 HashTable 的同步方法可能会进入阻塞或轮询状态。如线程 1 使用 put 进行添加元素，线程 2 不但不能使用 put 方法添加元素，并且也不能使用 get 方法来获取元素，所以竞争越激励效率越低。
究其原因是因为，所有访问 HashTable 的线程都必须竞争同一把锁，假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效地提高并发访问效率，这就是 ConcurrentHashMap 所使用的锁分段技术。该技术首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个数据段时，其他段的数据也能被其他线程访问。有些方法需要跨段，如 size() 和 containsValue()，它们可能需要锁定整个表而不仅是某个段，这需要按顺序锁定所有段，操作完成之后，又按顺序释放所有段的锁。
三、有效的方法 — BlockingQueue
阻塞队列为用户提供了一些有用的特性，例如，当队列满了时，再次调用 put 函数添加元素，那么调用线程将会阻塞，直到队列不再是填满状态。这个特性很有用，它就是生产者 — 消费者的一个实现，当我们需要这类的功能时直接使用 BlockingQueue 即可，避免了手动判断以及同步操作。
| 函数名 | 作用 |
|---|---|
add(e) |
把元素 e 加到 BlockingQueue 里，如果 BlockingQueue 可以容纳，则返回 true，否则抛出异常 |
offer(e) |
把元素 e 加到 BlockingQueue 里，如果 BlockingQueue 可以容纳，则返回 true，否则返回 false
|
offer(e,time,unit) |
把元素 e 加到 BlockingQueue 里，如果 BlockingQueue 可以容纳，则返回 true，否则在等待指定的时间之后继续尝试添加，如果失败则返回 false
|
put(e) |
把元素 e 加到 BlockingQueue 里，如果 BlockingQueue 不能容纳，则调用此方法的线程被阻塞直到 BlockingQueue 里面有空间再继续添加 |
take() |
取走 BlockingQueue 里排在队首的对象，若 BlockingQueue 为空，则进入等待状态直到 BlockingQueue 有新的对象被加入为止 |
poll(time,unit) |
取走并移除队列中队首元素，如果设定的阻塞时间内还没有获得数据，那么返回 null
|
element() |
获取队首元素，如果队列为空，那么抛出 NoSuchElementException 异常 |
peek() |
获取队首元素，如果队列为空，那么返回 null
|
remove() |
获取并移除队首元素，如果队列为空，那么抛出 NoSuchElementException 异常 |
BlockingQueue 在 Android JDK 中有多个实现：
-
ArrayBlockingQueue：基于数组实现的、线程安全的、有界的阻塞队列。ArrayBlockingQueue内部通过“互斥锁”保护竞争资源，实现了多线程对竞争资源的互斥访问。有界，是指ArrayBlockingQueue对应的数组是有界限的。阻塞队列，是指多线程访问竞争资源时，当竞争资源已被某线程获取时，其他要获取该资源的线程需要阻塞等待。而且，ArrayBlockingQueue是按FIFO（先进先出）原则对元素进行排序，元素都是从尾部插入到队列，从头部开始返回。 -
LinkedBlockingQueue：它是一个单向链表实现的阻塞队列。该队列按FIFO（先进先出）排序元素，新元素插入到队列的尾部，并且队列获取操作会获得位于队列头部的元素。链接队列的吞吐量通常高于基于数组的队列，但是，在大多数并发应用程序中，其可预知的性能要低。 -
LinkedBlockingDeque：它是由双向链表实现的双向并发阻塞队列。该阻塞队列同时支持FIFO和FILO两种操作方式，即可以从队列的头和尾同时操作（插入/删除），并且，该阻塞队列是支持线程安全的。此外，LinkedBlockingDeque还可以选容量（防止过度膨胀），即可以指定队列的容量。如果不指定，默认容量大小等于Integer.MAX_VALUE。
与 LinkedBlockingQueue 类似的还有 ConcurrentLinkedQueue。ConcurrentLinkedQueue 是一个基于链接结点的无界线程安全队列，它采用先进先出的规则对结点进行排序，当添加一个元素时，它会添加到队列的尾部，当获取一个元素时，它会返回队列头部的元素。
这里需要温习一下的就是，双向链表相对于单向链表的优缺点：
-
优点：对于双向链表中的任意一个结点，可以从两个方向进行操作，在单向链表中，只有获得结点的前驱结点的指针，才能删除该结点。而在双向链表中，因为每个结点都有指向前驱结点的指针，所以不必记录前驱结点的地址也能进行删除操作。
-
缺点：每个结点多出了一个额外的指向前驱结点地址的指针，需要更多的空间开销，另外，对于结点的插入或者删除需要操作更多的指针。
