总结文档

总结文档

普通集合

Arrays.asList()返回的是视图（ArrayList 内部类对象，只提供了替换数据的方法，其底层依旧是原数组数据）
- subList：返回的 List 是 ArrayList 中某段数据的一个视图，不可在使用时对原对象进行操作，否则会出现 CME 异常
HashMap
- 对于容量的初始化分配，在首次 put 操作时执行（lazy load）
  ii. 并发下出现的死链问题：https://www.jianshu.com/p/619a8efcf589、https://juejin.im/post/5a255bbd6fb9a0450c493f4d
  iii. JDK1.8 版本中的 HashMap 在高并发情况下存在数据丢失问题 - 临时结点 Node<K,V>可能由于并发问题被覆盖 - Entry 链表转为了红黑树

并发集合

LongAdder 与 AtomicLong
LongAdder（用空间换时间）
- 继承自 Striped64，内部的 Cell 类被 Contended 注解修饰，其目的是为了解决伪缓存共享的问题（争抢缓存行的所有权，两个变量被分配到了同一个缓存行中）
- 对于低竞争的情况下，直接采用 CAS 操作更新 base 变量
- 高竞争情况下，将每个线程操作 hash 到不同的 cells 数组中，从而将 AtomicLong 更新一个 value 的行为分散到多个 value 中，如果要获取值的话，直接将 Cell 数组中的各个值相加再加上 base 值就得到
如何实现原子操作的：调用 UnSafe.compareAndswapInt，底层指令确保操作执行原子性（比较更新操作）
iii. 原子数组（AtomicIntegerArray） - 数组通过其构造器传入，然后 AtomicIntegerArray 会将数组进行一次 copy 操作，因此对原有的数组没有任何影响
存在 ABA 问题，如何解决：版本号机制
ConcurrentLinkedQueue（优秀博文：https://juejin.im/entry/5b4dde4b5188251af6621e13）
哨兵节点：next 域指向了自己的节点（通常是待删除或者是一个空间节点），哨兵节点的设置（lazySetNext）
允许 tail、head 的更新存在滞后的情况出现
- 为什么允许更新滞后的情况出现
  - 如果让 tail 永远为队列的尾节点，则每次都需要使用循环 CAS 更新 tail 节点，如果能减少更新 tail 节点的次数，入队的性能更高
  - head 节点不一定就是队列的第一个含有元素的节点，也不是每次获取元素后就更新 head 节点，只有当 head 中的元素为空的时候才更新 head 节点，这和添加 offer() 方法中更新 tail 节点类似，减少 CAS 更新 head 节点的次数，出队的效率会更高
- 示例图
CopyOnWriteList
类似操作系统的 COW 机制
执行写操作时，复制出一份副本用于写操作，当写操作执行完毕后，采用 volatile 写语义将副本替换旧数据，实现并发安全的写操作，但是缺点是无法读取到最新的数据
Disruptor
使用环形数组结构，为了应对 Java 内存回收机制，采用数组而非链表（为什么）；同时数组对处理器的缓存机制更加友好——元素位置定位
核心思想：CAS 锁操作尽量代替原有的 Lock 操作
生产者
- 申请写入 m 个元素，若有 m 个元素可以写入，则返回最大序列号（判断是否会覆盖未读的元素）
- 遇到多个生产者重复写一个 queue 时，会为每个线程分配不同的一段数组空间进行操作
- 防止读到未写入的元素：新创建一个与 ring buffer 大小相同的 buffer——avaliable buffer，某个位置写入成功，相应位置置位标记为写入成功，读取时遍历 avaliable buffer
消费者等待策略
- 项目遇到的策略设置错误问题：YieldingWaitStrategy 很可能导致 CPU 负载 100%
ConcurrentHashMap
不同 java 版本的实现区别
- Java1.7 版本中，采用 segment 分段锁技术，segment[]数组中每个 segment 对应一段 table 数据，每个 segment 可以看做一个锁，这个锁负责一部分 Map 数据的读写
- Java1.8 版本中，直接用 table 数组的每个元素进行分段锁（个人觉得），通过提高锁的细粒度，更好的避免了并发冲突，cas 乐观锁更新机制
  - CAS：
    - CAS 的原理是拿期望的值和原本的一个值作比较，如果相同则更新成新的值。UnSafe 类的 objectFieldOffset() 方法是一个本地方法，这个方法是用来拿到“原来的值”的内存地址，返回值是 valueOffset。另外 value 是一个 volatile 变量，在内存中可见

扩容的实现（将扩容任务分给多个线程去完成，每个线程认领各自的桶区间，对各自负责的桶区间进行 resize 操作——核心也是并发高效的原因之一）

计算每个线程可以处理的桶区间，默认 16
- 让多个线程分摊 Map 的扩容操作，每个线程负责一部分（没有重叠部分，也就避免了资源的竞争问题）
- 实现代码，除以 CPU 核数是为了求出每个 CPU 处理的桶的个数，并让每个线程处理的桶的个数相同，避免出现转移任务不均匀的现象
- （if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE;）

新旧 Table，正在进行 resize 时，原 table 对应的槽位会放置一个 ForwardingNode 节点，将 find 请求转发至新的 table 中；当别的线程发现槽位的是 fwd 类的节点时，就自动跳过

对 putVal 可感知

1
2
3

else if ((fh = f.hash) == MOVED)
	tab = helpTransfer(tab, f);
else {…}

转发查询请求的代码
根据 Node 的 hash 值进行判断

如果对应的槽位存在实际值，则对该槽位进行加锁进行扩容操作，此时处理桶的行为是同步的

如果桶是链表的，则根据 hash 结果拆分成两个链表（高低位）

for (Node<K,V> p = f; p != lastRun; p = p.next) {
	int ph = p.hash; K pk = p.key; V pv = p.val;
	// 如果与运算结果是 0，那么就还在低位
	if ((ph & n) == 0) // 如果是0 ，那么创建低位节点
		ln = new Node<K,V>(ph, pk, pv, ln);
	else // 1 则创建高位
		hn = new Node<K,V>(ph, pk, pv, hn);
}

然后通过 CAS 操作更新新表高低槽位，将新生成的两个链表放入，同时更新旧表中对应槽位的占位符为 ForwardingNode 节点

通过 sizeCtl 进行显示当前有多少个线程正在进行扩容操作（被 volatile 修饰）
优秀博客：https://juejin.im/post/5b00160151882565bd2582e0
有这么一个问题，ConcurrentHashMap，有三个线程，A 先 put 触发了扩容，扩容时间很长，此时 B 也 put 会怎么样？此时 C 调用 get 方法会怎么样？C 读取到的元素是旧桶中的元素还是新桶中的
- A 先触发扩容，ConcurrentHashMap 迁移是在锁定旧桶的前提下进行迁移的，并没有去锁定新桶。
  - 在某个桶的迁移过程中，别的线程想要对该桶进行 put 操作怎么办？一旦某个桶在迁移过程中了，必然要获取该桶的锁，所以其他线程的 put 操作要被阻塞。因此 B 被阻塞。
  - 某个桶已经迁移完成（其他桶还未完成），别的线程想要对该桶进行 put 操作怎么办？该线程会首先检查是否还有未分配的迁移任务，如果有则先去执行迁移任务，如果没有即全部任务已经分发出去了，那么此时该线程可以直接对新的桶进行插入操作（映射到的新桶必然已经完成了迁移，所以可以放心执行操作）