摘要：不过在链表过长时会将其重构为红黑树，这样，其最坏的时间复杂度就会降低为，这样使得表的适应场景更广。该节点代表一棵红黑树。调用红黑树的相关方法完成操作。同样，和链表的一样，也是将红黑树拆分成两条子树。
接上一篇博文，来吧剩下的部分写完。
总体来说，HashMap的实现内部有两个关键点，第一是当表内元素和hash桶数组的比例达到某个阈值时会触发扩容机制，否则表中的元素会越来越挤影响性能；
第二是保存hash冲突的链表如果过长，就重构为红黑树提升性能。
关于第二点，对于HashMap来说，达到O(1)的查询性能只是平均时间复杂度，这需要key的hash值对应的位置分布的足够均匀。
来设想一种极端情况，假设某个黑客故意构造一组特定的数据，这些数据的hash值正好一样。当插入hash表中时，它们的位置也一样。
那么，这些数据会全部被组织到该位置的链表中，hash表退化为链表，这时的查询的时间复杂度为O(N)，也是hash表查询时间复杂度的最坏情况。
不过HashMap在链表过长时会将其重构为红黑树，这样，其最坏的时间复杂度就会降低为O(logN)，这样使得hash表的适应场景更广。
resize扩容
扩容分两个步骤：
计算扩容之后的大小。
进行具体的扩容操作。
计算扩容后大小
以下是第一个步骤的代码：
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 已经初始化过的情况
// 对边界情况的处理：如果hash桶数组的大小已经达到了最大值MAXINUM_CAPACITY 这里是2的30次方
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} // 扩容两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold // 这种情况对照构造函数看
newCap = oldThr;
else { // zero initial threshold signifies using defaults // 这种情况对照构造函数看
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // =_= 逻辑好绕
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 到此，newCap是新的hash桶数组大小，newThr是新的扩容阈值
threshold = newThr;
// 分配一个新的hash桶数组，然后把旧的数据迁移过来
/* ... */
}
逻辑是这样的，首先有三种情况，代码写的看起来很复杂：
hash桶数组已经初始化过。
扩容后是会溢出，也即达到了2的30次方。
扩容后不会溢出，这种情况扩容两倍。扩容后hash桶数组的大小依然是2的幂。
hash桶数组没有初始化过，但是指定了初始化大小。
hash桶数组没有初始化过，也没有指定初始化大小。
虽然逻辑很明确，但是代码写的看起来却很复杂。
其原因是HashMap内部记录的字段能表达的状态太多，每种情况都需要考虑周全。
第一阶段执行完毕后，HashMap内部的部分状态字段被更新。
最重要的是，newCap这个变量记录了扩容之后的大小。
执行扩容操作
final Node[] resize() {
/* ... */
// 分配一个新的hash桶数组，然后把旧的数据迁移过来
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) // 只有一个元素的情况
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 二叉树的情况
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order // 链表的情况
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do { // 遍历链表
next = e.next;
if ((e.hash & oldCap) == 0) {
// 如果注意到hash桶数组扩容是从2^N 到 2^(N +１) 这一事实，从二进制的角度分析取余运算，就不难发现优化思路。
// 总之，这个迭代的代码是把这条链表拆分成两条，然而不同的处理逻辑。
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 对于这两种不同类型的链表，移动的方式不一样
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
从思路上，总结如下：
分配一个新的hash桶数组，这是扩容后的数组。之后需要把之前的节点迁移过来。
遍历旧的hash桶数组，在其中保存有节点时，分不同情况处理：
只有一个节点的情况，直接将这个节点rehash到新的数组中。
该节点代表一棵红黑树。调用红黑树的相关方法完成操作。
该节点代表一个链表。将链表节点rehash到新的数组中。
先来看下红黑树的split函数：
final void split(HashMap map, Node[] tab, int index, int bit) {
/* ... */
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
// 只是这里面有一个逻辑，即如果拆分出的树太小，就重新转换回链表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
/* ... */
}
红黑树的各种操作代码我是无心看，各种旋转太复杂了。这里面主要有一个关键点，在于rehash的时候，会将红黑树节点也rehash。
同样，和链表的rehash一样，也是将红黑树拆分成两条子树。至于为什么是拆分为两条后面会说。
但是，如果拆分出来的子树太小了，就会重新将其重构回链表。
顺便说一句，由于删除操作的逻辑没有什么新东西之前就没有分析。我也没有在其中找到删除节点时，如果红黑树太小会将其重构回链表的操作。
rehash优化
对于链表的rehash操作，乍一看，这个逻辑还有些看不懂，从代码上来看是这样的逻辑，对于hash桶数组中第j个位置上的一个链表，进行遍历，根据条件分成两条：
(e.hash & oldCap) == 0
满足上述条件的串成一条链表loHead，不满足上述条件的串成一条链表hiHead。之后：
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
实际上，由于HashMap的hash桶数组的大小一定为2的幂这一性质，取余操作能够被优化。前面也说过这一点，这里以大小为8，也即0001000为例子：
设一个2的幂次方数N，如00001000，二进制写法中一定只有一个1.
任意一个数B余N，反映到二进制上，就是高于等于1的对应位置0，低于的保留。如00111110 % 00001000 = 00000110，前5位置0，后4位保留。
假如让这个数余2N，不难发现，反映到二进制上，变成了前4位置0，后4为保留。
严谨的数学表达我实在懒得写了，总之通过分析不难得到这个结论：
如果数B的第3位（从低位从0开始数）为0，那么B % N = B % 2N。
如果数B的第3位（从低位从0开始数）为1，那么B % N结果的第3位给置1等于B % 2N，也即B % N + N = B % 2N
有了以上结论，对照上面的代码，也就不难理解这段rehash代码的思路了：
(e.hash & oldCap) == 0
这句话是判断hash值的对应位是否为0，并分成两条不同的链表。
如果为0，则rehash后的位置不变。
如果不为0，则为以前的位置加上旧表的大小。
最后，我比较疑惑的一点是，花了这么大力气去优化，为什么能得到性能或内存上的提升？
我们分析下优化前后的时间复杂度：
如果不优化，则是遍历旧的hash桶数组，然后遍历每一个链表，并且把链表的每个节点rehash到新的hash桶数组上去。将链表插入到新的数组只需O(1)的时间，也即整个操作的时间复杂度为O(N)，N为hash表中元素的个数。
如果优化，则是遍历旧的hash桶数组，然后同样需要遍历每一个链表，把每一个节点分开到两条不同的子链表上去。。。时间复杂度仍然是O(N)...
看起来两种方案都需要遍历所有的链表节点，难道仅仅是减小一点时间复杂度的常数吗？
treeifyBin操作
之前说过当链表长度过大时会将其重构为红黑树，下面来看具体的代码。
// 8. 把链表转换成二叉树
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
// 如果hash桶数组的大小太小还得扩容。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 所需要的hash参数是为了定位是hash桶数组中的那个链表，可为啥不直接传index...
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode hd = null, tl = null;
// 遍历单链表，然后把给它们一个个的分配TreeNode节点
// 看下面这代码，这个TreeNode，记得拥有next和prev字段，看下面的代码是把它们串成双链表
do {
TreeNode p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 调用TreeNod.treeify()函数将这个已经组成双链表的TreeNode节点重构成红黑树
hd.treeify(tab);
}
}
之前提到过TreeNode拥有next和prev字段，因此它不仅能够用来组织红黑树，还能够组织双向链表。
这里看到了，这里首先将单链表的元素复制到TreeNode节点构成的双向链表中，然后通过TreeNode的treeify方法将其组织成红黑树。至于这个方法。。。各种旋转，红黑树的操作算法本身是很复杂的，就略过不看了。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/71637.html
