文档章节

CopyOnWriteArrayList

大白来袭
 大白来袭
发布于 2017/06/29 08:50
字数 1765
阅读 17
收藏 0

CopyOnWriteArrayList位于java.util.concurrent包下,可想而知,这个类是为并发而设计的。  由于opyOnWriteArrayList 也是List的一种实现类,当然有List的特点。

关注点 结论
是否允许为空 允许
是否允许重复 允许
是否有序 有序
是否线程安全 线程安全

Write的时候总是要Copy,也就是说对于CopyOnWriteArrayList,任何可变的操作(add、set、remove等等)都是伴随复制这个动作的。

CopyOnWriteArrayList底层

添加元素

对于CopyOnWriteArrayList来说,增加、删除、修改、插入的原理都是一样的,所以用增加元素来分析一下CopyOnWriteArrayList的底层实现机制就可以了。先看一段代码:

public static void main(String[] args)
{
     List<Integer> list = new CopyOnWriteArrayList<Integer>();
     list.add(1);
     list.add(2);
}

看一下这段代码做了什么,先是第3行的实例化一个新的CopyOnWriteArrayList:

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;
 
    /** The lock protecting all mutators */
    transient final ReentrantLock lock = new ReentrantLock();
 
    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;
    ...

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

    final void setArray(Object[] a) {
        array = a;
    }
}

底层就是一个Object[] array,然后实例化一个CopyOnWriteArrayList, Object array指向一个数组大小为0的数组。接着看一下,第4行的add一个整数1做了什么:

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

每一步都清楚地表示在图上了,一次add大致经历了几个步骤:

  1. 加锁
  2. 拿到原数组,得到新数组的大小(原数组大小+1),实例化出一个新的数组来
  3. 把原数组的元素复制到新数组中去
  4. 新数组最后一个位置设置为待添加的元素(因为新数组的大小是按照原数组大小+1来的)
  5. 把Object array引用指向新数组
  6. 解锁

整个过程看起来比较像ArrayList的扩容。有了这个基础,我们再来看一下第5行的add了一个整数2做了什么 :

和前面差不多,就不解释了。另外,插入、删除、修改操作也都是一样,每一次的操作都是以对Object[] array进行一次复制为基础的,不在赘述了。

普通List的缺陷

常用的List有ArrayList、LinkedList、Vector,其中前两个是线程非安全的,最后一个是线程安全的。我有一种场景,两个线程操作了同一个List,分别对同一个List进行迭代和删除,就如同下面的代码:

public static class T1 extends Thread
{
    private List<Integer> list;
 
    public T1(List<Integer> list)
    {
        this.list = list;
    }
 
    public void run()
    {
        for (Integer i : list)
        {
        }
    }
}
 
public static class T2 extends Thread
{
    private List<Integer> list;
 
    public T2(List<Integer> list)
    {
        this.list = list;
    }
 
    public void run()
    {
        for (int i = 0; i < list.size(); i++)
        {
            list.remove(i);
        }
    }
}

首先我在这两个线程中放入ArrayList并启动这两个线程:

public static void main(String[] args)
{
    List<Integer> list = new ArrayList<Integer>();
 
    for (int i = 0; i < 10000; i++)
    {
        list.add(i);
    }
 
    T1 t1 = new T1(list);
    T2 t2 = new T2(list);
    t1.start();
    t2.start();
}

运行结果为:

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
    at java.util.AbstractList$Itr.next(AbstractList.java:343)
    at com.xrq.test60.TestMain$T1.run(TestMain.java:19)

把ArrayList换成LinkedList,main函数的代码就不贴了,运行结果为:

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
    at java.util.LinkedList$ListItr.next(LinkedList.java:696)
    at com.xrq.test60.TestMain$T1.run(TestMain.java:19)

可能有人觉得,这两个线程都是线程非安全的类,所以不行。其实这个问题和线程安不安全没有关系,换成Vector看一下运行结果:

Exception in thread "Thread-0" java.util.ConcurrentModificationException
    at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
    at java.util.AbstractList$Itr.next(AbstractList.java:343)
    at com.xrq.test60.TestMain$T1.run(TestMain.java:19)

Vector虽然是线程安全的,但是只是一种相对的线程安全而不是绝对的线程安全,它只能够保证增、删、改、查的单个操作一定是原子的,不会被打断,但是如果组合起来用,并不能保证线程安全性。比如就像上面的线程1在遍历一个Vector中的元素、线程2在删除一个Vector中的元素一样,势必产生并发修改异常,也就是fail-fast。

CopyOnWriteArrayList的作用

把上面的代码修改一下,用CopyOnWriteArrayList:

public static void main(String[] args)
{
    List<Integer> list = new CopyOnWriteArrayList<Integer>();
 
    for (int i = 0; i < 10; i++)
    {
        list.add(i);
    }
 
    T1 t1 = new T1(list);
    T2 t2 = new T2(list);
    t1.start();
    t2.start();
}

可以运行一下这段代码,是没有任何问题的。

看到我把元素数量改小了一点,因为我们从上面的分析中应该可以出,CopyOnWriteArrayList的缺点,就是修改代价十分昂贵,每次修改都伴随着一次的数组复制;但同时优点也十分明显,就是在并发下不会产生任何的线程安全问题,也就是绝对的线程安全,这也是为什么我们要使用CopyOnWriteArrayList的原因。

另外,有两点必须讲一下。我认为CopyOnWriteArrayList这个并发组件,其实反映的是两个十分重要的分布式理念:

(1)读写分离

我们读取CopyOnWriteArrayList的时候读取的是CopyOnWriteArrayList中的Object[] array,但是修改的时候,操作的是一个新的Object[] array,读和写操作的不是同一个对象,这就是读写分离。这种技术数据库用的非常多,在高并发下为了缓解数据库的压力,即使做了缓存也要对数据库做读写分离,读的时候使用读库,写的时候使用写库,然后读库、写库之间进行一定的同步,这样就避免同一个库上读、写的IO操作太多

(2)最终一致

对CopyOnWriteArrayList来说,线程1读取集合里面的数据,未必是最新的数据。因为线程2、线程3、线程4四个线程都修改了CopyOnWriteArrayList里面的数据,但是线程1拿到的还是最老的那个Object[] array,新添加进去的数据并没有,所以线程1读取的内容未必准确。不过这些数据虽然对于线程1是不一致的,但是对于之后的线程一定是一致的,它们拿到的Object[] array一定是三个线程都操作完毕之后的Object array[],这就是最终一致。最终一致对于分布式系统也非常重要,它通过容忍一定时间的数据不一致,提升整个分布式系统的可用性与分区容错性。当然,最终一致并不是任何场景都适用的,像火车站售票这种系统用户对于数据的实时性要求非常非常高,就必须做成强一致性的。

最后总结一点,随着CopyOnWriteArrayList中元素的增加,CopyOnWriteArrayList的修改代价将越来越昂贵,因此,CopyOnWriteArrayList适用于读操作远多于修改操作的并发场景中。

本文转载自:https://www.cnblogs.com/kuoAT/p/6771653.html

上一篇: 模板模式
下一篇: LinkdedList
大白来袭
粉丝 4
博文 41
码字总数 13667
作品 0
海淀
程序员
私信 提问

暂无文章

聊聊nacos的NacosDiscoveryAutoConfiguration

序 本文主要研究一下nacos的NacosDiscoveryAutoConfiguration NacosDiscoveryAutoConfiguration nacos-spring-boot-project/nacos-discovery-spring-boot-autoconfigure/src/main/java/com/a......

go4it
22分钟前
4
0
如何保证消息的顺序性?

面试题 如何保证消息的顺序性? 面试官心理分析 其实这个也是用 MQ 的时候必问的话题,第一看看你了不了解顺序这个事儿?第二看看你有没有办法保证消息是有顺序的?这是生产系统中常见的问题...

米兜
27分钟前
6
0
变量求解:RMT函数

1. RMT函数:计算贷款每月付款额 = PMT (贷款利率,付款限期,本金) 2.单变量求解: 数据选项卡----> 模拟分析------>单变量求解:单变量求解前必须先执行PMT函数...

东方墨天
28分钟前
2
2
网络安全市场需求

最近,网络安全技能差距的热门话题流传开来。技能差距经常被紧急讨论,可以看出它在实践中的作用是很大的。但信息安全是一门广泛的学科,所以在谈论“技能差距”时需要更具体。有专家表示,真...

linuxCool
48分钟前
3
0
饿了么快应用初体验

作者:饿了么 顾诚 为什么我们选择了快应用 在很长一段时间里,原生饿了么应用对于新用户来说体验成本略高,对于迫切想要点餐的老用户操作有点繁琐;而 Web 版的饿了么应用在体验、速度、功能...

前端老手
51分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部