java的各种集合为什么不安全（List、Set、Map）以及代替方案

我们已经知道多线程下会有各种不安全的问题，都知道并发的基本解决方案，这里对出现错误的情况进行一个实际模拟，以此能够联想到具体的生产环境中。

一、List 的不安全

1.1 问题

看一段代码：

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

    for (int i = 0; i < 3; i++){
        new Thread(()->{
            list.add(UUID.randomUUID().toString().substring(0,8));
            System.out.println(list);
        },String.valueOf(i)).start();
    }
}

过程很简单，只有 3 个线程而已，对同一个 list 进行 add 的写操作，并随后进行输出的读操作。

输出结果，多执行几次，惊喜多多。

那么，情况不严重的时候，这里显然还正常运行结束了，只是导致了还没来得及写的时候，就已经读出了数据。

如果把线程数增加试试，可能还会看到这样的奇观：

报错了：重点异常：java.util.ConcurrentModificationException，翻译过来就是并发修改异常。

1.2 产生原因

普通的 ArrayList 集合里面没有任何特殊处理，在多线程情况下，他们可以共同进行访问。

那么在多线程同时操作的时候，按照操作的情况就有这几种：

1. 各个线程都读。不影响，前提是只有读；
2. 各个线程都写。会出现问题，这里的点有两种情况：
   1. 值覆盖问题，因为 ArrayList 的底层数组，写入值的时候要先计算到一个下标位置，然后给对应的位置去赋值，多线程就会出现值覆盖的问题；
   2. 空指针异常，因为 ArrayList 的底层数组，写入值在数组满的时候需要扩容，在扩容还没完成的时候，新的下标却已经计算出来并且要去插入，那么就会出现空指针异常。
3. 有的读有的写。那么显然对于多个线程来说，2 里面各个线程写的情况对应的问题就会出现。除此之外：
   1. 如果多线程有的读有的写，对于 ArrayList 底层，某些情况下，对象是不允许进行修改的，如果修改了，后面调用某些方法时，就会检测到，然后就直接抛出ConcurrentModificationException。
   2. 具体一下，因为源码里，写操作对集合修改是写，而next、remove等 Itr 的遍历读操作的时候会通过当前集合的修改次数与 Itr 对象创建时记录的次数校验集合是否被修改，如果修改了，不一致就说明正读的时候还有别的线程在改，就会抛出异常。
   3. JDK作者说了，会抛这个异常的都叫fail-fast iterator。

第 3 种情况就是对应了我们上面的代码在线程多起来的情况，因为输出 list 的时候需要遍历的读，而此时还有别的线程在进行 add 的修改操作。

1.3 解决方法

注意：当然不能自己加锁，因为集合类已经再演变过程有线程安全的替代品，自己的代码加锁的粒度已经在集合的外层再加一层了，粒度太大。

• 同样能够完成 ArrayList 功能的，可以使用 Vector，查看源码就会发现，Vector 的基本结构是一个叫 elementData 的 Object 类型的数组，和 ArrayList 类似，但是对应的操作方法，基本都加上了 synchronized 关键字，因此它是线程安全的集合。
• 数据量小的时候，使用 Collections.synchronizedList(new ArrayList())这种方式，来包裹这个集合，跟 Collections 里面 synchronizedMap包裹hashmap 是一样的，更多的，还有：

显然能传入参数的这些基本集合类都是线程不安全的。

• 第三种就是，直接使用 juc 包里面的，CopyOnWriteArrayList() 类，这个类就是并发包给我们提供的线程安全的列表类。1.4里介绍了这个集合。

1.4 CopyOnWriteArrayList

对于 CopyOnWriteArrayList 类，名字上就可以听的出来，写时复制的列表。

首先，按照前面的我们的分析，只要涉及了写的操作，和读或者写搭配的多线程情况，就会出现问题，那么多线程同时读却不会出现问题，因此相比较于直接都加上 synchronized 的方式，他的思想就是：读写分离。这个思想在数据库对于高并发的架构层面也有一样的设计。

这样一来，对于这个 List 集合来说，分为不同操作的保证线程安全的策略，就能够保证更好的性能。

写的方法，我们首先可以看 add 方法源码：

步骤很清楚，如果有了写操作，需要加锁：

1. 加锁
2. 获取到当前的集合数组；
3. 计算长度；
4. 调用 Arrays.copyOf 方法进行添加操作，每次只添加一个元素进去；
5. 修改引用，更新最新的集合；
6. return true。
7. 解锁

其中的 lock 在源码里就是一个：

可以看到是一个普通的 Object。

那么加锁的时候就用 synchronized 对 Object 进行加锁，没有采用 juc 的 ReetrantLock，注释li也写了，偏向于使用内置的 monitor 也就是 synchronized 底层 monitor 锁，这一点也充分说明了 synchronized 的性能更新使得源码作者使用它。

这个方法是处理最直接的，其他对应的写操作：remove、set等等也是一样的基础流程。

我们再来看看读操作 get 方法：

二、HashSet 的不安全

2.1 问题及原因

我们还是用 List 一样的测试代码；

public class TestSet {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < 100; i++){
            new Thread(()->{
                set.add(UUID.randomUUID().toString().substring(0,8));
                System.out.println(set);
            },String.valueOf(i)).start();
        }
    }
}

就会看到一样的错误：

2.2 出现问题的原因

其实从出现 ConcurrentModificationException 异常来看，我们可以猜测是和 List 类似的原因导致的异常。

可以看到，源码里面，Set 的底层维护的是一个 HashMap 来实现。对于遍历操作来说，都是一样的使用了 fail-fast iterator 迭代器，因此会出现这个异常。

另外，因为 HashSet 的底层是 HashMap ，本质上，对于每一个 key ，保证唯一，使用了一个 value 为 PRESENT 常量的键值对进行存储。

put 的过程也是调用 map 的 put 方法。

2.3 解决方案

• List 有对应的 Vector 可用，本来就是线程安全的集合，但是 Set 没有；
• 数据量小的时候，使用 Collections.synchronizedSet(new HashSet<>()) 这种方式，来包裹这个集合，上面我们使用 List 的时候也有类似的方法；
• 同样的，juc包为我们提供了新的线程安全集合 CopyOnWriteArraySet()。

2.4 CopyOnWriteArraySet

1. 按照前面的思路，List 的对应线程安全集合是在 List 集合的数组基础上进行加锁的相关操作。
2. 那么 Set 既然底层是 HashMap，对应的线程安全集合就应该是对 HashMap 的线程安全集合进行加锁，或者说直接用 ConcurrentHashMap 集合来实现 CopyOnWriteArraySet 。
3. 但事实上，源码并不是这么做的。

从名字来看，和 ConcurrentHashMap 也没有什么关系，而是类似 CopyOnWriteArrayList 的命名，说明是读写单独处理，来让他成为线程安全的集合，那为什么是 ArraySet 多一个 array 修饰语呢？

可以看到，他的思路没有顺延 util 包的 HashSet 的实现思路，而是直接使用了 CopyOnWriteArrayList 作为底层数据结构。也就是说没有利用 Map 的键值对映射的特性来保证 set 的唯一性，而是用一个数组为基底的列表来实现。（那显然在去重方面就要做额外的操作了。）

然后每一个实现的方法都很简单，基本是直接调用了 CopyOnWriteArrayList 的方法：

我们最担心的可能 产生问题的 remove 和 add 方法，也是使用了 CopyOnWriteArrayList 的方法：

而保证 set 的不重复性质的关键，显然就在于 CopyOnWriteArrayList 的 addIfAbsent 方法，我们还是点进 CopyOnWriteArrayList 源码看一看这个方法的实现：

其中的 indexOfRange 方法：

可以看到，也是加了 Monitor 锁来进行的，整个过程是这样的：

1. 获取本来的 set ，是一个数组，以快照形式返回当前的数组；
2. indexOfRange 方法通过遍历查找查找元素出现位置，addIfAbsent方法完成不存在则加入，如果前一个为 false 后一个就不会执行；
3. 加锁；
4. current 再次获取一次当前的快照，因为有可能第一次判断的过程有了其他线程的插入或者修改操作，此时已经不像等，就进入分支进行判断是否存在；
5. 否则就要加入这个元素，和 CopyOnWriteArrayList 添加元素的最后操作是一样的；
6. 解锁。

总结一下就是，线程安全的 Set 集合完全利用了 CopyOnWriteArrayList 集合的方法，对应的操作也是读写分别处理，写时复制的策略，通过 jvm 层面的锁来保证安全，那么保证不重复的方法就是遍历进行比较。

这样看来，相比于基于 HashMap 的去重方法，效率肯定会降低，不过如果基于线程安全的 HashMap ，插入操作从hash、比较、到考虑扩容各方面会因为加锁的过程更复杂，而对于一个不重复的 Set 来说，完全没必要，所以应该综合考虑之下采用了 List 为基础，暴力循环去重。

三、HashMap 的线程不安全

关于 HashMap 的相关问题，源码里已经分析过，大体是这样的。

不安全：

1. 普通读写不一致问题；
2. 死循环问题；
3. ConcurrentModificationException 异常。

解决：

1. util包的Hashtable集合线程安全；
2. 用 synchronizedMap(new HashMap())包装；
3. 使用 juc 包的 ConcurrentHashMap。

HashMap 和 ConcurrentHashMap 的源码分析：

HashMap源码解析、jdk7和8之后的区别、相关问题分析

ConcurrentHashMap源码解析，多线程扩容