HashMap扩容机制解析

全栈开发日记

发布于 2022-05-13 14:42:48

2230

发布于 2022-05-13 14:42:48

文章被收录于专栏：全栈开发日记

继HashMap初始化和第一次put()元素后，来研究一下探讨它的扩容机制。

通过查看Java JDK1.8putVal()源码可看到，有两种情况可能会触发扩容。

扩容时机

第一种情况：当HashMap第一次调用put方法时。

第二种情况：当存储在HashMap中元素的实际长度大于扩容临界值时。

什么是存储在HashMap中元素的实际长度？实际以键值对形式存储在HashMap中的Node，而不是HashMap中底层数组被使用的长度，两者完全不相同。存储在HashMap的键值对是以链表或红黑树存在的，就如同在数组上挂桶，数组的每一个索引上都可能存储着多个键值对。

什么是扩容临界值？HashMap中扩容临界值是通过变量threshold表示，它是通过当前底层数组长度*加载因子得到的。加载因子在上一篇中已经介绍过了，这里就不多说了。

扩容逻辑

如下进入resize()方法。由于方法比较长，所以这里分段解析。

// 底层数组
Node<K,V>[] oldTab = table;
// 当前底层数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 当前扩容临界值
int oldThr = threshold;
int newCap, newThr = 0;

这里显示判断了该数组是否是空，如果是空的说明这是这是HashMap第一次扩容。threshold是扩容临界值，每次扩容之后都要更新扩容临界值。

// 底层数组如果不为空 走这里
if (oldCap > 0) {
    // 判断底层数组是否已经扩容到了最大值
    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
}
// 如果底层数组为空，但是扩容临界值不为0，走这里
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);
}
threshold = newThr;

以上代码用于设置新的扩容临界值。

@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) {
                        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扩容就好比你原来用来装水的桶装满了，需要换一个更大的桶继续装水，你总不能把原来的小桶直接放到大桶中（当然这种构想应该也可以实现），所以以上代码作用就是将原来桶里的水换到大桶中。

JDK1.8和JDK1.8之前的resize()方法不同，我这里用的是JDK1.8，内容比1.8之前逻辑多了很多，毕竟加入了红黑树。

至此HashMap的扩容机制解析完毕，有兴趣的各位可以使用下面代码打断点进行debug查看扩容流程。

HashMap map = new HashMap();
for (int i=1; i < 14; i++) {
    if (i != 13) {
        map.put(i, i);
    }else {
        map.put(i, i); // 这里打断点
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-24，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap