目录

前言

顺序表

队列

哈希表

1、Hashtable

2、ConcurrentHashMap（重点）

---

前言

本文章主要介绍在多线程环境下，如何线程安全的使用一些常用的集合类（顺序表和哈希表）。

---

顺序表

1、自己使用同步锁机制（synchornized和ReentrantLock）保证线程安全

2、Collections.synchronizedList()

它是 Java 中 java.util.Collections 类提供的一个基于synchronized关键字，给List加锁的静态方法，用于创建安全的List。

3、写时拷贝

Java中提供了CopyOnWrit这个容器来解决线程安全问题。

它的解决思路是：

在多个线程读取容器中的数据的时候不会做任何操作，但是当一个线程要修改容器中的数据的时候，不能立刻修改当前引用所指向的数据，而是重新拷贝一份相同的容器，在这个新的容器中去修改数据。在写入数据的时候，其他线程只能读取旧容器中的数据。等修改完毕，把引用现在已经修改好的新的容器（引用的赋值是一个原子操作）。

优点：

 在读多写少的环境下，因为没有加锁，所以没有锁开销，也没有锁竞争，性能高。

缺点：

• 不能实现多个线程同时修改数据，因此不适用于写多读少的场景。
• 因为拷贝的参与，所以当数据量本身很大的情况下会消耗内存，并且时间开销也会增大。

---

队列

关于队列的线程安全，自然使用到的是阻塞队列：

1. ArrayBlockingQueue：   基于数组实现的阻塞队列

2. LinkedBlockingQueue： 基于链表实现的阻塞队列

3. PriorityBlockingQueue： 基于堆实现的带优先级的阻塞队列

4. TransferQueue：             最多只包含⼀个元素的阻塞队列

关于阻塞队列的详细介绍这里就不展开了，在同专栏第9节专门讲解了。

---

哈希表

HashMap本身是线程不安全的，在多线程环境下可以使用Hashtable/ConcurrentHashMap

1、Hashtable

Hashtable这个类只是对HashMap进行简单的加锁，也就是在关键方法上增加了synchronized关键字：

这就导致只要多个线程同时调用put或者get方法，即使他们想要访问的不是同一组数据，照样会进入阻塞状态，也就是所冲突，极大的影响了运行效率。

另外，如何在某一个线程使用put操作时，如果需要扩容，那么就会由当前线程进行扩容，如果涉及大量的元素拷贝，那么多线程的运行效率又会大幅降低。

总的来讲，HashTable相当于对整个哈希桶上了锁：

2、ConcurrentHashMap[推荐使用]

为了降低锁冲突概率，ConcurrentHashMap做出了以下优化：

• 读操作：没有加锁，但是加了volatile保证内存可见。
• 写操作：对每一个链表都进行了加锁（synchronized实现），如果写入数组中不同的下标，那么就不会发生所冲突，如图：
• CAS的使用：在锁竞争并不激烈的情况下，采用CAS来更新size（键值对 增加/减少），这种方式不用加锁，更轻量，提高运行效率（jdk8引入）。
   
• 分散计数器槽：在锁竞争激烈时，使用CAS就可能出现忙等的情况，使用CAS修改size就不太好了。为了避免多个线程同时修改同一个数据(size)，ConcurrentHashMap引入了分散计数器槽（Counter Cells），它的原理如下:

  1、分散计数器槽的初始化：

.     ◦ 当多个线程进行插入或删除操作时，如果检测到对单个计数器的竞争变得激烈，ConcurrentHashMap会创建一个计数器槽数组。

      ◦ 这个数组中的每个槽（cell）都可以独立地更新，从而减少竞争。

  2、计数器槽的更新：

     ◦ 当一个线程需要更新size（例如插入或删除元素）时，它会尝试使用CAS操作更新某个计数器槽。

     ◦ 如果更新失败（因为另一个线程同时在更新这个槽），该线程会尝试更新另一个槽，直到成功为止。

  3、计数器槽的汇总：

     ◦ 当需要获取ConcurrentHashMap的大小时，size()方法会遍历所有计数器槽，将它们的值相加得到总的元素数量。

---

Counter Cells的核心思想就是使用数组来降低并发负载。

• 扩容方式：与HashTable让发现需要扩容的线程去完成整个扩容任务不同，Concurrent把扩容任务分散给了多个线程去完成，即“化整为零”。
  大致步骤如下：​​​​

1、创建一个比原来还要大的数组。

2、每一个线程都尝试去获取一个没有完成旧数组到新数组迁移任务的桶（链表），然后对桶进行数据迁移、重新哈希（使用CAS保证线程安全，同时提高整体效率）。

3、所有桶都完成了数据迁移后，数组引用从旧数组指向新数组，扩容才真正完成。

---

注意，在扩容期间：

1）如果有put(插入操作)，先对旧桶进行哈希，如果旧桶没有数据迁移，那么就插入到旧桶中，如果已经数据迁移，就插入到新桶中。

2）如果是get（查找操作），先找旧桶，旧桶没有找到，找新桶。

这种扩容方式大大提高了并发性能（逐步迁移，降低阻塞概率）以及系统稳定性(扩容时，单个线程锁占用时间不会激增)。

---

完