写点什么

关于 Copy On Write Array List,你会安全使用么

  • 2022 年 8 月 23 日
    中国香港
  • 本文字数:2355 字

    阅读完需:约 8 分钟

关于Copy On Write Array List,你会安全使用么

本文分享自华为云社区《面试官:如何安全地使用List》,作者:李哥技术。


今天我们来讨论一个 JUC 中的集合类 CopyOnWriteArrayList。


为什么研究这个类


在很多应用场景中,对于集合的读操作的频率一定会远远大于写操作。由于读操作根本不会修改原有的数据,因此对于每次读取都进行加锁其实是一种资源浪费。我们应该允许多个线程同时访问 List 的内部数据,毕竟读取操作是线程安全的。


JDK 中提供了 CopyOnWriteArrayList 类,简称 COW。为了将读取的性能发挥到极致,CopyOnWriteArrayList 读取是完全不用加锁的,并且更厉害的是:写入也不会阻塞读取操作。只有写入和写入之间需要进行同步等待。这样一来,读操作的性能就会大幅度提升。那它是怎么做的呢?来吧,让我们一起研究一下。

设计原理


CopyOnWriteArrayList 底层实现是通过 Object[]存储元素的,内部的可变操作(add,set 等方法)都是把数据 copy 到一个新数组里,对新数组进行操作,再把新数组赋值给原来的对象,从而达到修改目的。

这样做的好处是不修改原数组,所以写操作不会影响到读操作。


从 CopyOnWriteArrayList 的名字就能看出 CopyOnWriteArrayList 是满足 CopyOnWrite 的 ArrayList,所谓 CopyOnWrite 也就是说:在计算机,如果你想要对一块内存进行修改时,我们不在原有内存块中进行写操作,而是将内存拷贝一份,在新的内存中进行写操作,写完之后呢,就将指向原来内存指针指向新的内存,原来的内存就可以被回收掉了。

定位


public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
复制代码



从类的继承关系来看


  1. 实现 RandomAccess 接口,说明可随机访问

  2. 实现 Cloneable 接口,说明可克隆

  3. 实现了 List 接口,说明是一个列表

  4. 实现 Serializable 接口,说明可序列化


接下来让我们研究一下 crud。


public boolean add(E e);// 新增元素,放在数组尾部
public void add(int index, E element);// 新增元素,放在数组指定位置
public boolean addIfAbsent(E e);// 新增元素,如果存在则返回false,如果不存在则放入末尾返回true
public int addAllAbsent(Collection<? extends E> c);// 批量新增元素,将指定集合中尚未包含在此列表中的所有元素附加到此列表的末尾,返回添加的个数
public boolean addAll(Collection<? extends E> c);// 将指定集合中的所有元素附加到此列表的末尾。
public boolean addAll(int index, Collection<? extends E> c);// 从指定位置开始,将当前位于该位置的元素(如果有)和任何后续元素向右移动(增加它们的索引)。新元素将按照指定集合的迭代器返回的顺序出现在此列表中。
复制代码



此函数用于将指定元素添加到此列表的尾部,处理流程如下:


  • 获取锁(保证线程安全)

  • 根据 Object 数组复制一个长度为 length+1 的 Object 数组为 newElements(此时,newElements[length]为 null)

  • 将下标为 length 的数组元素 newElements[length]设置为元素 e,再设置当前 Object[]为 newElements,释放锁,返回。这样就完成了元素的添加。


public E remove(int index);// 移除指定位置的元素,有可能抛出数组越界异常
public boolean remove(Object o);// 移除对象,如果不存在则返回false,存在则移除后返回true
public boolean removeAll(Collection<?> c);// 批量移除指定集合元素,这是一个非常消耗内存的方法,因为内部会额外指定一个临时数组用来存放需要保留的元素,一共涉及4个数组(老数组、传入数组、临时数组、结果数组)
public boolean removeIf(Predicate<? super E> filter);// 和removeAll类似,内部实现需要有临时数组,也是代价昂贵的方法,请谨慎使用
复制代码



指定位置删除的逻辑如下:


  • 获取锁

  • 获取数组,数组长度

  • 获取指定位置的元素(可能抛出数组越界异常)

  • 计算指定位置的元素是否是当前数组的最后一个

  • 如果是最后一个->不需要挪数据,只需要创建数组,copy 数据到数组即可(少 copy 最后一个),设置数组并返回即可

  • 如果不是最后一个->创建数组,copy 0~index 的数据到新数组,再 copy (index+1)的数据到新数组,设置数组并返回即可



set 方法,修改操作有可能数组越界,这一点需要注意。修改操作也是基于 copy 的,将数据 copy 到新数组,对新数组进行替换后再设置数组,从而达到 set 的目的。


public E get(int index);// 直接从数组中获取,可能抛出数组越界异常
public Spliterator<E> spliterator();
public Iterator<E> iterator();// 获取数组的迭代器,它的实现类是COWIterator,内部拥有一个快照的数组属性
public ListIterator<E> listIterator();// 获取listIterator迭代器,它的实现类是COWIterator,内部拥有一个快照的数组属性
public ListIterator<E> listIterator(int index);// 获取listIterator迭代器,index的作用是设置迭代器当前迭代的位置
复制代码


先来看一个内部类 COWIterator:



COWIterator 表示一个迭代器,其也有一个 Object 类型的数组作为 CopyOnWriteArrayList 数组的快照,这种快照风格的迭代器方法在创建迭代器时使用了对当时数组状态的引用。此数组在迭代器的生存期内不会更改,因此不可能发生冲突,并且迭代器保证不会抛出 ConcurrentModificationException。在创建迭代器以后,迭代器就不会反映列表的添加、移除或者更改,因为在迭代器上进行的元素更改操作(remove、set 和 add)不受支持。这些方法将抛出 UnsupportedOperationException。

更深入的理解


CopyOnWriteArrayList 每次写操作都会申请新内存空间,如果数据量较大的话,很容易触发 young gc 或者 full gc,并且拷贝也会比较消耗内存,虽然适合读多写少的应用场景,在互联网应用中,数据量稍微有点多再操作 add 或 set,非常容易引起故障,还是要谨慎使用。


再谈读,迭代读的时候是读取快照数据,只要生成了迭代器,迭代内的快照内容将保证不会发生改变,所以不适合用于实时读场景。


点击关注,第一时间了解华为云新鲜技术~

发布于: 刚刚阅读数: 4
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
关于Copy On Write Array List,你会安全使用么_List_华为云开发者联盟_InfoQ写作社区