ArrayList 线程不安全问题

ArrayList 底层的数据结构其实是数组结构。

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

我们来看一下 ArrayList 的 add 方法源码，上面的代码主要做了两步操作，判断当前 size+1 是否超过了数组长度和将当前数据放到数组的当前 size+1 的下标中。

这里就体现出线程不安全的情况了，在 ensureCapacityInternal(size + 1); 这步操作时，如果是多线程的情况下，如果数组大小为10，此时的 size 为9，那么线程 A 首先判断 size+1 不会导致数组下标越界，然后挂起。随后线程 B 也走到这一步发现不需要扩容，这时候执行完赋值方法后，size 大小为10了。此时线程A开始赋值，就会导致数组下标越界异常。

另外一种情况就是在 elementData[size++] = e; 这步操作的时候。我们为了好理解可以把这行代码拆分为如下代码：

elementData[size] = e;
size++；

我们发现这行代码其实并不是一个原子性的操作。它是首先将值新增到当前size位置，然后进行 size++。这个时候就会出现值被覆盖的问题。首先线程 A 将值新增到当前 size 后，在还未进行 size++ 的时候，线程 B 也将值新增到了当前的 size，此时就会造成线程A新增的值被覆盖。

LinkedList 线程不安全问题

LinkedList 的底层数据结构为双向链表，每个节点存储着数据值以及前继指针和后继指针的指向地址值。

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

我们先来看一下 LinkedList 的 add 方法，这个方法主要做了两个操作，一个是指针指向，一个是将 size++。那这里如果是多线程的情况下就会发生数据覆盖的问题。首先线程 A 改变了指针指向，在还未 size++ 时挂起，然后线程 B 也改变指针指向，将前置指针和后继指针指向 A 指向的位置，执行完成后就会导致线程A的数据因为没有指针指向它，而导致数据丢失。

synchronizedList

synchronizedList 的使用方式：

public void test(){
  ArrayList<String> list = new ArrayList<>();
  List<String> sycList = Collections.synchronizedList(list);
  sycList.add("a");
  sycList.remove("a");
}

从上面的使用方式中我们可以看出，synchronizedList 是将 List 集合作为参数来创建的 synchronizedList 集合。

synchronizedList 为什么是线程安全的呢？我们先来看一下他的源码：

@Override
public boolean add(T e) {
  synchronized(mutex) {
    return backingList.add(e);
  }
}

@Override
public boolean remove(Object o) {
  synchronized(mutex) {
    return backingList.remove(o);
  }
}

我们大概贴了一些常用方法的源码，从上面的源码中我们可以看出，其实 synchronizedList 线程安全的原因是因为它几乎在每个方法中都使用了 synchronized 同步锁。

synchronizedList 遍历为什么还需要加锁？

synchronizedList官方文档中给出的使用方式是以下方式：

List list = Collections.synchronizedList(new ArrayList());

synchronized (list) {
  Iterator i = list.iterator(); // Must be in synchronized block
  while (i.hasNext())
    foo(i.next());
}

在以上源码中我们可以看出，官方文档是建议我们在遍历的时候加锁处理的。但是既然内部方法以及加了锁，为什么在遍历的时候还需要加锁呢？我们来看一下它的遍历方法：

public Iterator<T> iterator() {
  return backingList.iterator();
}

从以上源码可以看出，虽然内部方法中大部分都已经加了锁，但是 iterator 方法却没有加锁处理。那么如果我们在遍历的时候不加锁会导致什么问题呢？

试想我们在遍历的时候，不加锁的情况下，如果此时有其他线程对此集合进行 add 或者 remove 操作，那么这个时候就会导致数据丢失或者是脏数据的问题，所以如果我们对数据的要求较高，想要避免这方面问题的话，在遍历的时候也需要加锁进行处理。

synchronizedList 适合对数据要求较高的情况，但是因为读写全都加锁，所有效率较低。

CopyOnWriteArrayList

CopyOnWriteArrayList 是在执行修改操作时，copy 一份新的数组进行相关的操作，在执行完修改操作后将原来集合指向新的集合来完成修改操作。

/** The array, accessed only via getArray/setArray. */  
private volatile transient Object[] array; //保证了线程的可见性  

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); //copy一份比当前数组长度+1的array数组
    else {
      newElements = new Object[len + 1]; //将add的参数赋值
      System.arraycopy(elements, 0, newElements, 0, index);
      System.arraycopy(elements, index, newElements, index + 1, numMoved);
    }
    newElements[index] = element;
    setArray(newElements); //将原数组指向新的数组
  } finally {
    lock.unlock();
  }
}

/**
  * 将原数组指向新的数组
  */
final void setArray(Object[] a) {
  array = a;
}

CopyOnWriteArrayList 在执行 add 方法和 remove 方法的时候，分别创建了一个当前数组长度 +1 和 -1 的数组，将数据 copy 到新数组中，然后执行修改操作。修改完之后调用 setArray 方法来指向新的数组。在整个过程中是使用 ReentrantLock 可重入锁来保证不会有多个线程同时 copy 一个新的数组，从而造成的混乱。并且使用 volatile 修饰数组来保证修改后的可见性。读写操作互不影响，所以在整个过程中整个效率是非常高的。

CopyOnWriteArrayList 效率较高，适合读多写少的场景，因为在读的时候读的是旧集合，所以它的实时性不高。

Reference

https://www.jianshu.com/p/6227ab5b33f7

https://www.jianshu.com/p/6455a4e66e14