HashMap扩容场景

Coding的哔哔叨叨 2021-02-26

740

hello，各位小伙伴们，首先祝大家元宵节快乐，另外，大家久等了，最近刚刚入职新单位，比较忙，多多包涵，不过文章还是会定期为大家更新的，暂定就先一周一篇吧，产出跟不上了...

HashMap扩容场景

Coding的哔哔叨叨

今天的文章内容，想和大家聊下HashMap扩容的场景，这儿大家可以先脑中思考下，你知道的HashMap有哪些扩容的场景，既然我这么问了，指定就不是一个，所以大家可以好好想想。

首先大家最熟悉对一定是当hashmap当前的容量超过负载因子*数组长度时，会发生扩容，但是，在java8的HashMap中，默认大家都知道java8中HashMap是数组+链表+红黑树的实现，如果有不知道的，好好反思下吧。

java8中，当链表长度大等于8时，HashMap会进行树形化，而当HashMap在树形化前，如果数组容量<64先进行一次扩容再进行树形化，来看代码：

.....
put(key,val)的其中一段代码：
else {
//循环，记录链表的长度，并判断是否大等于8
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            p.next = newNode(hash, key, value, null);
            //如果大等于8，进行红黑树的转化。
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }
}
 .....
 /**
 * treeifyBin树形化方法
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY=64
//先判断s会否<64，小于的话先进行resize().    
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

这儿有个问题，为什么要先进行一次扩容？这儿我是这么理解的。

hashMap从链表大于8后转为红黑树（小于6后转为链表），本质的原因是hash碰撞几率很大，所以导致了链表过长，如果只是将链表转成红黑树，本质意义上并没有解决碰撞的问题，对于性能的提升并不见得会有多好，所以先进行一次扩容，将key再散列一些，然后如果仍然出现碰撞且链表长度超过8，再变红黑树。

总结：扩容的时机有两个场景，

当数组容量超过负载因子*数组长度。
java8中在树形化前，如果数组容量<64先进行一次扩容再进行树形化。

不积跬步，无以至千里。

文章有帮助的话，点个转发、在看呗。
谢谢支持哟 (*^__^*)

END

👇

数据库

文章转载自Coding的哔哔叨叨，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

HashMap扩容场景

评论