三种线程安全的List

水深无声 2024-03-22 08:30 21阅读 0赞

在单线程开发环境中，我们经常使用[ArrayList][]作容器来存储我们的数据，但它不是线程安全的，在多线程环境中使用它可能会出现意想不到的结果。

#### [多线程][Link 1]中的ArrayList： ####

我们可以从一段代码了解并发环境下使用ArrayList的情况：

public class ConcurrentArrayList {
        
        public static void main(String[] args) throws InterruptedException {
        
            List<Integer> list = new ArrayList<>();
    
            Runnable runnable = () -> {
        
                for (int i = 0; i < 10000; i++) {
        
                    list.add(i);
                }
            };
            
            for (int i = 0; i < 2; i++) {
        
                new Thread(runnable).start();
            }
            
            Thread.sleep(500);
            System.out.println(list.size());
        }
    }
    123456789101112131415161718

代码中循环创建了两个线程，这两个线程都执行10000次数组的添加操作，理论上最后输出的结果应该为20000，但经过多次尝试，最后只出现了两种结果：

1.  数组索引越界异常

Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException: 10
    	at java.util.ArrayList.add(ArrayList.java:463)
    	at ConcurrentArrayList.lambda$main$0(ConcurrentArrayList.java:14)
    	at java.lang.Thread.run(Thread.java:748)
    10007
    12345

1.  输出结果小于20000

16093
    1

虽然仍有可能得到20000的结果，但概率非常低。我们要从ArrayList的源码中去分析为什么会出现这种结果。  
ArrayList数组默认初始化大小：

// 默认初始大小
    private static final int DEFAULT_CAPACITY = 10;
    ...
    // 数组size
    private int size;
    12345

ArrayList的add方法：

public boolean add(E e) {
        
        //确定集合的大小是否足够，如果不够则会进行扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    1234567

以上面错误1：ArrayIndexOutOfBoundsException: 10为例，出现错误的步骤如下：

1.  假设某时刻Thread-0和Thread-1都执行到了elementData\[size++\] = e; 这步，获取的size大小都为9，此时轮到Thread-1执行
2.  Thread-1执行elementData\[9\] = e，空间刚刚好够用，赋值完后size变为10。接着轮到Thread-0执行
3.  因为Thread-0已经跳过了ensureCapacityInternal(size + 1); 这步判断容量的检查步骤，因此它执行elementData\[10\] = e，而数组容量刚好为10！此时就出现了数组越界的错误。

另外，size++本身就是非原子性的，多个线程之间访问冲突，这时两个线程可能对同一个位置赋值，这就出现了出现size小于期望值的错误2结果。

#### [线程安全][Link 2]的List ####

目前比较常用的构建线程安全的List有三种方法：

1.  使用Vector容器
2.  使用Collections的静态方法synchronizedList(List< T> list)
3.  采用CopyOnWriteArrayList容器

##### 1.使用Vector容器 #####

Vector类实现了可扩展的对象数组，并且它是线程安全的。它和ArrayList在常用方法的实现上很相似，不同的只是它采用了同步关键词synchronized修饰方法。  
ArrayList中的add方法：

public void add(int index, E element) {
        
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    123456789

Vector中的add方法：

public void add(int index, E element) {
        
        insertElementAt(element, index);
    }
    ...
    // 使用了synchronized关键词修饰
    public synchronized void insertElementAt(E obj, int index) {
        
            modCount++;
            if (index > elementCount) {
        
                throw new ArrayIndexOutOfBoundsException(index
                                                         + " > " + elementCount);
            }
            ensureCapacityHelper(elementCount + 1);
            System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
            elementData[index] = obj;
            elementCount++;
        }
    12345678910111213141516

可以看出，Vector在通用方法的实现上ArrayList并没有什么区别（这里不比较扩容方式等细节）

##### 2. Collections.synchronizedList(List< T> list) #####

使用这种方法我们可以获得线程安全的List容器，它和Vector的区别在于它采用了同步代码块实现线程间的同步。通过分析源码，它的底层使用了新的容器包装原始的List。  
下图是新容器的继承关系图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY2ODQ4Mg_size_16_color_FFFFFF_t_70]  
synchronizedList方法：

public static <T> List<T> synchronizedList(List<T> list) {
        
            return (list instanceof RandomAccess ?
                    new SynchronizedRandomAccessList<>(list) :
                    new SynchronizedList<>(list));
        }
    12345

因为ArrayList实现了RandomAccess接口，因此该方法返回一个SynchronizedRandomAccessList实例。  
该类的add实现：

public void add(int index, E element) {
        
        synchronized (mutex) {
        list.add(index, element);}
    }
    123

其中，mutex是final修饰的一个对象：

final Object mutex;
    1

我们可以看到，这种线程安全容器是通过同步代码块来实现的，基础的add方法任然是由ArrayList实现。

我们再来看看它的读方法：

public E get(int index) {
        
        synchronized (mutex) {
        return list.get(index);}
    }
    123

和写方法没什么区别，同样是使用了同步代码块。线程同步的实现原理非常简单！

通过上面的分析可以看出，无论是读操作还是写操作，它都会进行加锁，当线程的并发级别非常高时就会浪费掉大量的资源，因此某些情况下它并不是一个好的选择。针对这个问题，我们引出第三种线程安全容器的实现。

##### 3. CopyOnWriteArrayList #####

顾名思义，它的意思就是在写操作的时候复制数组。为了将读取的性能发挥到极致，在该类的使用过程中，读读操作和读写操作都不互斥，这是一个很神奇的操作，接下来我们看看它如何实现。

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);
                // 赋值
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
        
                lock.unlock();
            }
        }
    12345678910111213141516

从CopyOnWriteArrayList的add实现方式可以看出它是通过lock来实现线程间的同步的，这是一个标准的lock写法。那么它是怎么做到读写互斥的呢？

// 复制数组
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    // 赋值
    newElements[len] = e;
    1234

真实实现读写互斥的细节就在这两行代码上。在面临写操作的时候，CopyOnWriteArrayList会先复制原来的数组并且在新数组上进行修改，最后再将原数组覆盖。如果写操作的过程中发生了线程切换，并且切换到读线程，因为此时数组并未发生覆盖，读操作读取的还是原数组。

换句话说，就是读操作和写操作位于不同的数组上，因此它们不会发生安全问题。

另外，数组定义private transient volatile Object\[\] array，其中采用volatile修饰，保证内存可见性，读取线程可以马上知道这个修改。

private transient volatile Object[] array;
    1

#### 三种方式的性能比较 ####

##### 1. 首先我们来看看三种方式在写操作的情况： #####

public class ConcurrentList {
        
        public static void main(String[] args) {
        
            testVector();
            testSynchronizedList();
            testCopyOnWriteArrayList();
        }
    
        public static void testVector(){
        
            Vector vector = new Vector();
            long time1 = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
        
                vector.add(i);
            }
            long time2 = System.currentTimeMillis();
            System.out.println("vector: "+(time2-time1));
        }
    
        public static void testSynchronizedList(){
        
            List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());
            long time1 = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
        
                list.add(i);
            }
            long time2 = System.currentTimeMillis();
            System.out.println("synchronizedList: "+(time2-time1));
        }
    
        public static void testCopyOnWriteArrayList(){
        
            CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
            long time1 = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
        
                list.add(i);
            }
            long time2 = System.currentTimeMillis();
            System.out.println("copyOnWriteArrayList: "+(time2-time1));
        }
    }
    12345678910111213141516171819202122232425262728293031323334353637

在代码中我让Vector和SynchronizedList两种实现方式进行写操作10000000次，而CopyOnWriteArrayList仅仅只有100000次，与前两种方式少了100倍！  
而结果却出乎意料：

vector: 3202
    synchronizedList: 1795
    copyOnWriteArrayList: 8159
    123

第三种方式使用的时间远大于前两种，写操作越多，时间差就越明显。

看似出乎意料，实则意料之中，copyOnWriteArrayList每进行一次写操作都会复制一次数组，这是非常耗时的操作，因此在面临巨大的写操作量时才会差异这么大。

不过前两种方式之间为什么差异也很明显？可能因为同步代码块比同步方法效率更高？但是同步代码块是直接包含ArrayList的add方法，理论上两种同步方式应该差异不大，欢迎大佬指点。

我们再来看看三种方式在读操作的情况：

##### 2. 我们再来看看三种方式在读操作的情况： #####

public class ConcurrentList {
        
        public static void main(String[] args) {
        
            testVector();
            testSynchronizedList();
            testCopyOnWriteArrayList();
        }
    
        public static void testVector(){
        
            Vector<Integer> vector = new Vector<>();
            vector.add(0);
            long time1 = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
        
                vector.get(0);
            }
            long time2 = System.currentTimeMillis();
            System.out.println("vector: "+(time2-time1));
        }
    
        public static void testSynchronizedList(){
        
            List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());
            list.add(0);
            long time1 = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
        
                list.get(0);
            }
            long time2 = System.currentTimeMillis();
            System.out.println("synchronizedList: "+(time2-time1));
        }
    
        public static void testCopyOnWriteArrayList(){
        
            CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
            list.add(0);
            long time1 = System.currentTimeMillis();
            for (int i = 0; i < 10000000; i++) {
        
                list.get(0);
            }
            long time2 = System.currentTimeMillis();
            System.out.println("copyOnWriteArrayList: "+(time2-time1));
        }
    }
    12345678910111213141516171819202122232425262728293031323334353637383940

这一次三种方式都进行了10000000次读操作，结果如下：

vector: 217
    synchronizedList: 224
    copyOnWriteArrayList: 12
    123

这次copyOnWriteArrayList的优势就显示出来了，它的读操作没有实现同步，因此加快了多线程的读操作。其他两种方式的差别不大。

#### 总结 ####

1.  获取线程安全的List我们可以通过Vector、Collections.synchronizedList()方法和CopyOnWriteArrayList三种方式
2.  读多写少的情况下，推荐使用CopyOnWriteArrayList方式
3.  读少写多的情况下，推荐使用Collections.synchronizedList()的方式

参考：

1.  [并发容器(二)—线程安全的List][List]
2.  [SynchronizedList和Vector的区别][SynchronizedList_Vector]

[ArrayList]: https://so.csdn.net/so/search?q=ArrayList&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E5%A4%9A%E7%BA%BF%E7%A8%8B&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E7%BA%BF%E7%A8%8B%E5%AE%89%E5%85%A8&spm=1001.2101.3001.7020
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY2ODQ4Mg_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/387baa0bc1a64a55a1533f5c70fc55de.png
[List]: https://blog.csdn.net/p_programmer/article/details/86027076
[SynchronizedList_Vector]: https://blog.csdn.net/w372426096/article/details/80679665