HashMap系列：2次方扩容

作者: 青叶小小 | 来源:发表于2021-01-25 10:20 被阅读0次

（一）HashMap系列：负载因子0.75
（二）HashMap系列：树化阀值8，退化阀值6
（三）HashMap系列：2次方扩容
 （四）HashMap系列：put元素（不看完将后悔一生！）

红黑树系列：
一、《算法—深入浅出》N叉树的介绍
 二、《算法—深入浅出》红黑树的旋转
 三、《算法—深入浅出》红黑树的插入
 四、《算法—深入浅出》红黑树的删除

一、前言

HashMap系列前两篇已经多次提到，HashMap 在元素达到负载因子阀值时，会自动扩容，HashMap 的初始化大小与扩容也是非常有讲究的，初始化大小的默认值不是随便定义的，扩容策略也是有考究的，今天我们就来聊聊：

初始化大小的默认值为何是 16；
扩容为何每次都是当前数组大小的 2 倍；

二、计算对象所在HashMap的下标

大家一般能想到的计算下标方式，应该都是从大学课本中学到的：

int index = K % Array.length;

含义很简单：对K取模，模数是数组的长度；

看起来没有问题，那有没有更快的计算方式呢？
HashMap源码就给了我们一种新的计算方式：（按位）与！

当我们有一个数组，长度为16，那么23这个数应该放在这个数组中的哪个下标位置上呢？

23 & (16 - 1) = ?

23:            0001 0111
16 - 1 = 15:   0000 1111
-------------------------
result:   0000 0111 (7)

&(与)： 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0；即：任何数 & 0 = 0

为什么 23 & (16 - 1) 而不是 23 & 16 呢？
因为数组的下标是从 0 开始！

16 是 2 的N次幂，16 - 1 = 15 其二进制为低位全是 1（16的二进制为 0001 0000，15的二进制为 0000 1111），因此，任何一个数与 15 做『与』操作，直接将高位置0，而低位则是遇1保留，与0则0，因此就能非常方便的获取实际的下标值。

不信的话，我们可以再来几个例子：

16 & (16 - 1) = ?                       22 & (16 - 1) = ?

16:            0001 0000                22:            0001 0110
16 - 1 = 15:   0000 1111                16 - 1 = 15:   0000 1111
----------------------------            -----------------------------
result:        0000 0000 (0)            result:        0000 0110 (6)

HashMap 源码中，默认的数组大小就是 16，那为何不能是其它数呢？
假设数组长度为 10：

2 & (10 - 1) = ?                       6 & (10 - 1) = ?

2:          0000 0010                  6:          0000 0110
10 - 1 = 9: 0000 1001                  10 - 1 = 9: 0000 1001
--------------------------             -------------------------
result:     0000 0000 (0)              result:     0000 0000 (0)

发现没？当数组长度为非 2 次幂时，虽然 key 不同，但是计算出来的下标都一样（0），非常容易出现 hash 冲突，而 2次幂则完美的解决这个冲突的问题。

三、当前数组大小的2倍扩容

在第二节中，我们了解到如何快速计算 hash数组的下标，以及 HashMap 源码中，默认初始的数组大小是 16 。本小中，我们将来看看，当新增元素达到数组的阀值时（数组大小 * 负载因子），HashMap 会开始扩容，扩容也是有讲究的，每次扩容都是当前数组大小的2倍。

例如，初始大小是16，当元素达到 12（16 * 0.75）时，会进行2倍扩容，大小变为 32（16 * 2）；下次扩容也是2倍变成64。每次扩容都保证数组的大小是 2的N次幂，道理就是第二节中阐述的。

每次扩容后，还需要重新计算 hash数组中每个元素的新的下标（因为分母，即数组大小改变了，hash下标肯定不对了嘛）。

我们来看个例子：

public class Main {

    public static void main(String[] args) {
        // 初始数组大小 16，随机放 6 个数
        int[] array = new int[16];
        for (int i = 0; i < 6; i ++) {
            int rand = (int) (Math.random() * 100);
            int idx = rand & 15;
            array[idx] = rand;
            System.out.println(rand + "在（16数组大小）的下标 = " + idx);
        }
        System.out.println(Arrays.toString(array));

        // 2倍扩容后，重新计算下标
        int[] newArray = new int[32];
        for (int i = 0; i < array.length; i ++) {
            if (array[i] == 0)
                continue;

            int idx = array[i] & 31;
            newArray[idx] = array[i];
            System.out.println(array[i] + "在（32数组大小）的下标 = " + idx);
        }
        System.out.println(Arrays.toString(newArray));
    }
}

重点一：注意标红的 19 在数组扩容后的下标变动
96在（16数组大小）的下标 = 0
4在（16数组大小）的下标 = 4
75在（16数组大小）的下标 = 11
12在（16数组大小）的下标 = 12
$\color{red}{19在（16数组大小）的下标 = 3}$
34在（16数组大小）的下标 = 2
[96, 0, 34, 19, 4, 0, 0, 0, 0, 0, 0, 75, 12, 0, 0, 0]

96在（32数组大小）的下标 = 0
34在（32数组大小）的下标 = 2
$\color{red}{19在（32数组大小）的下标 = 19}$
4在（32数组大小）的下标 = 4
75在（32数组大小）的下标 = 11
12在（32数组大小）的下标 = 12
[96, 0, 34, 0, 4, 0, 0, 0, 0, 0, 0, 75, 12, 0, 0, 0, 0, 0, 0, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

四、HashMap.resize 分析

HashMap 如果只是数组扩容2倍，再调整数组中每个元素的下标，那咱们也没必要分析了。我们别忘记，HashMap的数组结构：

数组 +（单链表 <--> 红黑树）

因此，扩容后，如果还有链表或者红黑树，那么，这些元素也需要判断是否需要调整（hash数组大小变了，下标也就可能改变），所以，一次扩容，涉及到三种情况的调整：

数组中的元素的 next 为 null，表明没有链表，也没有黑红树，则直接计算新的下标，放到新的数组中；
数组中的元素是红黑树，则进行拆分调整，可能还涉及到树的退化；
元素是链表，遍历调整；

4.1、数组的 rehash

final Node<K,V>[] resize() {
    ......
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) { // e = oldTab[j]
            oldTab[j] = null;          // 将原数组中的对象置为null
            if (e.next == null)        // 如果 next 为null，表明该节点没有链表，也不是红黑树
                newTab[e.hash & (newCap - 1)] = e; // 简单的放到新的下标中
        }
    }
}

4.2、红黑树的 rehash（建议大家先看：单链表的 rehash）

final Node<K,V>[] resize() {
    ......
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) { // e = oldTab[j]
            oldTab[j] = null;          // 将原数组中的对象置为null
            
            else if (e instanceof TreeNode) // 如果是红黑树
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        }
    }
}

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {             // bit = oldCap
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    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);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

红黑树的调整，大家可能会感到害怕、颤抖！如果，大家听取我的建议，先看了链表的 rehash，那么，再看红黑树的调整，将会觉得非常的简单！代码看起来较多，同样，我们将其拆为两部分（再次建议，一定要先看完链表的 rehash ，再看这里！！！！）：

4.2.1、树节点拆分至高、低位链表

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    
    // 与链表拆分相同，分为低位链表、高位链表
    // 虽然类型是 TreeNode，但在拆解时，只用到了 next 节点
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    
     // 记录低位列表、高位列表中元素的个数
    // 在树化与退化时，需要判断链表中的个数与8、6的关系
    int lc = 0, hc = 0;
    
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        
        // 高低位区分
        if ((e.hash & bit) == 0) {             // bit = oldCap
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    
    // 高低位链表的树化与退化
    .......
}

是不是非常的简单！但有一种极端情况，大家想的到么？
$\color{red}{当红黑树中的所有元素，都在低位链表中，那么？高位链表就是 null；或者，所有元素都在高位链表中，低位链表就是 null。}$

4.2.2、高低位链表的树化与退化

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    
    // 拆分为高、低位链表
    ......
    
    

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)            // 小于等于6，即树退化为单链表
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;                 // 否则树化
            if (hiHead != null)                  // else的情况：所有元素都在低位链表中，所以已经树化了！
                loHead.treeify(tab);
        }
    }
    ////////////////////////////////////////////// 高位操作：同上！
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

至于，如何树化与退化，这其实与红黑树的算法有关，大家可以看源码，也可以看我的红黑树系列，这里就不再展开了。

4.3、链表的 rehash

final Node<K,V>[] resize() {
    ......
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) { // e = oldTab[j]
            oldTab[j] = null;          // 将原数组中的对象置为null
            
            // 单个元素
            ...
            // 红黑树
            ...
            // 链表
            else {
                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) { // oldCap = oldTab.length;
                        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;
                }
            }
        }
    }
}

链表的拆分，代码较多，为了帮助大家能够快速的理解，我先给出一张逻辑图：

HashMap链接rehash .png

以及再将代码进行拆分，分为不同的维度来讲解，帮助大家理解：

4.3.1、变量

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

咋一看，有4个变量，但是，我们如果仔细想想，可以发现，其实是两个链表的首、尾索引（或者在C中叫指针更好理解）；这两个链表，分为低位链表（lo-link）和高位链表（hi-link）；
本来想和大家卖个关子，但想了想，还是先直接说出细节（低位链表、高位链表的作用）：

低位链表：原链表中的元素，如果 rehash 后，所对应到新扩容数组后的下标不变，则放入低位链表中；
高位链表：原链表中的元素，如果 rehash 后，所对应到新扩容数组后的下标发生改变，则放入高位链表中；

我们可以注意下 $\color{red}{【重点一：注意标红的 19 在数组扩容后的下标变动】}$ ，节点19，在数组 capacity = 16时，下标是3，而在数组 capacity = 32时，下标是19。

我们可以这么理解 $\color{red}{（重点二）}$ ：
节点 19 & 16 == 1，因此应该调整放入高位链表中，并且节点 19 新的下标 = 原下标 + 扩容前的数组大小，即 newIdx = oldIdx + oldCapacity ！

4.3.2、遍历链表

// 高、低位链表变量区
.....

// 链表遍历，从数组的第一个元素 e 开始
// e = oldTab[j]
do {
    next = e.next;
    .....
} while ((e = next) != null);

4.3.3、算法：高、低位节点区分（基于这个算法，可以衍生很多经典的算法）

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) { // 放入低位链表
        ....
    }
    else {                        // 放入高位链表
        ....
    }
} while ((e = next) != null);

什么？大家是不是看着很蒙？如果大家仔细看了第二小节中的：计算对象所在的 hash 下标，那么就容易想到（以 cap = 16 举例）：

23 & (16 - 1) = ?                        23 & 16 = ?

23:            0001 0111                 23:            0001 0111
16 - 1 = 15:   0000 1111                 16:            0001 0000
-----------------------------            -------------------------------
result:        0000 0111 (7)             result:        0001 0000 (16)

差异就在于：

快速获取下标，方法是 e.hash &（n-1）；
高低位的区分，方法是 e.hash & n ；
如果原来的元素，其键值大于原来的数组大小（capacity），那么，和原来的 capacity 与操作，一定不等于0；反之则为0。

大家可以看上面，我写扩容 Demo 时，打印输出有醒目的提醒： $\color{red}{【重点一：注意标红的 19 在数组扩容后的下标变动】}$

4.3.4、高低位链表加入添元素（高、低链表操作一样）

if ((e.hash & oldCap) == 0) {
    if (loTail == null)     // 如果低位链表尾索引为 null，表示链表为空
        loHead = e;         // 低位链表首索引 = e
    else
        loTail.next = e;    // 尾索引不为 null，则 尾索引.next = e
    loTail = e;             // 调整尾索引，指向链表中的最后一个元素
}
else {
    if (hiTail == null)     // 高位链表操作 等同 低位链表操作
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
}

4.3.5、高低位链表放入到新的数组中

大家可以看我上面醒目提示的：重点二；高位链表所属的位置

// 低位链表，仍旧放在原来的下标：j
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
// 高位链表，将会放到新的下标：j + oldCap
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

如果大家多想一步，会发现，后面的其它待调整元素，是不会和现在的 j 或者 j + oldCap 有冲突的！

好啦！HashMap 的扩容调整，内容很多，如果第一次看源码或者本文，需要好好的消化下！

HashMap系列：2次方扩容

一、前言

二、计算对象所在HashMap的下标

三、当前数组大小的2倍扩容

四、HashMap.resize 分析

4.1、数组的 rehash

4.2、红黑树的 rehash（建议大家先看：单链表的 rehash）

4.2.1、树节点拆分至高、低位链表

4.2.2、高低位链表的树化与退化

4.3、链表的 rehash

4.3.1、变量

4.3.2、遍历链表

4.3.3、算法：高、低位节点区分（基于这个算法，可以衍生很多经典的算法）

4.3.4、高低位链表加入添元素（高、低链表操作一样）

4.3.5、高低位链表放入到新的数组中

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

一些收藏

Android开发