源码分析HashMap的resize

九转成圣

发布于 2024-04-10 16:49:44

560

发布于 2024-04-10 16:49:44

文章被收录于专栏：csdncsdn

/**
 * 1.计算新容量
 * 2.计算新阈值
 * 3.根据新容量创建新数组,并将新数组赋值给table
 * 4.将老数组中的元素转移到新数组
 */
final HashMap.Node<K, V>[] resize() {
    HashMap.Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    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
    } 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"})
    // 创建新数组
    HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
    // 重新给table赋值
    table = newTab;
    // 将oldTab里面的元素赋值给tab
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            HashMap.Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                // 转移 类似于剪贴
                oldTab[j] = null;
                // hash桶中只有一个元素
                if (e.next == null)
                    // 相当于rehash
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    /**
                     * 拆成高低位2个树链表
                     * 若链表长度小于等于6则转为node链表
                     * 若链表长度>6则将树链表转为红黑是
                     */
                    ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // loHead 低位的头元素 loTail低位的为元素
                    HashMap.Node<K, V> loHead = null, loTail = null;
                    // hiHead高位的头元素 hiTail高位的尾元素
                    HashMap.Node<K, V> hiHead = null, hiTail = null;
                    // 
                    HashMap.Node<K, V> next;
                    // 将原链表拆成2个子链表
                    do {
                        // 为了在while条件中用
                        next = e.next;
                        // (e.hash & oldCap) == 0 计算高低位 
                        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;
                        // 将低位链表复制给新数组的j位置
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 将高位链表赋值给新数组的j+oldCap
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-10，如有侵权请联系 cloudcommunity@tencent.com 删除

resize