CopyOnWriteArrayList

星空怎样IP属地: 北京
字数 1,490阅读 598

[toc]

前言

CopyOnWriteArrayList是一个线程安全的集合,原理就是:在保证线程安全的前提下,牺牲掉写操作的效率来保证读操作的高效。所谓的CopyOnwrite就是通过赋值方式来完成对数据的修改,在进行修改的时候,复制一个新数组,在新数组上面进行修改操作,这样保证了不改变老数组,实现了读写分离,但是因为是通过复制方式对数据进行修改,所以不能保证数据实的实时性只能保证最终的一致性

定义

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

在定义上和ArrayList的定义差不多,不在过多解释。

属性

/** The lock protecting all mutators */
//一把锁
transient final ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */
//一个对象数组,只从方法getArray/setArray处接受值
private volatile transient Object[] array;
  • lock属性是CopyOnWriteArrayList中的锁,通过lock对add()、set()、remove()等方法进行锁操作
  • array是CopyOnWriteArrayList存放数据的数组只能通过getArray/setArray处理值
    注CopyOnWriteArrayList是没有size属性的因为不需要,因为每次修改都是拷贝一份正好可以存储目标个数的元素的数组,所以size=array.length,不像ArrayList数组长度实际要大于集合大小。

初始化

无参的构造方法

CopyOnWriteArrayList的初始容量是0。
无参的构造方法会调用setArray(),参数是一个空的数组,然后通过setArray把这个数组赋值给array

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    final void setArray(Object[] a) {
        array = a;
    }

使用另一个集合的Collection的构造方法

    public CopyOnWriteArrayList(Collection<? extends E> c) {
        //定义数组
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            //如果参数的类型恰好就是CopyOnWriteArrayList,那么直接将c强转成CopyOnWriteArrayList,然后在获取底层数组赋值到elements中
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            //参数不是CopyOnWriteArrayList
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            //如果elements不是一个Object[]类型数组,那么就将原数组变为Object[]类型数组,如果是Object[]数组,那么不需要转换直接赋值即可
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        //赋值属性
        setArray(elements);
    }

该构造方法执行流程如下:

  • 判断传入集合c的类型是否为CopyOnWriteArrayList类型,若是,则将获取该集合类型的底层数组。直接设置当前的CopyOnWriteArrayList的Object[]
  • 如果不是CopyOnWriteArrayList,那么将集合转化为数组elements,判断elements的类型是否为Object[]类型(toArray方法可能不会返回Object[]类型数组),若不是,则将elements转化为Object[]类型的数组
  • 设置当前CopyOnWriteArrrayList的Object[]为elements

参数是一个数组

public CopyOnWriteArrayList(E[] toCopyIn) {
        //直接赋值给array属性中
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

核心函数

copyOf函数(该函数是Arrays中的)

注:该函数是Arrays中的因为会被大量使用所以提前拿出来说明一下
该函数用于复制数组,截取或用null来填充(如果有必要),是副本具有指定的长度。属于浅拷贝

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        //确定copy的拷贝类型(将newTye转化为Object类型,将Object[].class转化为Object类型,判断两者是否相等,若相等则生成指定长度Object数组)
        //如果不相等生成指定类型的数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

添加元素的add()

从add方法中可以看到CopyOnWrite是如何实现的,在需要修改的时候,复制一个新数组,在新数组上修改,修改结束后取代老数组,这样保证了修改操作不影响正常读取,另外修改操作是加锁的,也就是说没有了线程不完全的问题,和ArrrayList相比,效率比较低,因为每一次添加元素都需要赋值数组,随着CopyOnWriteArrayList中元素真你感觉,修改代价将会越来越大

在集合末尾添加一个元素

public boolean add(E e) {
        //可重入锁
        final ReentrantLock lock = this.lock;
        //获取锁
        lock.lock();
        try {
            //获取数组
            Object[] elements = getArray();
            //获取数组长度
            int len = elements.length;
            //进行数组拷贝,长度是len+1,因需要添加一个新的元素
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            //将对应元素放到新的数组中
            newElements[len] = e;
            //设置数组
            setArray(newElements);
            return true;
        } finally {
            //释放锁
            lock.unlock();
        }
    }

此函数处理流程:

  • 获取锁(保证多线程的安全访问),获取当前的Object数组,获取数组长度
  • 根据Object数组赋值长度为length+1的数组为newElements(此时newElements[length]=null)
  • 将newElements[length]设置为元素e
  • 将newElements设置为CopyOnWriteArrayList的数组
  • 释放锁

在指定角标位置添加元素

    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        获取锁
        lock.lock();
        try {
            //获取数组
            Object[] elements = getArray();
            //获取数组长度
            int len = elements.length;
            //判断index是否数组越界
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
                                        
            //新的数组                            
            Object[] newElements;
            //如果等于0说明本身就在末尾添加,直接整个数组进行拷贝
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                //numMoved>0说明是在中间所以要分两次拷贝,并且把index的位置空出来
                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);
        } finally {
            //释放锁
            lock.unlock();
        }
    }

执行流程同上,只是如果index在中间位置,需要复制两次,把index的位置空出来。

set()

次方法用于指定的元素替代此列表指定位置上的元素,也是基于数组复制来实现的,原理和add类型

    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        //获取锁
        lock.lock();
        try {
            //获取数组
            Object[] elements = getArray();
            //获取旧元素
            E oldValue = get(elements, index);
            //如果旧值和新值不相等
            if (oldValue != element) {
                //copy一个新的数组
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                //将新值赋值进去
                newElements[index] = element;
                //替换数组
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                //如果oldValue==element那么直接设置数组(这个设置不太懂什么原因,因为elements没有变化只是又重新设置了一下)
                setArray(elements);
            }
            return oldValue;
        } finally {
        //释放锁
            lock.unlock();
        }
    }

其实整个过程也是对数组进行了拷贝,在拷贝的数组上面进行修改

remove函数

此函数用于移除列表指定位置上的元素

public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            //numMoved==0说明是删除末尾元素,numMoved>0说明是中间元素,不会出现小于0,小于0情况说明index>len删除的index不存在(不明白为什么没有做数组越界判断)
            int numMoved = len - index - 1;
            if (numMoved == 0)
                //数组拷贝直接将某位元素剔除 setArray(Arrays.copyOf(elements, len - 1));
            else {
                //两次拷贝数组剔除index的元素
                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;
        } finally {
        //释放锁
            lock.unlock();
        }
    }

整个过程其实和在指定位置添加一个元素过程一样,只是两次复制数组时候是将数组长度减一,把index上面对应的元素移除出去

总结

  • 读写分离,我们修改的是新的数组,读取的是老的数组,不是一个对象,实现了读写分离,这种技术数据库用的非常多,在高并发下未了环境数据库的压力,即使做了缓存也要对数据进行读写分离,读的时候使用读库,写的时候使用写库,然后读库、写库,进行一定同步,这样就避免同一个库上,读、写IO操作太多
  • 使用场景读操作远多于修改操作(因为每一次修改面临着,对原数组进行拷贝,随着数组越来越大,时间消耗就越来远长)

缺点

  • 写操作时候,需要数组拷贝,会很消耗内存,如果原数组内容比较多的情况下,可能导致young gc或full gc
  • 不能用于实时读取场景,拷贝数组都需要时间,所以调用一个set或者add方法后,读取到数据有可能还是旧的,也就是说CopyOnWriteArrayList只实现了最终一致性,但是没有满足实时的一致性

适用场景

就是读操作远远大于写操作的场景,不过也要慎用,不保证数据放多少情况,万一数据非常多,每一次add/set等操作都需要复制数组代价太高

CopyOnWriteArrayList为什么并发安全比Vector好

Vector对单独的add、remove等方法都加了synchronized,并且一个线程调用size时,另一个remove,然后size的值就不是最新的,会造成数组越界,这时候需要再加一个synchronized,这样双重锁,效率大大降低。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
0人点赞
更多精彩内容,就在简书APP
"小礼物走一走,来简书关注我"
还没有人赞赏,支持一下
星空怎样2020进大厂
总资产0.353共写了9.3W字获得10个赞共1个粉丝