HashMap基本的实现流程之扩容

本文接上篇：
《HashMap最基本的实现流程（源码角度）》

前言

上篇主要说了HashMap的put操作实现的主流程，分析了源码中某些关键步骤之所以那样写的原因；对于一些分支流程没有过多展开，这里就填一下扩容的坑；

扩容

这里先把涉及到扩容的地方的源码贴一下：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

如上图代码，这是HashMap添加元素的函数，上一篇中我们假设还没到扩容的条件，先走了下面的主流程，这里我们就来看一下分支流程——扩容；

1. 扩容的条件

即什么时候会触发扩容？回答这个问题时这里可能会有一个误区（不怕笑话，我之前就是按误区这么想的），就是当 数组存的元素个数大于阈值的时候 会触发扩容，并且回答时脑海中浮现的比例图是下图：

其实直到我真的去看了HashMap的源码我才意识到我的错误。上一篇我一开始也特别强调了下size的含义；其实触发扩容的条件应该是这样的：当哈希表中存的元素个数（size）超过了阈值（threashold）时。

这样就对了嘛？对了一半，看源码中判断的条件，且 后面还有半句，这就表示并不是size>threshold时就会扩容，什么时候size>threshold但还不扩容呢？——当要存的下一个元素的索引并没有冲突时。如下图，假设现在的参数情况如下：

capacity=4（2^2）
loadfactor=0.75
threshold=capacity*loadFactor=3
size=3(满足扩容第一个条件)

存储情况如下图：

这时要添加的元素的索引被计算出来是3（或者2），因为此时2或者3的位置都没有元素（即table[index]==null），即没有冲突，所以直接放进去，此时这种情况不会触发扩容。

所以，最终触发扩容的条件（其实源码中很清楚）：当哈希表重的元素个数超过了设定的阈值并且即将添加的元素发生冲突。
PS：这里之所以展开说，是因为今天恰巧看见有面经里描述有面试官这样问过。不然我也没在意这里（面试官都是魔鬼吗？？！peace）。

2. 扩容操作

首先从整体上了解扩容的流程：

可以看到，扩容的实质其实就是复制（我第一次知道这个实质是震惊的，扩容多高大上的词，万万没想到有着这么朴实无华的实现），并且扩容规律是二倍扩容（2*table.length），
这里有一个 疑问①：为什么扩容后要再次hash？ key还是原来那个key啊，rehash会有变化？稍后会说

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

根据代码可以看到，在创建新数组前会有一个判断分支：当hashmap已经扩容到允许的最大值（MAXIMUN_CAPACITY;2³⁰）时，阈值就变成Integer.MAX_VALUE(2³¹-1),并直接返回。这意思就很明确了，capacit=2³⁰后就不会再扩容了，因为size永远也达不到threshold了。

下面可以看到使用新长度（原长度的2倍，符合2的次幂）new一个新的数组。接下来就是把数组中的元素一个个复制到新数组中（transfer函数）。

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

这里可以看到，使用了一个双层循环去遍历哈希表，外层循环遍历数组，内层循环遍历链表，然后将遍历到的元素（entry）是哟个头插法插入到新的数组中。
这里有一个值得注意的点，就是这个函数的入参中有一个布尔变量rehash，通过这个变量来判断是否需要重新计算所复制元素的key的hash值。这个变量的入参是一个函数的返回值；

    final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

这里我们先不具体去了解函数的逻辑及意义，我们先知道一点，这个函数中操作了hashseed，而我们的key的hash也会受这个hashseed 的影响；所以这里就可以解答上面的疑问①了——因为在扩容的操作中调用了initHashSeedAsNeeded函数，而这个函数在特定条件下会影响hashseed的值，而hashSeed的值会影响key 的hash值，所以要重新hash。
解决了疑问①，我们再来看这个initHashSeedAsNeeded函数到底做了什么？以及目的是什么？我这里不展开讲了，可以看下以下两个文章：
文章1
文章2
这里直接给出结论：hashseed以这个函数设计的目的就是可以让用户去影响HashMap 中当key类型为String类型的hash方法，以期望达到降低碰撞的目的。而我们一般情况下hashseed的值一直是为0的，这个函数的返回一直是false的。

回到transfer函数，rehash=false，下面就是头插法插入元素了。

到这里扩容就结束了（其实还有一个二倍扩容后在二进制上的小细节，jdk1.7没用到，1.8用到了，后面再说吧）。

可以看到HashMap的扩容效率还是很低的，这也是为什么编码规范会提示你在创建HashMap的时候最好赋一个容量大小。因为用户根据实际需求赋值的容量，可以减少甚至避免（如果用户完全知道自己的Map要存多少东西）扩容操作，从而提高效率。

PS：之前HashMap这种官方的，我们拿来就用的东西，一直对我来说很神秘，很高大上，感觉遥不可及，他肯定使用了什么了不得的东西，可是当你看下去的时候，你会发现，原来就这啊，不就是复制嘛？他原来也是会使用双层循环的啊。当你再仔细看的时候，就会再次发现，他的那些精巧的构思是多么妙不可言！

以上

本文地址：https://blog.csdn.net/qq_21294185/article/details/109862417