Java中的集合和线程安全
通过java指南我们知道java集合框架（collection framework）如何为并发服务，我们应该如何在单线程和多线程中使用集合（collection）。
话题有点高端，我们不是很好理解。所以，我会尽可能的描述的简单点。通过这篇指南，你将会对java集合由更深入的了解，而且我敢保证，这会对你的日常编码非常有用。
1. 为什么大多数的集合类不是线程安全的？
你注意到了吗？为什么多数基本集合实现类都不是线程安全的？比如：arraylist, linkedlist, hashmap, hashset, treemap, treeset等等。事实上，所有的集合类（除了vector和hashtable以外）在java.util包中都不是线程安全的，只遗留了两个实现类（vector和hashtable）是线程安全的为什么？
原因是：线程安全消耗十分昂贵！
你应该知道，vector和hashtable在java历史中，很早就出现了，最初的时候他们是为线程安全设计的。（如果你看了源码，你会发现这些实现类的方法都被synchronized修饰）而且很快的他们在多线程中性能表现的非常差。如你所知的，同步就需要锁，有锁就需要时间来监控，所以就降低了性能。
这就是为什么新的集合类没有提供并发控制，为了保证在单线程中提供最大的性能。
下面测试的程序验证了vector和arraylist的性能，两个相似的集合类（vector是线程安全，arraylist非线程安全）
import java.util.*;
/**
* this test program compares performance of vector versus arraylist
* @author www.codejava.net
*
*/
public class collectionsthreadsafetest {
public void testvector() {
long starttime = system.currenttimemillis();
vector<integer> vector = new vector<>();
for (int i = 0; i < 10_000_000; i++) {
vector.addelement(i);
}
long endtime = system.currenttimemillis();
long totaltime = endtime - starttime;
system.out.println("test vector: " + totaltime + " ms");
}
public void testarraylist() {
long starttime = system.currenttimemillis();
list<integer> list = new arraylist<>();
for (int i = 0; i < 10_000_000; i++) {
list.add(i);
}
long endtime = system.currenttimemillis();
long totaltime = endtime - starttime;
system.out.println("test arraylist: " + totaltime + " ms");
}
public static void main(string[] args) {
collectionsthreadsafetest tester = new collectionsthreadsafetest();
tester.testvector();
tester.testarraylist();
}
}
通过为每个集合添加1000万个元素来测试性能，结果如下：
test vector: 9266 ms test arraylist: 4588 ms
如你所看到的，在相当大的数据操作下，arraylist速度差不多是vector的2倍。你也拷贝上述代码自己感受下。
2.快速失败迭代器（fail-fast iterators）
在使用集合的时候，你也要了解到迭代器的并发策略：fail-fast iterators
看下以后代码片段，遍历一个string类型的集合：
list<string> listnames = arrays.aslist("tom", "joe", "bill", "dave", "john");
iterator<string> iterator = listnames.iterator();
while (iterator.hasnext()) {
string nextname = iterator.next();
system.out.println(nextname);
}
这里我们使用了iterator来遍历list中的元素，试想下listnames被两个线程共享：一个线程执行遍历操作，在还没有遍历完成的时候，第二线程进行修改集合操作（添加或者删除元素），你猜测下这时候会发生什么？
遍历集合的线程会立刻抛出异常“concurrentmodificationexception”，所以称之为：快速失败迭代器（随便翻的哈，没那么重要，理解就ok）
为什么迭代器会如此迅速的抛出异常？
因为当一个线程在遍历集合的时候，另一个在修改遍历集合的数据会非常的危险：集合可能在修改后，有更多元素了，或者减少了元素又或者一个元素都没有了。所以在考虑结果的时候，选择抛出异常。而且这应该尽可能早的被发现，这就是原因。（反正这个答案不是我想要的~）
下面这段代码演示了抛出：concurrentmodificationexception
import java.util.*;
/**
* this test program illustrates how a collection's iterator fails fast
* and throw concurrentmodificationexception
* @author www.codejava.net
*
*/
public class iteratorfailfasttest {
private list<integer> list = new arraylist<>();
public iteratorfailfasttest() {
for (int i = 0; i < 10_000; i++) {
list.add(i);
}
}
public void runupdatethread() {
thread thread1 = new thread(new runnable() {
public void run() {
for (int i = 10_000; i < 20_000; i++) {
list.add(i);
}
}
});
thread1.start();
}
public void runiteratorthread() {
thread thread2 = new thread(new runnable() {
public void run() {
listiterator<integer> iterator = list.listiterator();
while (iterator.hasnext()) {
integer number = iterator.next();
system.out.println(number);
}
}
});
thread2.start();
}
public static void main(string[] args) {
iteratorfailfasttest tester = new iteratorfailfasttest();
tester.runiteratorthread();
tester.runupdatethread();
}
}
如你所见，在thread1遍历list的时候，thread2执行了添加元素的操作，这时候异常被抛出。
需要注意的是，使用iterator遍历list，快速失败的行为是为了让我更早的定位问题所在。我们不应该依赖这个来捕获异常，因为快速失败的行为是没有保障的。这意味着如果抛出异常了，程序应该立刻终止行为而不是继续执行。
现在你应该了解到了concurrentmodificationexception是如何工作的，而且最好是避免它。
同步封装器
至此我们明白了，为了确保在单线程环境下的性能最大化，所以基础的集合实现类都没有保证线程安全。那么如果我们在多线程环境下如何使用集合呢？
当然我们不能使用线程不安全的集合在多线程环境下，这样做会导致出现我们期望的结果。我们可以手动自己添加synchronized代码块来确保安全，但是使用自动线程安全的线程比我们手动更为明智。
你应该已经知道，java集合框架提供了工厂方法创建线程安全的集合，这些方法的格式如下：
collections.synchronizedxxx(collection)
这个工厂方法封装了指定的集合并返回了一个线程安全的集合。xxx可以是collection、list、map、set、sortedmap和sortedset的实现类。比如下面这段代码创建了一个线程安全的列表：
list<string> safelist = collections.synchronizedlist(new arraylist<>());
如果我们已经拥有了一个线程不安全的集合，我们可以通过以下方法来封装成线程安全的集合：
map<integer, string> unsafemap = new hashmap<>(); map<integer, string> safemap = collections.synchronizedmap(unsafemap);
如你锁看到的，工厂方法封装指定的集合，返回一个线程安全的结合。事实上接口基本都一直，只是实现上添加了synchronized来实现。所以被称之为：同步封装器。后面集合的工作都是由这个封装类来实现。
提示：
在我们使用iterator来遍历线程安全的集合对象的时候，我们还是需要添加synchronized字段来确保线程安全，因为iterator本身并不是线程安全的，请看代码如下：
list<string> safelist = collections.synchronizedlist(new arraylist<>());
// adds some elements to the list
iterator<string> iterator = safelist.iterator();
while (iterator.hasnext()) {
string next = iterator.next();
system.out.println(next);
}
事实上我们应该这样来操作：
synchronized (safelist) {
while (iterator.hasnext()) {
string next = iterator.next();
system.out.println(next);
}
}
同时提醒下，iterators也是支持快速失败的。
尽管经过类的封装可保证线程安全，但是他们依然有着自己的缺点，具体见下面部分。
并发集合
一个关于同步集合的缺点是，用集合的本身作为锁的对象。这意味着，在你遍历对象的时候，这个对象的其他方法已经被锁住，导致其他的线程必须等待。其他的线程无法操作当前这个被锁的集合，只有当执行的线程释放了锁。这会导致开销和性能较低。
这就是为什么jdk1.5+以后提供了并发集合的原因，因为这样的集合性能更高。并发集合类并放在java.util.concurrent包下，根据三种安全机制被放在三个组中。
第一种为：写时复制集合：这种集合将数据放在一成不变的数组中；任何数据的改变，都会重新创建一个新的数组来记录值。这种集合被设计用在，读的操作远远大于写操作的情景下。有两个如下的实现类：copyonwritearraylist 和 copyonwritearrayset.
需要注意的是，写时复制集合不会抛出concurrentmodificationexception异常。因为这些集合是由不可变数组支持的，iterator遍历值是从不可变数组中出来的，不用担心被其他线程修改了数据。第二种为：比对交换集合也称之为cas（compare-and-swap）集合：这组线程安全的集合是通过cas算法实现的。cas的算法可以这样理解：
为了执行计算和更新变量，在本地拷贝一份变量，然后不通过获取访问来执行计算。当准备好去更新变量的时候，他会跟他之前的开始的值进行比较，如果一样，则更新值。
如果不一样，则说明应该有其他的线程已经修改了数据。在这种情况下，cas线程可以重新执行下计算的值，更新或者放弃。使用cas算法的集合有：concurrentlinkedqueue and concurrentskiplistmap.
需要注意的是，cas集合具有不连贯的iterators，这意味着自他们创建之后并不是所有的改变都是从新的数组中来。同时他也不会抛出concurrentmodificationexception异常。第三种为：这种集合采用了特殊的对象锁（java.util.concurrent.lock.lock）：这种机制相对于传统的来说更为灵活，可以如下理解：
这种锁和经典锁一样具有基本的功能，但还可以再特殊的情况下获取：如果当前没有被锁、超时、线程没有被打断。
不同于synchronization的代码,当方法在执行，lock锁一直会被持有，直到调用unlock方法。有些实现通过这种机制把集合分为好几个部分来提供并发性能。比如：linkedblockingqueue，在队列的开后和结尾，所以在添加和删除的时候可以同时进行。
其他使用了这种机制的集合有：concurrenthashmap 和绝多数实现了blockingqueue的实现类
同样的这一类的集合也具有不连贯的iterators，也不会抛出concurrentmodificationexception异常。
我们来总结下今天我们所学到的几个点：
- 大部分在java.util包下的实现类都没有保证线程安全为了保证性能的优越，除了vector和hashtable以外。
- 通过collection可以创建线程安全类，但是他们的性能都比较差。
- 同步集合既保证线程安全也在给予不同的算法上保证了性能，他们都在java.util.concurrent包中。
翻译来自：