欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JUC—CopyOnWriteArrayList源码深度解析

程序员文章站 2022-04-15 19:12:28
基于JDK1.8详细介绍了CopyOnWriteArrayList的底层源码实现,包括写操作、读操作、迭代操作等,并介绍了写时复制(COW)机制的原理。...

  基于JDK1.8详细介绍了CopyOnWriteArrayList的底层源码实现,包括写操作、读操作、迭代操作等,并介绍了写时复制(COW)机制的原理。

1 CopyOnWriteArrayList的概述

public class CopyOnWriteArrayList< E >
  extends Object
  implements List < E >, RandomAccess, Cloneable, Serializable

  我们常用的Lsit集合ArrayLsit是一种读取效率很高的集合,但是它是不安全的,比如它的add方法,在多线程并发情况下可能因为两个写操作的相互覆盖而丢失数据。
  在JDK1.5之前,我们在Java开发中想要使用线程安全的Lsit时只能使用Vector。Vector是一个古老的集合,它对于增删改查等方法基本都加了synchronized,虽然保证同步,但是这相当于对整个Vector都加上了一把大锁,每个方法执行的时候都要去获得锁,性能非常低下。
  JDK1.5的时候出现的JUC包中提供了很多线程安全并且并发性能较好的容器,其中就有线程安全的List的实现,也是唯一的实现:CopyOnWriteArrayList。
  CopyOnWriteArrayList实现了List接口,具有List集合体系的公共特征,比如一系列通过索引操作集合元素的方法!
  CopyOnWriteArrayList实现了RandomAccess标志性接口,标志着它支持快速随机访问,因此底层一定是使用数组来实现。
  CopyOnWriteArrayList实现了Cloneable和Serializable标志性接口,支持克隆和序列化。
  CopyOnWriteArrayList还支持null元素。
JUC—CopyOnWriteArrayList源码深度解析

1.1 写时复制

  写时复制(Copy-On-Write,简称COW)思想是计算机程序设计领域中的一种优化策略。其核心思想是,如果有多个调用者(Callers)同时要求相同的资源(如内存或者是磁盘上的数据存储),他们会共同获取相同的指针指向相同的资源,直到某个调用者视图修改资源内容时,系统才会真正复制一份专用副本(private copy)给该调用者,而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的(transparently)。此做法主要的优点是如果调用者没有修改资源,就不会有副本(private copy)被创建,因此多个调用者只是读取操作时可以共享同一份资源。
  很明显,写时复制机制非常适合读多写少的并发场景。Redis使用RDB写快照备份的时候,就用到了Linux底层的Copy-On-Write技术,会fork出子进程并且与父进程共享内存空间,当父、子进程中有内存写入操作时,会复制一份内存页单独处理。从JDK1.5开始Java并发包里也提供了两个使用COW机制实现的并发容器,它们就是CopyOnWriteArrayList和CopyOnWriteArraySet。
  CopyOnWriteArrayList 对所有读操作不加锁,通过volatile 保证其数组可见性。对于写(增、删、改)操作,在加Lock锁之后先复制一份新集合,在新集合上面写,然后将新集合赋给底层数组的引用,最后解锁。因此写-读不会阻塞,只有写-写阻塞,大大提升了读的性能。
  CopyOnWriteArrayList在读方面的性能远远优于Vector,非常适合读多写少的并发情况。但是也造成了“脏读”的问题。另外CopyOnWriteArrayList是并发包的唯一并发list。

2 CopyOnWriteArrayList的原理

2.1 基本结构

  CopyOnWriteArrayList的基本结构还是很简单的。底层使用数组实现,持有一个数组的引用array。读操作不需要加锁,因此使用了volatile来保证可见性,写操作需要加锁,内部肯定持有一个锁的引用lock。内部元素实际上是Object类型的,因此没有额外的结点类。

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

    /**
     * 写操作时使用的锁,可以看到在初始化CopyOnWriteArrayList实例时就会被初始化
     */
    final transient ReentrantLock lock = new ReentrantLock();

    /**
     * 底层数组,只能通过getArray和setArray方法访问
     */
    private transient volatile Object[] array;

    /**
     * 获取数组,非私有的方法
     *
     * @return 底层数组
     */
    final Object[] getArray() {
        return array;
    }

    /**
     * 设置数组
     *
     * @param a 指定数组
     */
    final void setArray(Object[] a) {
        array = a;
    }
}

2.2 构造器

2.2.1 CopyOnWriteArrayList()

public CopyOnWriteArrayList()

  创建一个空列表。

/**
 * 创建一个空列表
 */
public CopyOnWriteArrayList() {
    //调用setArray方法,传入新建的集合,默认容量为0
    setArray(new Object[0]);
}

2.2.2 CopyOnWriteArrayList( c )

public CopyOnWriteArrayList(Collection<? extends E> c)

  按照集合的迭代器返回的顺序创建一个包含指定集合元素的列表。如果指定的集合为null,则抛出NullPointerException。

/**
 * 按照集合的迭代器返回的顺序创建一个包含指定集合元素的列表。
 * 实际上是浅克隆
 *
 * @param c 指定集合
 */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    /*如果两个集合的类型一样*/
    if (c.getClass() == CopyOnWriteArrayList.class)
        //那么直接强转并调用getArray方法获取指定集合的内部数组
        elements = ((CopyOnWriteArrayList<?>) c).getArray();
    /*否则*/
    else {
        //转换为数组
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //这里的数组实际类型可能不是Object[]类型,因此需要判断,不可强转
        //这里注释中的(see 6260652)实际上是BUG编号,地址为:https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
        if (elements.getClass() != Object[].class)
            //如果实际类型不一致,那么只能拷贝元素,这里实际上是浅克隆
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    //调用setArray方法设置array
    setArray(elements);
}

2.2.3 CopyOnWriteArrayList( toCopyIn )

public CopyOnWriteArrayList(E[] toCopyIn)

  创建一个包含指定数组的副本的列表。

/**
 * 创建一个包含指定数组的副本的列表。
 * 实际上是浅克隆
 *
 * @param toCopyIn 指定数组
 * @throws NullPointerException 如果指定数组为空
 */
public CopyOnWriteArrayList(E[] toCopyIn) {
    //调用Arrays.copyOf方法创建包含toCopyIn数组全部元素的新Object[]类型的数组
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

2.3 写操作

2.3.1 add操作

2.3.1.1 add(E e)

public boolean add(E e)

  将指定元素添加到此列表的尾部。

/**
 * 将指定元素添加到此列表的尾部。
 *
 * @param e 指定元素
 * @return 如果添加成功返回true,最终都会返回true
 */
public boolean add(E e) {
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取lock锁
    lock.lock();
    try {
        //获取底层数组
        Object[] elements = getArray();
        //获取长度
        int len = elements.length;
        //将此时的底层数组拷贝一份,长度加一,实际上是返回了一个和原数组没有关系的新数组
        //数组里面的内容如果是对象类型(排除不变模式的类,比如String、包装类)的话,那么仍然只是浅克隆
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //新数组末尾存放元素e
        newElements[len] = e;
        //将新数组赋值给array引用
        setArray(newElements);
        //返回true
        return true;
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}

2.3.1.2 add(index, element)

public void add(int index, E element)

  在此列表的指定位置上插入指定元素。将当前在该位置上的元素(如果有)以及所有后续元素向右移(其索引加 1)。
  如果index索引超出范围(index > len || index < 0),那么抛出IndexOutOfBoundsException异常。

/**
 * 在此列表的指定索引位置上插入指定元素。将当前在该索引位置上的元素(如果有)以及所有后续元素向右移(其索引加 1)。
 *
 * @throws IndexOutOfBoundsException 如果索引超出范围 (index > len || index < 0)
 */
public void add(int index, E element) {
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取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;
        //如果为0,那么就是相当于在原数组最后的索引之后添加元素,没有需要向后移动的元素
        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;
        //将新数组赋值给array引用
        setArray(newElements);
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}

2.3.1.3 addIfAbsent( e )

public boolean addIfAbsent(E e)

  如果指定元素不存在,那么添加该元素。如果成功添加元素则返回true。
  这个方法的判断的判断实际上比想象中严格,大概步骤为:

  1. 首先获取当前的底层数组snapshot,然后在该数组中查找是否有指定值e,如果存在那么直接返回false,否则调用内部addIfAbsent方法;
  2. 在内部addIfAbsent方法中,首先加锁,然后再次获取此时的底层数组current,判断snapshot和current是否是同一个数组,如果是,那么新建数组,拷贝current的数组,插入e,返回true,解锁;如果不是,那么判断新数组中是否存在e,如果存在那么返回false,不存在则新建数组,拷贝current的数组,插入e,返回true,解锁。

即先采用不加锁的方式快速判断一次,如果存在指定元素那么就直接返回false了,如果不存在那么再采用加锁的方式判断,这样做可以避免每一次都必须加锁。实际上CopyOnWriteArraySet的add方法内部就是调用该方法!

/**
 * 如果指定元素不存在,那么添加元素
 *
 * @param e 指定元素
 * @return 如果添加成功返回true
 */
public boolean addIfAbsent(E e) {
    //首先获取此时的底层数组
    Object[] snapshot = getArray();
    //首先调用indexOf在数组范围类重头到尾查找指定元素,将会返回第一次出现的索引
    //如果返回值大于等于0,那么表示存在,那么直接返回false
    //否则表示不存在,直接在末尾添加e,
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
}

/**
 * 在指定数组的指定开始索引(包括)和指定结束索引(不包括)之间搜索并返回指定元素出现的第一个索引位置
 *
 * @param o        指定元素
 * @param elements 指定数组
 * @param index    要搜索的第一个索引
 * @param fence    要搜索的最后一个索引
 * @return 元素索引,或 -1(如果不存在)
 */
private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    /*如果指定元素不为null*/
    if (o == null) {
        //循环遍历
        for (int i = index; i < fence; i++)
            //对于null,使用 == 判断
            if (elements[i] == null)
                return i;
    }
    /*否则*/
    else {
        //循环遍历
        for (int i = index; i < fence; i++)
            //对于非null,使用equals判断
            if (o.equals(elements[i]))
                return i;
    }
    //没找到就返回-1
    return -1;
}

/**
 * 添加指定元素到指定数组中
 *
 * @param e        指定元素
 * @param snapshot 指定数组
 * @return false 添加失败  true 添加成功
 */
private boolean addIfAbsent(E e, Object[] snapshot) {
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取lock锁
    lock.lock();
    try {
        //获取此时底层数组
        Object[] current = getArray();
        //获取此时底层数组的长度
        int len = current.length;
        //如果最开始的数组和此时的数组 ==判断不相等
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            //那么获取两个数组的最小容量common
            int common = Math.min(snapshot.length, len);
            //遍历[0,common-1]
            for (int i = 0; i < common; i++)
                //判断索引位置上 两个数组相同索引位置的元素是否不相等 以及 指定元素和此时数组该索引位置的元素是否相等
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    //如果都为true 说明某个位置上该元素已经被加入进此时数组中了
                    //返回false
                    return false;
            //遍历当前数组的[common-1,len)尝试获取e的索引,判断返回值是否大于0
            if (indexOf(e, current, common, len) >= 0)
                //如果大于0,说明该元素已经被加入进此时数组中了
                //返回false
                return false;
        }
        //到这一步,表示最开始的数组和此时的数组是一个对象 或者 此时数组中没有该元素
        //那么拷贝新数组
        Object[] newElements = Arrays.copyOf(current, len + 1);
        //插入元素
        newElements[len] = e;
        //将新数组赋值给array引用
        setArray(newElements);
        //返回true
        return true;
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}

/**
 * 判断两元素是否相等
 */
private static boolean eq(Object o1, Object o2) {
    //如果是null则使用==比较,否则使用equals比较
    return (o1 == null) ? o2 == null : o1.equals(o2);
}

2.3.1.4 addAllAbsent( c )

public int addAllAbsent(Collection<? extends E> c)

  按照指定集合的迭代器返回元素的顺序,将指定集合中尚未包含在此列表中的所有元素添加列表的尾部。返回添加的元素数量。并且对于本集合中不存在而指定集合中存在多个相同的元素只会添加一次(去重)。

/**
 * 按照指定集合的迭代器返回元素的顺序,将指定集合中尚未包含在此列表中的所有元素添加列表的尾部。
 *
 * @param c 指定集合
 * @return 添加的元素数量
 * @throws NullPointerException 如果指定集合为 null
 */
public int addAllAbsent(Collection<? extends E> c) {
    //获取指定集合数组cs
    Object[] cs = c.toArray();
    //如果为长度为0,那么直接返回0
    if (cs.length == 0)
        return 0;
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取lock锁
    lock.lock();
    try {
        //获取当前的array数组
        Object[] elements = getArray();
        //获取长度
        int len = elements.length;
        //计数器,同时作为cs数组添加元素的引用,初始为0
        int added = 0;
        // uniquify and compact elements in cs
        //遍历指定集合数组
        for (int i = 0; i < cs.length; ++i) {
            //获取元素e
            Object e = cs[i];
            //如果e在当前array数组中不存在 并且 在cs数组中[0,added-1]的索引之间也不存在该元素
            if (indexOf(e, elements, 0, len) < 0 &&
                    indexOf(e, cs, 0, added) < 0)
                //那么cs的索引位置存放e,之后added自增1
                cs[added++] = e;
            //上面的操作,实际上将需要添加的元素临时加入到cs数组中,从0开始存放,直到added位置(不包括)
            //并且对于elements中不存在而cs中存在多个相同的元素只会添加一次(去重)
        }

        //遍历完毕,如果added大于0,表示有需要添加的元素,那么同样新建数组添加
        if (added > 0) {
            //新建数组newElements,拷贝当前array的数据
            Object[] newElements = Arrays.copyOf(elements, len + added);
            //然后将需要添加的元素,即cs中的[0,added-1]之间的元素拷贝到新数组newElements中的len索引开始之后的位置
            System.arraycopy(cs, 0, newElements, len, added);
            //将新数组赋值给array引用
            setArray(newElements);
        }
        //返回added
        return added;
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}

2.3.2 remove操作

2.3.2.1 remove( index )

public E remove(int index)

  移除此列表指定索引位置上的元素。将所有后续元素都向左移(其索引减 1)。返回从此列表中移除的元素。
  如果没有元素或者索引超出范围 (index < 0 || index >= size()),则抛出异常ArrayIndexOutOfBoundsException。

/**
 * 移除此列表指定位置上的元素。将所有后续元素都向左移(其索引减 1)。
 *
 * @param index 指定索引
 * @return 返回从此列表中移除的元素。
 * @throws ArrayIndexOutOfBoundsException 如果没有元素或者索引超出范围 (index < 0 || index >= size())
 */
public E remove(int index) {
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取lock锁
    lock.lock();
    try {
        //获取当前array数组
        Object[] elements = getArray();
        //获取长度
        int len = elements.length;
        //获取指定索引的元素
        E oldValue = get(elements, index);
        /*后续元素向前移动*/
        int numMoved = len - index - 1;
        //如果删除的元素是最后一个,
        if (numMoved == 0)
            //直接复制该元素前的所有元素到新的数组,copyOf内部还是创建了数组的
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            //否则,创建新的数组,长度为len-1
            Object[] newElements = new Object[len - 1];
            //将[0,index)的元素整体复制,个数为index个
            System.arraycopy(elements, 0, newElements, 0, index);
            //将index+1索引开始至至最后一个元素向前复制移动
            System.arraycopy(elements, index + 1, newElements, index,
                    numMoved);
            //将新数组赋值给array引用
            setArray(newElements);
        }
        //返回被移除的元素
        return oldValue;
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}

/**
 * 获取指定数组的指定索引的元素
 *
 * @param a     指定数组
 * @param index 指定索引
 * @return 元素
 * @throws ArrayIndexOutOfBoundsException 如果没有元素或者索引超出范围 (index < 0 || index >= size())
 */
private E get(Object[] a, int index) {
    return (E) a[index];
}

2.3.2.2 remove( o )

public boolean remove(Object o)

  从此列表移除第一次出现的指定元素(从0索引开始)。如果此列表包含指定元素(或者此列表由于调用而发生更改),则返回 true。

/**
 * 从此列表移除第一次出现的指定元素(从0索引开始)。
 *
 * @param o 指定元素
 * @return 如果此列表包含指定元素(或者此列表由于调用而发生更改),则返回 true。
 */
public boolean remove(Object o) {
    //获取此时的array数组snapshot
    Object[] snapshot = getArray();
    //获取指定元素在snapshot中的索引位置index
    int index = indexOf(o, snapshot, 0, snapshot.length);
    //如果index小于0,则返回false;否则调用内部的remove方法移除
    return (index < 0) ? false : remove(o, snapshot, index);
}


/**
 * 内部remove方法
 *
 * @param o        指定元素
 * @param snapshot 外部remove方法中获取的array数组
 * @param index    指定元素在snapshot中第一次出现的的索引
 * @return 如果此列表包含指定元素(或者此列表由于调用而发生更改),则返回 true。
 */
private boolean remove(Object o, Object[] snapshot, int index) {
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取lock锁
    lock.lock();
    try {
        //获取最新array数组
        Object[] current = getArray();
        //获取最新数组长度
        int len = current.length;
        //如果两个数组不是同一个数组,说明在此期间有线程写了数组
        if (snapshot != current) findIndex:{
            //获取两个数组的最小长度prefix
            int prefix = Math.min(index, len);
            //循环遍历[0,prefix-1]
            for (int i = 0; i < prefix; i++) {
                //判断索引位置上 两个数组相同索引位置的元素是否不相等 以及 指定元素和此时数组该索引位置的元素是否相等
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    //如果都为true 说明该位置就是需要删除的索引位置
                    index = i;
                    //break跳出语句块
                    break findIndex;
                }
            }
            //如果index大于len,说明最新数组变短了并且没有这个元素
            if (index >= len)
                //直接返回false
                return false;
            //否则获取最新数组指定位置的元素 如果和0 ==比较相等
            if (current[index] == o)
                //break跳出语句块
                break findIndex;
            //在current的[index,len-1]索引之间查找o
            index = indexOf(o, current, index, len);
            //如果index小于0
            if (index < 0)
                //那么直接返回false
                return false;
        }
        //到这里说明两个数组是同一个数组 或者在最新数组中找到了o的索引,那么开始删除

        //新建数组长度为len - 1
        Object[] newElements = new Object[len - 1];
        //拷贝[0,index-1]的索引元素到新数组对应索引
        System.arraycopy(current, 0, newElements, 0, index);
        //拷贝[index+1,len-1]索引的元素到新数组并前移一位索引
        System.arraycopy(current, index + 1,
                newElements, index,
                len - index - 1);
        //将新数组赋值给array引用
        setArray(newElements);
        //返回true
        return true;
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}


/**
 * 判断两元素是否相等
 */
private static boolean eq(Object o1, Object o2) {
    //如果是null则使用==比较,否则使用equals比较
    return (o1 == null) ? o2 == null : o1.equals(o2);
}


/**
 * 在指定数组的指定开始索引(包括)和指定结束索引(不包括)之间搜索并返回指定元素出现的第一个索引位置
 *
 * @param o        指定元素
 * @param elements 指定数组
 * @param index    要搜索的第一个索引
 * @param fence    要搜索的最后一个索引
 * @return 元素索引,或 -1(如果不存在)
 */
private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    /*如果指定元素不为null*/
    if (o == null) {
        //循环遍历
        for (int i = index; i < fence; i++)
            //对于null,使用 == 判断
            if (elements[i] == null)
                return i;
    }
    /*否则*/
    else {
        //循环遍历
        for (int i = index; i < fence; i++)
            //对于非null,使用equals判断
            if (o.equals(elements[i]))
                return i;
    }
    //没找到就返回-1
    return -1;
}

2.3.3 set操作

2.3.3.1 set(index, element)

public E set(int index, E element)

  用指定的元素替代此列表指定索引位置上的元素。返回以前在指定位置的元素。
  如果没有元素或者索引超出范围 (index < 0 || index >= size()),则抛出ArrayIndexOutOfBoundsException。

/**
 * 用指定的元素替代此列表指定索引位置上的元素。
 *
 * @param index   指定索引
 * @param element 指定元素
 * @return 以前在指定位置的元素
 * @throws ArrayIndexOutOfBoundsException 如果没有元素或者索引超出范围 (index < 0 || index >= size())
 */
public E set(int index, E element) {
    //获取lock锁引用
    final ReentrantLock lock = this.lock;
    //获取lock锁
    lock.lock();

    try {
        //获取当前array数组elements
        Object[] elements = getArray();
        //获取在elements中指定索引位置的元素oldValue
        E oldValue = get(elements, index);
        /*如果oldValue不等于指定元素*/
        if (oldValue != element) {
            //获取elements的长度
            int len = elements.length;
            //新建数组拷贝elements的数据
            Object[] newElements = Arrays.copyOf(elements, len);
            //指定索引位置上设置为新元素
            newElements[index] = element;
            //将新数组赋值给array引用
            setArray(newElements);
        }
        /*否则*/
        else {
            //什么都不干,但还是将获取到的数组再写回去,相当于volatile的写语义,保证可见性
            setArray(elements);
        }
        //返回旧值
        return oldValue;
    } finally {
        //无论是添加成功还是抛出异常,最终一定会释放锁
        lock.unlock();
    }
}

/**
 1. 获取指定数组的指定索引的元素
 2.  3. @param a     指定数组
 4. @param index 指定索引
 5. @return 元素
 6. @throws ArrayIndexOutOfBoundsException 如果没有元素或者索引超出范围 (index < 0 || index >= size())
 */
private E get(Object[] a, int index) {
    return (E) a[index];
}

2.3.4 总结

  从以上的增、删、改操作中我们可以发现:

  1. 相比某些并发容器,比如ConcurrentLinkedQueue,CopyOnWriteArrayList允许null元素。
  2. 底层数据结构和ArrayList一样,都是一个Object[]类型的数组,但是并没有延迟初始化策略,初始容量就为0,不支持指定容量。添加元素时如果容量不够就会扩容。
  3. 增、删、改操作都需要获得锁,并且都是同一把锁,这样增、删、改操作变成了串行操作。
  4. 增、删、改操作都是在一个原集合的新拷贝集合上操作的,操作完毕之后会将新集合赋给底层array数组引用,最后都会释放锁。没有抢到锁的线程将会被阻塞在lock中的同步队列里面,在释放锁之后,会唤醒阻塞的线程并自动尝试获取锁。
  5. 增、删、改操作由于需要争夺锁,并且每次都需要新建集合-拷贝数据-写回集合,因此性能非常低。

2.4 读操作

2.4.1 get操作

public E get(int index)

  返回列表中指定索引位置的元素。如果没有元素或者索引超出范围则抛出ArrayIndexOutOfBoundsException异常。
  get方法并没有加锁,因此数据是弱一致性的。因为在get访问底层数组的时候,可能存在一条写线程正在操作同一个索引位置的数据,但是由于在拷贝集合上操作的,因此get方法不能感知到这个写操作导致的元素的变换,还是获取了原数组索引位置的值。在写操作结束之后,再次获取相同索引位置的值时,会发现元素已经改变,可称之为“脏读”。
  另外,虽然volatile修饰了数组,但是只能保证数组引用的可见性(在写数组引用时,其他读线程度能感知到),但是对于数组内部元素没有任何保证。

/**
 * 获取指定索引的元素,如果索引超出范围则抛出ArrayIndexOutOfBoundsException 异常。
 * @param index 指定索引
 * @return 指定索引的元素
 */
public E get(int index) {
    return get(getArray(), index);
}

2.4.2. size操作

public int size() 返回此列表中的元素数。
public boolean isEmpty() 如果此列表不包含任何元素,则返回 true。

  size方法和isEmpty方法没有加锁,因此得到的结果不一定是正确的。

/**
 * 返回此集合的元素数量
 *
 * @return 此集合的元素数量
 */
public int size() {
    //直接获取的底层数组的长度,长度一定等于元素数量
    //因为初始容量一定为0,每次添加元素时长度会增加1,而每次删除元素时长度会减去1
    return getArray().length;
}

/**
 * 如果此列表不包含任何元素,则返回 true。
 *
 * @return 如果此列表不包含任何元素,则返回 true。
 */
public boolean isEmpty() {
    //判断size()方法是否返回0
    return size() == 0;
}

2.4.3 contains操作

public boolean contains(Object o)
  如果此列表包含至少一个指定的元素,则返回 true。 public
boolean containsAll(Collection<?> c)
  如果此列表包含指定 集合的所有元素,则返回true。如果指定集合为 null,则抛出NullPointerException异常。

  contains方法和containsAll方法没有加锁,因此得到的结果不一定是正确的。

/**
 * 判断是否包含单个元素
 *
 * @param o 指定元素
 * @return 如果此列表包含至少一个指定的元素,则返回 true。
 */
public boolean contains(Object o) {
    //获取此时的array数组
    Object[] elements = getArray();
    //调用index尝试查找指定元素,如果返回值大于等于0,则返回true,否则返回false
    return indexOf(o, elements, 0, elements.length) >= 0;
}

/**
 * 判断是否保证指定集合的全部元素
 *
 * @param c 制定集合
 * @return 如果此列表包含指定 集合的所有元素,则返回 true。
 * @throws NullPointerException 如果指定集合为 null
 */
public boolean containsAll(Collection<?> c) {
    //获取此时的array数组
    Object[] elements = getArray();
    //获取长度
    int len = elements.length;
    //遍历指定集合
    for (Object e : c) {
        //循环调用indexOf方法判断,只要有一个没有包含就直接返回false
        if (indexOf(e, elements, 0, len) < 0)
            return false;
    }
    //最后表示全部包含或者制定集合为空集合,那么返回true
    return true;
}

2.4.4 迭代操作

public Iterator< E > iterator()

  返回以恰当顺序在此列表元素上进行迭代的迭代器。
  构造该迭代器时,所返回的迭代器中仅仅包含一个此时array集合的快照,具有弱一致性。因为在遍历过程中如果有其他线程写数据,那么将会使用新的数组替代原数组。
  遍历该迭代器时不需要执行任何同步,同时该迭代器也不支持 remove 、set、add等写快照的方法,强行调用将会抛出UnsupportedOperationException异常,因为这些方法对于快照来说没有任何意义。

/**
 * 返回以恰当顺序在此列表元素上进行迭代的迭代器。
 * 构造该迭代器时,所返回的迭代器中仅仅包含一个此时array集合的快照,具有弱一致性。
 * 遍历该迭代器时不需要执行任何同步。该迭代器也不支持 remove 方法。
 *
 * @return 一个迭代器
 */
public Iterator<E> iterator() {
    //返回一个COWIterator迭代器实例,传递此时的array数组,initialCursor传递0
    return new COWIterator<E>(getArray(), 0);
}

/**
 * COW模式的迭代器实现,具有弱一致性
 *
 * @param <E>
 */
static final class COWIterator<E> implements ListIterator<E> {
    /**
     * 数组的快照
     */
    private final Object[] snapshot;
    /**
     * 要返回的下一个元素的索引
     */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        //在iterator()中cursor=1
        cursor = initialCursor;
        //保存此时的数组快照
        snapshot = elements;
    }

    /**
     * 是否还有下一个元素
     *
     * @return true 有 false 没有
     */
    public boolean hasNext() {
        return cursor < snapshot.length;
    }

    /**
     * 获取下一个元素
     *
     * @return
     */
    @SuppressWarnings("unchecked")
    public E next() {
        //如果hasNext返回false,那么抛出NoSuchElementException异常,表示遍历完毕了
        if (!hasNext())
            throw new NoSuchElementException();
        //返回快照指定索引cursor的元素,之后cursor自增1
        return (E) snapshot[cursor++];
    }
    //--------------------------------------
    //在CopyOnWriteArrayList的全部迭代器中,remove、set、add等写操作都是不支持的
    //因为这里第二代的只是一个快照,对快照的写没有任何意义
    //--------------------------------------

    /**
     * Not supported. Always throws UnsupportedOperationException.
     *
     * @throws UnsupportedOperationException always; {@code remove}
     *                                       is not supported by this iterator.
     */
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     *
     * @throws UnsupportedOperationException always; {@code set}
     *                                       is not supported by this iterator.
     */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported. Always throws UnsupportedOperationException.
     *
     * @throws UnsupportedOperationException always; {@code add}
     *                                       is not supported by this iterator.
     */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }

    //--------------------------------------
    //下面的方法是给ListIterator迭代器用的
    //--------------------------------------

    public int previousIndex() {
        return cursor - 1;
    }


    public boolean hasPrevious() {
        return cursor > 0;
    }

    @SuppressWarnings("unchecked")
    public E previous() {
        if (!hasPrevious())
            throw new NoSuchElementException();
        return (E) snapshot[--cursor];
    }

    public int nextIndex() {
        return cursor;
    }


    /**
     * JDK1.8新加的默认方法
     *
     * @param action 消费者
     */
    @Override
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        Object[] elements = snapshot;
        final int size = elements.length;
        for (int i = cursor; i < size; i++) {
            @SuppressWarnings("unchecked") E e = (E) elements[i];
            action.accept(e);
        }
        cursor = size;
    }
}

2.4.4.1 测试

System.out.println("======下面测试并发list=======");
CopyOnWriteArrayList<Object> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
copyOnWriteArrayList.add(1);
copyOnWriteArrayList.add(2);
Iterator<Object> cIterator = copyOnWriteArrayList.iterator();
Thread thread = new Thread(() -> {
    copyOnWriteArrayList.set(0, "修改");
    copyOnWriteArrayList.add("增加");
});
thread.start();
thread.join();
while (cIterator.hasNext()) {
    Object next = cIterator.next();
    System.out.println(next);
}
System.out.println("----------");
for (Object next : copyOnWriteArrayList) {
    System.out.println(next);
}
System.out.println("======下面测试普通list=======");

ArrayList<Object> objects = new ArrayList<>();
objects.add(1);
objects.add(2);
Iterator<Object> aIterator = objects.iterator();
Thread thread2 = new Thread(() -> {
    objects.set(0, "修改");
    objects.add("增加");
});
thread2.start();
thread2.join();
while (aIterator.hasNext()) {
    Object next = aIterator.next();
    System.out.println(next);
}
System.out.println("----------");
for (Object next : objects) {
    System.out.println(next);
}

  结果:

====== 下面测试并发list =======
1
2


修改
2
增加
====== 下面测试普通list =======
java.util.ConcurrentModificationException

  CopyOnWriteArrayList未抛出异常,但是数据不一致,这也叫安全失败(fail-safe);普通list则是直接抛出异常,这也叫快速失败(fail-fast)。

2.4.5 总结

  从我们上面分析的读操作来看,所有的读都没有加锁,这样读线程会拥有非常良好的并发性能。
  但是缺点就是遍历的只是数组的快照,即使底层数组发生了增删改变化,快照也不会变化,所以不会发生并发异常。数据也只能保证数据的最终一致性,不能保证数据的实时一致性,因此可能会读到脏数据,写操作越多,读到脏数据的概率越大。

3 CopyOnWriteArrayList的总结

  CopyOnWriteArrayList继承了ArrayLsit的优点,对于读操作有非常良好的并发性能,而写操作的性能则大打折扣。并且由于COW机制可能会导致读取到脏数据,为什么JUC中没有即类似于ArrayLsit既能线程安全又能保证数据强一致性的List集合呢?
  原理很简单,如果要想数据强一致性,那么必然导致读-写都必须加锁,并且读-写互相阻塞,这样不就又变成了Vector了吗?虽然后续可以采用读写锁来进行优化,但是每一次的读仍然需要获取“读锁”,只要有一个写锁就会阻塞所有的读锁,其并发性能仍然一般,最终JUC采用了基于COW的CopyOnWriteArrayList来作为普通List在并发环境下的实现,对于读操作完全没有并发瓶颈(完全不加锁),但是对于写操作却加独占锁,这样就和Vector一样变得串行化,并且读到的数据是弱一致性的,因此CopyOnWriteArrayList并不是一个通用的并发List。

如果有什么不懂或者需要交流,可以留言。另外希望点赞、收藏、关注,我将不间断更新各种Java学习博客!

本文地址:https://blog.csdn.net/weixin_43767015/article/details/107397247