集合的线程安全List

╰+哭是因爲堅強的太久メ 2022-09-11 09:17 221阅读 0赞

# 线程安全集合类 #

![image-20210913180939520][]

线程安全集合类可以分为三大类：  
遗留的线程安全集合如 Hashtable ， Vector

使用 Collections 装饰的线程安全集合，如：  
Collections.synchronizedCollection  
Collections.synchronizedList  
Collections.synchronizedMap  
Collections.synchronizedSet  
Collections.synchronizedNavigableMap  
Collections.synchronizedNavigableSet  
Collections.synchronizedSortedMap  
Collections.synchronizedSortedSet

java.util.concurrent.\*

## 特点 ##

java.util.concurrent.\* 下的线程安全集合类，可以发现它们有规律，里面包含三类关键词：  
Blocking、CopyOnWrite、Concurrent  
Blocking 大部分实现基于锁，并提供用来阻塞的方法  
CopyOnWrite 之类容器修改开销相对较重  
Concurrent 类型的容器  
内部很多操作使用 cas 优化，一般可以提供较高吞吐量

弱一致性  
遍历时弱一致性，例如，当利用迭代器遍历时，如果容器发生修改，迭代器仍然可以继续进行遍  
历，这时内容是旧的。安全失败(fail-safe)机制

遍历时如果发生了修改，对于非安全容器来讲，使用 **fail-fast** 机制也就是让遍历立刻失败，抛出  
ConcurrentModificationException，不再继续遍历

# **快速失败(fail-fast)和安全失败(fail-safe)** #

提到集合的线程安全问题就不得不先了解快速失败(fail-fast)和安全失败(fail-safe)

## **一：快速失败（fail—fast）** ##

在遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。 并发修改异常

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。

## **二：安全失败（fail—safe）** ##

在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent（juc）包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

**总结：**

Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。

java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。

# 同步容器和并发容器 #

# 同步容器 #

Vector、Hashtable、Collections

# 并发容器 #

ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet、bolckingQueue …  
![在这里插入图片描述][3777405e246b969b53ea5a883d46b72b.png]

# List #

## ArrayList ##

package com.dongguo.concurrent.collection;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.UUID;
    
    /** * @author Dongguo * @date 2021/9/3 0003-15:25 * @description: List集合线程不安全演示 */
    public class UnSafeListDemo { 
        public static void main(String[] args) { 
            List list = new ArrayList();
            for (int i = 1; i <= 3; i++) { 
                new Thread(()->{ 
                    list.add(UUID.randomUUID().toString().substring(0,8));//执行写操作
                    System.out.println(list);//执行读操作
                },"t"+i).start();
            }
        }
    }

第一次运行结果：

[edb445d9]
    [edb445d9]
    [edb445d9]

第二次运行结果

[03bd74e5]
    [03bd74e5, 9def0238]
    [03bd74e5, 9def0238, f3d85190]

第三次运行结果

[77ae1026, 962660f8]
    [77ae1026, 962660f8, b2248fc2]
    [77ae1026, 962660f8]

每次执行都不一样，都没有报错。

因为三个线程谁先写谁先读是不确定的

**将循环次数增大**

package com.dongguo.concurrent.collection;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.UUID;
    
    /** * @author Dongguo * @date 2021/9/3 0003-15:25 * @description: List集合线程不安全演示 */
    public class UnSafeListDemo { 
        public static void main(String[] args) { 
            List list = new ArrayList();
            for (int i = 1; i <= 30; i++) { 
                new Thread(()->{ 
                    list.add(UUID.randomUUID().toString().substring(0,8));//执行写操作
                    System.out.println(list);//执行读操作
                },"t"+i).start();
            }
        }
    }

运行结果：

![image-20210903154149704][]

### 问题: 为什么会出现并发修改异常? ###

查看ArrayList的add方法源码

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

显然ArrayList并没有做任何同步操作。ArrayList是线程不安全的

那么我们如何去解决List类型的线程安全问题?

## **Vector** ##

Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。 Vector 继承了AbstractList，实现了List；所以，它是一个队列，支持相关的添加、删除、修改、遍历等功能。 Vector 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在Vector中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。 Vector 实现了Cloneable接口，即实现clone()函数。它能被克隆。

和ArrayList不同，Vector中的操作是线程安全的。

package com.dongguo.concurrent.collection;
    
    import java.util.List;
    import java.util.UUID;
    import java.util.Vector;
    
    /** * @author Dongguo * @date 2021/9/3 0003-15:25 * @description: Vector */
    public class UnSafeListDemo { 
        public static void main(String[] args) { 
            List list = new Vector();
            for (int i = 1; i <= 30; i++) { 
                new Thread(()->{ 
                    list.add(UUID.randomUUID().toString().substring(0,8));//执行写操作
                    System.out.println(list);//执行读操作
                },"t"+i).start();
            }
        }
    }

运行结果：

![image-20210903154808363][]

运行结果没有发生java.util.ConcurrentModificationException

查看Vector的add方法

/** * Appends the specified element to the end of this Vector. * * @param e element to be appended to this Vector * @return {@code true} (as specified by {@link Collection#add}) * @since 1.2 */
    public synchronized boolean add(E e) { 
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

add方法被synchronized同步修饰,线程安全!因此没有并发异常

## **Collections** ##

Collections提供了方法synchronizedList保证list是同步线程安全的

package com.dongguo.concurrent.collection;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.UUID;
    
    /** * @author Dongguo * @date 2021/9/3 0003-17:16 * @description: Collections提供了方法synchronizedList保证list是同步线程安全的 */
    public class SafeListCollectionsDemo { 
        public static void main(String[] args) { 
            List<String> list = Collections.synchronizedList(new ArrayList<>());
            for (int i = 0; i < 30; i++) { 
                new Thread(() -> { 
                    list.add(UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(list);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210903171839289][]

运行结果也没有发生java.util.ConcurrentModificationException

查看方法源码

@Override
    public boolean add(T e) { 
        synchronized(mutex) { 
            return backingList.add(e);
        }
    }

## **CopyOnWriteArrayList** ##

CopyOnWriteArrayList它相当于线程安全的ArrayList。和ArrayList一样，它是个可变数组；但是和ArrayList不同的时，它具有以下特性：

1.  它最适合于具有以下特征的应用程序：List 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
2.  它是线程安全的。
3.  因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大。
4.  迭代器支持hasNext(), next()等不可变操作，但不支持可变 remove()等操作。
5.  使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

设计思想：

1.  独占锁效率低：采用读写分离思想解决
2.  写线程获取到锁，其他写线程阻塞
3.  复制思想：

当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行 Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

CopyOnWriteArrayList只能保证最终一致性，不能保证实时一致性。

这时候会抛出来一个新的问题，也就是数据不一致的问题。如果写线程还没来得及写回内存，其他的线程就会读到了旧数据。

package com.dongguo.concurrent.collection;
    
    
    import java.util.List;
    import java.util.UUID;
    import java.util.concurrent.CopyOnWriteArrayList;
    
    /** * @author Dongguo * @date 2021/9/3 0003-17:16 * @description: CopyOnWriteArrayList */
    public class SafeListCollectionsDemo { 
        public static void main(String[] args) { 
            List list = new CopyOnWriteArrayList();
            for (int i = 0; i < 30; i++) { 
                new Thread(() -> { 
                    list.add(UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(list);
                }, "t" + i).start();
            }
        }
    }

运行结果：

![image-20210903172303227][]

没有线程安全问题

CopyOnWriteArrayList的add方法

private transient volatile Object[] array;
    ...
    	final Object[] getArray() { 
            return array;
        }
    ...
    	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();
            }
        }
    ...

### **原理分析** ###

下面从“动态数组”和“线程安全”两个方面进一步对CopyOnWriteArrayList的原理进行说明。

### **“动态数组”机制** ###

它内部有个“volatile数组”(array)来保持数据。在“添加/修改/删除”数据时，都会新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给“volatile数组”, 这就是它叫做CopyOnWriteArrayList的原因

由于它在“添加/修改/删除”数据时，都会新建数组，所以涉及到修改数据的操作，CopyOnWriteArrayList效率很低；但是单单只是进行遍历查找的话，效率比较高。

private transient volatile Object[] array;

### **“线程安全”机制** ###

通过volatile和互斥锁来实现的。

通过“volatile数组”来保存数据的。一个线程读取volatile数组时，总能看到其它线程对该volatile变量最后的写入；就这样，通过volatile提供了“读取到的数据总是最新的”这个机制的保证。

通过互斥锁ReentrantLock来保护数据。在“添加/修改/删除”数据时，会先“获取互斥锁”，再修改完毕之后，先将数据更新到“volatile数组”中，然后再“释放互斥锁”，就达到了保护数据的目的

[image-20210913180939520]: /images/20220828/2e90749b7b424c629465fd074178fd97.png
[3777405e246b969b53ea5a883d46b72b.png]: /images/20220828/1686b86798e74720a8eaa9a627f47307.png
[image-20210903154149704]: /images/20220828/6d35c582194e423c93e9d74f584dee77.png
[image-20210903154808363]: /images/20220828/2656501cace4449b9da0a5e986dd83c7.png
[image-20210903171839289]: /images/20220828/21e2c256cff245c79858369b71196bbc.png
[image-20210903172303227]: /images/20220828/a96c43a993db4052af33e499ea0b96c7.png