java并发数据结构之CopyOnWriteArrayList


CopyOnWriteArrayList是一个线程安全的List实现,其在对对象进行读操作时,由于对象没有发生改变,因此不需要加锁,反之在对象进行增删等修改操作时,它会先复制一个对象副本,然后对副本进行修改,最后将修改后的副本对象写回,从而保证操作的线程安全,下面我们看一下具体的代码实现。

构造函数

通过CopyOnWriteArrayList链表的构造,可以看出主要是依赖ReentrantLock与数组实现线程安全的链表

/** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

     /**
     * Creates an empty list.
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

写操作

add实现

add是一个标准的使用ReentrantLock加锁保证线程安全操作的实现

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#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);//copy一个副本对象
            newElements[len] = e;//赋值
            setArray(newElements);//把对象写回去
            return true;
        } finally {
            lock.unlock();//释放锁
        }
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();//获取自身数组对象
            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];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;//赋值
            setArray(newElements);//把对象写回去
        } finally {
            lock.unlock();//释放锁
        }
    }

remove实现

在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];//声明一个新数组
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } 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);
    }

    /**
     * A version of remove(Object) using the strong hint that given
     * recent snapshot contains o at the given 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: {//这里判断数组是否已经被修改,如果有修改就重新定位下标
                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;
                    }
                }
                if (index >= len)//下标超过当前数组长度返回false
                    return false;
                if (current[index] == o)//下标未改变,直接返回
                    break findIndex;
                index = indexOf(o, current, index, len);//遍历剩余部分
                if (index < 0)
                    return false;
            }
            Object[] newElements = new Object[len - 1];//创建一个长度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();
        }
    }

读操作

读操作非常简单,无需加锁

/**
     * {@inheritDoc}
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        return get(getArray(), index);
    }

    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

      通过对源码的分析,可以看到CopyOnWriteArrayList只在需要保证线程安全的写操作上加锁,核心思想就是减少锁竞争,从而提高并发时的读取性能,适用于写少读多的应用场景。

      以上就是对CopyOnWriteArrayList内部核心源码的基本走读与解析,其线程安全的实现模式很有代表意义,十分值得初学者参考与学习,希望对大家能有所帮助,其中如有不足与不正确的地方还望指正与海涵,十分感谢。

本站声明:
1. iCode9 技术分享网(下文简称本站)提供的所有内容,仅供技术学习、探讨和分享;

2. 关于本站的所有留言、评论、转载及引用,纯属内容发起人的个人观点,与本站观点和立场无关;

3. 关于本站的所有言论和文字,纯属内容发起人的个人观点,与本站观点和立场无关;

4. 本站文章均是网友提供,不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属;如您发现该文章侵犯了您的权益,可联系我们第一时间进行删除;

5. 本站为非盈利性的个人网站,所有内容不会用来进行牟利,也不会利用任何形式的广告来间接获益,纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/295018.html

(0)
上一篇 2022年12月31日
下一篇 2022年12月31日

相关推荐

发表回复

登录后才能评论