八、JDK1.8中HashMap扩容机制

大家好，又见面了，我是你们的朋友全栈君。

导读

前面文章一、深入理解-Java集合初篇中我们对Java的集合体系进行一个简单的分析介绍，上两篇文章二、Jdk1.7和1.8中HashMap数据结构及源码分析、三、JDK1.7和1.8HashMap数据结构及源码分析-续中我们分别对JDK1.7和JDK1.8中HashMap的数据结构、主要声明变量、构造函数、HashMap的put操作方法做了深入的讲解和源码分析。四、深入理解Java中的HashMap「网易面试快答」文章中主要针对面试中常见的面试问题进行简单解答。五、深入理解JDK1.7中HashMap哈希冲突解决方案和六、深入理解JDK1.8中HashMap哈希冲突解决方案中对HashMap中哈希冲突及减少哈希冲突的解决方案做详细的介绍，并通过源码加深大家的理解。七、JDK1.7中HashMap扩容机制中介绍了JDK1.7中HashMap的扩容机制及扩容过程中可能出现的死锁及数据丢失问题。 本篇文章我们将要介绍JDK1.8中HashMap的扩容机制，并通过一个实例来展示链表的哈希扩容。

如果大家在面试中针对Java集合或者Java中的HashMap大家还有什么疑问或者其他问题，可以评论区告诉我。

简单介绍

JDK1.7—》哈希表，链表

JDK1.8—》哈希表，链表，红黑树— JDK1.8之后，当链表长度超过8使用红黑树。

代码语言：javascript复制

非线程安全

0.75的负载因子，扩容必须为原来的两倍。

默认大小为16，传入的初始大小必须为2的幂次方的值，如果不为也会变为2的幂次方的值。

根据HashCode存储数据。

HashMap扩容机制-为什么负载因子默认为0.75f？

负载因子0.75 如果容量大大0.75则扩容为原来的两倍。扩容因此 0.75 空间利用率和时间效率在0.75的时候达到了平衡。在统计学上0.693是最佳的选择。然后可能更想着有空间利用率，而且在。Net语言中 hashmap的负载因子是0.7.

JDK1.8-优化扩容机制

如果是红黑树，则去红黑树中移动，如果是链表呢

JDK1.8优化方式：

二进制位运算展示(64为，高位0，低位是值)

Hash 101010100 0111 1100 -hash值 length 000000000 0001 0000 -height16 -初始化长度

hashkey & length—–注意与插入数组时候不同。插入数据时候&的是数组下标，这里&的是数组长度。 结果是16—-hi高位指针 hiHead与hiTail—》

结果是0—-lo低位指针 loHeah与loTail—》

把低位的指针指向原来数组的索引位置把高位的指针指向原来的数组的索引位置原来的长度的位置例如原来 key 在数组中的索引位置是2，默认长度是16. 那么把低位指针指向的数据移动到数组中下标为2的位置，把高位指针指向的数据指向 2 16的数组下标中的位置。

首先总结一下JDK1.8的HashMap都在什么时候触发resize()方法，根据阅读源码总结了三个时机触发扩容，这里只做介绍，后面根据源码详细分析 HashMap是由数组链表红黑树构成的，数组就称之为桶了

①众所周知当HashMap的使用的桶数达到总桶数*加载因子的时候会触发扩容； ②当某个桶中的链表长度达到8进行链表扭转为红黑树的时候，会检查总桶数是否小于64，如果总桶数小于64也会进行扩容； ③当new完HashMap之后，第一次往HashMap进行put操作的时候，首先会进行扩容。原理会在下面根据源码分析，这里先做个例子并思考一下原因，下面分析完自然懂得原因。

在jdk1.8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全

多线程在put元素时

代码解析：

代码语言：javascript复制

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) { 
   
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /** * tab = table 值为当前哈希表的值 * n = tab.length 值为当前哈希表长度 * 如果当前哈希表为空 或者 当前哈希表长度为0 * 则tab = resize * n = resize.length; */
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;<br>　　　　　　//没有hash碰撞时，后续值直接覆盖
    /** * i = (n - 1) & hash 得到的值为当前hash应该插入的数组位置 * p = tab[i]; 把p 指向哈希表下标为i的位置 * 如果该位置为空 ，代表该哈希位置还未插入过数据， * 则把当前要插入的数据生成新Node直接插入 */
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else { 
   //如果哈希表下标为i的的位置有数据则执行以下操作
        Node<K,V> e; K k;
        /** * 判断一个两个node是否相同，有两个指标 1.两个node的hash值相同；2.两个node的key相同 * 注意：当前p指向哈希表中下标为i的位置的首位 * 如果首位的哈希值与要新插入的哈希值相同 并且 * k = p.key * (k == key || (key != null && key.equeals(k)； * 其实意思就是如果要新插入的node的与当前p指向的位置为同一个元素 * 则 e = p; */
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        /** * 注意：当前p指向哈希表中下标为i的位置的首位 * 如果当前p指向的位置的类型已经是红黑树 * 则把新node数据直接插入红黑树中 */
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        /** * 注意：当前p指向哈希表中下标为i的位置的首位 * 否则当前p指向的哈希表中下标为i的位置是一个线性链表 */
        else { 
   
            for (int binCount = 0; ;   binCount) { 
   
                /** * 注意：当前p指向哈希表中下标为i的位置的首位 * 循环执行 e = p.next ； 直到 e == null * 其实就是循环访问线性链表直到线性链表结尾 * 把要插入的值生成新Node插入线性链表结尾 */
                if ((e = p.next) == null) { 
   
                    //把要插入的值生成新Node插入线性链表结尾
                    p.next = newNode(hash, key, value, null);
                    //如果操作的长度大于等于（8 - 1） 则转红黑树 
                    //TREEIFY_THRESHOLD为转红黑树的门槛因子
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);//把当前线性链表转为红黑树
                    break;//插入新数据后跳出for循环
                }
                /** * 循环访问线性链表的过程中对每一个node元素与要插入的元素进行判断 * 判断一个两个node是否相同，有两个指标 * 1.两个node的hash值相同；2.两个node的key相同 * 如果 为同一个元素则跳出for循环 */
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //如果未到达线性链表末尾且当前线性链表中不存在
                //于要插入的元素相同的node则继续for循环
                p = e;
            }
        }
        if (e != null) { 
    // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
      modCount;//增加修改的次数
    if (  size > threshold)//判断当前哈希表长度是否超过负载门槛
        resize();//哈希表扩容
    afterNodeInsertion(evict);
    return null;
}

每个put操作都有可能会触发哈希表扩容

代码语言：javascript复制

/** * JDK1.8---哈希表扩容 * @return */
final Node<K,V>[] resize() { 
   
    Node<K,V>[] oldTab = table;
    /** * 获取原哈希表容量 如果哈希表为空则容量为0 ，否则为原哈希表长度 */
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    /** * 获取原哈希表扩容门槛 */
    int oldThr = threshold;
    /** * 初始化新容量和新扩容门槛为0 */
    int newCap, newThr = 0;
    /** //如果原容量大于 0 ---这个if语句中计算进行扩容后的容量及新的负载门槛 */
    if (oldCap > 0) { 
   
            //判断原容量是否大于等于HashMap允许的容量最大值 2的30次幂
            if (oldCap >= MAXIMUM_CAPACITY) { 
   
                //如果原容量已经大于等于了允许的最大容量，
                // 则把当前HashMap的扩容门槛设置为Integer允许的最大值
                    threshold = Integer.MAX_VALUE;
                    return oldTab;//不再扩容直接返回
                }
            /** * newCap = oldCap << 1 ; 类似 newCap = oldCap * 2 移位操作更加高效 * 表示把原容量的二进制位向左移动一位， * 扩大为原来的2倍，同样还是2的n次幂 * 如果新的数组容量小于HashMap允许的容量最大值 2的30次幂 * 并且 原数组容量小于默认的初始化数组容量 2的4次幂 =16 */
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                             oldCap >= DEFAULT_INITIAL_CAPACITY)
            /** * //新的扩容门槛为原来的扩容门槛的2倍，同样二进制左移操作 //类似 newThr = oldThr * 2 移位操作更加高效 */
                newThr = oldThr << 1; // double threshold
        }
    /** * 如果 原数组容量小于等于零 * 并且 原负载门槛大于0 则 * 新数组容量为原负载门槛大小 */
    else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
    /** * 这个elese语句 初始化默认容量和默认负载门槛 * 如果原数组容量小于等于0 * 并且原负载门槛也小于等于0 * 则 * 新 数组容量为 默认HashMap设置的默认初始化容量 1《4 = 2的4次幂 = 16 * 新 负载门槛为 默认负载因子（0.75f） * 16; */
    else { 
                  // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    /** * 如果新负载门槛为 0 则开始使用新的 数组容量进行计算 */
    if (newThr == 0) { 
   
           // 新的数组容量 * 负载因子
            float ft = (float)newCap * loadFactor;
        /** * 如果新数组容量 小于 HashMap允许的最大容量(2的30次幂) * 并且 新计算的负载门槛 小于 HashMap允许的最大容量(2的30次幂) * 则新的 负载门槛为 计算后的值 的最大整型 -直接截取 * 否则 新的负载门槛为Integer.MAX_VALUE */
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                              (int)ft : Integer.MAX_VALUE);
        }
    //设置全局负载门槛为计算后的新的负载门槛
    threshold = newThr;
    /** * 根据新的数组容量创建新的哈希桶 赋值给newTab */
    @SuppressWarnings({ 
   "rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    /** * 把新创建的哈希桶赋值给全局table; */
    table = newTab;
    /** * 现在开始真正的扩容 */
    if (oldTab != null) { 
   //如果老的哈希表不为空则执行以下语句
           //for 循环，循环老的容量次
            for (int j = 0; j < oldCap;   j) { 
   
                    Node<K,V> e;
                /** * //从哈希数组的第一个下标（0）开始开始递增 * 注释： * e = oldTab[0] ; * e = oldTab[1] ; 循环访问每次哈希数组下标的内容 * e = oldTab[j]; * 如果 e != null 则开始访问数组中的内容 */
                if ((e = oldTab[j]) != null) { 
   
                            把原数组中下标为j的位置置空
                            oldTab[j] = null;
                            //e.next == null 则代表线性链表只有一个元素e
                            if (e.next == null)
                                /** * //根据e 的哈希值和 （新数组容量 -1）相 * 与得到 e该存放到新数组中的下标 * 然后把e放入对应新数组的下标中。 */
                                newTab[e.hash & (newCap - 1)] = e;
                            else if (e instanceof TreeNode)
                                /** * //如果当前e的类型已经改变为红黑树 * 则对红黑树进行分割 ？ */
                                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                            else { 
    // preserve order
                                /** * 进入这个else循环代表当前数组下标中存放的元素还是线性链表 */
                                    Node<K,V> loHead = null, loTail = null;//定义两个指针，分别指向低位头部和低位尾部
                                    Node<K,V> hiHead = null, hiTail = null;//定义两个指针，分别指向高位头部和高位尾部
                                    Node<K,V> next;
                                /** * do-while循环中针对数组下标为j的 * 线性链表进行循环查询，直到线性链表结束 * 并根据每个Node的hash值与原数组容量相与得到新的值。 * 与原数组容量相与后的值只会为0 或 原数组容量。 * 根据得到的这两个值 进行判断 * 如果 值为 0 * 则把他们放到 loHead和loTail指向的新的线性链表当中 * --尾部插入 * 如果 值为 原数组容量 * 则把他们放到 hiHead和hiTail指向的新的线性链表当中 * --尾部插入 */
                                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);
                                /** * 原线性链表结束 * 如果新的loTail指向的线性链表不为空， * 则把它的最后结尾值的指针指向null值 * 并把loHeah与loTail指向的新的链表放到新数组 * 下标为j的位置上。 * 如果新的hiTail指向的线性链表不为空， * 则把它的最后结尾值的指针指向null值 * 并把hiHeah与hiTail指向的新的链表放到新数 * 组下标为 （j   oldCap） 的位置上。 */
                                if (loTail != null) { 
   
                                            loTail.next = null;
                                            newTab[j] = loHead;
                                        }
                                    if (hiTail != null) { 
   
                                            hiTail.next = null;
                                            newTab[j   oldCap] = hiHead;
                                        }
                                }
                        }
                }
        }
    return newTab;
}

哈希扩容总结：

注意扩容前桶中的结点分为两种，一种是依旧在之前那个桶对应的下标的桶中，另一种是之前所在的桶的下标 oldCap ，分开的条件是该结点的K的hash值与扩容之前的总桶数n做了一个&运算（以前做映射的时候的公式为hash&（n-1）n为总桶数注意两个公式区别），为什么要使用这个条件分为两个链表，主要是判断出扩容之后哪些结点依旧在之前那个桶对应的下标的桶中，哪些结点在之前所在的桶的下标 oldCap的桶中原理如下图：

为什么经过rehash之后，元素的位置要么是在原位置，要么是在原位置加原数组长度的位置？

要搞明白这个问题首先要清楚 HashMap的数组长度恒定为2的n次方，也就是说只会为16，32，64，128这种数。源码中有限制，也就是说即使你创建HashMap的时候是写的 Map<String,String> hashMap = new HashMap<>(13); 最后数组长度也会变成16，而不是你的13. 会取与你传入的数最近的一个2的n次方的数。那么明确这一点有什么用呢？HashMap中运算数组的位置使用的是leng-1，那么就是对于初始长度为16的数组，扩容之后为32，对应的leng-1就是15，31，他们所对应的二进制为