【多线程】线程安全集合类，ConcurrentHashMap实现原理

线程安全集合类

ArrayList、Queue、HsahMap… 都是线程不安全的

Vector、Stack、Hashtable 都是线程安全的（内置了 synchronized），实际上这几个东西并不推荐使用

• 因为这几个都是无脑加 synchronized，无论如何都要加锁，哪怕单线程也要加锁，不科学。很有可能出现阻塞，可能会使程序效率大打折扣
• 编译器的“锁消除”并不能 100%解决问题，只能把十拿九稳的地方进行优化，有些代码是锁消除机制摸不透的

解决方案

多线程环境使用顺序表

1. 自己加锁

• 给 ArrayList 套了个壳。ArrayList 各种操作本身不带锁，通过上述套壳之后，得到了新的对象，新的对象里面的关键方法都是带有锁的

3. 使用 CopyOnWriteArrayList

这里面主要用到了“写实拷贝”

• 线程安全问题，在多个线程修改同一个数据的时候会触发

• 把顺序表复制一份，修改新的顺序表内容，然后修改引用的指向，这样就不会有线程安全问题
  • “修改引用指向”这个操作是原子的，不需要加锁

这种操作有很大的局限性

1. 修改不能太频繁（复制开销很大）
2. 顺序表也不应该太大

一般在服务器加载配置文件的时候，就要把配置文件的内容解析出来，放到内存的数据结构中（顺序表/哈希表…）

• 服务器的修改频率很低
• 配置文件一般体积都不大（几 kb）

多线程环境使用队列

1. 自己加锁
2. BlockingQueue（线程安全的）

多线程环境使用哈希表

HashMap 肯定不行，它是线程不安全的。更靠谱的是 Hashtable，其在一些关键方法上添加了 synchornized，但这个不好用

• 他俩区别就是有无 synchornized

后来标准库又引入了一个更好的解决方案：ConcurrentHashMap

ConcurrentHashMap

改进：

1. 缩小锁的粒度

• Hashtable 是直接在方法上使用 synchornized，相当于是对 this 加锁，整个哈希表就只有这一把锁，此时，尝试修改两个不同链表上的元素，都会触发锁冲突（Hashtable 底层实现是数组+链表）

• 锁的粒度很大，是一个全局锁，同一时刻只能有一个线程访问整个哈希表。

• 仔细观察就可以发现，如果修改两个不同链表上的元素，不涉及到线程安全问题（修改不同变量）

  • 如果修改的是同一个链表上的元素，就可能涉及到线程安全问题
  • 比如这俩变量在链表上的位置是相邻的，操作引用的时候，就可能涉及到操作同一个引用

• 此时，针对同一个链表操作，再加锁；针对不同链表操作，就不必加锁了（不要产生锁冲突）

ConcurrentHashMap 就是把锁变小了，给每一个链表都发了一个锁

• 弄出了这么多锁，会付出更多空间的代价吗？
  • 不会；Java 中，任何一个对象都可以直接作为锁对象。本身哈希表中就得有数组，数组的元素都是已经存在的（每个链表的头结点），此时，只要使用数组元素（链表头结点）作为加锁的对象即可

• 每个链表就是构成桶的一个木板。所谓“锁桶”，就是针对每个木板（每个链表）分别加锁的

在 Java 1.7 及其之前，ConcurrentHashMap 是通过“分段锁”来实现的

• 给若干个链表分配一把锁
• 这种设定，不太合适，实现更复杂，效率也不够高，还要引入额外的空间开销（重新定义锁）
  从 Java 8 开始，这里的设定就变成每个链表一把锁了

2. 充分使用 CAS

充分使用 CAS 原子操作，减少了一些加锁

• 比如，针对哈希表元素个数的维护

synchornized 里面不是刚开始是偏向锁或者轻量级锁，速度很快吗？

• synchornized 有可能成为重量级锁，并且是否升级了不可控

3. 针对扩容操作

扩容是一个重量操作

0.75 是负载因子默认的扩容阈值，不是负载因子本体

• 负载因子是你算出来的数
• 拿着实际的元素个数/数组长度（桶的个数）算出来的数值，这个值可能是 0.1，可能是 0.5 可能是 1，可能是 10
• 然后我们拿着这个值和扩容阈值进行比较，看看是否需要扩容

负载因子：描述了每个桶上面平均有多少个元素

• 此时桶上的链表的元素不应该太长，才能保证遍历的时间复杂度为 $O(1)$

如果太长：

1. 变成树（长度不平均的情况）
2. 扩容
   • 创建一个更大的数组，把旧的 Hash 表的元素都给搬运到（删除/插入）到新的数组上
   • 如果 hash 表本身元素非常多，这里的扩容操作就会消耗很长时间
   • hash 表平时都很快，突然间某个操作就变慢了，过一会又快了（表现不稳定，坏事）
   • 我们无法控制何时触发扩容，一旦触发扩容，就会导致这次操作非常耗时（用户直观感受：卡顿）

HashMap 的扩容操作是一把梭哈，在某一次插入元素操作中，整体完成扩容（就会卡顿，耗时）

ConcurrentHashMap 的策略是“化整为零，蚂蚁搬家”

• 每次只搬运一部分元素
• 假设有 1kw 个元素，此时扩容的时候，每次插入/查找/删除，都会搬运一部分元素（每次搬运 5k 个元素），一共花 2k 次搬完（花的时间更长，但是值得）
• 确保每操作消耗的时间都不会很长，避免出现很卡的情况

在扩容过程中，同时存在两份哈希表，一份是新的，一份是旧的

• 插入操作：直接往新的上插入
• 删除操作：新的旧的都直接删除
• 查找操作：新的旧的都要查询一下