Java 1.7 中 HashMap 扩容

问：简单说说你对 HashMap 构造方法中 initialCapacity（初始容量）、loadFactor（加载因子）的理解？

答：这两个参数对于 HashMap 来说很重要，直接从一定程度决定了 HashMap 的性能问题。

initialCapacity 初始容量代表了哈希表中桶的初始数量，即 Entry< K,V>[] table 数组的初始长度，不过特别注意，table 数组的长度虽然依赖 initialCapacity，但是每次都会通过 roundUpToPowerOf2(initialCapacity) 方法来保证为 2 的幂次。

loadFactor 加载因子是哈希表在其容量自动增加之前可以达到多满的一种饱和度百分比，其衡量了一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。散列当前饱和度的计算为当前 HashMap 中 Entry 的存储个数除以当前 table 数组桶长度，因此当哈希表中 Entry 的数量超过了 loadFactor 加载因子乘以当前 table 数组桶长度时就会触发扩容操作。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大则对空间的利用更充分，从而导致查找效率的降低，如果负载因子太小则散列表的数据将过于稀疏，从而对空间造成浪费。系统默认负载因子为 0.75，一般情况下无需修改。
因此如果哈希桶数组很大则较差的 Hash 算法分部也会比较分散，如果哈希桶数组很小则即使好的 Hash 算法也会出现较多碰撞，所以就需要权衡好的 Hash 算法和扩容机制，也就是上面两个参数的作用。

问：简单说说 JDK1.7 中 HashMap 什么情况下会发生扩容？如何扩容？

答：HashMap 中默认的负载因子为 0.75，默认情况下第一次扩容阀值是 12（16 * 0.75），故第一次存储第 13 个键值对时就会触发扩容机制变为原来数组长度的二倍，以后每次扩容都类似计算机制；这也就是为什么 HashMap 在数组大小不变的情况下存放键值对越多查找的效率就会变低（因为 hash 碰撞会使数组变链表），而通过扩容就可以一定程度的平衡查找效率（尽量散列数组化）的原因所在。

具体的扩容方式对于 JDK 1.8 前后的实现是有一点区别的，不过大体思路不变。下面给出 JDK 1.7 的具体扩容流程：

        //JDK1 .7 扩容最核心的方法，newTable为新容量数组大小
        void transfer (HashMapEntry[]newTable ){
            //新容量数组桶大小为旧的table的2倍
            int newCapacity = newTable.length;
            // 遍历旧的数组桶table
            for (HashMapEntry<K, V> e : table) {
                // 如果这个数组位置上有元素且存在哈希冲突的链表结构则继续遍历链表
                while (null != e) {
                    //取当前数组索引位上单向链表的下一个元素
                    HashMapEntry<K, V> next = e.next;
                    //重新依据hash值计算元素在扩容后数组中的索引位置
                    int i = indexFor(e.hash, newCapacity);
                    //将数组i的元素赋值给当前链表元素的下一个节点
                    e.next = newTable[i];
                    //将链表元素放入数组位置
                    newTable[i] = e;
                    //将当前数组索引位上单向链表的下一个元素赋值给e进行新的一圈链表遍历
                    e = next;
                }
            }
        }

可以看到，整个扩容过程就是一个取出数组元素（实际数组索引位置上的每个元素是每个独立单向链表的头部，也就是发生 Hash 冲突后最后放入的冲突元素）然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标然后进行交换（即原来 hash 冲突的单向链表尾部变成了扩容后单向链表的头部）。下面给出图解流程：