List线程安全问题

1. 发现问题

List<Integer> list = new ArrayList<>(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"A").start(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"B").start(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"C").start(); try { 
    TimeUnit.SECONDS.sleep(3); }catch (InterruptedException e) { 
    e.printStackTrace(); } System.out.println("list.size() = " + list.size()); 

开启三个线程，每个线程向ArrayList中插入1w条数据。

之后等待三秒，等到每个线程都执行完毕时再查看ArrayList中的元素个数。

运行结果：

• 问题一：ArrayIndexOutOfBoundsException

public boolean add(E e) { 
    ensureCapacityInternal(size + 1); // 检查容量，必要时扩容 elementData[size++] = e; //扩容后 添加元素 return true; } 

在多线程环境中时，多个线程同时进入add()方法，同时检查容量，例如当前容量为5，而已占用4。

三个线程同时检查，都发现还有容量，则都同时添加元素。

由此导致ArrayIndexOutOfBoundsException。

• 问题二：实际插入元素个数小于预期插入元素个数

从运行结果可以看出，最终list.size()只有18935 <= 30000。我们希望能够插入30000个元素，可是实际上只插入了<= 30000个元素。

还是从源码入手：

public boolean add(E e) { 
    ensureCapacityInternal(size + 1); elementData[size++] = e; //添加元素后 size自增 return true; } 

试想一下，如果多个线程同时向size位插入元素，且都没有来得及size++，那么导致的结果就是

多个元素被插入在了同一个位置，相互抵消。

2. 解决问题（一）Vector

早期，IT前人为了解决List在并发时出现的问题，引入了Vector实现类。

Vetor的实现方式与ArrayList大同小异，它的底层也是一个数组，在添加时自增长。

public synchronized boolean add(E e) { 
    modCount++; ensureCapacityHelper(elementCount + 1); //检查容量 必要时增长 elementData[elementCount++] = e; return true; } 

与ArrayList不同的是，它的add()方法带有synchronized关键字。

这表明当线程调用该方法时，会自动占用锁，直到这个线程的任务完成，期间不会放弃该锁。

而且当线程占有该锁时，别的线程无法进入Vetor类调用带有synchronized关键字的方法。

这很好的避免了多线程竞争的现象，从而保证了并发安全。

试一试？

Vector<Integer> list = new Vector<>(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"A").start(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"B").start(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"C").start(); try { 
    TimeUnit.SECONDS.sleep(3); }catch (InterruptedException e) { 
    e.printStackTrace(); } System.out.println("list.size() = " + list.size()); // 30000 

3.解决问题（二）Collections.synchronizedList(List

list)


废话不多说，直接上源码。

List<Object> list = Collections.synchronizedList(new ArrayList<>()); // Collections.synchronizedList 源码 public static <T> List<T> synchronizedList(List<T> list) { 
    return (list instanceof RandomAccess ? //暂且不说 new SynchronizedRandomAccessList<>(list) : new SynchronizedList<>(list)); //创建一个 SynchronizedList 实例 } SynchronizedList(List<E> list) { 
    super(list); // 调用父类构造器 this.list = list; } SynchronizedCollection(Collection<E> c) { 
    this.c = Objects.requireNonNull(c); //要求传入的 集合类实例 非空 并将这个集合赋值给 c 变量 mutex = this; // 将自己赋值给 互斥锁变量 } public static <T> T requireNonNull(T obj) { 
    if (obj == null) throw new NullPointerException(); //为空则抛出异常 return obj; } 

Collections.synchronizedList()方法会返回一个SynchronizedList类的实例，其中包含了调用该方法时传入的集合，在构造期间，将SynchronizedCollection作为互斥锁。

此时，当我们再调用add()方法：

public boolean add(E e) { 
    synchronized (mutex) { 
    //锁住 SynchronizedCollection 集合类 return c.add(e); } } 

这是，当调用add()方法，SynchronizedCollection会锁住自己，从而保证线程安全。

当有线程正在使用mutex互斥锁时，其他变量无法占有该锁。

4. 手写实现一个简易版SynchronizedCollection

package top.ptcc9; import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.ListIterator; / * @Author HE LONG CAN * @Description TODO * @Date 2022-04-21 22:55:24 */ public class MySynchronizedArrayList<E> implements List<E> { 
    private Collection<E> list = null; / * 充当锁 final避免object被重新赋值 */ private final Object object = new Object(); public MySynchronizedArrayList(Collection<E> t) { 
    this.list = t; } @Override public int size() { 
    return list.size(); } @Override public boolean add(E e) { 
    synchronized (object) { 
    //枷锁 list.add(e); } return true; } //..... 此处省略 List 接口的一万个方法 } List<Integer> list = new MySynchronizedArrayList<>(new ArrayList<>()); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"A").start(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"B").start(); new Thread(() -> { 
    for (int i = 0; i < 10000; i++) { 
    list.add(1); } },"C").start(); try { 
    TimeUnit.SECONDS.sleep(3); }catch (InterruptedException e) { 
    e.printStackTrace(); } System.out.println("list.size() = " + list.size()); // 30000 

5. 解决问题（三）CopyOnWriteArrayList

一个写时复制的List，写操作时加锁，过程中创建一个新的数组长度为原来的数组+1，并将原有数组元素添加到新数组中，之后添加新元素到末尾。

读时不加锁，底层数组被volatile修饰，线程可见。

他的核心就是：读时不阻塞，大大提升了读的速度。

废话不多说，直接上源码：

List<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>(); final transient ReentrantLock lock = new ReentrantLock(); private transient volatile Object[] array; // volatile线程可见 底层数组 //调用构造器 public CopyOnWriteArrayList() { 
    setArray(new Object[0]); //设置底层 array为一个空数组 } //将传入 array 设置给 底层 array final void setArray(Object[] a) { 
    array = a; } // 写时 public boolean add(E e) { 
    final ReentrantLock lock = this.lock; // 获取锁对象 lock.lock(); //锁住 try { 
    Object[] elements = getArray(); //获取到原有 数组 int len = elements.length; //获取原有长度 // 创建新数组为原有长度 + 1，将原有数据拷贝到新数组里，此时新数组有一个空位 Object[] newElements = Arrays.copyOf(elements, len + 1); // 向空位添加新元素 newElements[len] = e; // 将新数组 替换掉 旧数组 setArray(newElements); return true; } finally { 
    lock.unlock(); //解锁 } } // 获取列表长度 public int size() { 
    // 由于底层array线程可见，所以array一旦改变 size 也会被其他线程发现 return getArray().length; } final Object[] getArray() { 
    return array; } 

线程可见的重要性：

由于JVM中，栈空间是线程私有的。而栈中存在一个局部变量表，用于存储运行时需要的变量。

在线程被开启时，线程会将自己所需要的变量都拷贝到自己的栈内存中。在循环过程中，局部变量表中的元素是无法感知到变量的改变的。

简单来说，线程在使用外部变量时，无法感知到变量的改变。

• 线程不可见的一个栗子：

List<Integer> list = new CopyOnWriteArrayList<>(); list.add(0); new Thread(() -> { 
    while (list.get(0) == 0) { 
    //循环获取 list 的 0 位元素 } System.out.println("结束了"); }).start(); try { 
    TimeUnit.SECONDS.sleep(3); }catch (InterruptedException e) { 
    e.printStackTrace(); } list.add(0,1); //三秒后修改 list 的 0 位元素 // .... 程序无法结束 因为主线程对list的修改，线程内部无法感知 

跑起来后，可以发现程序无法结束。

• 使用CopyOnWriteArrayList线程可见的栗子：

// 使用　CopyOnWriteArrayList List<Integer> list = new CopyOnWriteArrayList<>(); list.add(0); new Thread(() -> { 
    while (list.get(0) == 0) { 
    } System.out.println("结束了"); }).start(); try { 
    TimeUnit.SECONDS.sleep(3); }catch (InterruptedException e) { 
    e.printStackTrace(); } list.add(0,1); // .... 程序可以结束，因为CopyOnWriteArrayList底层数组被 volatile 修饰 // 所以是线程间可见的 

6. 三个并发集合容器性能比较

① 只读10并发

• Vector

public class RunTester { 
    private static List<Integer> list = null; public static void main(String[] args) throws InterruptedException { 
    list = new Vector<>(); list.add(0); int theadNum = 10; CountDownLatch countDownLatch = new CountDownLatch(theadNum); long start = System.currentTimeMillis(); for (int i = 0; i < theadNum; i++) { 
    new Thread(() -> { 
    for (int j = 0; j < ; j++) { 
    list.get(0); } countDownLatch.countDown(); }).start(); } countDownLatch.await(); //阻塞，直到执行完毕 long end = System.currentTimeMillis(); //list.size() = 1 耗时 => 204 ms System.out.println("list.size() = " + list.size() + " 耗时 => " + (end - start) + " ms"); } } 

• SynchronizedCollection

public class RunTester { 
    private static List<Integer> list = null; public static void main(String[] args) throws InterruptedException { 
    list = Collections.synchronizedList(new ArrayList<>()); list.add(0); int theadNum = 10; CountDownLatch countDownLatch = new CountDownLatch(theadNum); long start = System.currentTimeMillis(); for (int i = 0; i < theadNum; i++) { 
    new Thread(() -> { 
    for (int j = 0; j < ; j++) { 
    list.get(0); } countDownLatch.countDown(); }).start(); } countDownLatch.await(); //阻塞，直到执行完毕 long end = System.currentTimeMillis(); //list.size() = 1 耗时 => 205 ms System.out.println("list.size() = " + list.size() + " 耗时 => " + (end - start) + " ms"); } } 

• CopyOnWriteArrayList

public class RunTester { 
    private static List<Integer> list = null; public static void main(String[] args) throws InterruptedException { 
    list = new CopyOnWriteArrayList<>(); list.add(0); int theadNum = 10; CountDownLatch countDownLatch = new CountDownLatch(theadNum); long start = System.currentTimeMillis(); for (int i = 0; i < theadNum; i++) { 
    new Thread(() -> { 
    for (int j = 0; j < ; j++) { 
    list.get(0); } countDownLatch.countDown(); }).start(); } countDownLatch.await(); //阻塞，直到执行完毕 long end = System.currentTimeMillis(); //list.size() = 1 耗时 => 53 ms System.out.println("list.size() = " + list.size() + " 耗时 => " + (end - start) + " ms"); } } 

分析：

// Vector.get() public synchronized E get(int index) { 
    if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); } // Synchronized 集合 get() public E get(int index) { 
    synchronized (mutex) { 
    return list.get(index); //调用 List.get()方法 } } // CopyOnWriteArrayList.get() public E get(int index) { 
    return get(getArray(), index); } private E get(Object[] a, int index) { 
    return (E) a[index]; } 

从运行耗时来看，CopyOnWriteArrayList的性能比其他两个好得多。

从源码来看，Vector和Synchronized集合类都使用到了synchronized关键字，锁住了整个方法。

这样使得多条线程并发访问get()方法时，只会同时有一个线程在真正调用get()方法。

而CopyOnWriteArrayList的get()方法没有使用到锁，所以所有线程都是一起访问的，所以它的性能更好。

② 只写10并发

• Vector

public class RunTester { 
    private static List<Integer> list = null; public static void main(String[] args) throws InterruptedException { 
    list = new Vector<>(); list.add(0); int theadNum = 10; CountDownLatch countDownLatch = new CountDownLatch(theadNum); long start = System.currentTimeMillis(); for (int i = 0; i < theadNum; i++) { 
    new Thread(() -> { 
    for (int j = 0; j < ; j++) { 
    list.add(0); } countDownLatch.countDown(); }).start(); } countDownLatch.await(); //阻塞，直到执行完毕 long end = System.currentTimeMillis(); //list.size() = 耗时 => 228 ms System.out.println("list.size() = " + list.size() + " 耗时 => " + (end - start) + " ms"); } } 

• SynchronizedCollection

public class RunTester { 
    private static List<Integer> list = null; public static void main(String[] args) throws InterruptedException { 
    list = Collections.synchronizedList(new ArrayList<>()); list.add(0); int theadNum = 10; CountDownLatch countDownLatch = new CountDownLatch(theadNum); long start = System.currentTimeMillis(); for (int i = 0; i < theadNum; i++) { 
    new Thread(() -> { 
    for (int j = 0; j < ; j++) { 
    list.add(0); } countDownLatch.countDown(); }).start(); } countDownLatch.await(); //阻塞，直到执行完毕 long end = System.currentTimeMillis(); //list.size() = 耗时 => 260 ms System.out.println("list.size() = " + list.size() + " 耗时 => " + (end - start) + " ms"); } } 

• CopyOnWriteArrayList

public class RunTester { 
    private static List<Integer> list = null; public static void main(String[] args) throws InterruptedException { 
    list = new CopyOnWriteArrayList<>(); list.add(0); int theadNum = 10; CountDownLatch countDownLatch = new CountDownLatch(theadNum); long start = System.currentTimeMillis(); for (int i = 0; i < theadNum; i++) { 
    new Thread(() -> { 
    for (int j = 0; j < ; j++) { 
    list.add(0); } countDownLatch.countDown(); }).start(); } countDownLatch.await(); //阻塞，直到执行完毕 long end = System.currentTimeMillis(); //大于10分钟 不想等了 System.out.println("list.size() = " + list.size() + " 耗时 => " + (end - start) + " ms"); } } 

从运行结果可以看出，CopyOnWriteArrayList的写性能，实在是太差了，这是为什么呢？

我们来看看源码：

// CopyOnWriteArrayList.add() public boolean add(E e) { 
    final ReentrantLock lock = this.lock; lock.lock(); try { 
    Object[] elements = getArray(); //获取旧数组 int len = elements.length; //长度 //创建一个原来数组长度 + 1 的新数组，复制原有内容到新数组 Object[] newElements = Arrays.copyOf(elements, len + 1); //添加一个元素 newElements[len] = e; //替换掉旧数组 setArray(newElements); return true; } finally { 
    lock.unlock(); } } 

CopyOnWriteArrayList使用写时复制。

添加新元素时，每次仅扩容1，然后将旧数组内容拷贝到新数组中，所以它的扩容，是每次都会触发的。这也是导致写性能差最主要的原因。

但是为什么要只扩容1呢？为何不像Vector一样，每次扩容两倍呢？

我猜测，这应该是为了避免维护一个size变量，size表示当前实际存入元素的个数。

而每次扩容1，那么数组的长度就是size，所以省去了size的并发修改。

简单来说，强悍的读取性能，是牺牲写入性能换来的。

所以这也表明，CopyOnWriteArrayList容器虽好，可不要滥用。

在写多于读的情况下，它的性能甚至比其他两个并发容器都要差得多！