精灵王


  • 首页

  • 文章归档

  • 所有分类

  • 关于我

  • 搜索
设计模式-行为型 设计模式-创建型 设计模式-结构型 设计 系统设计 设计模式之美 分布式 Redis 并发编程 个人成长 周志明的软件架构课 架构 单元测试 LeetCode 工具 位运算 读书笔记 操作系统 MySQL 异步编程 技术方案设计 集合 设计模式 三亚 游玩 转载 Linux 观察者模式 事件 Spring SpringCloud 实战 实战,SpringCloud 源码分析 线程池 同步 锁 线程 线程模型 动态代理 字节码 类加载 垃圾收集器 垃圾回收算法 对象创建 虚拟机内存 内存结构 Java

源码分析:线程安全的列表—CopyOnWriteArrayList

发表于 2021-06-09 | 分类于 Java | 0

简介

CopyOnWriteArrayList 是一个线程安全的ArrayList,但是它的每次操作(add ,set,remove等)都是通过复制一个底层的数组副本来实现的,在写操作的时候都会加上锁,有读写分离的意思。

CopyOnWrite

写入时复制(英语:Copy-on-write,简称COW)是一种计算机程序设计领域的优化策略。其核心思想是,如果有多个调用者(callers)同时请求相同资源(如内存或磁盘上的数据存储),他们会共同获取相同的指针指向相同的资源,直到某个调用者试图修改资源的内容时,系统才会真正复制一份专用副本(private copy)给该调用者,而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源,就不会有副本(private copy)被创建,因此多个调用者只是读取操作时可以共享同一份资源。——维基百科

结构分析

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList实现了List接口,所以具有列表的基础功能;同时实现了RandomAccess接口,所以也支持随机访问(数组随机访问特性);实现了Cloneable和Serializable接口,支持克隆和序列号。

重要属性

// 锁
final transient ReentrantLock lock = new ReentrantLock();
// 数组
private transient volatile Object[] array;

CopyOnWriteArrayList内部使用的ReentrantLock非公平锁,还有一个volatile修饰的数组,保证了更换数组引用后对其他线程的可见性,并且两个属性都不支持序列化。

内部类:COWIterator

static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot; // array 快照
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor; // 游标,后续调用 next 将返回的元素索引
  ...
}

COWIterator 表示迭代器,实现了ListIterator接口,内部有一个Object类型的数组作为CopyOnWriteArrayList数组的快照,在创建迭代器的时候记录了当时数组状态的引用。

在迭代器内不支持add、set、remove操作,会抛出UnsupportedOperationException异常。

public void remove() {
    throw new UnsupportedOperationException();
}
public void set(E e) {
    throw new UnsupportedOperationException();
}
public void add(E e) {
    throw new UnsupportedOperationException();
}

方法分析

构造方法

// 初始化默认无参数构造方法
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}
// 初始化指定集合
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    // 判断类型
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

// 创建一个包含给定数组副本的列表
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 将toCopyIn转化为Object[]类型数组,然后设置当前数组
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

最终调用的都是setArray方法。

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

构造方法小结:

  1. 初始化时没有指定数组的初始长度。
  2. Arrays.copyOf的逻辑就是底层的System.arraycopy数组赋值。

添加元素:add(e)方法

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 0.加锁
    lock.lock();
    try {
        // 1.拿到数组引用
        Object[] elements = getArray();
        int len = elements.length;
        // 2.copy一个长度+1的数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 3.将新增元素加入到数组的最后
        newElements[len] = e; 
        // 4.覆盖旧数组
        setArray(newElements);
        return true;
    } finally {
        // 5.解锁
        lock.unlock();
    }
}
// 获取数组
final Object[] getArray() {
    return array;
}
// 覆盖数组
final void setArray(Object[] a) {
    array = a;
}

add方法小结:

  1. 加锁
  2. 拿到原数组引用
  3. copy一个长度+1的新数组
  4. 将新增元素加入到新数组的最后
  5. 新数组覆盖旧数组
  6. 释放锁,返回结果

添加元素:add(index, element)方法

指定添加元素的索引

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 0.获得锁
    lock.lock();
    try {
        //1.原数组引用
        Object[] elements = getArray();
        //2.原数组长度
        int len = elements.length;
        if (index > len || index < 0) // 检测索引是否越界
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index; // 移动的数
        if (numMoved == 0)
            // 实际上也就是复制一个数组加入到数组的最后
            newElements = Arrays.copyOf(elements, len + 1); 
        else {
            // 新数组
            newElements = new Object[len + 1];
            // index位置分割的两个数组,分段复制
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 指定位置设置成新的元素
        newElements[index] = element;
        // 覆盖数组
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

add 方法小结:

  1. 大体逻辑和上面没有指定位置的方法一致
  2. 指定的中间位置,相当于把原数组切割成了两个数组,需要分别复制到长度+1的新数组

添加元素:addIfAbsent(e)方法

如果添加的元素不存在,才可以添加成功,该方法可避免多线程情况下重复添加元素。

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    // indexOf 的功能就是找到元素是否存在,存在则返回其索引,不存在返回-1by:https://jinglingwang.cn
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

// 不存在则添加
private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    // 1.加锁
    lock.lock();
    try {
        // 数组引用
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) { // 不一致?说明其他线程先行一步更改了数组
            // Optimize for lost race to another addXXX operation
            // snapshot.length 是旧的数组长度   len是发现变化后的数组长度
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                 // 判断两个数组的内容是否一致,并检查当前要加入的元素是否已经存在于变化后的数组中
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    // 检查不通过返回false(两个条件都要满足)
                    return false;
            if (indexOf(e, current, common, len) >= 0) // 再检查一次
                    return false;
        }
        // 正常的流程,和上面的add一致by:https://jinglingwang.cn
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

方法小结:

  1. 大体逻辑和上面没有指定位置的方法一致
  2. 多了一个检查环节,如果添加时,数组发生了变化,要检查加入的元素是否已经存在于变化后的数组中(by:https://jinglingwang.cn)
  3. 数组有变化,也会加入到变化后的新数组中

删除元素:remove方法

// 移除指定索引位置的元素
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 {
            // 新的长度减一的数组
            Object[] newElements = new Object[len - 1];
            // 复制两次,相当于删掉了elements[index]
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements); // 设置新数组的引用
        }
        return oldValue; // 返回旧值by:https://jinglingwang.cn
    } finally {
        lock.unlock(); // 解锁
    }
}
// 移除指定元素
public boolean remove(Object o) {
    Object[] snapshot = getArray();
    // 元素所在位置索引
    int index = indexOf(o, snapshot, 0, snapshot.length);
    return (index < 0) ? false : remove(o, snapshot, index);
}
// 移除指定元素
private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁
    try {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) findIndex: { // 数组有变化会进入到if分支里面
            int prefix = Math.min(index, len);
            for (int i = 0; i < prefix; i++) {
                // 在新的数组中找到了和旧的元素不一致,并且就是要移除的值
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    index = i; // 从新数组中重新确认的索引
                    break findIndex;
                }
            }
            // 上面for循环没找到,有可能元素在新的数组中还是在那个index位置没变化(current[i] != snapshot[i] 条件不满足)
            if (index >= len) // 如果新数组是移除了一个元素,index最多也就等于len,既然新数组移除了元素,上面又没检查出来?直接返回false
                return false;
            if (current[index] == o) // 元素在新数组的同一个位置,没变化
                break findIndex;
            index = indexOf(o, current, index, len); // 位置有变化,就重新找到新位置
            if (index < 0)  // 没找到,已经删掉了,本次删除失败 by:https://jinglingwang.cn
                return false;
        }
       // 后面的逻辑和上面的一直
        Object[] newElements = new Object[len - 1];
        System.arraycopy(current, 0, newElements, 0, index);
        System.arraycopy(current, index + 1,
                         newElements, index,
                         len - index - 1);
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

remove方法小结

  1. 加锁,找索引,copy删除,覆盖旧数组,解锁返回
  2. 复杂点的是移除指定元素的时候要检测在删除的过程中,数组是否发生了变化
  3. 如果有变化,需要重新校验元素是否还存在,并且找到删除元素在新数组中的索引位置,然后删除。

修改值:set方法

修改指定位置的值。

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        Object[] elements = getArray();
        // 旧值
        E oldValue = get(elements, index);

        if (oldValue != element) { // 两个值不一样
            int len = elements.length;
            // 复制一个长度一样的新数组
            Object[] newElements = Arrays.copyOf(elements, len);
            // 在新数组中指定位置设置元素
            newElements[index] = element;
            // 设置数组
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
		        // 值一样,设置数组
            setArray(elements);
        }
        return oldValue; // 返回旧值
    } finally {
        lock.unlock(); // 解锁
    }
}

set方法小结:

  1. 加锁
  2. 找到指定索引的值
  3. 复制一个长度一样的新数组
  4. 在新数组中指定位置设置新元素
  5. 设置为新数组,解锁返回

获取元素:get方法

public E get(int index) {
    return get(getArray(), index);
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

get方法小结:

  1. get 没有加锁
  2. 直接拿到当前数组,获取返回指定位置的值
  3. 这里有可能getArray 获取到的还是一个旧的数组(比如其他线程调用了add、set、remove方法,但是还没有调用setArray(newElements)方法),所以这里是弱一致性。

迭代器:iterator

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}
public ListIterator<E> listIterator() {
    return new COWIterator<E>(getArray(), 0);
}
public ListIterator<E> listIterator(int index) {
    Object[] elements = getArray();
    int len = elements.length;
    if (index < 0 || index > len)
        throw new IndexOutOfBoundsException("Index: "+index);

    return new COWIterator<E>(elements, index);
}

可以以上3个迭代器最终都是通过构造一个COWIterator。

private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor; // 初始迭代的光标
    snapshot = elements; // 获取迭代器时,当前数组的快照
}

在获取迭代器时,COWIterator内部保留了当前数组的快照。

迭代遍历的方法:

public boolean hasNext() {
    // 判断是否还有下一个元素
    return cursor < snapshot.length;
}

public boolean hasPrevious() {
    // 判断是否还有上一个元素
    return cursor > 0;
}

@SuppressWarnings("[unchecked](http://jinglingwang.cn)")
public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++]; // 获取下一个元素
}

@SuppressWarnings("unchecked")
public E previous() {
    if (! hasPrevious())
        throw new NoSuchElementException();
    return (E) snapshot[--cursor]; // 获取上一个元素
}

测试CopyOnWriteArrayList的弱一致性

从上面的get方法分析和迭代器分析中,我们发现他们拿到的数组都有可能是已经过时了的数组,也就是在其他线程调用了add、set、remove方法,但是还没有调用setArray(newElements)方法时,可能就没法获取到最新的数据。

示例:

CopyOnWriteArrayList cowArray = new CopyOnWriteArrayList();
cowArray.add(1);
cowArray.add(2);
cowArray.add(3);
cowArray.add(4);
Iterator it = cowArray.iterator();
while(it.hasNext()){
    System.out.print(it.next()+ " ");
}
cowArray.add("jinglingwang.cn");
if(it.hasNext()){
    System.out.print(it.next()+ " ");
}

输出结果只会有:1 2 3 4,后面再次迭代时,持有的还是获取迭代器前的数组,因为每次add操作都会产生一个新的数组,而迭代器包含的数组引用是是不包含jinglingwang.cn的,所以迭代器没法遍历出最后新添加的数据,也就是CopyOnWriteArrayList 的弱一致特性。

总结

  1. CopyOnWriteArrayList 是一个线程安全的ArrayList,以上是基于jdk1.8的分析。
  2. 每次对数据的修改都会copy一份新的数组(哪怕数组的长度没变化),对内存要求比较高。
  3. CopyOnWriteArrayList 是弱一致性,不能保证修改数据后,其他线程马上就能感知。
  4. CopyOnWriteArrayList 不能限制数组的最长长度,使用需要谨慎。
  5. jdk1.8版本是通过ReentrantLock锁实现的,jdk11就已经改成了synchronized锁。
精 灵 王 wechat
👆🏼欢迎扫码关注微信公众号👆🏼
  • 本文作者: 精 灵 王
  • 本文链接: https://jinglingwang.cn/archives/copyonwritearraylist
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 设计模式-行为型 # 设计模式-创建型 # 设计模式-结构型 # 设计 # 系统设计 # 设计模式之美 # 分布式 # Redis # 并发编程 # 个人成长 # 周志明的软件架构课 # 架构 # 单元测试 # LeetCode # 工具 # 位运算 # 读书笔记 # 操作系统 # MySQL # 异步编程 # 技术方案设计 # 集合 # 设计模式 # 三亚 # 游玩 # 转载 # Linux # 观察者模式 # 事件 # Spring # SpringCloud # 实战 # 实战,SpringCloud # 源码分析 # 线程池 # 同步 # 锁 # 线程 # 线程模型 # 动态代理 # 字节码 # 类加载 # 垃圾收集器 # 垃圾回收算法 # 对象创建 # 虚拟机内存 # 内存结构 # Java
源码分析:ConcurrentHashMap—JDK1.8版本
源码分析:线程安全的集合—CopyOnWriteArraySet
  • 文章目录
  • 站点概览
精 灵 王

精 灵 王

青春岁月,以此为伴

106 日志
14 分类
48 标签
RSS
Github E-mail
Creative Commons
Links
  • 添加友链说明
© 2023 精 灵 王
渝ICP备2020013371号
0%