源码|jdk源码之HashMap分析(二)

2018-07-17

接上一篇博文，来吧剩下的部分写完。
总体来说，HashMap的实现内部有两个关键点，第一是当表内元素和hash桶数组的比例达到某个阈值时会触发扩容机制，否则表中的元素会越来越挤影响性能；
第二是保存hash冲突的链表如果过长，就重构为红黑树提升性能。

关于第二点，对于HashMap来说，达到O(1)的查询性能只是平均时间复杂度，这需要key的hash值对应的位置分布的足够均匀。

来设想一种极端情况，假设某个黑客故意构造一组特定的数据，这些数据的hash值正好一样。当插入hash表中时，它们的位置也一样。
那么，这些数据会全部被组织到该位置的链表中，hash表退化为链表，这时的查询的时间复杂度为O(N)，也是hash表查询时间复杂度的最坏情况。

不过HashMap在链表过长时会将其重构为红黑树，这样，其最坏的时间复杂度就会降低为O(logN)，这样使得hash表的适应场景更广。

1. resize扩容

扩容分两个步骤：

计算扩容之后的大小。
进行具体的扩容操作。

1.1. 计算扩容后大小

以下是第一个步骤的代码：

final Node<K,V>[] resize() {
    Node<K,V>[] 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桶数组已经初始化过。
1. 扩容后是会溢出，也即达到了2的30次方。
2. 扩容后不会溢出，这种情况扩容两倍。扩容后hash桶数组的大小依然是2的幂。
hash桶数组没有初始化过，但是指定了初始化大小。
hash桶数组没有初始化过，也没有指定初始化大小。

虽然逻辑很明确，但是代码写的看起来却很复杂。
其原因是HashMap内部记录的字段能表达的状态太多，每种情况都需要考虑周全。

第一阶段执行完毕后，HashMap内部的部分状态字段被更新。
最重要的是，newCap这个变量记录了扩容之后的大小。

1.2. 执行扩容操作

final Node<K,V>[] resize() {
    /* ... */
    // 分配一个新的hash桶数组，然后把旧的数据迁移过来
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order // 链表的情况
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> 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桶数组，在其中保存有节点时，分不同情况处理：
1. 只有一个节点的情况，直接将这个节点rehash到新的数组中。
2. 该节点代表一棵红黑树。调用红黑树的相关方法完成操作。
3. 该节点代表一个链表。将链表节点rehash到新的数组中。

先来看下红黑树的split函数：

final void split(HashMap<K,V> map, Node<K,V>[] 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一样，也是将红黑树拆分成两条子树。至于为什么是拆分为两条后面会说。
但是，如果拆分出来的子树太小了，就会重新将其重构回链表。

顺便说一句，由于删除操作的逻辑没有什么新东西之前就没有分析。我也没有在其中找到删除节点时，如果红黑树太小会将其重构回链表的操作。

1.3. rehash优化

对于链表的rehash操作，乍一看，这个逻辑还有些看不懂，从代码上来看是这样的逻辑，对于hash桶数组中第j个位置上的一个链表，进行遍历，根据条件分成两条：

1	(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为保留。
严谨的数学表达我实在懒得写了，总之通过分析不难得到这个结论：
1. 如果数B的第3位（从低位从0开始数）为0，那么B % N = B % 2N。
2. 如果数B的第3位（从低位从0开始数）为1，那么B % N结果的第3位给置1等于B % 2N，也即B % N + N = B % 2N

有了以上结论，对照上面的代码，也就不难理解这段rehash代码的思路了：

1	(e.hash & oldCap) == 0

这句话是判断hash值的对应位是否为0，并分成两条不同的链表。

如果为0，则rehash后的位置不变。
如果不为0，则为以前的位置加上旧表的大小。

最后，我比较疑惑的一点是，花了这么大力气去优化，为什么能得到性能或内存上的提升？
我们分析下优化前后的时间复杂度：

如果不优化，则是遍历旧的hash桶数组，然后遍历每一个链表，并且把链表的每个节点rehash到新的hash桶数组上去。将链表插入到新的数组只需O(1)的时间，也即整个操作的时间复杂度为O(N)，N为hash表中元素的个数。
如果优化，则是遍历旧的hash桶数组，然后同样需要遍历每一个链表，把每一个节点分开到两条不同的子链表上去。。。时间复杂度仍然是O(N)…

看起来两种方案都需要遍历所有的链表节点，难道仅仅是减小一点时间复杂度的常数吗？

1.4. treeifyBin操作

之前说过当链表长度过大时会将其重构为红黑树，下面来看具体的代码。

// 8. 把链表转换成二叉树
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> 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<K,V> hd = null, tl = null;
        // 遍历单链表，然后把给它们一个个的分配TreeNode节点
        // 看下面这代码，这个TreeNode，记得拥有next和prev字段，看下面的代码是把它们串成双链表
        do {
            TreeNode<K,V> 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方法将其组织成红黑树。至于这个方法。。。各种旋转，红黑树的操作算法本身是很复杂的，就略过不看了。