21 张图 | 带你领略集合的线程不安全

云流

关注

发布于: 刚刚

本篇主要内容如下：

本篇主要内容

本篇所有示例代码已更新到我的 Github

本篇文章已收纳到我的 Java 在线文档 www.passjava.cn

悟空聊架构推荐搜索关键词列表：并发集合 ArrayListHashSetHashMap

集合，准备团战

一、线程不安全之 ArrayList

集合框架有 Map 和 Collection 两大类，Collection 下面有 List、Set、Queue。List 下面有 ArrayList、Vector、LinkedList。如下图所示：

集合框架思维导图

JUC 并发包下的集合类 Collections 有 Queue、CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentMap

JUC 包下的 Collections

我们先来看看 ArrayList。

1.1、ArrayList 的底层初始化操作

首先我们来复习下 ArrayList 的使用，下面是初始化一个 ArrayList，数组存放的是 Integer 类型的值。

new ArrayList<Integer>();

复制代码

那么底层做了什么操作呢？

1.2、ArrayList 的底层原理

1.2.1 初始化数组

/** * Constructs an empty list with an initial capacity of ten. */public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

复制代码

创建了一个空数组，容量为 0，根据官方的英文注释，这里容量应该为 10，但其实是 0，后续会讲到为什么不是 10。

1.2.1 ArrayList 的 add 操作

public boolean add(E e) {    ensureCapacityInternal(size + 1);  // Increments modCount!!    elementData[size++] = e;    return true;}

复制代码

重点是这一步：elementData[size++] = e; size++和 elementData[xx]=e，这两个操作都不是原子操作（不可分割的一个或一系列操作，要么都成功执行，要么都不执行）。

1.2.2 ArrayList 扩容源码解析

（1）执行 add 操作时，会先确认是否超过数组大小

ensureCapacityInternal(size + 1);

复制代码

ensureCapacityInternal 方法

（2）计算数组的当前容量 calculateCapacity

private void ensureCapacityInternal(int minCapacity) {    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}

复制代码

minCapacity : 值为 1

elementData：代表当前数组

我们先看 ensureCapacityInternal 调用的 ensureCapacityInternal 方法

calculateCapacity(elementData, minCapacity)

复制代码

calculateCapacity 方法如下：

private static int calculateCapacity(Object[] elementData, int minCapacity) {    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        return Math.max(DEFAULT_CAPACITY, minCapacity);    }    return minCapacity;}

复制代码

elementData：代表当前数组，添加第一个元素时，elementData 等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA（空数组）

minCapacity：等于 1

DEFAULT_CAPACITY：等于 10

返回 Math.max(DEFAULT_CAPACITY, minCapacity) = 10

小结：所以第一次添加元素时，计算数组的大小为 10

（3）确定当前容量 ensureExplicitCapacity

ensureExplicitCapacity 方法

minCapacity = 10

elementData.length=0

小结：因 minCapacity > elementData.length，所以进行第一次扩容，调用 grow()方法从 0 扩大到 10。

（4）调用 grow 方法

grow 方法

oldCapacity=0，newCapacity=10。

然后执行 elementData = Arrays.copyOf(elementData, newCapacity);

将当前数组和容量大小进行数组拷贝操作，赋值给 elementData。数组的容量设置为 10

elementData 的值和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的值将会不一样。

（5）然后将元素赋值给数组第一个元素，且 size 自增 1

elementData[size++] = e;

复制代码

（6）添加第二个元素时，传给 ensureCapacityInternal 的是 2

ensureCapacityInternal(size + 1)

复制代码

size=1，size+1=2

（7）第二次添加元素时，执行 calculateCapacity

mark

elementData 的值和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的值不相等，所以直接返回 2

（8）第二次添加元素时，执行 ensureExplicitCapacity

因 minCapacity 等于 2，小于当前数组的长度 10，所以不进行扩容，不执行 grow 方法。

mark

（9）将第二个元素添加到数组中，size 自增 1

elementData[size++] = e

复制代码

（10）当添加第 11 个元素时调用 grow 方法进行扩容

mark

minCapacity=11， elementData.length=10，调用 grow 方法。

（11）扩容1.5倍

int newCapacity = oldCapacity + (oldCapacity >> 1);

复制代码

oldCapacity=10，先换算成二级制 1010，然后右移一位，变成 0101，对应十进制 5，所以 newCapacity=10+5=15，扩容 1.5 倍后是 15。

扩容 1.5 倍

（12）小结

1.ArrayList 初始化为一个空数组
2.ArrayList 的 Add 操作不是线程安全的
3.ArrayList 添加第一个元素时，数组的容量设置为10
4.当 ArrayList 数组超过当前容量时，扩容至1.5倍（遇到计算结果为小数的，向下取整），第一次扩容后，容量为 15，第二次扩容至 22...
5.ArrayList 在第一次和扩容后都会对数组进行拷贝，调用Arrays.copyOf方法。

安全出行

1.3、ArrayList 单线程环境是否安全？

场景：

我们通过一个添加积木的例子来说明单线程下 ArrayList 是线程安全的。

将积木 三角形A、四边形B、五边形C、六边形D、五角星E依次添加到一个盒子中，盒子中共有 5 个方格，每一个方格可以放一个积木。

ArrayList 单线程下添加元素

代码实现：

（1）这次我们用新的积木类BuildingBlockWithName

这个积木类可以传形状 shape 和名字 name

/** * 积木类 * @author: 悟空聊架构 * @create: 2020-08-27 */class BuildingBlockWithName {    String shape;    String name;    public BuildingBlockWithName(String shape, String name) {        this.shape = shape;        this.name = name;    }    @Override    public String toString() {        return "BuildingBlockWithName{" + "shape='" + shape + ",name=" + name +'}';    }}

复制代码

（2）初始化一个 ArrayList

ArrayList<BuildingBlock> arrayList = new ArrayList<>();

复制代码

（3）依次添加三角形 A、四边形 B、五边形 C、六边形 D、五角星 E

arrayList.add(new BuildingBlockWithName("三角形", "A"));arrayList.add(new BuildingBlockWithName("四边形", "B"));arrayList.add(new BuildingBlockWithName("五边形", "C"));arrayList.add(new BuildingBlockWithName("六边形", "D"));arrayList.add(new BuildingBlockWithName("五角星", "E"));

复制代码

（4）验证arrayList中元素的内容和顺序是否和添加的一致

BuildingBlockWithName{shape='三角形,name=A}BuildingBlockWithName{shape='四边形,name=B}BuildingBlockWithName{shape='五边形,name=C}BuildingBlockWithName{shape='六边形,name=D}BuildingBlockWithName{shape='五角星,name=E}

复制代码

我们看到结果确实是一致的。

小结： 单线程环境中，ArrayList 是线程安全的。

1.4、多线程下 ArrayList 是不安全的

场景如下： 20 个线程随机往 ArrayList 添加一个任意形状的积木。

多线程场景往数组存放元素

（1）代码实现：20 个线程往数组中随机存放一个积木。

多线程下 ArrayList 是不安全的

（2）打印结果：程序开始运行后，每个线程只存放一个随机的积木。

打印结果

数组中会不断存放积木，多个线程会争抢数组的存放资格，在存放过程中，会抛出一个异常:ConcurrentModificationException（并行修改异常）

Exception in thread "10" Exception in thread "13" java.util.ConcurrentModificationException

复制代码

mark

这个就是常见的并发异常：java.util.ConcurrentModificationException

1.5 那如何解决 ArrayList 线程不安全问题呢？

有如下方案：

1.用 Vector 代替 ArrayList
2.用 Collections.synchronized(new ArrayList<>())
3.CopyOnWriteArrayList

1.6 Vector 是保证线程安全的？

下面就来分析 vector 的源码。

1.6.1 初始化 Vector

初始化容量为 10

public Vector() {    this(10);}

复制代码

1.6.2 Add 操作是线程安全的

Add 方法加了synchronized，来保证 add 操作是线程安全的（保证可见性、原子性、有序性），对这几个概念有不懂的可以看下之前的写的文章-》反制面试官 | 14 张原理图 | 再也不怕被问 volatile!

Add 方法加了 synchronized

1.6.3 Vector 扩容至 2 倍

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

复制代码

容量扩容至 2 倍

注意： capacityIncrement 在初始化的时候可以传值，不传则默认为 0。如果传了，则第一次扩容时为设置的 oldCapacity+capacityIncrement，第二次扩容时扩大 1 倍。

缺点： 虽然保证了线程安全，但因为加了排斥锁synchronized，会造成阻塞，所以性能降低。

阻塞

1.6.4 用积木模拟 Vector 的 add 操作

vector 的 add 操作

当往 vector 存放元素时，给盒子加了一个锁，只有一个人可以存放积木，放完后，释放锁，放第二元素时，再进行加锁，依次往复进行。

1.7 使用 Collections.synchronizedList 保证线程安全

我们可以使用 Collections.synchronizedList 方法来封装一个 ArrayList。

List<Object> arrayList = Collections.synchronizedList(new ArrayList<>());

复制代码

为什么这样封装后，就是线程安全的？

源码解析： 因为 Collections.synchronizedList 封装后的 list，list 的所有操作方法都是带synchronized关键字的（除 iterator()之外），相当于所有操作都会进行加锁，所以使用它是线程安全的（除迭代数组之外）。

加锁

mark

注意： 当迭代数组时，需要手动做同步。官方示例如下：

synchronized (list) {     Iterator i = list.iterator(); // Must be in synchronized block     while (i.hasNext())         foo(i.next());}

复制代码

1.8 使用 CopyOnWriteArrayList 保证线程安全

复制

1.8.1 CopyOnWriteArrayList 思想

Copy on write：写时复制，一种读写分离的思想。
写操作：添加元素时，不直接往当前容器添加，而是先拷贝一份数组，在新的数组中添加元素后，在将原容器的引用指向新的容器。因为数组时用 volatile 关键字修饰的，所以当 array 重新赋值后，其他线程可以立即知道（volatile 的可见性）
读操作：读取数组时，读老的数组，不需要加锁。
读写分离：写操作是 copy 了一份新的数组进行写，读操作是读老的数组，所以是读写分离。

1.8.2 使用方式

CopyOnWriteArrayList<BuildingBlockWithName> arrayList = new CopyOnWriteArrayList<>();

复制代码

1.8.3 底层源码分析

CopyOnWriteArrayList 的 add 方法分析

add 的流程：

先定义了一个可重入锁 ReentrantLock
添加元素前，先获取锁lock.lock()
添加元素时，先拷贝当前数组 Arrays.copyOf
添加元素时，扩容+1（len + 1）
添加元素后，将数组引用指向新加了元素后的数组setArray(newElements)

为什么数组重新赋值后，其他线程可以立即知道？

因为这里的数组是用 volatile 修饰的，哇，又是volatile，这个关键字真妙^_^

 private transient volatile Object[] array;

复制代码

妙啊

1.8.4 ReentrantLock 和 synchronized 的区别

划重点

相同点：

1.都是用来协调多线程对共享对象、变量的访问
2.都是可重入锁，同一线程可以多次获得同一个锁
3.都保证了可见性和互斥性

不同点：

乐观

1.ReentrantLock 显示的获得、释放锁， synchronized 隐式获得释放锁
2.ReentrantLock 可响应中断， synchronized 是不可以响应中断的，为处理锁的不可用性提供了更高的灵活性
3.ReentrantLock 是 API 级别的， synchronized 是 JVM 级别的
4.ReentrantLock 可以实现公平锁、非公平锁
5.ReentrantLock 通过 Condition 可以绑定多个条件
6.底层实现不一样， synchronized 是同步阻塞，使用的是悲观并发策略， lock 是同步非阻塞，采用的是乐观并发策略

1.8.5 Lock 和 synchronized 的区别

自动挡和手动挡的区别

1.Lock 需要手动获取锁和释放锁。就好比自动挡和手动挡的区别
1.Lock 是一个接口，而 synchronized 是 Java 中的关键字， synchronized 是内置的语言实现。
2.synchronized 在发生异常时，会自动释放线程占有的锁，因此不会导致死锁现象发生；而 Lock 在发生异常时，如果没有主动通过 unLock()去释放锁，则很可能造成死锁现象，因此使用 Lock 时需要在 finally 块中释放锁。
3.Lock 可以让等待锁的线程响应中断，而 synchronized 却不行，使用 synchronized 时，等待的线程会一直等待下去，不能够响应中断。
4.通过 Lock 可以知道有没有成功获取锁，而 synchronized 却无法办到。
5.Lock 可以通过实现读写锁提高多个线程进行读操作的效率。

二、线程不安全之 HashSet

有了前面大篇幅的讲解 ArrayList 的线程不安全，以及如何使用其他方式来保证线程安全，现在讲 HashSet 应该更容易理解一些。

2.1 HashSet 的用法

用法如下：

Set<BuildingBlockWithName> Set = new HashSet<>();set.add("a");

复制代码

初始容量=10，负载因子=0.75（当元素个数达到容量的 75%，启动扩容）

2.2 HashSet 的底层原理

public HashSet() {    map = new HashMap<>();}

复制代码

底层用的还是 HashMap()。

考点： 为什么 HashSet 的 add 操作只用传一个参数（value)，而 HashMap 需要传两个参数（key 和 value)

2.3 HashSet 的 add 操作

private static final Object PRESENT = new Object();
public boolean add(E e) {    return map.put(e, PRESENT)==null;}

复制代码

考点回答： 因为 HashSet 的 add 操作中，key 等于传的 value 值，而 value 是 PRESENT，PRESENT 是 new Object();，所以传给 map 的是 key=e, value=new Object。Hash 只关心 key，不考虑 value。

为什么 HashSet 不安全： 底层 add 操作不保证可见性、原子性。所以不是线程安全的。

2.4 如何保证线程安全

1.使用 Collections.synchronizedSet
Set<BuildingBlockWithName> set = Collections.synchronizedSet(new HashSet<>());
2.使用 CopyOnWriteArraySet
CopyOnWriteArraySet<BuildingBlockWithName> set = new CopyOnWriteArraySet<>();

2.5 CopyOnWriteArraySet 的底层还是使用的是 CopyOnWriteArrayList

public CopyOnWriteArraySet() {    al = new CopyOnWriteArrayList<E>();}

复制代码

三、线程不安全之 HashMap

3.1 HashMap 的使用

同理，HashMap 和 HashSet 一样，在多线程环境下也是线程不安全的。

Map<String, BuildingBlockWithName> map = new HashMap<>();map.put("A", new BuildingBlockWithName("三角形", "A"));

复制代码

3.2 HashMap 线程不安全解决方案：

1.Collections.synchronizedMap

Map<String, BuildingBlockWithName> map2 = Collections.synchronizedMap(new HashMap<>());

复制代码

2.ConcurrentHashMap

ConcurrentHashMap<String, BuildingBlockWithName> set3 = new ConcurrentHashMap<>();

复制代码

3.3 ConcurrentHashMap 原理

ConcurrentHashMap，它内部细分了若干个小的 HashMap，称之为段(Segment)。默认情况下一个 ConcurrentHashMap 被进一步细分为 16 个段，既就是锁的并发度。如果需要在 ConcurrentHashMap 中添加一个新的表项，并不是将整个 HashMap 加锁，而是首先根据 hashcode 得到该表项应该存放在哪个段中，然后对该段加锁，并完成 put 操作。在多线程环境中，如果多个线程同时进行 put 操作，只要被加入的表项不存放在同一个段中，则线程间可以做到真正的并行。

四、其他的集合类

LinkedList: 线程不安全，同 ArrayListTreeSet：线程不安全，同 HashSetLinkedHashSet：线程不安全，同 HashSetTreeMap：同 HashMap，线程不安全 HashTable： 线程安全

总结

本篇第一个部分详细讲述了 ArrayList 集合的底层扩容原理，演示了 ArrayList 的线程不安全会导致抛出并发修改异常。然后通过源码解析的方式讲解了三种方式来保证线程安全：

Vector是通过在add等方法前加synchronized来保证线程安全
Collections.synchronized()是通过包装数组，在数组的操作方法前加synchronized来保证线程安全
CopyOnWriteArrayList通过写时复制来保证线程安全的。

第二部分讲解了 HashSet 的线程不安全性，通过两种方式保证线程安全：

Collections.synchronizedSet
CopyOnWriteArraySet

第三部分讲解了 HashMap 的线程不安全性，通过两种方式保证线程安全：

Collections.synchronizedMap
ConcurrentHashMap

另外在讲解的过程中，也详细对比了 ReentrantLock 和 synchronized 及 Lock 和 synchronized 的区别。

彩蛋： 聪明的你，一定发现集合里面还漏掉了一个重要的东西：那就是Queue。

来源：https://mp.weixin.qq.com/s/SxgoRnxqECmXVZp9YGUb3A

发布于: 刚刚阅读数: 3

云流

关注

还未添加个人签名 2020.09.02 加入

还未添加个人简介

发布

暂无评论

创作场景

21 张图 | 带你领略集合的 线程不安全

一、线程不安全之 ArrayList

1.1、ArrayList 的底层初始化操作

1.2、ArrayList 的底层原理

1.2.1 初始化数组

1.2.1 ArrayList 的 add 操作

1.2.2 ArrayList 扩容源码解析

1.3、ArrayList 单线程环境是否安全？

1.4、多线程下 ArrayList 是不安全的

1.5 那如何解决 ArrayList 线程不安全问题呢？

1.6 Vector 是保证线程安全的？

1.6.1 初始化 Vector

1.6.2 Add 操作是线程安全的

1.6.3 Vector 扩容至 2 倍

1.6.4 用积木模拟 Vector 的 add 操作

1.7 使用 Collections.synchronizedList 保证线程安全

1.8 使用 CopyOnWriteArrayList 保证线程安全

1.8.1 CopyOnWriteArrayList 思想

1.8.2 使用方式

1.8.3 底层源码分析

1.8.4 ReentrantLock 和 synchronized 的区别

1.8.5 Lock 和 synchronized 的区别

二、线程不安全之 HashSet

2.1 HashSet 的用法

2.2 HashSet 的底层原理

2.3 HashSet 的 add 操作

2.4 如何保证线程安全

2.5 CopyOnWriteArraySet 的底层还是使用的是 CopyOnWriteArrayList

三、线程不安全之 HashMap

3.1 HashMap 的使用

3.2 HashMap 线程不安全解决方案：

3.3 ConcurrentHashMap 原理

四、其他的集合类

总结

云流

评论

21 张图 | 带你领略集合的线程不安全