Java中的Collections.synchronizedList()和CopyOnWriteArrayList

我们知道ArrayList在多线程的环境下并不是线程安全的，那如果我们需要在多线程的场景下使用连续存储并且数据具有有序性，可直接快速访问元素的集合时，可以使用Collections.synchronizedList()或者CopyOnWriteArrayList替代

Collections.synchronizedList()

Collections.synchronizedList()用于将普通的List转化为线程安全的同步列表。其底层是基于装饰器模式，通过包装将原始列表转换为对其所有操作都添加同步锁，来确保多线程的环境下的安全性

装饰器模式包装List

Collections.synchronizedList()是一个静态方法，调用此方法直接返回同步列表对象。SynchronizedList是一个包装类，其底层维护的依然是普通的List。只是在所有的操作中都添加了同步锁来保证线程安全。

SynchronizedList继承了SynchronizedCollection，拥有父类中的所有属性和方法。SynchronizedCollection中并不是所有方法都添加了同步锁，使用时需谨慎。

以下情况仍然需要手动加锁：

1. 使用迭代器遍历集合时，synchronizedList并没有对迭代器操作添加同步锁，在使用时需要手动添加
2. 其他单个添加同步锁的操作，在单独使用时，是线程安全的。但是组合使用的时候，还是需要用户手动加锁(比如：put-if-absent：这种类似的组合操作，synchronizedList中的方法不能保证一组操作的原子性)

方法

构造方法

提供了两个构造方法，其中一个可以手动添加锁对象。如果不选择手动添加，则默认的是当前创建好的synchronizedList实例对象

    static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {
        private static final long serialVersionUID = -7754090372962971524L;

        final List<E> list;

        //默认锁为当前实例
        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        //手动添加锁
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }
    }

equals和HashCode

        //调用原始list.equals(o)之前添加同步锁
        public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized (mutex) {return list.equals(o);}
        }

        //调用原始list.hashCode()之前添加同步锁
        public int hashCode() {
            synchronized (mutex) {return list.hashCode();}
        }

增删改查

        //在调用原始list方法外层，都用同步锁包裹
        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }

        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }

        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }

        public boolean addAll(int index, Collection<? extends E> c) {
            synchronized (mutex) {return list.addAll(index, c);}
        }

        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }

查找指定元素索引位

        //调用原始list方法外层，使用同步锁包裹
        public int indexOf(Object o) {
            synchronized (mutex) {return list.indexOf(o);}
        }

        public int lastIndexOf(Object o) {
            synchronized (mutex) {return list.lastIndexOf(o);}
        }

截取替换排序 

        public List<E> subList(int fromIndex, int toIndex) {
            synchronized (mutex) {
                return new SynchronizedList<>(list.subList(fromIndex, toIndex),
                                            mutex);
            }
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            synchronized (mutex) {list.replaceAll(operator);}
        }
        @Override
        public void sort(Comparator<? super E> c) {
            synchronized (mutex) {list.sort(c);}
        }

迭代器操作

        //用户需要手动加锁
        public ListIterator<E> listIterator() {
            return list.listIterator(); // Must be manually synched by user
        }

        public ListIterator<E> listIterator(int index) {
            return list.listIterator(index); // Must be manually synched by user
        }

手动加锁

    synchronized (list) {
        Iterator<E> it = list.iterator();
        while (it.hasNext()) {
            // 操作
        }
    }

组合操作

    synchronized (list) {
        if (!list.contains(element)) {
            list.add(element);
        }
    }

CopyOnWriteArrayList

CopyOnWriteArrayList采用的是写时复制的思想，在增删改的操作时(添加同步锁)，复制原始的旧数组进行操作，最后将操作完成的副本替换为原始的数组。读操作直接访问当前数组，无需加锁。

这种设计，在读操作时，无法保证数据是最新的数组数据。可能访问的是旧数据，但能保证数据的最终一致性(每一个线程的写操作都是原子性的，数据不会出现错乱或者意外丢失)。

构造方法

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;


    final transient Object lock = new Object();

    //volatile关键字修饰，多线程间数据可见
    private transient volatile Object[] array;


    final Object[] getArray() {
        return array;
    }

    final void setArray(Object[] a) {
        array = a;
    }

    //构造函数，通过setArray访问array
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }


    //如果传入的是CopyOnWriteArrayList类型的集合，则直接将原数组引用拷贝
    //到新集合，后续写操作由于是复制数组快照，操作后将快照替换为原数组，所以
    //作为传入参数的数组被修改，引用拷贝到es的数组不会受影响
    //如果传入的是其他类型的集合，则会拷贝一个新数据，与原传入的集合不是同一个
    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] es;
        if (c.getClass() == CopyOnWriteArrayList.class)
            es = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            es = c.toArray();
            if (es.getClass() != Object[].class)
                es = Arrays.copyOf(es, es.length, Object[].class);
        }
        setArray(es);
    }

 
    //拷贝一个新数据
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

尾部添加元素

    //在数组尾部添加元素(同步代码块)
    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;
        }
    }

指定位置添加元素

    //指定位置添加元素(同步代码块)
    public void add(int index, E element) {
        synchronized (lock) {
            Object[] es = getArray();
            int len = es.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException(outOfBounds(index, len));
            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(es, len + 1);
            else {
                newElements = new Object[len + 1];
                //分两次复制，第一次为index之前的元素，第二次为index之后的元素，
                //将index索引位空出来放置element
                System.arraycopy(es, 0, newElements, 0, index);
                System.arraycopy(es, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;
            setArray(newElements);
        }
    }

删除指定位置元素

    //删除指定索引位元素
    public E remove(int index) {
        synchronized (lock) {
            Object[] es = getArray();
            int len = es.length;
            E oldValue = elementAt(es, index);
            int numMoved = len - index - 1;
            Object[] newElements;
            //尾部删除，直接复制尾部之前的元素到新数组
            if (numMoved == 0)
                newElements = Arrays.copyOf(es, len - 1);
            //其他部位删除，第一次复制index之前的元素，第二次将index之后的元素前移一位
            else {
                newElements = new Object[len - 1];
                System.arraycopy(es, 0, newElements, 0, index);
                System.arraycopy(es, index + 1, newElements, index,
                                 numMoved);
            }
            setArray(newElements);
            return oldValue;
        }
    }

删除指定元素

    public boolean remove(Object o) {
        Object[] snapshot = getArray();
        int index = indexOfRange(o, snapshot, 0, snapshot.length);
        return index >= 0 && remove(o, snapshot, index);
    }

    //同步代码块中重新获取了原数组信息，与同步代码块之外的snapshot对比
    //(多线程情况下可能数组会被其他线程修改)
    private boolean remove(Object o, Object[] snapshot, int index) {
        synchronized (lock) {
            Object[] current = getArray();
            int len = current.length;
            if (snapshot != current) findIndex: {
                int prefix = Math.min(index, len);
                for (int i = 0; i < prefix; i++) {
                    if (current[i] != snapshot[i]
                        && Objects.equals(o, current[i])) {
                        index = i;
                        break findIndex;
                    }
                }
                if (index >= len)
                    return false;
                if (current[index] == o)
                    break findIndex;
                index = indexOfRange(o, current, index, len);
                if (index < 0)
                    return false;
            }
            Object[] newElements = new Object[len - 1];
            //第一次复制index之前的元素，第二次将index之后的元素前移一位
            System.arraycopy(current, 0, newElements, 0, index);
            System.arraycopy(current, index + 1,
                             newElements, index,
                             len - index - 1);
            setArray(newElements);
            return true;
        }
    }

Vector与Collections.synchronizedList()与CopyOnWriteArrayList