转载

Java并发数据结构 — 并发List

前言

由于并行程序与串行程序的不同特点，适用于串行程序的一些数据结构可能无法直接在并发环境下正常工作，这是因为这些数据结构不是线程安全的，所以特意集中学习了下关于并发环境下关于List、Set、Map有哪些常用的安全数据结构，这一片文章记录并发List的学习内容。

安全的List实现

1.Vector
2.Collections.synchronizedList(List<T> list) ；
3.CopyOnWriteArrayList（主要来看它）

并发List之CopyOnWriteArrayList

Vector或者CopyOnWriteArrayList是两个线程安全的List实现。ArrayList不是线程安全的，因为，应该尽量避免在多线程环境下使用ArrayList。如果因为某些原因必须使用，也应该使用下面这种包装方式：

List<String> selfList = Collections.synchronizedList(new ArrayList<>());

CopyOnWriteArrayList的内部实现与Vector又有所不同。从定义上可以看出来Copy-On-Write就是CopyOnWriteArrayList的实现机制。即当对象进行写操作时，复制该对象；若是读操作，则直接返回结构，操作过程中不进行同步。 CopyOnWriteArrayList 很好的利用了对象的不变性，在没有对对象进行写操作前，由于对象未发生改变，因此不需要加锁。而在试图改变对象时，总是先获取对象的一个副本，然后对副本进行修改，最后将副本写回。这种实现方式的核心思想是实现锁竞争，从而提高在高并发是的读取性能，但是他却在一定程度上牺牲了写的性能。进一步深入CopyOnWriteArrayList的源码。其get()方法的实现：

public E get(int index) {
        return elementAt(getArray(), index);
    }

static <E> E elementAt(Object[] a, int index) {
        return (E) a[index];
    }

可以看出，作为一个线程安全的实现，CopyOnWriteArrayList的get()方法并没有任何锁操作, 读的时候不需要加锁，如果读的时候有多个线程正在向ArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的ArrayList。而对比Vector的get实现：

 public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
    }

 E elementData(int index) {
        return (E) elementData[index];
    }

Vector使用了同步关键字，所有的get（）操作都必须先获取到对象多才能进行。在高并发情况下，大量的锁竞争会拖累系统性能。其add()方法的实现：

final transient Object lock = new Object();

public boolean add(E e) {
        synchronized (lock) {
            Object[] es = getArray();
            int len = es.length;
            es = Arrays.copyOf(es, len + 1);
            es[len] = e;
            setArray(es);
            return true;
        }
    }

可以发现在添加的时候需要加锁，否则多线程写的时候会Copy出N个副本出来,因此写的性能显然不好。还有其他的一些remove、clear、clone、contains等和ArrayList用法基本一致，感兴趣可以自己去看下，对比下于ArrayList有什么不同。关于CopyOnWriteArrayList的读写实现也都比较简单，下面以一个例子来看看它的应用场景吧。

CopyOnWriteArrayList的应用场景

本片的主题是并发安全List，所以其主要使用于并发多线程对List有读写操作的场景下。比如有一个流量监控系统，其中有一个功能是要统计今日的访问IP，这显然是一个并发场景，因为同一个时间点可能有多个访问进来，为了保证统计结果的准确行可以考虑使用CopyOnWriteArrayList来存储ip数据：

/**
 * @Author: 王琦 <QQ.Eamil>1124602935@qq.com</QQ.Eamil>
 * @Date: 2019-4-29 0029 23:04
 * @Description: 流量平台IP统计
 */
public class DataMonitorService {

    /**
     * 流量统计，IP监控列表
     */
    private static CopyOnWriteArrayList<String> MONITOR_IP = new CopyOnWriteArrayList();

    /**
     * 是否在监控中
     */
    public static boolean isMonitor(String ip){
        return MONITOR_IP.contains(ip) ? true : false;
    }

    /**
     *  获取最新一个ip
     */
    public static String lastIp(){
        return MONITOR_IP.get(MONITOR_IP.size()-1);
    }

    /**
     * 添加至监控列表
     */
    public static void addMonitor(String ip){
        if (!isMonitor(ip)) {
            MONITOR_IP.add(ip);
        }
    }
}