Java并发编程学习系列二：集合不安全

概念

Java集合类框架的基本接口有哪些？

总共有两大接口：Collection 和 Map ，一个元素集合，一个是键值对集合； 其中 List 和 Set 接口继承了 Collection 接口，一个是有序元素集合，一个是无序元素集合； 而 ArrayList 和 LinkedList 实现了 List 接口，HashSet 实现了 Set 接口，这几个都比较常用； HashMap 和 HashTable 实现了 Map 接口，并且 HashTable 是线程安全的，但是 HashMap 性能更好；

Collection 和 Collections 有什么区别？

• java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection 接口在 Java 类库中有很多具体的实现。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式，其直接继承接口有 List 与 Set。

• Collections 则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

List、Set、Map 之间的区别是什么？

快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

快速失败：当你在迭代一个集合的时候，如果有另一个线程正在修改你正在访问的那个集合时，就会抛出一个 ConcurrentModification 异常。

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

安全失败：你在迭代的时候会去底层集合做一个拷贝，所以你在修改上层集合的时候是不会受影响的，不会抛出 ConcurrentModification 异常。

在 java.util.concurrent 包下的全是安全失败的。可以在多线程下并发使用，并发修改。

List

并发不安全

首先我们查看如下案例：

public class ListTest {

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        for(int i=0;i<10;i++){
            new Thread(()->{
                list.add(UUID.randomUUID().toString().substring(0,5));
                System.out.println(list);
            },String.valueOf(i)).start();
        }
    }
}
复制代码

执行上述代码，会抛出 java.util.ConcurrentModificationException 并发异常。

解决方案

1、Vector

public class ListTest {

    public static void main(String[] args) {
        List<String> list = new Vector<>();

        for(int i=0;i<10;i++){
            new Thread(()->{
                list.add(UUID.randomUUID().toString().substring(0,5));
                System.out.println(list);
            },String.valueOf(i)).start();
        }
    }
}
复制代码

Vector 类是在 JDK1.0 出现的，比 ArrayList 还早，那为什么不推荐该方法呢？查看源码得知：

    public synchronized boolean add(E var1) {
        ++this.modCount;
        this.ensureCapacityHelper(this.elementCount + 1);
        this.elementData[this.elementCount++] = var1;
        return true;
    }
复制代码

使用 Synchronized 关键字来实现同步操作，效率较低。原因：在 Java 早期版本中，synchronized 属于重量级锁，效率低下，因为监视器锁（monitor）是依赖于底层的操作系统的 Mutex Lock 来实现的，Java 的线程是映射到操作系统的原生线程之上的。如果要挂起或者唤醒一个线程，都需要操作系统帮忙完成，而操作系统实现线程之间的切换时需要从用户态转换到内核态，这个状态之间的转换需要相对比较长的时间，时间成本相对较高，这也是为什么早期的 synchronized 效率低的原因。庆幸的是在 Java 6 之后 Java 官方对从 JVM 层面对 synchronized 较大优化，所以现在的 synchronized 锁效率也优化得很不错了。JDK1.6 对锁的实现引入了大量的优化，如自旋锁、适应性自旋锁、锁消除、锁粗化、偏向锁、轻量级锁等技术来减少锁操作的开销。

2、使用 Collections 工具类

List<String> list = Collections.synchronizedList(new ArrayList<>());
复制代码

同样我们来查看源码， Collections.synchronizedList() 的定义如下：

    public static <T> List<T> synchronizedList(List<T> var0) {
        return (List)(var0 instanceof RandomAccess ? new Collections.SynchronizedRandomAccessList(var0) : new Collections.SynchronizedList(var0));
    }
复制代码

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
复制代码

一路跳转后，最终定位到 SynchronizedCollection 静态内部类，List 对象也就变为了 SynchronizedCollection 类型，查看其 add 方法定义：

        public boolean add(E var1) {
            synchronized(this.mutex) {
                return this.c.add(var1);
            }
        }
复制代码

同 Vector 一样，还是采用的 Synchronized 关键字来做同步操作，只是封装在 Collections 工具类中。

3、使用CopyOnWriteArrayList

我们来通过看源码的方式来理解 CopyOnWriteArrayList，实际上 CopyOnWriteArrayList 内部维护的也是一个数组

private transient volatile Object[] array;
复制代码

只是该数组是被 volatile 修饰，注意这里 仅仅修饰的是数组引用 ，与被 volatile 修饰的普通变量有所区别，关于这点我在之前的文章中有分析，对 volatile 还不是太了解的朋友也可以去看一下。对 list 来说，我们自然而然最关心的就是读写的时候，分别为 get 和 add 方法的实现。

以下方式利用 CopyOnWriteArrayList 来保证线程安全。

List<String> list = new CopyOnWriteArrayList<>();
复制代码

CopyOnWriteArrayList 比 Vector 更高级，因为加锁的方式不一样，前者使用 Lock 锁。查看其 add 方法定义：

    public boolean add(E var1) {
        ReentrantLock var2 = this.lock;
        var2.lock();

        boolean var6;
        try {
            Object[] var3 = this.getArray();
            int var4 = var3.length;
            Object[] var5 = Arrays.copyOf(var3, var4 + 1);
            var5[var4] = var1;
            this.setArray(var5);
            var6 = true;
        } finally {
            var2.unlock();
        }

        return var6;
    }
复制代码

除了通过 Lock 来加锁处理，每次写数据前，都会另外通过 Arrays.copyOf 方法复制一份数据，在写入的时候避免覆盖，造成数据问题。

我们需要注意 CopyOnWriteArrayList 中的这两个字段属性以及相关方法。

    final transient ReentrantLock lock = new ReentrantLock();
    private transient volatile Object[] array;

    final Object[] getArray() {
        return this.array;
    }

    final void setArray(Object[] var1) {
        this.array = var1;
    }
复制代码

注意事项：

1. 采用 ReentrantLock 来加锁，保证同一时刻只有一个线程在对数据进行读写操作；
2. 数组引用是 volatile 修饰的，因此将旧的数组引用指向新的数组，根据 volatile 的 happens-before 规则，写线程对数组引用的修改对读线程是可见的的，但是数组中的元素并不可见。
3. 由于在写数据的时候，是在新的数组中插入数据的，从而保证读写是在两个不同的数据容器中进行操作。

CopyOnWriteArrayList 的缺点：

1. 内存占用问题 ：因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对 象的内存，旧的对象和新写入的对象（注意:在复制的时候只是复制容器里的引用，只是在写的时候会创建新对象添加到新容器里，而旧容器的对象还在使用，所以有两份对象内存）。如果这些对象占用的内存比较大，比 如说 200M 左右，那么再写入 100M 数据进去，内存就会占用 300M，那么这个时候很有可能造成频繁的 minor GC 和 major GC。
2. 数据一致性问题 ：CopyOnWrite 容器只能保证数据的最终一致性，不能保证数据的实时一致性。所以如果你希望写入的的数据，马上能读到，请不要使用 CopyOnWrite 容器。

CopyOnWriteArrayList 的优点：

1. 线程安全，能够保证数据一致性。
2. 与 Vector、ArrayList 相比，CopyOnWriteArrayList 在多线程遍历迭代过程中不会报错。

关于优缺点中各自的第二条，通过以下案例向大家说明：

public class CowTest {

    public static void main(String[] args) {
        // 初始化一个list，放入5个元素
        final List<Integer> list = new CopyOnWriteArrayList<>();
//        final List<Integer> list = new Vector<>();
//        final List<Integer> list = Collections.synchronizedList(new ArrayList<>());
        for(int i = 0; i < 5; i++) {
            list.add(i);
        }

        // 线程一：通过Iterator遍历List
        Thread t1 = new Thread(()-> {
            for(int item : list) {
                System.out.println("遍历元素：" + item);
                // 由于程序跑的太快，这里sleep了1秒来调慢程序的运行速度
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });

        // 线程二：add一个元素
        Thread t2 = new Thread(() ->{
            // 由于程序跑的太快，这里sleep了1秒来调慢程序的运行速度
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            list.add(5);
        });
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();
            System.out.println(list);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}
复制代码

执行结果为：

遍历元素：0
遍历元素：1
遍历元素：2
遍历元素：3
遍历元素：4
[0, 1, 2, 3, 4, 5]
复制代码

当线程1在遍历集合，线程2往集合中新增一个数据，如果使用前两种线程安全的替换方案，有可能产生 ConcurrentModificationException 异常。为什么 CopyOnWriteArrayList 就没问题呢？原因在于它保证线程安全采用的是 写时复制并加锁 ，所以线程1在遍历时拿到的集合是旧的，这也就是结果中为啥没有输出5的原因，虽然拿到的是旧集合，但是至少不会报错。

CopyOnWriteArrayList 只能保证数据最终一致性，这点从结果中可以看出来，当在线程2中给集合新增了元素，但是无法立即通知到线程1，所以无法保证数据实时性。但是当其他线程再次读取集合时，才能读取到完整的新数据。

最后总结一下， CopyOnWriteArrayList 适合在读多写少的场景使用，实时性要求不高，不然读取到的可能是旧数据。添加数据可以采用批量添加 addAll 方法，减少内存占用。

Set

并发不安全

首先我们查看如下案例：

public class SetTest {

    public static void main(String[] args) {
        Set<String> set= new HashSet<>();

        for (int i = 0; i < 20; i++) {
            new Thread(()->{
                set.add(UUID.randomUUID().toString().substring(0,5));
                System.out.println(set);
            },String.valueOf(i)).start();
        }
    }
}
复制代码

执行上述代码，会抛出 java.util.ConcurrentModificationException 并发异常。

解决方案

1、使用 Collections 工具类

Set<String> set = Collections.synchronizedSet(new HashSet<>());
复制代码

同 List 使用 Collections.synchronizedList() 一样，通过 synchronized 来实现线程安全。

2、使用CopyOnWriteArraySet

Set<String> set = new CopyOnWriteArraySet<>();
复制代码

我们点击查看 CopyOnWriteArraySet 类，发现其背后通过 CopyOnWriteArrayList 来存储数据。

    private final CopyOnWriteArrayList<E> al;

    public CopyOnWriteArraySet() {
        this.al = new CopyOnWriteArrayList();
    }
复制代码

我们知道 Set 集合中的元素是不可重复，那么这是怎么做到的呢？首先来查看 add 方法。

    public boolean add(E var1) {
        return this.al.addIfAbsent(var1);
    }
复制代码

实际上是执行 CopyOnWriteArrayList 中的 addIfAbsent 方法。

public boolean addIfAbsent(E var1) {
    Object[] var2 = this.getArray();    //获取当前数组信息
    //indexOf方法用于比对新增值在原数组中是否存在，若存在，则返回值不小于0，否则返回-1，即要执行addIfAbsent方法
    return indexOf(var1, var2, 0, var2.length) >= 0 ? false : this.addIfAbsent(var1, var2);
}

private boolean addIfAbsent(E var1, Object[] var2) {
    ReentrantLock var3 = this.lock;
    var3.lock();

    try {
        Object[] var4 = this.getArray();
        int var5 = var4.length;
        boolean var13;
        if (var2 != var4) {
            int var6 = Math.min(var2.length, var5);

            for(int var7 = 0; var7 < var6; ++var7) {
                if (var4[var7] != var2[var7] && eq(var1, var4[var7])) {
                    boolean var8 = false;
                    return var8;
                }
            }

            if (indexOf(var1, var4, var6, var5) >= 0) {
                var13 = false;
                return var13;
            }
        }

        Object[] var12 = Arrays.copyOf(var4, var5 + 1);
        var12[var5] = var1;
        this.setArray(var12);
        var13 = true;
        return var13;
    } finally {
        var3.unlock();
    }
}
复制代码

同 CopyOnWriteArrayList 中的 add 方法类似，addIfAbsent 方法也是先加锁，然后写前复制来保证线程安全。

Map

并发不安全

首先我们查看如下案例：

public class MapTest {

    public static void main(String[] args) {

//        Map<String,Object> map = new HashMap<>();
        //加载因子和初始容量
        //等价于：new HashMap(16,0.75)

        for (int i = 0; i < 30; i++) {
            new Thread(()->{
                map.put(Thread.currentThread().getName(), UUID.randomUUID().toString().substring(0,5));
                System.out.println(map);
            },String.valueOf(i)).start();

        }
    }
}
复制代码

执行上述代码，会抛出 java.util.ConcurrentModificationException 并发异常。

解决方案

1、使用 Collections 工具类

Map<String,Object> map = Collections.synchronizedMap(new HashMap<>());
复制代码

2、使用Hashtable

Map<String,Object> map = new Hashtable<>();
复制代码

该类通过对读写进行加锁（synchronized）操作，一个线程在读写元素，其余线程必须等待，性能较低。

3、使用 ConcurrentHashMap

Map<String,Object> map = new ConcurrentHashMap<>();
复制代码

关于 ConcurrentHashMap 的详细学习，可以参考这篇 文章 。

参考文献

并发容器之CopyOnWriteArrayList

先简单说一说Java中的CopyOnWriteArrayList

如何线程安全地遍历List：Vector、CopyOnWriteArrayList