一、初始化和add

构造方法恶化add

ArrayList（int initialCapacity）会不会初始化数组大小？

会初始化数组大小！但是List的大小没有变，因为list的大小是返回size的。

test

二、set方法

set方法

从方法中可以看出，element是可以传null的。至于为什么强调这个，请继续看下去。

三、remove方法

• remove(Object o)

  
  remove(Object o)

删除逻辑

这里对o判断为null的情形就是为了应对set方法把数组中间的元素设置为null的情形，把数组零散的数据规整一下。
o不为null的情形，也提醒我们需要重写equal()方法。

• remove(int index)

  
  remove(int index)
  

  这个删除方法就更简单了，删除的逻辑和fastRemove()几乎一模一样。

四、时间复杂度

如果我们不指定位置直接添加元素时(add(E element))，元素会默认会添加在最后，不会触发底层数组的复制，不考虑底层数组自动扩容的话，时间复杂度为O(1) ，在指定位置添加元素(add(int index, E element))，需要复制底层数组，根据最坏打算，时间复杂度是O(n)。

底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)。

当我们ArrayLIst里有大量数据时，这时候去频繁插入/删除元素会触发底层数组频繁拷贝，效率不高，还会造成内存空间的浪费，这个问题在另一个类：LinkedList里有解决方案，请期待后续文章讲解。

五、Arraylist与Vector的区别

首先我们给出标准答案：
1、Vector是线程安全的，ArrayList不是线程安全的。
2、ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。
Vector是怎么保证线程安全的：
只要是关键性的操作，方法前面都加了synchronized关键字，来保证线程的安全性。当执行synchronized修饰的方法前，系统会对该方法加一把锁，方法执行完成后释放锁，加锁和释放锁的这个过程，在系统中是有开销的，因此，在单线程的环境中，Vector效率要差很多。（多线程环境不允许用ArrayList，需要做处理）。

六、性能更高的线程安全容器 -- CopyOnWriteArrayList

先来看看为什么需要CopyOnWriteArrayList,它出现的意义是什么？

package collections.copyonwrite;

import java.util.Iterator;
import java.util.Vector;

public class CopyOnWriteArrayListDemo3 {
    private static Vector<String> vector = new Vector();
    static {
        vector.add("1");
        vector.add("2");
        vector.add("3");
        vector.add("4");
    }
    public static void main(String[] args) {
        Iterator<String> iterator = vector.iterator();
        Thread thread = new Thread(()->{
            try {
                Thread.sleep(1500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("come ");
            vector.remove(2);}
        );
        thread.start();
        while (iterator.hasNext()){
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println(iterator.next());
        }

    }
}

运行结果：

抛出ConcurrentModificationException异常

如果想要完美解决上面所讲的问题，我们可以在遍历前加锁：

package collections.copyonwrite;

import java.util.Iterator;
import java.util.Vector;

public class CopyOnWriteArrayListDemo3 {
    private static Vector<String> vector = new Vector();
    static {
        vector.add("1");
        vector.add("2");
        vector.add("3");
        vector.add("4");
    }
    public static void main(String[] args) {
        Iterator<String> iterator = vector.iterator();
        Thread thread = new Thread(()->{
            try {
                Thread.sleep(1500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("come ");
            vector.remove(2);}
        );
        thread.start();
        synchronized (vector){
            while (iterator.hasNext()){
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(iterator.next());
            }
        }
    }
}

运行结果：

remove操作必须等待迭代的锁释放了再去remove，这样就不会抛ConcurrentModificationException错误了

迭代时无法编辑是vector的致命缺点。

所以我们的CopyOnWriteArrayList就登场了！

package collections.copyonwrite;

import java.util.Iterator;
import java.util.Vector;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListDemo3 {
    private static CopyOnWriteArrayList<String> cow = new CopyOnWriteArrayList();

    static {
        cow.add("1");
        cow.add("2");
        cow.add("3");
        cow.add("4");
    }
    public static void main(String[] args) {
        Iterator<String> iterator = cow.iterator();
        Thread thread = new Thread(()->{
            try {
                Thread.sleep(1500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("come ");
            cow.remove(2);}
        );
        thread.start();
            while (iterator.hasNext()){
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(iterator.next());
            }
    }
}

结果：

image.png
注意这里的运行结果虽然和上个例子的结果是一样的，但是本质完全不一样。这里remove不需要“等待”迭代操作。

6.1 看一下CopyOnWriteArrayList基本的结构

    /** 可重入锁对象 */
    final transient ReentrantLock lock = new ReentrantLock();

    /** CopyOnWriteArrayList底层由数组实现，volatile修饰 */
    private transient volatile Object[] array;

    /**
     * 得到数组
     */
    final Object[] getArray() {
        return array;
    }

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

    /**
     * 初始化CopyOnWriteArrayList相当于初始化数组
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

看起来挺简单的，CopyOnWriteArrayList底层就是数组，加锁就交由ReentrantLock来完成。

6.2 真相浮出水面

CopyOnWriteArrayList使用迭代器遍历时不需要显示加锁，看看add()、clear()、remove()与get()方法的实现可能就有点眉目了。

    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;
            
            // 将volatile Object[] array 的指向替换成新数组
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

通过代码我们可以知道：在添加的时候就上锁，并复制一个新数组，增加操作在新数组上完成，将array指向到新数组中，最后解锁。
remove()、clear()、set()和add()类似，这里不再阐述。
看到这我们知道每进行一次add()等修改操作是在新数组完成的，那我们是不是能猜想迭代时之所以不用加锁，是因为“读“和”写”是分离的，在各自数组上完成，互不干扰。
所以我们来求证一下，来看一下他的迭代器吧：

    // 1. 返回的迭代器是COWIterator
    public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }


    // 2. 迭代器的成员属性
    private final Object[] snapshot;
    private int cursor;

    // 3. 迭代器的构造方法
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    // 4. 迭代器的方法...
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

    //.... 可以发现的是，迭代器所有的操作都基于snapshot数组，而snapshot是传递进来的array数组

到这里，我们应该就可以想明白了！CopyOnWriteArrayList在使用迭代器遍历的时候，操作的都是原数组！所以读和写在两块不同的内存上，自然就不需要加锁同步了。
另外我们从源码中也可以得出一个结论，调用CopyOnWriteArrayList.iterator()方法返回迭代器时传的参数当前的底层数组，所以迭代器的值取决于诞生时间，而非迭代时间。我们来看一个例子比较容易理解。

package collections.copyonwrite;

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * 描述：     对比两个迭代器
 */
public class CopyOnWriteArrayListDemo2 {

    public static void main(String[] args) throws InterruptedException {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>(new Integer[]{1, 2, 3});

        System.out.println(list);
        //迭代器的值取决于诞生时间，而非迭代时间
        Iterator<Integer> itr1 = list.iterator();

        list.remove(2);
        Thread.sleep(1000);
        System.out.println(list);

        Iterator<Integer> itr2 = list.iterator();

        itr1.forEachRemaining(System.out::println);
        itr2.forEachRemaining(System.out::println);

    }
}

运行结果：

image.png

6.3 CopyOnWriteArrayList缺点

看了上面的实现源码，我们应该也大概能分析出CopyOnWriteArrayList的缺点了。

• 内存占用：如果CopyOnWriteArrayList经常要增删改里面的数据，经常要执行add()、set()、remove()的话，那是比较耗费内存的。
  因为我们知道每次add()、set()、remove()这些增删改操作都要复制一个数组出来。

• 数据一致性：CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。
  从上面的例子也可以看出来，比如线程A在迭代CopyOnWriteArrayList容器的数据。线程B在线程A迭代的间隙中将CopyOnWriteArrayList部分的数据修改了(已经调用setArray()了)。但是线程A迭代出来的是原有的数据。

6.4适用场景

• 读操作尽可能快，而写操作慢一点也没关系
• 读多写少：黑名单，每日大多只更新一遍；监听器：迭代操作远多于修改操作。