JDK8的HashMap扩容原理

HashMap扩容代码主要可以分为entry数组扩容以及历史元素重新rehsh转移到新扩容的entry数组中

第一步entry数组扩容

final Node<K,V>[] resize() {
    //获取旧entry数组
    Node<K,V>[] oldTab = table;
    //拿到旧entry数组的大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //拿到旧entry数组扩容的临界值（数组大小*加载因子）
    int oldThr = threshold;
    //定义新entry数组的大小和扩容临界值；
    int newCap, newThr = 0;
    //entry数组中已经存在元素
    if (oldCap > 0) {
        //如果旧entry数组容量超出最大值，则不进行扩容处理，直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新entry数组库容至旧entry数组的两倍
        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;
    //如果旧entry数组也为空，说明需要进行数组初始化
    else {               
        //数组默认初始化大小16
        newCap = DEFAULT_INITIAL_CAPACITY;
        //DEFAULT_LOAD_FACTOR：加载因子默认大小为0.75
        //所以newThr = 0.75*16=12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    threshold = newThr;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
}

第二步，把历史元素重新rehash转移到新扩容的entry数组中

//循环遍历旧entry数组
for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        //拿到当前遍历到的entry
        oldTab[j] = null;
        //如果这个entry没下一个节点，没有形成链状（该位置没有hash冲突）
        //则直接把该entry重新rehash分配到新的entry数组中，重新rehash分配到的位置可能是j或者j+oldCap
        if (e.next == null)
            newTab[e.hash & (newCap - 1)] = e;
        //处理entry是树形结构的情况
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        // 说明这个entry存在下一个节点，需要对这个entry（实际是个链表）进行拆解处理；
        else {
            //此处定义两组entry，一组entry分配到新entry数组中的j位置(loHead)
            //另一组entry分配到新entry数组的j+oldCap的位置(hiHead)
            //因为entry形成链状后，使用的是尾插法进行插入；
            //所以loTail、hiTail是为了维护记录各自entry链表中的最后一个节点，以便进行插入；
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do {
                next = e.next;
                //将旧entry的链表拆分成两类，拆分维度(e.hash & oldCap) == 0
                if ((e.hash & oldCap) == 0) {
                  //尾插法，使用loTail跟踪链表的最后一个节点
                    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);
            //entry链表拆分完毕，将其放入新entry数组的位置中
            if (loTail != null) {
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) {
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}

要点总结

1. 为什么链表形状的entry进行拆分之后，一部分是放入到新entry数组的j位置，一部分放入的是新entry数组的 j+ oldCap位置（为什么扩容都是原来的两倍）

• entry链表拆分维度是根据(e.hash & oldCap) == 0来拆分的，e.hash & oldCap = 1则放入新entry数组的j + oldCap位置；
• 由于oldCap的大小都是2的幂次方以及新entry数组的大小是oldCap*2；所以二进制表示中如果oldCap是10000（16）那么新entry数组的大小newCap就是100000（32）
• 所以e.hash & oldCap = 1 <=>（e.hash & 10000）=1 满足的话，说明e.hash的二进制表示中第5位必定是1
• Map获取元素的get方法中，从entry数组中定位下标时用的是tab[(n - 1) & hash]，n代表的是entry数组大小；
• 在未扩容前n=16，(n - 1) & hash <=> 1111 & e.hash；扩容后n=32，(n - 1) & hash <=> 11111 & e.hash；在上述推导得出如果e.hash & oldCap = 1，那么说明在未扩容旧数组大小的二进制表示中为1的那个位置，e.hash也必定为1。所以11111 & e.hash <=> oldCap + (1111 & e.hash)，所以e.hash & oldCap = 1则放入新entry数组的 j+ oldCap位置！