(七) 线程安全的集合

如果多线程要并发的修改一个数据结构，例如散列表，那么很容易破坏这个数据结构。可以通过锁来保护共享数据结构，但是选择线程安全的实现作为替代可能更容易些。
1.高效的映像、集合和队列
java.util.concurrent包提供了映像、集合和队列的高效实现：
(1)ConcurrentLinkedQueue : 一个基于链接节点的无界线程安全队列。此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部，队列获取操作从队列头部获得元素。当多个线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许使用 null 元素。
(2)ConcurrentHashMap : 支持获取的完全并发和更新的所期望可调整并发的哈希表。并发的散列镜像表默认支持16个写者线程同时执行，如果大于16个，其余的会被阻塞，但没有必要指定更大数目。
(3)ConcurrentSkipListMap : 可缩放的并发 ConcurrentNavigableMap 实现。映射可以根据键的自然顺序进行排序，也可以根据创建映射时所提供的 Comparator 进行排序，具体取决于使用的构造方法。
(4)ConcurrentSkipListSet : 一个基于 ConcurrentSkipListMap 的可缩放并发 NavigableSet 实现。set 的元素可以根据它们的自然顺序进行排序，也可以根据创建 set 时所提供的 Comparator 进行排序，具体取决于使用的构造方法。
这些集合使用复杂的算法，通过允许并发地访问数据结构的不同部分来使竞争极小化。
size方法 : 于大多数集合不同，size方法不必在常量时间内操作。确定这样的集合当前的大小通常需要遍历。
迭代器 : 集合返回弱一致性(weakly consisteut)的迭代器，这意味着迭代器不一定能反映出他们被构造之后的所有的修改。但是它们不会将同一个值返回两次，也不会抛出ConcurrentModificationException异常。与之形成对照的是，集合如果在迭代器构造之后发生改变，java.util包中得迭代器会抛出一个ConcurrentModificationException的异常。

ConcurrentHashMap和ConcurrentSkipListMap类 : 有相应的方法用于原子性的关联插入以及关联删除。
V putIfAbsent(K key, V value) : 该方法自动添加新的关联，前提是原来没有这一关联。对于多线程访问的缓存来说这很有用，确保只有一个线程向缓存添加项。
boolean remove(Object key, Object value) : putIfAbsent的相反操作，将原子性的删除键值对。只有目前将键的条目映射到给定值时，才移除该键的条目。
boolean replace(K key, V oldValue, V newValue) : 原子性的用新值替换旧值，假定旧值与指定的键值关联。只有目前将键的条目映射到给定值时，才替换该键的条目。

类 java.util.concurrent.ConcurrentLinkedQueue<E>
构造 ConcurrentLinkedQueue<E>() : 构造一个可以被多线程安全访问的无边界非阻塞的队列。

类 java.util.concurrent.ConcurrentHashMap<K,V>
构造 ConcurrentHashMap() : 创建一个带有默认初始容量 (16)、加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射。
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) : 创建一个带有指定初始容量、加载因子和并发级别的新的空映射。
initialCapacity : 集合的初始容量，默认为16
loadFactor : 控制调整：如果每一个桶的平均负载超过这个因子，表的大小会被从新调整。默认值为0.75
concurrencyLevel : 并发写者线程的估计数目
 
类 java.util.concurrent.ConcurrentSkipListSet
构造 ConcurrentSkipListSet() : 构造一个新的空 set，该set按照元素的自然顺序对其进行排序。或元素实现comparable接口。
构造 ConcurrentSkipListSet(Comparator<? super E> comparator) : 构造一个新的空set，该set按照指定的比较器对其元素进行排序。

类 java.util.concurrent.ConcurrentSkipListMap<K,V>
构造 ConcurrentSkipListMap() : 构造一个新的空映射，该映射按照键的自然顺序进行排序。
构造 ConcurrentSkipListMap(Comparator<? super K> comparator) : 构造一个新的空映射，该映射按照指定的比较器进行排序。

2.写数组的拷贝
CopyOnWriteArrayList 和 CopyOnWriteArraySet是线程安全的集合。
分析构造
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements = c.toArray();
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elements.getClass() != Object[].class)
        elements = Arrays.copyOf(elements, elements.length, Object[].class);
    setArray(elements);
}
public CopyOnWriteArraySet(Collection<? extends E> c) {
    al = new CopyOnWriteArrayList<E>();
    al.addAllAbsent(c);
}
得到结论：底层数组进行了复制。

3.旧的线程安全的集合
任何集合类通过使用同步包装器(sychronization wrapper)变成线程安全的
List<E> syncArrayList = Collections.synchronizedList(new ArrayList<E>);
Map<K, V) syncHashMap = Collections.synchronizedHashMap(new HashMap<K, V>);

结果集合的方法使用锁加以保护，提供了线程的安全访问
1.确保没有任何线程通过原始的非同步方法访问数据结构，最便利的方法是确保不保存任何指向原始对象的引用，构造一个集合并立即传递给包装器。
2.如果在另一个线程可能进行修改时要对集合进行迭代，仍然需要使用“客户端”封锁。
e.g.synchronized(syncHashMap){
        Iterator<K> iter = syncHashMap.KeySet().iterator();
        while(iter.hasNext()){
            ... ...
        }
    }
for-each必须使用同样地代码，如果在迭代过程中，别的线程修改集合，迭代器会失败，并抛出ConcurrentModificationException异常。
最好使用java.util.concurrent包中定义的集合，不使用同步包装器中得。有一个例外是经常被修改的列表，在那种情况下同步的ArrayList可以胜过CopyOnWriteArrayList。