并发编程集合

本文将介绍同步编程领域中的集合。

一、线程不安全的集合

很多集合都不是线程安全的，例如常用的 ArrayList、HashMap。

二、同步集合

1. 手工包装

可以书写一个包装类，将集合封装在内部，在其访问路径上做好并发控制，如下：

SafeArrayList<T> {

  	List<T> c = new ArrayList<>();


  	synchronized T get(int idx){
    	return c.get(idx);
  	}

  	synchronized void add(int idx, T t) {
    	c.add(idx, t);
  	}

  	synchronized boolean addIfNotExist(T t){
    	if(!c.contains(t)) {
      		c.add(t);
      		return true;
    	}
    	return false;
  	}
}

2. 快捷包装

Collections 类中提供了快捷包装方法，如下：

1
2
3

List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());
Map map = Collections.synchronizedMap(new HashMap());

3. Java 提供的同步集合

Java 提供了 Vector、Stack 和 Hashtable 等同步集合。

4. 性能问题

同步集合的性能较差，其原因是使用了 synchronized 作为控制并发访问的手段，而 synchronized 将会对整个对象加锁，锁的粒度太大。

5. 线程安全问题

同步集合只能保证它提供的操作是线程安全的，并不能保证由它提供的操作所构成的操作是线程安全的。

例如：

void ergodic(List list) {
	List synchronizedList = Collections. synchronizedList(list);
    Iterator i = synchronizedList.iterator();
    while (i.hasNext()) {
        foo(i.next());
    }
}

其中，操作 i.hasNext() 是线程安全的、操作 i.next() 是线程安全的，但由两个命令所构成的操作并不是线程安全的。

如果希望保证线程安全，应该：

void ergodic(List list) {
	List synchronizedList = Collections. synchronizedList(list);
    synchronized (synchronizedList) {
    	Iterator i = synchronizedList.iterator();
        while (i.hasNext()) {
            foo(i.next());
        }
    }
}

三、并发集合

1. 说明

并发容器由 JUC 提供，性能更好。

并发容器关系图如下：

2. List - CopyOnWriteArrayList

(1) Copy-on-Write

具体请看：

编程思想 Copy-on-Write

(2) 内部结构

CopyOnWriteArrayList 会在内部维护一个数组，用于存放集合内元素。

(3) 写操作的进行方式

假如发生写操作，CopyOnWriteArrayList 会将数组复制一份，在新数组上执行写操作，原有的数组继续执行读操作，待写操作执行完成后，将数组指针指向新数组。

(4) 使用场景

CopyOnWriteArrayList 适用于写操作较少，且能够容忍读写的短暂不一致的场景。

并且，CopyOnWriteArrayList 中的数据也不应放置过多，否则每次复制数组时代价过高。

3. Map - ConcurrentHashMap

具体请看：

并发编程 ConcurrentHashMap

4. ConcurrentSkipListMap

ConcurrentHashMap 和 ConcurrentSkipListMap 的区别在于，ConcurrentSkipListMap 的 key 是有序的。

ConcurrentSkipListMap 的底层数据结构是跳表，其操作复杂度为 O(log n)，理论上不会因并发线程数的增大而影响性能。当并发度较高时，可以使用 ConcurrentSkipListMap。

关于跳表，具体请看：

数据结构跳表

5. Queue

可以将这些 Queue 划分为：

阻塞：当队列已满时，入队操作阻塞；当队列为空时，出队操作阻塞
非阻塞：当队列已满时，入队操作返回失败；当队列为空时，出队操作返回 null

参考

Java 并发编程实战

开发 JAVA 并发编程 JUC

并发编程 ConcurrentHashMap 上一篇

编程思想 Copy-on-Write 下一篇

并发编程 集合