黑马程序员技术交流社区

标题: 【上海校区】Java并发包中的List源码剖析 [打印本页]

---

作者: 不二晨    时间: 2019-2-22 16:41
标题: 【上海校区】Java并发包中的List源码剖析
CopyOnWriteArrayList（写时复制ArrayList）

写时复制：这是JUC并发包下的基于写时复制的ArrayList。为什么是写时复制呢？因为当调用对这个ArrayList中的元素进行修改的方法时，会先复制一个原数组的副本，对这个副本进行操作，最后再让原数组的引用指向这个新的数组，实现数据的更新，这个过程的原子性通过独占锁来保证，这就是写时复制。它归类于并发包的原因是，对这个类的操作是线程安全的，底层通过独占锁来实现（这个类没有用到CAS）。
弱一致性：通过以上描述就可以发现，读取是不受任何影响的，任何线程都可以对数据进行读取，即便数据被copy一份正在修改，也可以读，这就带来了一个问题，先调用了修改List的方法，再调用读取其中某个元素的方法，若该元素在修改的方法中被修改，理论上读取的应该是修改后的数据，然而，因为修改数据是对副本（快照）修改，在它还没有更新引用时，别的线程拿到的依然是原先的数组，这就和代码的先后逻辑冲突了，这就是弱一致性问题。

CopyOnWriteArrayList源码分析

初始化：
它有3种构造方法。
1、无参构造：
在初始化时会new一个长度为0的数组。
2、传入一个集合对象的构造方法：
? extends E 通配符申明了在CopyOnWriteArrayList中元素的类型是E的子类或者其本身，在方法中申明一个数组来接收。先判断传入的集合c和CopyOnWriteArrayList类是否是相同类，如果是相同则直接调用getArray()方法获取传入的那个CopyOnWriteArrayList类的实例的数组引用，把它赋予这个构造方法中的数组，也就是说可以拿一个CopyOnWriteArrayList的对象传入另一个CopyOnWriteArrayList的构造方法，使得后者持有前者数组的引用并可以修改它。如果是一个其他集合类，就调用toArray()方法，得到数组，然后再判断元素是否为Object类，如果不是，则获取一个副本，其中的元素转型为Object类的实例。最后调用set方法更新CopyOnWriteArrayList中维护的数组的引用。
3、传入一个数组的构造方法：
直接把它转为Object并设置为CopyOnWriteArrayList的array。

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }   
    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            elements = c.toArray();
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    }
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

添加元素：
先实例化一个独占锁，然后加锁。获取原数组的引用，计算长度，然后获取副本，这个副本长度比原先大1，添加一个元素到末尾，最后还需要释放锁。

   public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

获取指定位置的元素：

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

修改指定元素：
和添加操作原理相同，在独占锁中完成数据的复制，修改和设置。

    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) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

删除元素：

    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);
            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;
        } finally {
            lock.unlock();
        }
    }

CopyOnWriteArrayList迭代器的弱一致性问题

写了一个小Demo来引出弱一致性问题：
先添加了两个元素，再获取一个迭代器，再添加一个元素，最后用迭代器输出数据。

public class Test {     
        public static void main(String[] args){
                    CopyOnWriteArrayList<Integer> copyOnWriteArrayList=new CopyOnWriteArrayList<>();
                    copyOnWriteArrayList.add(3);
                    copyOnWriteArrayList.add(5);
                    Iterator<Integer> iterator=copyOnWriteArrayList.iterator();
                    copyOnWriteArrayList.add(2);
                    while(iterator.hasNext()){
                            System.out.println(iterator.next());
                    }
        }                       
}

输出：

源码：
获取原数组引用，初始化光标为0。

    public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }
   private COWIterator(Object[] elements, int initialCursor) {
         cursor = initialCursor;
         snapshot = elements;
    }

**分析：**这里虽然先后添加了3个元素，但实际上迭代器中只有2个元素。这是因为CopyOnWriteArrayList遵循写时复制的原则，得到的迭代器持有数组的引用，如果在这期间数组被修改，是不会影响到原数组的，因为修改的是副本，更新的也是副本的引用，迭代器得到的数组就是一个“快照”，它稳定而不会被修改。因此在获取迭代器后对原数组进行修改是不会再迭代器上体现的。

普通ArrayList

换为普通的ArrayList进行测试，代码如下：

public class Test {   
        public static void main(String[] args){
                    ArrayList<Integer> arrayList=new ArrayList<>();
                    arrayList.add(3);
                    arrayList.add(5);
                    Iterator<Integer> iterator=arrayList.iterator();
                    arrayList.add(2);
                    while(iterator.hasNext()){
                            System.out.println(iterator.next());
                    }
        }               
}

输出：

分析：
不出意外，报错了。普通ArrayList的操作都是基于原数组的，如果对原数组修改，就会出现问题，下面来看看源码。在获取下一个元素的时候会调用checkForComodification();

        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        final void checkForComodification() {
            if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
        }

在实例化迭代器的时候会保存一个expectedModCount值，这个值由modCount赋予。

private class Itr implements Iterator<E> {
        int expectedModCount = modCount;
}

modCount会在每次修改数组后更新，下面的add方法中调用了 ensureCapacityInternal(size + 1);方法。其中再调用ensureExplicitCapacity(minCapacity);方法。最后，我们可以看到modCount++;的结果。也就是说，在数组被修改后，modCount会改变，可以理解为版本+1。expectedModCount还是原先的值，那么在上面的迭代器的modCount != expectedModCount比较结果为true，抛出异常。

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }   
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }   

小结

CopyOnWriteArrayList采用了写时复制的策略，修改时都是基于副本进行操作，最后会更新引用关系，修改的过程是线程安全的。但CopyOnWriteArrayList存在弱一致性问题，即修改操作不能立刻可见，在读取数据的时候可能会出现不一致的现象。迭代器遍历的数组是一个快照，反映的是迭代器获取前数组的状态。
---------------------
【转载，仅作分享，侵删】
作者：mayifan_blog
原文：https://blog.csdn.net/mayifan_blog/article/details/87214647
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-2-26 15:33
奈斯，感谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2