JDK1.8中HashMap的resize优化

HashMap's resize() in JDK1.8

Posted by S.L on November 11, 2019

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);
}

References