并发中的List集合 并发arraylist

实际开发中, 我们使用频率最高的容器估计是list集合,那肯定会遇并发操作.那该如何保证在多线程并发的环境下安全,高效的使用list集合呢?好,这就是今天我们聊话题:并发中的List集合.

家族体系

List: 有序集合（也称为序列 ）。用户可以精确控制列表中每个元素的插入位置。 也可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。 常用方法有:

添加: boolean add(E e);

删除: boolean remove(Object o);

修改: E set(int index, E element);

查询: E get(int index);

下面是List接口的实现体系:

常见的实现类:

ArrayList : 可调整大小的数组的实现List接口

LinkedList :实现List和Deque接口的双链表

Vector: 实现了可扩展的对象数组,是同步的ArrayList

CopyOnWriteArrayList:带有快照功能的读写安全并发容器类

Stack:最先进先出（LIFO）堆栈的对象

具体分析

List集合实现类众多,本篇挑出具有代表选3个实现类来逐一分析, 在并发环境下,它们的使用注意.

ArrayList

ArrayList 类其下所有操作方法都没有使用任何加锁痕迹,这表明该类是一个线程不安全类.比如下面添加的方法:

 public boolean add(E e) {
 ensureCapacityInternal(size + 1); 
 elementData[size++] = e;
 return true;
 }
 private void ensureCapacityInternal(int minCapacity) {
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
 }
 ensureExplicitCapacity(minCapacity);
 }

在多线程环境下, 如果使用ArrayList进行操作时,可能存在线程不安全的隐患, 比如下面的例子:

需求:事先准备好一个集合list, 一个线程删除最后一个元素, 一个线程清空list集合

public class App {
 public static void main(String[] args) {
 ArrayList<String> list = new ArrayList<>();
 list.add("1");
 list.add("2");
 new Thread(new Runnable() {
 public void run() {
 //集合大小
 int len = list.size();
 try {
 //睡5s
 Thread.sleep(5000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 //删除最后一个
 list.remove(len-1);
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 //清空集合
 list.clear();
 }
 }, "t2").start();
 }
}

不出意外,线程t1,在执行list.remove操作时报错了

Exception in thread "t1" java.lang.IndexOutOfBoundsException: Index: 1, Size: 0
 at java.util.ArrayList.rangeCheck(ArrayList.java:653)
 at java.util.ArrayList.remove(ArrayList.java:492)
 at cn.wolfcode.ch13.App$1.run(App.java:20)
 at java.lang.Thread.run(Thread.java:745)

分析:线程t1先执行,获取到的list的size为2, 暂停5s, 线程t2开始执行, 清空list集合, 线程t1休眠时间结束,此时再删除就出现数组越界.因为数据已清空.

问: 怎么解决这个问题, 可能有朋友提出使用Vector, 它是线程安全的, 确定么?

Vector

Vector类出现时间比Arraylist早, 在JDK1.0 版本时候就出来了, JDK1.2版本之后纳入的list集合体系.Vector 对外暴露的方法都是以synchronized修饰的, 也表示其自带线程同步基因.天生是线程安全的.如下:

 public synchronized boolean add(E e) {
 modCount++;
 ensureCapacityHelper(elementCount + 1);
 elementData[elementCount++] = e;
 return true;
 }

了解Vector类之后我们回到刚刚的问题, 将ArrayList改为Vector再看

public class App {
 public static void main(String[] args) {
 // ArrayList<String> list = new ArrayList<>();
 Vector<String> list = new Vector<>();
 list.add("1");
 list.add("2");
 new Thread(new Runnable() {
 public void run() {
 //集合大小
 int len = list.size();
 try {
 //睡5s
 Thread.sleep(5000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 //删除最后一个
 list.remove(len-1);
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 //清空集合
 list.clear();
 }
 }, "t2").start();
 }
}

切换成Vector之后, 大家会发现,错误依旧, 什么原因? 原因非常简单, 是大家对Vector线程安全的误解:

Vector确实是线程安全的, 但是它的安全是有前提的.并发环境下, vector只能保证同一时刻,唯一一个线程同步操作vector, 因为vector方法执行必须先得持有vector对象锁.

 public synchronized boolean add(E e) {
 modCount++;
 ensureCapacityHelper(elementCount + 1);
 elementData[elementCount++] = e;
 return true;
 }

在这前提下, 如果我们对Vector方法进行复合操作, Vector的同步也就是一个摆设. 比如上述例子中线程t1执行list.size()方法,此时线程t1持有list对象锁.其他线程等待. 线程t1执行完list.size方法之后会释放list对象锁. 之后进入休眠. 线程t2获取list对象锁后, 遍可以操作list, 而一旦线程t2操作了list对象, 那数组越界问题就出现了. 所以说, list.size 跟 list.remove 这2个方法 单独操作时,是线程安全的, 一定分开操作,那vector就不是大家所认为的线程安全操作了.

至于上述问题怎么解决, 只需要加额外的锁, 保证list操作是同步即可

ArrayList

public class App {
 public static void main(String[] args) {
 ArrayList<String> list = new ArrayList<>();
 list.add("1");
 list.add("2");
 new Thread(new Runnable() {
 public void run() {
 synchronized (list){
 //集合大小
 int len = list.size();
 try {
 //睡5s
 Thread.sleep(5000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 //删除最后一个
 list.remove(len-1);
 }
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 synchronized (list){
 //清空集合
 list.clear();
 }
 }
 }, "t2").start();
 }
}

Vector : 跟Arraylist区别是线程t2不需要给list加锁, 默认已经加上了.

public class App {
 public static void main(String[] args) {
 Vector<String> list = new Vector<>();
 list.add("1");
 list.add("2");
 new Thread(new Runnable() {
 public void run() {
 synchronized (list){
 //集合大小
 int len = list.size();
 try {
 //睡5s
 Thread.sleep(1000);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 //删除最后一个
 list.remove(len-1);
 }
 }
 }, "t1").start();
 new Thread(new Runnable() {
 public void run() {
 //清空集合
 list.clear();
 }
 }, "t2").start();
 }
}

结论: Vector 在复合操作无法保证线程安全, 需要额外加锁以保证线程安全.

Collections.synchronizedList

JDK1.2之后提供一个工具类Collections用于对集合进行功能增强, 里面有synchronizedList方法可以将普通的Arraylist转换成线程安全的list, 具体操作:

ArrayList<String> list1 = new ArrayList<>();
List<String> list = Collections.synchronizedList(list1);

上面代码可以看到,普通的Arraylist作为参数,在执行完Collections.synchronizedList方法后可以得到线程安全的list集合.具体怎么做到的呢?

一起看下源码

Collections:

 public static <T> List<T> synchronizedList(List<T> list) {
 return (list instanceof RandomAccess ?
 new SynchronizedRandomAccessList<>(list) :
 new SynchronizedList<>(list));
 }

调用synchronizedList,它底层有个三元判断表达式, 这里姑且不理会判断逻辑, 继续点入SynchronizedRandomAccessList 会发现它其实是SynchronizedList一个子类, 所以我们只需要跟踪SynchronizedList类即可.再深入.

Collections$SynchronizedList: Collections静态内部类:

static class SynchronizedList<E>
 extends SynchronizedCollection<E>
 implements List<E> {
 final List<E> list;
 SynchronizedList(List<E> list) {
 super(list);
 this.list = list;
 }
 public E get(int index) {
 synchronized (mutex) {return list.get(index);}
 }
 public E set(int index, E element) {
 synchronized (mutex) {return list.set(index, element);}
 }
 public void add(int index, E element) {
 synchronized (mutex) {list.add(index, element);}
 }
 public E remove(int index) {
 synchronized (mutex) {return list.remove(index);}
 }
 //省略一堆方法
}

看方法,大家就可以发现,SynchronizedList会对传入的ArrayList类进行功能增强, list中的crud方法都都进行加锁处理.而锁对象叫mutex.而这个mutex是啥, 我们继续跟踪, 点击SynchronizedList类继承父类SynchronizedCollection,会发现, SynchronizedCollection还是Collections的静态内部类

Collections$SynchronizedCollection

 static class SynchronizedCollection<E> implements Collection<E>, Serializable {
 private static final long serialVersionUID = 3053995032091335093L;
 final Collection<E> c; // Backing Collection
 final Object mutex; // Object on which to synchronize
 SynchronizedCollection(Collection<E> c) {
 this.c = Objects.requireNonNull(c);
 mutex = this;
 }
 //再省略一堆方法
}

此时你会看到SynchronizedCollection持有一个final修饰的mutex属性, 其构造器中的给mutex属性赋值,而值恰恰是它自己.折腾来折腾去,大家会发现 Collections.synchronizedList(list1); 转换的结果与Vector操作实现类似.换一句话说,在复合操作时Collections.synchronizedList(list1)也一样需要额外加锁控制保证线程安全.

CopyOnWriteArrayList

前面Arraylist Vector synchronizedList 方法都无法优雅解决list的复合操作, 那这个

CopyOnWriteArrayList 应该可以解决了吧? 呵呵, 你想多了.CopyOnWriteArrayList设计确实是为了解决list复合操作线程安全问题.但是它针对仅仅是并发环境下读与写线程安全.简单的讲, 它只能保证, 一边线程主读(遍历/获取), 一边线程主写(添加/删除/修改)操作上的安全. 而前面提到的例子,一边线程读写, 一边线程读,这情景 已经不适用CopyOnWriteArrayList操作范畴了.

本文作者：叩丁狼教育高级讲师王一飞老师