List & Set

作者: 程序员札记 | 来源:发表于2022-04-26 07:20 被阅读0次

ArrayList 的线程安全变体，其中所有可变操作(添加、设置等)都是通过创建底层数组的新副本来实现的，
适用于集合大小通常保持较小，只读操作大大超过可变操作，并且在遍历期间需要防止线程之间的干扰。

package com.conrrentcy.juc;

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.TimeUnit;

public class CopyOnWriteArrayListTest {
    public static void main(String[] args) throws InterruptedException {
        test1();
        test2();
    }

    private static void test1() throws InterruptedException {
        CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
        copyOnWriteArrayList.add("Hello");
        copyOnWriteArrayList.add("CopyOnWriteArrayList");
        copyOnWriteArrayList.add("2019");
        copyOnWriteArrayList.add("good good study");
        copyOnWriteArrayList.add("day day up");
        new Thread(() -> {
            copyOnWriteArrayList.remove(1);
            copyOnWriteArrayList.remove(3);
        }).start();
        TimeUnit.SECONDS.sleep(3);
        Iterator<String> iterator = copyOnWriteArrayList.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
    
    private static void test2() throws InterruptedException {
        CopyOnWriteArrayList<String> copyOnWriteArrayList=new CopyOnWriteArrayList<>();
        copyOnWriteArrayList.add("Hello");
        copyOnWriteArrayList.add("CopyOnWriteArrayList");
        copyOnWriteArrayList.add("2019");
        copyOnWriteArrayList.add("good good study");
        copyOnWriteArrayList.add("day day up");
        Iterator<String> iterator = copyOnWriteArrayList.iterator();
        new Thread(()->{
            copyOnWriteArrayList.remove(1);
            copyOnWriteArrayList.remove(3);
        }).start();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

}

主要方法源码解析

add

我们可以通过add方法添加一个元素

public boolean add(E e) {
        //1.获得独占锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();//2.获得Object[]
            int len = elements.length;//3.获得elements的长度
            Object[] newElements = Arrays.copyOf(elements, len + 1);//4.复制到新的数组
            newElements[len] = e;//5.将add的元素添加到新元素
            setArray(newElements);//6.替换之前的数据
            return true;
        } finally {
            lock.unlock();//7.释放独占锁
        }
    }
final Object[] getArray() {
        return array;
    }

当调用add方法，代码会跑到（1）去获得独占锁，因为独占锁的特性，导致如果有多个线程同时跑到（1），只能有一个线程成功获得独占锁，并且执行下面的代码，其余的线程只能在外面等着，直到独占锁被释放。
线程获得到独占锁后，执行（2），获得array，并且赋值给elements ，（3）获得elements的长度，并且赋值给len，（4）复制elements数组，在此基础上长度+1，赋值给newElements，（5）将我们需要新增的元素添加到newElements，（6）替换之前的数组，最后跑到（7）释放独占锁。

CopyOnWriteArrayList是如何保证【写】时线程安全的？因为用了ReentrantLock独占锁，保证同时只有一个线程对集合进行修改操作。
数据是存储在CopyOnWriteArrayList中的array数组中的。
在添加元素的时候，并不是直接往array里面add元素，而是复制出来了一个新的数组，并且复制出来的数组的长度是【旧数组的长度+1】，再把旧的数组替换成新的数组，这是尤其需要注意的。

get

public E get(int index) {

        return get(getArray(), index);

    }

final Object[] getArray() {

        return array;

    }

我们可以通过调用get方法，来获得指定下标的元素。

首先获得array，然后获得指定下标的元素，看起来没有任何问题，但是其实这是存在问题的。别忘了，我们现在是多线程的开发环境，不然也没有必要去使用JUC下面的东西了。

试想这样的场景，当我们获得了array后，由于整个get方法没有独占锁，所以另外一个线程还可以继续执行修改的操作，比如执行了remove的操作，remove和add一样，也会申请独占锁，并且复制出新的数组，删除元素后，替换掉旧的数组。而这一切get方法是不知道的，它不知道array数组已经发生了天翻地覆的变化，这就是弱一致性。

set

我们可以通过set方法修改指定下标元素的值。

public E set(int index, E element) {

        //(1)获得独占锁

        final ReentrantLock lock = this.lock;

        lock.lock();

        try {

            Object[] elements = getArray();//(2)获得array

            E oldValue = get(elements, index);//(3)根据下标,获得旧的元素

            if (oldValue != element) {//(4)如果旧的元素不等于新的元素

                int len = elements.length;//(5)获得旧数组的长度

                Object[] newElements = Arrays.copyOf(elements, len);//(6)复制出新的数组

                newElements[index] = element;//(7)修改

                setArray(newElements);//(8)替换

            } else {

                //(9)为了保证volatile 语义，即使没有修改，也要替换成新的数组

                // Not quite a no-op; ensures volatile write semantics

                setArray(elements);

            }

            return oldValue;

        } finally {

            lock.unlock();//(10)释放独占锁

        }

    }

当我们调用set方法后：

和add方法一样，先获取独占锁，同样的，只有一个线程可以获得独占锁，其他线程会被阻塞。
获取到独占锁的线程获得array，并且赋值给elements。
根据下标，获得旧的元素。
进行一个对比，检查旧的元素是否不等于新的元素，如果成立的话，执行5-8，如果不成立的话，执行9。
获得旧数组的长度。
复制出新的数组。
修改新的数组中指定下标的元素。
把旧的数组替换掉。
为了保证volatile语义，即使没有修改，也要替换成新的数组。
不管是否执行了修改的操作，都会释放独占锁。

通过源码解析，我们应该更有体会：

通过独占锁，来保证【写】的线程安全。
修改操作，实际上操作的是array的一个副本，最后才把array给替换掉。

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

        }

    }

可以看到，remove方法和add，set方法是一样的，第一步还是先获取独占锁，来保证线程安全性，如果要删除的元素是最后一个，则复制出一个长度为【旧数组的长度-1】的新数组，随之替换，这样就巧妙的把最后一个元素给删除了，如果要删除的元素不是最后一个，则分两次复制，随之替换。

迭代器

在解析源码前，我们先看下迭代器的基本使用：

public class Main {public static void main(String[] args) {

        CopyOnWriteArrayList<String> copyOnWriteArrayList=new CopyOnWriteArrayList<>();

        copyOnWriteArrayList.add("Hello");

        copyOnWriteArrayList.add("copyOnWriteArrayList");

        Iterator<String>iterator=copyOnWriteArrayList.iterator();

        while (iterator.hasNext()){

            System.out.println(iterator.next());

        }

    }

}

运行结果：

Hello
copyOnWriteArrayList

代码很简单，这里就不再解释了，我们直接来看迭代器的源码：

public Iterator<E> iterator() {

        return new COWIterator<E>(getArray(), 0);

    }

static final class COWIterator<E> implements ListIterator<E> {

        private final Object[] snapshot;

        private int cursor;

        private COWIterator(Object[] elements, int initialCursor) {

            cursor = initialCursor;

            snapshot = elements;

        }

        // 判断是否还有下一个元素

        public boolean hasNext() {

            return cursor < snapshot.length;

        }

        //获取下个元素

        @SuppressWarnings("unchecked")

        public E next() {

            if (! hasNext())

                throw new NoSuchElementException();

            return (E) snapshot[cursor++];

        }

当我们调用iterator方法获取迭代器，内部会调用COWIterator的构造方法，此构造方法有两个参数，第一个参数就是array数组，第二个参数是下标，就是0。随后构造方法中会把array数组赋值给snapshot变量。

snapshot是“快照”的意思，如果Java基础尚可的话，应该知道数组是引用类型，传递的是指针，如果有其他地方修改了数组，这里应该马上就可以反应出来，那为什么又会是snapshot这样的命名呢？没错，如果其他线程没有对CopyOnWriteArrayList进行增删改的操作，那么snapshot就是本身的array，但是如果其他线程对CopyOnWriteArrayList进行了增删改的操作，旧的数组会被新的数组给替换掉，但是snapshot还是原来旧的数组的引用。也就是说当我们使用迭代器便利CopyOnWriteArrayList的时候，不能保证拿到的数据是最新的，这也是弱一致性问题

CopyOnWriteArraySet

HashSet 的线程安全的变体。所有操作都使用内部 CopyOnWriteArrayList 的集合，

适用于集合大小通常保持较小，只读操作大大超过可变操作，并且在遍历期间需要防止线程之间的干扰。

ConcurrentSkipListSet

TreeSet 的线程安全的变体；基于 ConcurrentSkipListMap 的可缩放并发 NavigableSet 实现，多个线程并发安全地执行插入、删除、更新和访问操作。**

List & Set

主要方法源码解析

add

get

set

remove

迭代器

CopyOnWriteArraySet

ConcurrentSkipListSet

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读