数据结构:synchronize + CAS + 红黑树
Node 的 val 和 next 都用 volatile 修饰,保证可见性
并发扩容
一个线程发起扩容时,就会通过 CAS 设置 sizeCtl 属性(volatile 修饰),告知其他线程扩容状态变更。创建一个两倍容量的新数组 nextTable,单线程完成。
扩容时会判断这个值(sizeCtl 属性),如果超过阈值则需要扩容
首先根据运算得到需要遍历的次数 i,然后利用 tabAt 方法获得 i 位置的元素 f
初始化一个 forwardNode 实例 fwd,如果 f == null,则在 table 中的 i 位置放入 fwd
否则采用头插法的方式把当前旧 table 数组的指定任务范围的数据给迁移到新的数组,然后给旧 table 原位置赋值 fwd
迁移数据至少每次获取 16 个迁移任务,transferIndex 扩容索引,迁移数据前先 CAS 操作该变量,相当于任务头指针
查到遍历过所有的节点以后就完成了复制工作,把 table 指向 nextTable ,并更新 sizeCtl 为新数组大小的 0.75 倍,
ForwardingNode 节点
标记作用,表示其他线程正在扩容,并且此节点已经扩容完毕
关联了 nextTable,扩容期间可以通过 find 方法,访问已经迁移到了 nextTable 中的数据
如果遍历到的节点是 forward 节点,就向后继续遍历,再加上给节点上锁的机制,就完成了多线程的控制。多线程遍历节点,处理了一个节点,就把对应点的值 set 为 forward,另外一个线程看到 forward,就向后遍历。这样交叉就完成了复制工作。
读操作无锁
Node 的 val 和 next 使用 volatile 修饰,读写线程对该变量互相可见
数组用 volatile 实现,保证扩容时倍读线程感知