转载

同步技术新大陆--写时复制技术（CopyOnWriteArrayList、CopyOnWriteArraySet）

写入时复制是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。

2、集合中的写时复制

集合数据主要就两个操作读、写；读是读取内容，写是改变内容；读的时候读取存储资源，写的时候，复制一份修改后再重置原有资源；这样就具有以下特色：

读数据、写数据不会因为非原子操作，导致数据异常
写数据间相互不影响
读数据时，只是当时最新，并不一定是当时操作逻辑中最新
写数据时，最后面写数据会覆盖前面写数据

因此如果要做到线程安全，就必须再写时进行加锁

而CopyOnWriteArrayList集合就是这种写时复制+写时加锁来实现的；CopyOnWriteArraySet内部代理了CopyOnWriteArrayList，进而实现不重复数据的集合；下面就来介绍下CopyOnWriteArrayList

3、CopyOnWriteArrayList集合

list集合，内部采用数组来存储；写时复制，并加锁；直接读数据；

final transient Object lock = new Object();
    private transient volatile Object[] array;
复制代码

lock是对synchronized锁标志，array是资源数组，使用volatile关键字，写操作会再任何线程下次操作资源时可见

3.1 写数据

3.1.1 增加数据

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

synchronized关键字加锁
获取数组资源，并使用Arrays工具类copy数据
再copy数据中加入新数据
把copy数据重新写回

public void add(int index, E element) {
        synchronized (lock) {
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException(outOfBounds(index, len));
            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;
            setArray(newElements);
        }
    }
复制代码

特定索引增加数据，可以任意位置增加数据；

校验索引是否有效，无效抛出异常
分段copy数据，以index为分割线（最开始、最后面一个，可以一段copy完成）
copy数据index位置加入数据
把copy数据重新写回

保证数据不重复，增加数据

public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();
        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
    }

    private boolean addIfAbsent(E e, Object[] snapshot) {
        synchronized (lock) {
            Object[] current = getArray();
            int len = current.length;
            if (snapshot != current) {
                // Optimize for lost race to another addXXX operation
                int common = Math.min(snapshot.length, len);
                for (int i = 0; i < common; i++)
                    if (current[i] != snapshot[i]
                        && Objects.equals(e, current[i]))
                        return false;
                if (indexOf(e, current, common, len) >= 0)
                        return false;
            }
            Object[] newElements = Arrays.copyOf(current, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        }
    }
复制代码

查找待增加的数据的索引
如果索引>= 0 表明存在，进一步处理，如果不存在则结束
加锁重复检查数据是否存在，存在，则结束
不存在，则copy数据，加入copy数据尾；并把copy数据写回

3.1.2 改变数据

public E set(int index, E element) {
        synchronized (lock) {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                setArray(elements);
            }
            return oldValue;
        }
    }
复制代码

改变指定位置数据：

读取指定位置index的数据
如果指定位置数据==要改变数据，则直接写回；
copy原数据，并置换index位置数据，并把copy数据写回

3.1.3 删除指定位置数据

public E remove(int index) {
        synchronized (lock) {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        }
    }
复制代码

加锁，进行copy数据，copy数据时，不包括要删除的数据，把copy数据重置回去

3.1.4 删除指定数据

public boolean remove(Object o) {
        Object[] snapshot = getArray();
        int index = indexOf(o, snapshot, 0, snapshot.length);
        return (index < 0) ? false : remove(o, snapshot, index);
    }

    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 = indexOf(o, current, index, len);
                if (index < 0)
                    return false;
            }
            Object[] newElements = new Object[len - 1];
            System.arraycopy(current, 0, newElements, 0, index);
            System.arraycopy(current, index + 1,
                             newElements, index,
                             len - index - 1);
            setArray(newElements);
            return true;
        }
    }
复制代码

查找数据所在位置
未找到，则不处理
找到位置，则加锁
重新检查数据是否发生变换，若发生变化，则重新查找位置，并检查是否有效，无效则退出
以删除数据位置，分两段进行copy数据，并把copy的数据重置回去

3.1.5 清除数据

public void clear() {
        synchronized (lock) {
            setArray(new Object[0]);
        }
    }
复制代码

加锁，置为空数组

3.2 读数据

很简单的逻辑，获取数据索引位置

public E get(int index) {
        return get(getArray(), index);
    }
    
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
复制代码

还有一些其它方法，比如获取位置索引，集合大小等