跳至主要內容

05、Java 集合:List 之 CopyOnWriteArrayList

安图新大约 9 分钟

05、Java 集合:List 之 CopyOnWriteArrayList

1.CopyOnWrite

  • Copy-On-Write 简称 COW,是一种用于程序设计中的优化策略。CopyOnWrite 容器即写时复制的容器。通俗的理解是当往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行 Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。这样做的好处是可以对 CopyOnWrite 容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以 CopyOnWrite 容器也是一种读写分离的思想,读和写不同的容器。
  • CopyOnWrite 并发容器用于读多写少的并发场景。
  • 复制用法导致内存占用可能过高。
  • 保证数据最终一致性,无法保证实时一致性。

2.CopyOnWriteArrayList

public class CopyOnWriteArrayList
implements List, RandomAccess, Cloneable, java.io.Serializable

1、

2、 ArrayList 的一个线程安全的变体,其中所有可变操作(add、set 等等)都是通过对底层数组进行一次新的复制来实现的;
3、 内存一致性效果:当存在其他并发 collection 时,将对象放入 CopyOnWriteArrayList 之前的线程中的操作 happen-before 随后通过另一线程从 CopyOnWriteArrayList 中访问或移除该元素的操作;

成员变量

    //非序列化的可重入的互斥锁
    transient final ReentrantLock lock = new ReentrantLock();
    //非序列化且保证可见性的数组
    private volatile transient Object[] array;

构造方法

    /**
     * 创建一个空列表
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

    /**
     * 创建一个按 collection 的迭代器返回元素的顺序包含指定 collection 元素的列表。
     */
    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);
    //给成员变量array数组复制
    setArray(elements);
}

    /**
     * 创建一个保存给定数组的副本的列表。
     */
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length,   Object[].class));
}

int size(): 返回此列表中的元素数。

public int size() {
   return getArray().length;
 }

add 方法:add,addIfAbsent

//将指定元素添加到此列表的尾部。
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    //一直等待直到获取到锁
    lock.lock();
    try {
        Object[] elements = getArray();//获取元素数组
        int len = elements.length;//获取数组长度
        //将数组进行复制生成新数组,长度+1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;//将新增元素e放在列表队尾
        setArray(newElements);//将新数组值替换原数组
        return true;
    } finally {
        lock.unlock();//释放锁
    }
}

    /**
     * 在此列表的指定位置上插入指定元素。
     */
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    //一直等待直到获取锁
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //数组边界检查
        if (index > len || index < 0)
        throw new IndexOutOfBoundsException("Index: "+index+
                            ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)//添加到列表队尾
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            //new一个新的空数组
            newElements = new Object[len + 1];
            //复制原有数组数据(索引为0至index-1)到新数组(从索引0开始)
            System.arraycopy(elements, 0, newElements, 0, index);
            //复制原有数组数据(索引为index-1至最后)到新数组(从索引index开始)
            System.arraycopy(elements, index, newElements, index + 1,
                 numMoved);
        }
        //设置指定索引index元素为element
        newElements[index] = element;
        //将改动后的新数组替换原有数组
        setArray(newElements);
    } finally {
        //释放锁
        lock.unlock();
    }
}

/**
*添加元素(如果不存在)。
*/
public boolean addIfAbsent(E e) {
    final ReentrantLock lock = this.lock;
    //一直等待直到获取锁
    lock.lock();
    try {
        //获取现有数组
        Object[] elements = getArray();
        int len = elements.length;
        //new一个新的空数组,长度+1,为了添加新元素
        Object[] newElements = new Object[len + 1];
        for (int i = 0; i < len; ++i) {
            //判断两个元素对象是否相同
            if (eq(e, elements[i]))//相同,直接退出add方法
                return false; // exit, throwing away copy
            else
                newElements[i] = elements[i];//不相同,进行数组逐个复制
        }
        //元素不存在,将元素放至列表尾部
        newElements[len] = e;
        //将新添加好的数组替换原有数组
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();//释放锁
    }
}

//匹配两个对象是否相同,注意使用的equals
private static boolean eq(Object o1, Object o2) {
    return (o1 == null ? o2 == null : o1.equals(o2));
}

/**
*按照指定 collection 的迭代器返回元素的顺序,将指定 collection 中尚未包含在此列表中的所有元素添加列表的尾部。
*return 添加的元素数量
*/
public int addAllAbsent(Collection<? extends E> c) {
    //将collection转换成数组
    Object[] cs = c.toArray();
    if (cs.length == 0)
        return 0;//collection中无元素,return 添加元素数量为0
    //new新数组
    Object[] uniq = new Object[cs.length];
    final ReentrantLock lock = this.lock;
    //一直等待直到获取锁
    lock.lock();
    try {
        //获取原有数组
        Object[] elements = getArray();
        int len = elements.length;
        //遍历要新增的集合,且排重
        for (int i = 0; i < cs.length; ++i) { // scan for duplicates
        Object e = cs[i];
        //判断要添加的元素e在原有数组是否已存在
        //判断要添加的元素e在临时new的新数组uniq中是否已存在
        //都不存在,则添加元素e至临时new的新数组uniq中
        if (indexOf(e, elements, 0, len) < 0 &&
            indexOf(e, uniq, 0, added) < 0)
            uniq[added++] = e;
        }
        //有添加新的元素,进行数组复制
        if (added > 0) {
            //复制原有数组到新的数组中,size为原有数组size+本次新增个数
            Object[] newElements = Arrays.copyOf(elements, len + added);
            //复制要新增的元素数组到上一步骤的数组的尾部
            System.arraycopy(uniq, 0, newElements, len, added);
            //将新的数组(原有数组+本次新增)替换原有数组
            setArray(newElements);
        }
        return added;//返回新增个数
    } finally {
        lock.unlock();//释放锁
    }
}

由源码可知,add 和 addIfAbsent 方法差别在添加时,后者有排重判断,若原有数组中不存在,则新增,否则什么也不做。且在排重的同时,收集要新增的元素,最后进行数组复制并替换原有数组。
addIfAbsent 单个元素时,排重同时数组复制,避免了 System.arraycopy 步骤。

remove 方法:remove(int index) ,remove(Object o) ,removeAll(Collection c)

/**
* 移除此列表指定位置上的元素。
*/
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    //一直等待直到获取锁
    lock.lock();
    try {
        //获取原有数组
        Object[] elements = getArray();
        int len = elements.length;
        //获取指定索引对应的元素
        Object oldValue = elements[index];
        //计算要移动的元素个数
        int numMoved = len - index - 1;
        if (numMoved == 0)
            //要移除的元素在队尾,直接进行元素复制且截取并替换原有数组
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            //new临时数组,长度为原有数组size-1
            Object[] newElements = new Object[len - 1];
            //复制索引从0到指定index之前的数组到newElements
            System.arraycopy(elements, 0, newElements, 0, index);
            //复制索引从index+1到队尾的数组到newElements
            System.arraycopy(elements, index + 1, newElements, index,
                 numMoved);
            //替换原有数组
            setArray(newElements);
        }
        //以前在指定位置的元素
        return (E)oldValue;
    } finally {
        lock.unlock();//释放锁
    }
}

/**
 *从此列表移除第一次出现的指定元素(如果存在)。
 */
public boolean remove(Object o) {
    final ReentrantLock lock = this.lock;
    //一直等待直到获取锁
    lock.lock();
    try {
        //获取原有数组
        Object[] elements = getArray();
        int len = elements.length;
        if (len != 0) {
        int newlen = len - 1;
        //new一个新数组,长度为原有数组size-1
        Object[] newElements = new Object[newlen];
        for (int i = 0; i < newlen; ++i) {
            if (eq(o, elements[i])) {
                //找到对应元素,将其后面的所有元素放入新数组中
                for (int k = i + 1; k < len; ++k)
                    newElements[k-1] = elements[k];
                //新数组替换原有数组
                setArray(newElements);
                return true;
            } else
                //未找到对应数组,将数组copy至新数组汇总
                newElements[i] = elements[i];
        }
        //因上面循环未循环原有数组最后一个元素,故有下面的判断
        // 判断要移除的元素是否在列表尾部
        if (eq(o, elements[newlen])) {
            //在尾部,直接将newElements替换原有数组
            setArray(newElements);
            return true;
        }
        }
        return false;
    } finally {
        lock.unlock();//释放锁
    }
}

/**
 *从此列表移除所有包含在指定 collection 中的元素。
 */
public boolean removeAll(Collection<?> c) {
    final ReentrantLock lock = this.lock;
    //一直等待直到获取锁
    lock.lock();
    try {
        //获取原有数组
        Object[] elements = getArray();
        int len = elements.length;
        if (len != 0) {

    //原有数组有数据
            int newlen = 0;
            //new 临时数组
            Object[] temp = new Object[len];
            for (int i = 0; i < len; ++i) {
                Object element = elements[i];
                //如果要移除的元素中不包含当前集合中的元素,则元素复制
                if (!c.contains(element))
                    temp[newlen++] = element;
            }
        if (newlen != len) {

    //原有长度与新数组长度不相等,说明有元素被移除
            //将新数组复制并替换原有数组,newlen<len
            setArray(Arrays.copyOf(temp, newlen));
            return true;
        }
      }
        return false;
    } finally {
        lock.unlock();//释放锁
    }
}

removem 某元素时,匹配的同时,进行数组 copy,避免了 System.arraycopy 步骤。
remove 某 Collection 时,是用 Collection 判断元素是否存在,同时进行数组复制,便于最终新数组替换原有数组。

Eset(int index, E element): 用指定的元素替代此列表指定位置上的元素。

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    ////一直等待直到获取锁
    lock.lock();
    try {
        //获取原有数组
        Object[] elements = getArray();
        //获取指定索引的元素
        Object oldValue = elements[index];
        //判断两个元素是否相同
        if (oldValue != element) {
            int len = elements.length;
            //复制原有数组到新数组
            Object[] newElements = Arrays.copyOf(elements, len);
            //设置指定索引的元素为新element
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return (E)oldValue;
    } finally {
        lock.unlock();
    }
 }

初看源码时,疑惑 newElements[index] = element;为什么不能改成 elements[index] = element;从而省却 Arrays.copyOf 步骤,其实是自己进入了误区,因 Object[] elements = getArray();获取的是引用地址,若使用 elements[index] = element;则相当于原有的数组被改动了,没有做到读写分离。
比如 indexOf,contains,toArray,get 等方法都使用到了 getArray(),会受到影响。
判断两个元素是否相同时:oldValue != element,使用了“”号,当类未重写 hashCode 与 equals 时,“”与 equals 是等价的,只是普遍习惯比较值相等时使用 equals,对象是否相同时使用“==”。
Object.equals()源码:

 public boolean equals(Object obj) {
    return (this == obj);
}

Iterator iterator():返回以恰当顺序在此列表元素上进行迭代的迭代器。

public Iterator\<E\> iterator() {
    //返回可遍历Iterator,游标从0开始
    return new COWIterator\<E\>(getArray(), 0);
}

内部类 COWIterator:private static class COWIterator implements ListIterator

private static class COWIterator implements ListIterator {


        /** 数组快照 **/
        private final Object[] snapshot;
        /** 游标  */
        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;
        }
        //判断是否有下一个元素
        public boolean hasNext() {
            return cursor < snapshot.length;
        }
        //判断是否有前一个元素
        public boolean hasPrevious() {
            return cursor > 0;
        }
        //获取下一个元素
        public E next() {
        if (! hasNext())
                throw new NoSuchElementException();
        return (E) snapshot[cursor++];
        }
        //获取前一个元素
        public E previous() {
        if (! hasPrevious())
                throw new NoSuchElementException();
        return (E) snapshot[--cursor];
        }
        //获取下一个游标
        public int nextIndex() {
            return cursor;
        }
        //获取前一个游标
        public int previousIndex() {
            return cursor-1;
        }
        //遍历时,迭代器不能移除数组元素
        public void remove() {
            throw new UnsupportedOperationException();
        }
        //遍历时,迭代器不能设置数组元素
        public void set(E e) {
            throw new UnsupportedOperationException();
        }
        //遍历时,迭代器不能新增数组元素
        public void add(E e) {
            throw new UnsupportedOperationException();
        }
}
上次编辑于:
贡献者: Andy