集合.md 30 KB
hashmap
put方法
该方法首先会判断hashmap的数组是否被初始化，如果没有初始化，则首先进行初始化操作。其次判断该key是不是null，如果为null则在数组下标为0的地方进行插入操作，如果不为null，则进行下一步判断。 如果数组该位置为null，则新建一个node，进行插入，如果不为null，则采用头插法插入元素，如果链表长度大于8，并且数组长度大于64，则将链表转换为红黑树。如果小于64则直接扩容
为什么hashmap长度为16
- 减少hash冲突
- 每次扩容只用移动一半的元素
这是因为hashmap缓存了key的hash值，每次移动元素只需要新的高位与1相与就行。
get方法
判断该元素时候为空，如果为空直接返回，如果不为空则返回value
为什么选择红黑树
红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树。
Java 中的 HashMap 底层原理使用数组和链表/红黑树实现，而不使用 B 树，原因有以下几点：
- 红黑树的查找、插入、删除操作复杂度相对稳定，不会像 B 树 那样随着树高逐渐变差，平均时间复杂度为 O(log n)。B 树虽然有更快的查找速度，但在 Java 中，HashMap 的数据量一般都在1K以下，单机内存完全可以满足红黑树的需求。
- 空间利用率方面，B 树中非叶子节点需要存储下一级节点的指针，因此每个节点占用的空间相对较大，而红黑树只需要保存左右子节点和父节点的指针，所以相对来说更加节省空间。
- 红黑树相对于 B 树 更容易实现。
- 在实际应用中，虽然B树比红黑树有更优异的性能表现，但其实现比较复杂，在使用时需要结合具体场景来考虑。相比之下，红黑树实现简单，维护成本低，且平均情况下的性能也能够满足HashMap的需求，因此选择红黑树作为HashMap的底层数据结构更为合适。
综上所述，HashMap 选择红黑树而不是 B 树 作为其底层数据结构，主要是出于对效率和实现的考虑。
红黑树特征：
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
负载因子为什么是0.75
而加载因子就是表示Hash表中元素的填满程度。
加载因子 = 填入表中的元素个数 / 散列表的长度
加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了；
加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。
（泊松分布）选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。
解决冲突的方法
1. 开放定址法
Hi = (H(key) + di) MOD m，其中i=1,2,…,k(k<=m-1)
H(key)为哈希函数，m为哈希表表长，di为增量序列，i为已发生冲突的次数。其中，开放定址法根据步长不同可以分为3种：
1.1 线性探查法（Linear Probing）：di = 1,2,3,…,m-1
简单地说，就是以当前冲突位置为起点，步长为1循环查找，直到找到一个空的位置，如果循环完了都占不到位置，就说明容器已经满了。举个栗子，就像你在饭点去街上吃饭，挨家去看是否有位置一样。
1.2 平方探测法（Quadratic Probing）：di = ±12, ±22，±32，…，±k2（k≤m/2）
相对于线性探查法，这就相当于的步长为di = i2来循环查找，直到找到空的位置。以上面那个例子来看，现在你不是挨家去看有没有位置了，而是拿手机算去第i2家店，然后去问这家店有没有位置。
1.3 伪随机探测法：di = 伪随机数序列
这个就是取随机数来作为步长。还是用上面的例子，这次就是完全按心情去选一家店问有没有位置了。
但开放定址法有这些缺点：
- 这种方法建立起来的哈希表，当冲突多的时候数据容易堆集在一起，这时候对查找不友好；
- 删除结点的时候不能简单将结点的空间置空，否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点，只能在被删结点上添加删除标记，而不能真正删除结点；
- 如果哈希表的空间已经满了，还需要建立一个溢出表，来存入多出来的元素。
2. 再哈希法
Hi = RHi(key), 其中i=1,2,…,k
RHi()函数是不同于H()的哈希函数，用于同义词发生地址冲突时，计算出另一个哈希函数地址，直到不发生冲突位置。这种方法不容易产生堆集，但是会增加计算时间。
所以再哈希法的缺点是：增加了计算时间。
3. 链地址法（拉链法）
将冲突位置的元素构造成链表。在添加数据的时候，如果哈希地址与哈希表上的元素冲突，就放在这个位置的链表上。
拉链法的优点：
- 处理冲突的方式简单，且无堆集现象，非同义词绝不会发生冲突，因此平均查找长度较短；
- 由于拉链法中各链表上的结点空间是动态申请的，所以它更适合造表前无法确定表长的情况；
- 删除结点操作易于实现，只要简单地删除链表上的相应的结点即可。
拉链法的缺点：需要额外的存储空间。
从HashMap的底层结构中我们可以看到，HashMap采用是数组+链表/红黑树的组合来作为底层结构，也就是开放地址法+链地址法的方式来实现HashMap。
4. 建立公共溢出区：将哈希表分为基本表和溢出表，将发生冲突的都存放在溢出表中。
hashmap1.8死循环
还有可能卡在at java.util.HashMap$TreeNode.balanceInsertion(HashMap.java:2229) 可能Node节点转换为TreeNode结点异常，红黑树再平衡的时候会导致死循环
HashTable如何保证线程安全
HashMap是非同步的，没有对读写等操作进行锁保护，是线程不安全的。 Hashtable是同步的，所有的读写操作都进行了锁保护，是线程安全的。 Hashtable的底层是数组+链表实现的
简单一句话：加锁
ConcurrentHashMap1.7
Java 7 中 ConcurrentHashMap 的存储结构如上图，ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。
初始化逻辑
- 必要参数校验。
- 校验并发级别
concurrencyLevel大小，如果大于最大值，重置为最大值。无参构造默认值是 16. - 寻找并发级别
concurrencyLevel之上最近的 2 的幂次方值，作为初始化容量大小，默认是 16。 - 记录
segmentShift偏移量，这个值为【容量 = 2 的 N 次方】中的 N，在后面 Put 时计算位置时会用到。默认是 32 - sshift = 28. - 记录
segmentMask，默认是 ssize - 1 = 16 -1 = 15. - 初始化
segments[0]，默认大小为 2，负载因子 0.75，扩容阀值是 2*0.75=1.5，插入第二个值时才会进行扩容。
为什么在构造函数初始化s0？
方便后期其他key落到不同的segment中，能够知道加载因子，和默认容量一些基本参数，就是相当于提供了一个模板
put方法逻辑
- 计算要 put 的 key 的位置，获取指定位置的
Segment。 如果指定位置的
Segment为空，则初始化这个Segment.初始化 Segment 流程：
- 检查计算得到的位置的
Segment是否为 null. - 为 null 继续初始化，使用
Segment[0]的容量和负载因子创建一个HashEntry数组。 - 再次检查计算得到的指定位置的
Segment是否为 null. - 使用创建的
HashEntry数组初始化这个 Segment. - 自旋判断计算得到的指定位置的
Segment是否为 null，使用 CAS 在这个位置赋值为Segment.
- 检查计算得到的位置的
Segment.put插入 key,value 值。
put方法低层逻辑
tryLock()获取锁，获取不到使用scanAndLockForPut方法继续获取。- 计算 put 的数据要放入的 index 位置，然后获取这个位置上的
HashEntry。 - 遍历 put 新元素，为什么要遍历？因为这里获取的
HashEntry可能是一个空元素，也可能是链表已存在，所以要区别对待。 如果这个位置上的
HashEntry不存在：- 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
- 直接头插法插入。
如果这个位置上的
HashEntry存在：- 判断链表当前元素 key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值
- 不一致，获取链表下一个节点，直到发现相同进行值替换，或者链表表里完毕没有相同的。
- 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
- 直接链表头插法插入。
如果要插入的位置之前已经存在，替换后返回旧值，否则返回 null.
扩容
ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。
ConcurrentHashMap1.8
初始化逻辑
ConcurrentHashMap的初始化是通过自旋和 CAS 操作完成的
put方法
- 根据 key 计算出 hashcode 。
- 判断是否需要进行初始化。
- 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
- 如果当前位置的
hashcode == MOVED == -1,则需要进行扩容。 - 如果都不满足，则利用 synchronized 锁写入数据。
- 如果数量大于
TREEIFY_THRESHOLD则要执行树化方法，在treeifyBin中会首先判断当前数组长度 ≥64 时才会将链表转换为红黑树。
cas使用时候：没有发生冲突的时候 synchronized使用：index发生冲突的时候
get方法
- 根据 hash 值计算位置。
- 查找到指定位置，如果头节点就是要找的，直接返回它的 value.
- 如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
- 如果是链表，遍历查找之。
扩容方法
//新增元素时，也就是在调用 putVal 方法后，为了通用，增加了个 check 入参，用于指定是否可能会出现扩容的情况
//check >= 0 即为可能出现扩容的情况，例如 putVal方法中的调用
private final void addCount(long x, int check){
... ...
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
//检查当前集合元素个数 s 是否达到扩容阈值 sizeCtl ，扩容时 sizeCtl 为负数，依旧成立，同时还得满足数组非空且数组长度不能大于允许的数组最大长度这两个条件才能继续
//这个 while 循环除了判断是否达到阈值从而进行扩容操作之外还有一个作用就是当一条线程完成自己的迁移任务后，如果集合还在扩容，则会继续循环，继续加入扩容大军，申请后面的迁移任务
while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sc < 0 说明集合正在扩容当中
if (sc < 0) {
//判断扩容是否结束或者并发扩容线程数是否已达最大值，如果是的话直接结束while循环
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)
break;
//扩容还未结束，并且允许扩容线程加入，此时加入扩容大军中
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//如果集合还未处于扩容状态中，则进入扩容方法，并首先初始化 nextTab 数组，也就是新数组
//(rs << RESIZE_STAMP_SHIFT) + 2 为首个扩容线程所设置的特定值，后面扩容时会根据线程是否为这个值来确定是否为最后一个线程
else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
//扩容状态下其他线程对集合进行插入、修改、删除、合并、compute等操作时遇到 ForwardingNode 节点会调用该帮助扩容方法 (ForwardingNode 后面介绍)
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
//此处的 while 循环是上面 addCount 方法的简版，可以参考上面的注释
while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
//putAll批量插入或者插入节点后发现链表长度达到8个或以上，但数组长度为64以下时触发的扩容会调用到这个方法
private final void tryPresize(int size) {
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);
int sc;
//如果不满足条件，也就是 sizeCtl < 0 ，说明有其他线程正在扩容当中，这里也就不需要自己去扩容了，结束该方法
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
//如果数组初始化则进行初始化，这个选项主要是为批量插入操作方法 putAll 提供的
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
//初始化时将 sizeCtl 设置为 -1 ，保证单线程初始化
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
//初始化完成后 sizeCtl 用于记录当前集合的负载容量值，也就是触发集合扩容的阈值
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
//插入节点后发现链表长度达到8个或以上，但数组长度为64以下时触发的扩容会进入到下面这个 else if 分支
else if (tab == table) {
int rs = resizeStamp(n);
//下面的内容基本跟上面 addCount 方法的 while 循环内部一致，可以参考上面的注释
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}
说明：总的来说
在调用 addCount 方法增加集合元素计数后发现当前集合元素个数到达扩容阈值时就会触发扩容 。
扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点会触发扩容 。帮助该桶进行扩容
putAll 批量插入或者插入节点后发现存在链表长度达到 8 个或以上，但数组长度为 64 以下时会触发扩容 。
注意：桶上链表长度达到 8 个或者以上，并且数组长度为 64 以下时只会触发扩容而不会将链表转为红黑树 。
//调用该扩容方法的地方有：
//java.util.concurrent.ConcurrentHashMap#addCount 向集合中插入新数据后更新容量计数时发现到达扩容阈值而触发的扩容
//java.util.concurrent.ConcurrentHashMap#helpTransfer 扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点时触发的扩容
//java.util.concurrent.ConcurrentHashMap#tryPresize putAll批量插入或者插入后发现链表长度达到8个或以上，但数组长度为64以下时触发的扩容
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 计算每条线程处理的桶个数，每条线程处理的桶数量一样，如果CPU为单核，则使用一条线程处理所有桶
// 每条线程至少处理16个桶，如果计算出来的结果少于16，则一条线程处理16个桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // 初始化新数组(原数组长度的2倍)
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
//将 transferIndex 指向最右边的桶，也就是数组索引下标最大的位置
transferIndex = n;
}
int nextn = nextTab.length;
// 新建一个占位对象，该占位对象的 hash 值为 -1 该占位对象存在时表示集合正在扩容状态，key、value、next 属性均为 null ，nextTable 属性指向扩容后的数组
// 该占位对象主要有两个用途：
// 1、占位作用，用于标识数组该位置的桶已经迁移完毕，处于扩容中的状态。
// 2、作为一个转发的作用，扩容期间如果遇到查询操作，遇到转发节点，会把该查询操作转发到新的数组上去，不会阻塞查询操作。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 该标识用于控制是否继续处理下一个桶，为 true 则表示已经处理完当前桶，可以继续迁移下一个桶的数据
boolean advance = true;
// 该标识用于控制扩容何时结束，该标识还有一个用途是最后一个扩容线程会负责重新检查一遍数组查看是否有遗漏的桶
boolean finishing = false; // to ensure sweep before committing nextTab
// 这个循环用于处理一个 stride 长度的任务，i 后面会被赋值为该 stride 内最大的下标，而 bound 后面会被赋值为该 stride 内最小的下标
// 通过循环不断减小 i 的值，从右往左依次迁移桶上面的数据，直到 i 小于 bound 时结束该次长度为 stride 的迁移任务
// 结束这次的任务后会通过外层 addCount、helpTransfer、tryPresize 方法的 while 循环达到继续领取其他任务的效果
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
// 每处理完一个hash桶就将 bound 进行减 1 操作
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
// transferIndex <= 0 说明数组的hash桶已被线程分配完毕，没有了待分配的hash桶，将 i 设置为 -1 ，后面的代码根据这个数值退出当前线的扩容操作
i = -1;
advance = false;
}
// 只有首次进入for循环才会进入这个判断里面去，设置 bound 和 i 的值，也就是领取到的迁移任务的数组区间
else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
// 扩容结束后做后续工作，将 nextTable 设置为 null，表示扩容已结束，将 table 指向新数组，sizeCtl 设置为扩容阈值
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 每当一条线程扩容结束就会更新一次 sizeCtl 的值，进行减 1 操作
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//(sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT 成立，说明该线程不是扩容大军里面的最后一条线程，直接return回到上层while循环
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT 说明这条线程是最后一条扩容线程
// 之所以能用这个来判断是否是最后一条线程，因为第一条扩容线程进行了如下操作：
// U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)
// 除了修改结束标识之外，还得设置 i = n; 以便重新检查一遍数组，防止有遗漏未成功迁移的桶
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)
// 遇到数组上空的位置直接放置一个占位对象，以便查询操作的转发和标识当前处于扩容状态
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
// 数组上遇到hash值为MOVED，也就是 -1 的位置，说明该位置已经被其他线程迁移过了，将 advance 设置为 true ，以便继续往下一个桶检查并进行迁移操作
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// 该节点为链表结构
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
// 遍历整条链表，找出 lastRun 节点
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// 根据 lastRun 节点的高位标识(0 或 1)，首先将 lastRun设置为 ln 或者 hn 链的末尾部分节点，后续的节点使用头插法拼接
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
// 使用高位和低位两条链表进行迁移，使用头插法拼接链表
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
//setTabAt方法调用的是 Unsafe 类的 putObjectVolatile 方法
//使用 volatile 方式的 putObjectVolatile 方法，能够将数据直接更新回主内存，并使得其他线程工作内存的对应变量失效，达到各线程数据及时同步的效果
//使用 volatile 的方式将 ln 链设置到新数组下标为 i 的位置上
setTabAt(nextTab, i, ln);
//使用 volatile 的方式将 hn 链设置到新数组下标为 i + n(n为原数组长度) 的位置上
setTabAt(nextTab, i + n, hn);
//迁移完成后使用 volatile 的方式将占位对象设置到该 hash 桶上，该占位对象的用途是标识该hash桶已被处理过，以及查询请求的转发作用
setTabAt(tab, i, fwd);
//advance 设置为 true 表示当前 hash 桶已处理完，可以继续处理下一个 hash 桶
advance = true;
}
//该节点为红黑树结构
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
//lo 为低位链表头结点，loTail 为低位链表尾结点，hi 和 hiTail 为高位链表头尾结点
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
//同样也是使用高位和低位两条链表进行迁移
//使用for循环以链表方式遍历整棵红黑树，使用尾插法拼接 ln 和 hn 链表
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
//这里面形成的是以 TreeNode 为节点的链表
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
//形成中间链表后会先判断是否需要转换为红黑树：
//1、如果符合条件则直接将 TreeNode 链表转为红黑树，再设置到新数组中去
//2、如果不符合条件则将 TreeNode 转换为普通的 Node 节点，再将该普通链表设置到新数组中去
//(hc != 0) ? new TreeBin<K,V>(lo) : t 这行代码的用意在于，如果原来的红黑树没有被拆分成两份，那么迁移后它依旧是红黑树，可以直接使用原来的 TreeBin 对象
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
//setTabAt方法调用的是 Unsafe 类的 putObjectVolatile 方法
//使用 volatile 方式的 putObjectVolatile 方法，能够将数据直接更新回主内存，并使得其他线程工作内存的对应变量失效，达到各线程数据及时同步的效果
//使用 volatile 的方式将 ln 链设置到新数组下标为 i 的位置上
setTabAt(nextTab, i, ln);
//使用 volatile 的方式将 hn 链设置到新数组下标为 i + n(n为原数组长度) 的位置上
setTabAt(nextTab, i + n, hn);
//迁移完成后使用 volatile 的方式将占位对象设置到该 hash 桶上，该占位对象的用途是标识该hash桶已被处理过，以及查询请求的转发作用
setTabAt(tab, i, fwd);
//advance 设置为 true 表示当前 hash 桶已处理完，可以继续处理下一个 hash 桶
advance = true;
}
}
}
}
}
}
总结
设计方面
基于sizeCtI共享变量，通知各线程当前哈希桶的状态;基于transferindex共享变量，重新划分区间，保证每一个子区间最多只有一个线程进行扩容;
基于双table + 标记节点，保证扩容过程中get操作的不受扩容影响;
实现方面
- 共享变量用volatile修饰，保证线程间的可见性;
- sizeCtl、transferlndex采用自旋+CAS进行修改，保证原子性
- 节点的迁移和标记采用synchronized关键字加锁，保证原子性;