专栏首页JavaEdgeCopyOnWriteArrayList 源码解析
原创

CopyOnWriteArrayList 源码解析

我不停奔跑只为追赶当年被寄予厚望的自己。 ——利文斯顿

0 前言

我们知道 ArrayList 非线程安全,需要自己加锁或者使用 Collections.synchronizedList 包装.

从JDK1.5开始JUC里提供了使用 CopyOnWrite 机制实现的并发容器线程安全的 List - CopyOnWriteArrayList,简称 COW

1 CopyOnWrite 设计思想

1.1 基本概念

CopyOnWrite 写时复制.

一般来说就是当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器复制出一个新的容器,往新的容器里添加元素,添加完元素之后,再将原容器引用指向新容器.

即一开始大家都在共享同一内容,当有人想修改该内容时,才会真地把内容copy出去形成一个新的内容然后再改,这是一种延时懒惰策略.

1.2 设计优点

可并发读 CopyOnWrite 容器,而无需加锁,因为当前容器不会添加任何元素.

所以这也是一种读写分离的思想,读写的是不同的容器.

2 继承体系

  • 和 ArrayList 的继承体系类似

3 属性

  • 保护所有更改器的锁
  • 仅能通过getArray / setArray访问的数组
  • lock 内存偏移量

4 构造方法

4.1 无参

  • 创建一个空 list

4.2 有参

  • 创建一个列表,该列表包含指定集合的元素,其顺序由集合的迭代器返回。
  • 创建一个保存给定数组副本的列表

下面开始看源码,到底是如何实现写时复制的.

5 add(E e)

向 COW 里添加元素,是需要加锁的,否则并发写时 copy 出N个副本!

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 1.加锁
    lock.lock();
    try {
        // 得到原数组
        Object[] elements = getArray();
        int len = elements.length;
        // 2.复制出新数组,加一是因为要添加yi'ge'yuan's
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 把新元素添加到新数组里,直接放在数组尾部
        newElements[len] = e;
        // 把原数组引用指向新数组
        setArray(newElements);
        return true;
    } finally {
        // finally 里面释放锁,保证即使 try 发生了异常,仍然能够释放锁 
        lock.unlock();
    }
}

getArray

  • 获取数组.非priavte,以便也可以从CopyOnWriteArraySet类(直接组合了CopyOnWriteArrayList作为成员变量)访问

setArray

  • 将引用设置到新数组

都加锁,为什么还需要拷贝数组,而不直接在原数组修改?

  • volatile 修饰的是数组引用!简单的在原来数组修改几个元素的值,这种操作是无法发挥可见性的,必须通过修改数组内存地址
  • 在新数组上执行 copyOf,对原数组无任何影响,只有新数组完全拷贝完成之后,外部才能访问,避免了原数组数据变动可能造成的不良影响

6 get

get(int index)

  • 读指定位置元素

get(Object[] a, int index)

读时无需加锁,如果读时其它线程正在向ArrayList添加数据,读还是只会读到旧数据,因为写时并不会锁住旧的数组.

7 remove

7.1 指定索引删除

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        // 先得到旧值
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        // 如果要删除的数据正好是数组的尾部,直接删除
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 若删除的数据在数组中间:
            // 1. 设置新数组的长度减一,因为是减少一个元素
            // 2. 从 0 拷贝到数组新位置
            // 3. 从新位置拷贝到数组尾部
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

依旧三板斧:

  1. 加锁
  2. 根据删除索引的位置,进行不同策略拷贝
  3. 解锁

7.2 批量删除

public boolean removeAll(Collection<?> c) {
    if (c == null) throw new NullPointerException();
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        if (len != 0) {
            // newlen 表新数组的索引位置,新数组中存在不包含在 c 中的元素
            int newlen = 0;
            Object[] temp = new Object[len];
            // 循环,把不包含在 c 里面的元素,放到新数组中
            for (int i = 0; i < len; ++i) {
                Object element = elements[i];
                // 不包含在 c 中的元素,从 0 开始放到新数组中
                if (!c.contains(element))
                    temp[newlen++] = element;
            }
            // 拷贝新数组,变相的删除了不包含在 c 中的元素
            if (newlen != len) {
                setArray(Arrays.copyOf(temp, newlen));
                return true;
            }
        }
        return false;
    } finally {
        lock.unlock();
    }
}

并非直接对数组元素逐个删除,而先对数组值循环判断,将无需删除的数据放到临时数组,最后临时数组中的数据就是我们不需要删除的数据.

8 总结

CopyOnWrite 并发容器适用于读多写少的并发场景.CopyOnWrite容器有很多优点,但同时也存在问题,开发时候需要注意:

内存占用问题

写时,内存里会同时驻存两个对象的内存,旧对象和新写入对象(复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存).若这些对象占用内存较大,很可能造成频繁GC,应用响应时间也变长.

针对该问题,可通过压缩容器中元素,减少大对象的内存,或者直接不使用CopyOnWrite容器,而使用其他并发容器,如ConcurrentHashMap。

数据一致性问题

CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性,请酌情使用.

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 看完这篇CopyOnWriteArrayList源码解析,和阿里面试官扯了整整一个小时!

    我们知道 ArrayList 非线程安全,需要自己加锁或者使用 Collections.synchronizedList 包装. 从JDK1.5开始JUC里提...

    JavaEdge
  • Docker容器实战(七) - 容器中进程视野下的文件系统

    这么一搞,进程就真的被“装”在了一个与世隔绝的房间里,而这些房间就是PaaS项目赖以生存的应用“沙盒”。

    JavaEdge
  • JVM参数调优基础-参数的类型详解

    -help -server -client -version -showversion -cp -classpath

    JavaEdge
  • 百度工程师的独白:我们为什么要编辑城市基因

    人类几千年的文明催生了城市的发展,计算机与复杂科学带给我们新的资源——大数据。那么,城市里藏了哪些大数据?它们又该如何开采与利用?大数据如何辅助城市规划与商业选...

    DT数据侠
  • 编辑城市基因——百度工程师的独白

    人类几千年的文明催生了城市的发展,计算机与复杂科学带给我们新的资源——大数据。那么,城市里藏了哪些大数据?它们又该如何开采与利用?大数据如何辅助城市规划与商业选...

    DT数据侠
  • 用于组合优化的强化学习:学习策略解决复杂的优化问题

    从人类诞生之初,每一项技术创新,每一项改善我们生活的发明都是经过奇思妙想后设计出来的。从火到车轮,从电力到量子力学,我们对世界的理解和我们周围事物的复杂性,已经...

    AiTechYun
  • C/C++/Qt屏蔽输出流技巧

    Qt君
  • 【ECCV 2018】Facebook开发姿态转换模型,只需一张照片就能让它跳舞(视频)

    DensePose 是 Facebook 研究员 Natalia Neverova、Iasonas Kokkinos 和法国 INRIA 的 Rıza Alp ...

    新智元
  • Hive中数据的压缩及存储

    启动namenode、datanode、resourcemanager、nodemanager。 一个窗口输入:hive-0.13.1]$ bin/hives...

    魏晓蕾
  • QDebug小知识

      禁用在 QChar,QString 和 QByteArray内容周围自动插入引号字符。当开启引号字符禁用时,这些类型的打印将不带引号字符,也不会转义不可打印...

    Qt君

扫码关注云+社区

领取腾讯云代金券