HashMap 在 JDK1.8 中的扩容流程（源码分析）

扩容发生的条件

• 当 HashMap 中键值对 key-value 个数大于阀值的时候（注意不是什么桶或数组的占用情况）
• HashMap 为空或者数组长度为 0
• 升级成红黑树时，数组长度小于64，会进行一次扩容代替升级

//在put时会执行putVal()方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ... ...
	//数组为空，或者数组长度为0会扩容
	if ((tab = table) == null || (n = tab.length) == 0)
	    n = (tab = resize()).length;
	... ...
	//键值对的个数大于阀值会扩容   
	if (++size > threshold)
	    resize();
	... ...
}
/**
 * The number of key-value mappings contained in this map.
 */
transient int size;
           

//升级红黑树时
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //数组长度小于64，会进行一次扩容代替升级
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if() {
    //链表升级红黑树
    }
}
           

扩容流程

1. 1.8版本中扩容时如果 Node 桶的数据结构是链表会生成 low 和 high 两条链表，是红黑树则生成 low 和 high 两颗红黑树
2. 依靠 (hash & oldCap) == 0 判断 Node 中的每个结点归属于 low 还是 high。
3. 把 low 插入到 新数组中 当前数组下标的位置，把 high 链表插入到 新数组中 [当前数组下标 + 旧数组长度] 的位置
4. - HashMap 在扩容时为什么能通过位运算 (e.hash & oldCap) 得到新数组下标

链表与红黑树的扩容情况

链表

 如果是链表则生成 low 和 high 两条链表，再插入到新数组的相应下标的位置。low 对应新数组中的下标为 [当前数组下标]，high 对应新数组中的下标为 [当前数组下标 + 旧数组长度]

//把原链表中的元素插入到 low 和 high 链表中，依靠 (e.hash & oldCap) == 0 判断
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;
}

//把 low 的头结点插入到当前数组下标的位置，
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
//把 high 的头结点插入  新数组中 [当前数组下标 + 旧数组长度] 的位置
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}
           

红黑树

 如果是红黑树生成的 low，high的插入，如果生成的 low，high 树中元素个数小于等于6退化成链表再插入到新数组的相应下标的位置。low 对应新数组中的下标为 [当前数组下标]，high 对应新数组中的下标为 [当前数组下标 + 旧数组长度]

if (loHead != null) {
	//如果生成的红黑树元素个数小于等于6退化
    if (lc <= UNTREEIFY_THRESHOLD)
        tab[index] = loHead.untreeify(map);
    else {
    	//插入的下标为 [当前数组下标 + 旧数组长度]
        tab[index] = loHead;
        if (hiHead != null) // (else is already treeified)
            loHead.treeify(tab);
    }
}
if (hiHead != null) {
	//如果生成的红黑树元素个数小于等于6退化
    if (hc <= UNTREEIFY_THRESHOLD)
    	//插入的下标为 [当前数组下标 + 旧数组长度]
        tab[index + bit] = hiHead.untreeify(map);
    else {
        tab[index + bit] = hiHead;
        if (loHead != null)
            hiHead.treeify(tab);
    }
}
           

HashMap知识点总结（附源码分析链接）