> HashMap源码解读:扩容 - Yuyy
Yuyy
Yuyy
HashMap源码解读:扩容

HashMap源码解读:扩容

引言

HashMap的扩容是个很重要的操作,jdk1.7往前这里会发生死链问题,都是值得研究的。我最开始以为HashMap线程不安全的原因是因为扩容,没有注意到jdk版本的影响,就去看1.8的扩容为啥会发生死链,但因此也发现了这个方法里的巧妙设计。

分析

以下这段代码是jdk1.8HashMap扩容时,遍历原HashMap的桶,将元素放到新HashMap的桶里。

            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        // 疑问一:桶里只有一个元素时,直接覆盖到新的桶里,不担心Hash碰撞吗?
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 疑问二:计算桶的位置时,为什么不是e.hash & (newCap - 1)
                        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;
                        }
                    }
                }
            }

疑问一

桶里只有一个元素时,直接覆盖到新的桶里,不担心Hash碰撞吗?

newTab[e.hash & (newCap - 1)] = e;

这点想了许久没想明白,最终颠倒了下思路,利用反证法才解释清除了为什么这里不用担心Hash碰撞。

假定:在新桶里的元素都是来自同一个旧桶里。那么就不担心Hash碰撞,这里明确了旧桶里只有一个元素,所以可以直接覆盖到新桶里。似乎一切都说的通了,那我们来证明下这个假定。

看看是怎么计算的新桶的位置,这和put元素时相同,那么我们梳理下这两者的联系。

假定以前容量为16,那么现在容量为32。

假定e.hash=110111001

  • 计算旧桶位置(以前put时)oldIndex=110111001&1111=1001

  • 计算新桶的位置B(扩容时)newIndex=110111001&11111=11001

新桶里的元素,e.hash后五位是相同的,那后四位肯定相同,意思是旧桶位置也相同。到此,这个上诉的假定已被我们证明了,疑点也被解释清楚了!

一个新桶里的元素都来自于同一个旧桶,那反过来也是这样吗?

肯定不是的,从上面计算桶的位置可知,hashcode的第五位(从左往右)不同取值会产生2种情况,1001和11001。不过这两种情况是有关联的,仔细看看两种情况。

  • 当第五位为0时,新桶的位置和旧桶相同,都是1001=9(10进制)。
  • 当第五位为1时,新桶位置为11001=9(10进制)+10000(2进制)=9+16=25

结论:旧桶里的元素,扩容后,有两种可能。一、新桶的位置和旧桶相同。二、新桶位置=旧桶位置+扩容前的容量。

当我们思考到这里时,后面的问题都不是问题了。

疑问二

计算桶的位置时,为什么不是e.hash & (newCap – 1)

                        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;
                        }

阅读这段代码,得出两个信息

  1. 通过条件(e.hash & oldCap) == 0将元素分成两个链表
  2. 将两个链表放到了两个桶里,一个桶的位置和旧桶相同,另一个是旧桶位置+扩容前的容量

看到第二个信息时,是不是很兴奋,这不就是我们通过疑问一推导出来的吗?

我们再来看看第一个信息,这个条件和疑问一推导出来的条件(hashcode的第五位取值)有何关联。

e.hash & oldCap=110111001 & 16 = 110111001 & 10000 = 1(第五位)

破案了,一切真相大白!这个条件就是在取hashcode的第五位,和我们前面推导的一致!

到此,HashMap扩容的神秘面纱已经被我们揭开了。感谢我的朋友LiJun和我一起分析,推导,享受理解源码那一刻的兴奋

其他疑问

HashMap jdk7,8线程不安全的地方在哪?以后详细分析

发表评论

textsms
account_circle
email

Yuyy

HashMap源码解读:扩容
HashMap源码解读:扩容 引言 HashMap的扩容是个很重要的操作,jdk1.7往前这里会发生死链问题,都是值得研究的。我最开始以为HashMap线程不安全的原因是因为扩容,没有注意到jdk版本的影…
扫描二维码继续阅读
2021-09-09
友情链接
标签
归档
近期文章