【大厂面试题系列】：JDK7、8 HashMap扩容原理源码讲解！！！

前言

JDK7 和JDK8 的扩容方法都基于 resize()方法，但底层实现却有所不同

JDK7 HashMap扩容

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length); //新的容量为旧数组容量的两倍
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

//扩容方法
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //如果老的数组容量大于最大值，即2的30次方，则将其容量设置为Integer.MAX_VALUE返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    //根据新的容量创建Entry数组
    Entry[] newTable = new Entry[newCapacity];
    
    //将就数组的值rehash到新数组中去
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    //更新阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}


void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    
    //for循环遍历数组
    for (Entry<K,V> e : table) {
        //遍历链表
        while(null != e) {
            Entry<K,V> next = e.next;
            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;
        }
    }
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

全部 rehash（重新计算索引位置） 消耗大，采用头插法在多线程环境下可能出现死循环，jdk8已经优化

总结

• 新数组容量为旧数组容量的两倍
• 根据新的容量创建数组，然后调用transfer方法遍历Entry数组和遍历Entry数组每个元素的遍历，对链表上的每个元素重新计算索引值，然后放到新数组中去
• rehash完成之后，将原数组引用指向新数组，然后更新阈值

JDK8 HashMap扩容

//扩容方法
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) {
        //如果老的数组容量大于最大值，即2的30次方，则将其容量设置为Integer.MAX_VALUE返回
        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，但是阈值大于0时，那么新容量就设置为阈值
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        //如果都为0，那么容量设置为默认值16，阈值为容量 * 加载因子 == 16 * 0.75
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //若新的阈值为0，那么用新的容量 * 加载因子重新计算
    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;
    //如果旧数组不为null
    if (oldTab != null) {
        //遍历旧的数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果当前元素不为null，用中间变量把保存当前元素
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果只有一个元素
                if (e.next == null)
                    //重新做hash散列并赋值
                    newTab[e.hash & (newCap - 1)] = e;
                //如果是红黑树的话，那么就要把新的hash表也变成红黑树结构
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    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;
}

loHead，下标不变情况下的链表头

loTail，下标不变情况下的链表尾

hiHead，下标改变情况下的链表头

hiTail，下标改变情况下的链表尾

if((e.hash & oldCap) == 0)，就是代表散列下标不变的情况，这种情况下代码只使用了loHead和loTail两个参数，由他们组成了一个链表，否则将使用hiHead和hiTail参数。

JDK8 和 JDK7 在rehash上是有所不同的，JDK7是对全部元素 rehash，而JDK8对此进行优化，根据 if((e.hash & oldCap) == 0) 判断是否需要移动元素

举例：

18 % 16=2     18 % 32=18
34 % 16=2     34 % 32=2
50 % 16=2     50 % 32=18

区分哪些元素应该在原来的位置，那些在新的位置。

总结

• 如果旧的数组容量不能为空且老的数组容量大于最大值，即2的30次方，则将其容量设置为Integer.MAX_VALUE返回，否则的话将新容量设为原来的两倍，对阈值也进行扩容
• 如果旧数组容量为0，但是阈值大于0时，那么新容量就设置为阈值
• 如果都为0，那么容量设置为默认值16，阈值为容量 * 加载因子 == 16 * 0.75
• 把就数组元素放到新数组中去
  • 如果旧数组不为null，那么遍历旧数组，如果旧数组每个元素即链表头节点不为null，且只有一个元素的话，那么将该元素重新散列到新数组中去
  • 如果是红黑树结构的话，那么在新的数组中也要是红黑树结构
  • 如果都不是的话，则需要通过if ((e.hash & oldCap) == 0)判断当前节点是否需要改变位置，对于不需要改变的节点初始化loHead为头节点，loTail为尾节点通过next往后移，而需要改变得元素初始化hiHead为头节点，hiTail为尾节点通过next往后移
  • 最后，对于loHead在新数组原索引处放置，对于hiHead，则在当前位置 + olgTab(旧数组容量)放置

觉得不错的小伙伴可以一键三连哦！，感谢支持！！！

更多面试题请移步 大厂面试题专栏