MENU

Java 集合类 - 扩容机制(二)HashMap

June 18, 2018 • Code

前言:通过源码分析 HashMap 的扩容机制。

HashMap 扩容源码

  • HashMap 中扩容相关方法为 resize(),该方法同时也负责内置数组初始化。

  • 不同于 ArrayList,HashMap 类在 Java7 与 Java8 中存在诸多不同,在扩容机制上也做了改动。重点理解 Java8 中扩容方法。

Java7 与 Java8 内部数组结构如下图。

Java8 版本

方法源码

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
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) {
        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"})
        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;
                    }
                }
            }
        }
    }
    return newTab;
}

分析

扩容主要分为两部分:

  1. 计算合理的新容量及阀值

  2. 复制已有元素到新数组

第一部分:计算合理的新容量及阀值
  • 流程图:

  • 源码注释分析
final Node<K,V>[] resize() {

    /* ============ 第一部分:计算合理的新容量及阀值 ============ */
    Node<K,V>[] oldTab = table;
    // 旧表的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;

    // 旧阀值
    int oldThr = threshold;
    int newCap, newThr = 0;

    // 如果旧容量大于 0,并且大于最大容量 1 << 30(大概 10 亿),则将阀值上调为最大值,返回
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }

        // 新容量 = 旧 * 2,并验证是否小于最大值同时旧容量大于 16 (默认值)
        // 大于 16 的设计主要是因为 newThr 在这里是直接采用 * 2 的操作,
        // 方便,但是不够准确,这在容量较大的时候是可以接受的,但是如果
        // 容量本身就不大,计算就必须精确了,即 float ft = (float)newCap * loadFactor
        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
        // 有这一步是因为 HashMap 中没有一个字段是表示容量的,只有表示阀值的,而如果你传入了初始容量,
        // 实际上就是设置了阀值,所以这种情况下 table 还为 null,自然 oldCap 小于 0,而 oldThr 不为0
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 如果旧容量与旧阀值均为 0,说明没有传入容量参数,同时是 table 还没初始化,用默认大小 16
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 观察上面的代码流程可知,newThr 为 0,
        // 有两种情况:
        // 1. 传入阀值初始化的时候,所以要修正阀值
        // 2. 将容量扩为原来 2 倍后,新容量大于最大容量或
        //      原来的容量小于 16,新阀值还没有更新
        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;

    ...
    ...
}

初始化 HashMap 传入初始容量:

复制已有元素到新数组
  • 流程图

  • 方法注释分析
final Node<K,V>[] resize() {

    ...
    ...

    /* ============ 第二部分:复制操作 ============ */
    // 如果旧表中有值,复制操作,注意在这里 Java7 与 Java8 的不同
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 将旧表中对应节点置空,帮助 GC
                oldTab[j] = null;
                /**
                 * 链中只有一个元素,"重哈希"算出在新表中位置,存入
                 * 这里的亮点在于"重哈希",这里的"重哈希"对比 Java7 中是一个比较巧妙的设计
                 * 这里没有采用 Java7 中繁琐的 Hash,而是由设置的容量大小必须为 2 的幂来简单地得到
                 * 当前元素在新表中应在的位置。
                 *
                 * 假设原容量为 16,当前元素在第 5 个条链中,取 hash 最后 4 位
                 * 那么在新容量 32中,当前元素可能的位置有 2 个,原第 5 条链或 (5 + 原容量)条链中
                 * 即取 hash 最后 5 位,少掩一位,由于多出来的 1 位 0 或 1 的可能性相等,所以相等于对
                 * 哈希表做了一次均衡
                 */
                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;
                    /**
                     * 在这循环里主要干一件事,就是将每条链分成两条链,lo 和 hi
                     * lo 表示重新计算后位置不变,hi 则是放在对应 newTab[j + oldCap]
                     * 同时注意,分成两条链后节点顺序不会逆序
                     */
                    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;
                    }
                }
            }
        }
    }
    return newTab;
}

Java7 版本

  • resize 方法
/**
 * Rehashes the contents of this map into a new array with a
 * larger capacity.  This method is called automatically when the
 * number of keys in this map reaches its threshold.
 *
 * If current capacity is MAXIMUM_CAPACITY, this method does not
 * resize the map, but sets threshold to Integer.MAX_VALUE.
 * This has the effect of preventing future calls.
 *
 * @param newCapacity the new capacity, MUST be a power of two;
 *        must be greater than current capacity unless current
 *        capacity is MAXIMUM_CAPACITY (in which case value
 *        is irrelevant).
 */
void resize(int newCapacity) {
    //  传入的 new Capacity 值为 2 * table.length
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    /* ------------ 第一部分:容量及阀值判断修正 ------------ */
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    /* ------------ 第二部分:复制操作 ------------ */
    Entry[] newTable = new Entry[newCapacity];
    // transfer 方法将元素复制到新数组
    // 其中 initHashSeedAsNeeded 方法用来初始化 hashSeed,hashSeed 用来计算 hash 值
    // 返回 true 代表需要重新计算哈希(hashSeed 值已改变)
    transfer(newTable, initHashSeedAsNeeded(newCapacity));

    // 将新的数组怀阀值赋给 table 及 threshold
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
  • transfer 方法
/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            // 重新计算 hash 值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }

            // 计算索引位置
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

小结

通过源码学习 Java 中 HashMap 扩容机制。从上面的对比可看出,Java8 引入红黑树后代码复杂了许多,主要目的是为了改善 HashMap 在大量数据哈希冲突时的性能表现。

Last Modified: July 12, 2018
Archives QR Code
QR Code for this page
Tipping QR Code