重写jdk源码：HashMap的resize方法优化思考

痛定思痛。 2023-06-15 11:12 107阅读 0赞

友情提示：本文推理结果是不准确的，**因为在HashMap中处于数组同一位置的元素的哈希值大部分情况是不同的**，但整个思考过程比较完整，有兴趣的可以看看。

--------------------

话不多说，我们直接看HashMap的resize方法源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70][]

重点在715-744行，我直接说结论，我会用一行代码去替换掉这近30行，如下：

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

**你可能看出来了，这和上面的** **e.next == null 判断之后的操作是一样的，所以可以直接将这2个判断合并**，**重写之后的resize方法如下：**

final Node<K,V>[] resize() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                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;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                           newTab[e.hash & (newCap - 1)] = e;
                        }
                    }
                }
            }
            return newTab;
        }

**  **

**分析思考：**

下面来分析一下我的思考过程，其实我首先想到的是下面这个版本：

if ((e.hash & oldCap) == 0) {
    	newTab[j] = e;
    }else {
    	newTab[j+ oldCap]= e;
    }

然后觉得能不能更优，就有了下面这个2行的代码：

newTab[e.hash & oldCap == 0?j:j+ oldCap] = e;

本来都这儿可以结束了，但我突然发现，还可以更简洁，所以有了开头的那一行代码，和源码中的712行一样，所以直接就能合并了。

在我发现了这个优化后，是考虑弄个类继承HashMap去测试验证一下，但由于resize方法不是public修饰的，且是final关键字修饰的，所以必须得将整个 HashMap的源码复制过来，再修改其resize方法即可实现验证，我觉得太麻烦，而且也没必要。

所以这里呢我会以原作者的思路，通过逆推的方式来验证我这个优化的准确性。我们继续来分析一下resize方法的 715-744行 代码，它首先定义了 loHead，loTail 和 hiHead，hiTail 这四个变量，目的就是为了区分 (e.hash & oldCap) == 0 和  (e.hash & oldCap) != 0 的情况，这个情况是因为在HashMap扩容后 e.hash & 2n-1 的值只可能是原数组的索引下标 **j** 或者原数组的索引下标加上原数组的长度  **j + oldCap** 。但其实完全没必要定义四个变量，只需要定义2个 head 和 tail 即可。**为什么呢？现在我们着重看下do-while 循环中的代码：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70 1][]

重点在 721 行，可以看出来 **e.hash() 和 oldCap  这2个变量在** **do-while 循环中 是不变的，因为整个链表e都是在原数组的同一个位置的，所以它们的哈希值肯定是相等的。**基于这个结论，我们在原作者的思路上可以一下优化他的715-744行代码，如下：

Node<K,V> head = null, tail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if (tail == null)
                                    head = e;
                                else
                                    tail.next = e;
                                tail = e;
                            } while ((e = next) != null);
                            if (tail != null) {
                                tail.next = null;
                                newTab[(head.hash & oldCap) == 0?j:j+ oldCap] =  head;
                            }

只用了 head 和 tail 2个变量就完成了原来的功能。写到这儿，我想你大概明白了，分析上面的代码可以看出来，其实 head 和 tail 变量并没有什么实际用处。在do-while 循环结束后**，**先判断 tail 是否为空 ，这行完全没必要，因为在588行已经判断了e不为null了，如下：

![201911221136311.png][]

所以进入循环后 tail 肯定不会为空的，然后用 head 的哈希值与 oldCap 按位与运算后得到在数组中的索引位置，将head放入新数组中，这行根本就是多余的，**因为 head=e 只会在第一次循环的时候赋值，所以整个do-while 循环没有必要，直接****用 e 替换head是完全没问题的，这样用 e 替换后就得到了我开头优化的那行代码:**

newTab[(e.hash & oldCap) == 0?j:j+ oldCap] = e;

然后发现 e.hash 值既然是固定的，就没必要用三元表达式了，直接用 e.hash & (newCap - 1) 得到下标索引就行了：

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

所以我们用原作者的思路推出了我们这个优化代码。

**总结：**

我第一次看到 715-744行 这段代码是有点不知所云的，总觉得有些别扭，在看了一遍之后，我得到的结论就是**newTab\[j\] = e;**

所以在经过思考和分析后就得到了这一行优化代码：

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

另外在源码中可以感觉到有点花里胡哨，弄得很复杂。事实上我们回过头来思考，会发现 715-744行整个的目的就是将原数组中的链表顺序复制进新数组中即可，避免jdk1.7中扩容数据迁移时候的死循环，所以其实很简单就能做到了

如果觉得有问题的同学，可以在评论中指出来

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191122101347672.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191122111932124.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy,size_16,color_FFFFFF,t_70
[201911221136311.png]: https://img-blog.csdnimg.cn/201911221136311.png