CopyOnWriteArrayList,一个面试中经常问到的冷门容器-白红宇

CopyOnWriteArrayList,一个面试中经常问到的冷门容器

阅读量：4036 次

发布时间：2019-05-24

本文共 2642 字，大约阅读时间需要 8 分钟。

话说这个容器都说比较冷门，我自己也确实是没用过，但是在看各种面经的时候却经常见到。因此这篇文章适合正载找工作的你。

最近把名称改了，由java的架构师技术栈，改为了愚公要移山。觉得自己并不聪明，但是勤奋和努力还是少不了的。因此愚公适合自己。

OK。开始今天的文章。

一、简介

1、ArrayList非线程安全的缺陷

说到这个容器，从名字就可以看出，不得不说另外一个容器，也就是ArrayList。ArrayList是非线程安全的，也就是说在多个线程下进行读写，会出现异常。先举一个简单地例子，看看会出现什么问题，再来理解：

public class ArrayListTest {
   	private static List
   
     list = new ArrayList<>();	public static void main(String[] args) {
   		list.add("1");list.add("2");list.add("3");		final Iterator
    
      it = list.iterator();		ExecutorService service = Executors.newFixedThreadPool(10);		//10个线程读		for (int i = 0; i < 10; i++) {
   			service.execute(new Runnable() {
   				@Override				public void run() {
   					while (it.hasNext()) {
   						System.err.println(it.next());					}				}			});		}		//10个线程写		for (int i = 0; i < 10; i++) {
   			service.execute(new Runnable() {
   				@Override				public void run() {
   					list.add("愚公");				}			});		}	}}

我们运行一下就会出现错误：

这里我们可以看到会抛出ConcurrentModificationException，这个异常是基于 fast-fail 机制的。不知道的可以私下了解一下。

上面这个案例说明了ArrayList使用的局限性，既然是非线程安全，那我们就使用一些机制把他变安全不就好了。变安全的方法有很多。比如说替换成Vector，再或者是使用 Collections，可以将 ArrayList 包装成一个线程安全的类。不过这两种方法也有很大的缺点，那就是他们使用的都是独占锁，独占式锁在同一时刻只有一个线程能够获取，效率太低。于是CopyOnWriteArrayList 应用而生了。

2、CopyOnWriteArrayList 介绍

（1）独占锁效率低：采用读写分离思想解决

既然独占锁的效率低下，那我们可以换一种方式，采用读写分离式的思想将读操作和写操作进行分开即可。

读操作不加锁，所有线程都不会阻塞。写操作加锁，线程会阻塞。

（2）写线程获取到锁，其他线程包括读线程阻塞

但是这时候又出现了另外一个问题了：写线程获取到锁之后，其他的读线程会陷入阻塞。

（3）复制思想：解决问题2

这咋办呢？我们可以再转化一下思想：

当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

这时候会抛出来一个新的问题，也就是数据不一致的问题。如果写线程还没来得及写会内存，其他的线程就会读到了脏数据。

这就是CopyOnWriteArrayList 的思想和原理。就是拷贝一份写。所以使用条件也很局限，那就是在读多写少的情况下比较好。

二、源码分析（基于JDK1.8）

既然CopyOnWriteArrayList 主要是针对的读写操作，我们可以看看这两个方法的源码是如何实现的。

1、get方法

public E get(int index) {
         return get(getArray(), index);}//这个方法很简单，没有加锁：主要是通过getArray()来实现的final Object[] getArray() {
         return array;}

整个读的过程没有添加任何锁，就是普通的数组获取。

2、add方法

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();     }}

写操作添加了一个锁ReentrantLock，这个锁我们可以决定在什么时候加锁和释放更加灵活。保证了写操作线程安全。能够体现Copy的思想代码是 Arrays.copyOf(elements, len + 1);也就是数组复制了一份，最后setArray回去。

三、总结

这个容器很简单，虽然是采用了读写分离的思想，但是却有很大不同，不同之处在于copy。

1、读写锁

读线程具有实时性，写线程会阻塞。解决了数据不一致的问题。但是读写锁依然会出现读线程阻塞等待的情况

2、CopyOnWriteArrayList

读线程具有实时性，写线程会阻塞。不能解决数据不一致的问题。但是CopyOnWriteArrayList 不会出现读线程阻塞等待的情况

OK，今天的文章先写到这。因为简单比较短。

转载地址：http://opbdi.baihongyu.com/

你可能感兴趣的文章