JDK1.8中HashMap的resize优化

JDK1.8中对HashMap结构做了很多优化，包括引入了红黑树和扩容优化等。本文对扩容过程中涉及到的知识点进行分析。

确定哈希桶索引

不管是增加、删除还是查找键值对，定位到哈希桶数组的位置都是很关键的第一步。

HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。

源码

下面的代码来自JDK1.7和JDK1.8：

// 方法一
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 方法二
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

这里的Hash算法本质上就是三步：

取key的hashCode值
高位运算
取模运算

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。

但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

那么 h & (length-1) 有啥优势呢？

数组长度的技巧

其实 indexFor 这个方法非常巧妙，它通过 h & (table.length - 1) 来得到该对象的保存slot位置，而HashMap底层数组的长度总是2的n次方，这就是是HashMap在速度上的优化所在：

当length总是2的n次方时，h & (table.length - 1) 运算等价于对length取模，也就是 h % table.length ，但是 & 比 % 具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16) ，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低bit都参与到Hash的计算中，同时不会有太大的开销。

下面举例说明，其中n为table的长度： index_for_hash 这张图很好的说明了在JDK1.8中对 key 的数据如何计算出存储到桶的位置的。

扩容机制

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。

源码

下面是JDK1.7的resize源码，与1.8的区别并不大（但去掉了transfer方法）：

void resize(int newCapacity) {   // 传入新的容量
    Entry[] oldTable = table;    // 引用扩容前的Entry数组
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {  // 扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; // 修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        return;
    }

    Entry[] newTable = new Entry[newCapacity];  // 初始化一个新的Entry数组
    transfer(newTable);                         // 关键函数！！将数据转移到新的Entry数组里
    table = newTable;                           // HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);// 修改阈值，向下取整
}

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
    Entry[] src = table;                   // src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { // 遍历旧的Entry数组
        Entry<K,V> e = src[j];             // 取得旧Entry数组的每个元素
        if (e != null) { // 过滤掉空链表的slot
            src[j] = null;// 释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                e.next = newTable[i]; // 头结点插入，导致新链表顺序和原链表元素相反
                newTable[i] = e;      // 将元素放在slot数组上
                e = next;             // 访问下一个Entry链上的元素
            } while (e != null);
        }
    }
} 

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话），这一点和Jdk1.8有区别，下文详解。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

图文示例

因为默认容量都是2的幂次方，所以n-1后的二进制的每一位都是1： index计算

元素在重新计算hash之后，因为n变为之前的2倍，那么n-1的mask范围在高位多了1bit(红色)，因此新的index就会发生这样的变化： new_index

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值在新的n下的的计算索引规则中新增的那个bit是1还是0就好了，是0的话索引没变（0&1=0，index仍然由低几位bit决定），是1的话索引变成「原索引+oldCap」（因为新的n是2*oldCap，二进制长度增加了1位，计算index的n-1的二进制就是1，也就是增加了oldCap）。

这一点在JDK1.8的JavaDoc中也有相应的提示：

/**
 * 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()

下图为当cap从16扩充为32时触发resize后的前后对比示意图： resize_from_16_to_32 说明：

左图为cap=16时的存储，右图为cap=32时的存储
绿色为cap扩容后，用新的计算index规则变更bucket的节点
蓝色为cap扩容后，仍然不会改变bucket的节点
左图中15位置的slot的绿色的节点在cap扩容后分别映射到了新的slot，即31，且保持顺序不变
而右图slot为16和17处的绿色节点的值来自扩容前slot为0和1中的绿色节点
左图中slot为1的蓝色节点再cap扩容后重新建立了新的链表并赋值到slot为1的头结点这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增高位的1bit是0还是1可以认为是随机的，因此resize的过程，「均匀的」把之前的冲突的节点分散到新的bucket 了。这一块就是JDK1.8新增的优化点。

JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是从上图可以看出，JDK1.8不会倒置。具体可以参考源码。

源码分析

final Node<K,V>[] resize() {
    // 重置之前暂记录之前数组桶的信息及相关配置信息
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果之前 table 中有数据的话
    if (oldCap > 0) {
        // 如果超出了最大容量值，设置 threshold 最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 将之前的 table 大小扩大一倍作为新的数组桶的容量，当然不能超出最大值
        // 前提是之前 table 大小要大于默认值，不然数据量小没有扩容的必要直接使用默认值即可
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }

    else if (oldThr > 0) // 如果之前 table 中没有数据，将之前 table 的 threshold 作为新 table 的容量大小
        newCap = oldThr;
    else {               // 如果 oldCap 与 oldThr 之前都没有指定那么使用默认值创建，初始化创建 map 其实就是进入的这个分支
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 装载因子 * 默认容量大小作为新的 threshold
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的 threshold == 0 使用新的容量大小重新计算
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    }
    // 替换掉原先的 threshold 为新的值
    threshold = newThr;
    // 创建一个新的数组桶准备复制迁移数据
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 如果之前的 table 不为 null 开始迁移数据
    if (oldTab != null) {
        // 遍历之前的 table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 处理不为 null 的数据
            if ((e = oldTab[j]) != null) {
                // 将原 table 中的数据置为 null 便于断开其可能存在的引用链利于垃圾回收
                oldTab[j] = null;
                // 如果只有数组桶的一个数据，也就是槽位链表没有数据，这直接放入新的 table 槽位即可
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果节点是树节点 红黑树挡在单独章节分析 - TODO
                // 如果链表结点数据小于 6 会将红黑树退化为链表
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // 处理 table 中槽位存在链表的情况并且不是树的情况，将原先的单个链表分化为 2 个链表
                    // 通过这段代码就避免了添加数据需要再次 hash puVal() 的低效率问题
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 低位存储在 loHead 中
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else { // 否则放入 hiHead 链表中也就是 原索引槽位 + oldCap
                            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;
}

其中解释了为什么resize后新的链表不会改变原有链表中元素的顺序关系以及slot没有变化的元素和变化的元素为什么存在i和i+oldCap的位置。

免去了之前调用putVal()进行resize，并重新计算一次哈希：

public V put(K key, V value) {
    // onlyIfAbsent：false 表示如果存在则更新，不存在则插入
    return putVal(hash(key), key, value, false, true);
}

/**
 * 根据传入 key 的 hashCode 的无符号右移 16 位次方作为其 map 中的 hash 值
 * @param key
 * @return
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

避免扩容

如果线上的很多业务实例化之前可以知道Map的大小可以一次性实例化的时候设置好相应的cap参数，避免后续resize的时候对性能产生影响。

可以使用Guava的

References

本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.

HashMap's resize() in JDK1.8