HashMap:如何进行扩容？

在说明hashMap如何进行扩容之前，先说下为什么要进行扩容？是因为hashMap初始化的容量不够用了吗？不是，是因为当hashMap元素的个数 > hashMap容量*0.75时，存储新元素发生hashcode碰撞的概率变得很大。那么，什么是hashcode碰撞？

1.什么是hashcode碰撞？

hashcode碰撞就是当存入多个元素的时候，元素key的hashcode出现了一样的情况。当hashmap存入元素的时候，如果碰撞较少，那么出现的存储情况如图：

碰撞较少
如果碰撞比较频繁，就会出现的存储情况如图：
碰撞比较频繁
综上：hashcode碰撞会导致hashMap中元素分布不均衡，hashMap中元素分布不均衡就会导致查找元素的效率变得很低。

2.怎么减少hashcode碰撞的几率，使元素的分布更加均匀？

hashMap为了减少hashcode碰撞的几率，会在对key进行hash的时候进行扰动，也就是让计算出来的hashCode更随机。

// > java8
 (h = key.hashCode()) ^ (h >>> 16)

但即使这样，当hashMap元素的个数 > hashMap容量*负载因子（默认0.75）时，hashcode碰撞的概率也会变得较为频繁。这时候就需要对hashmap进行扩容了。

3.hashMap怎么进行扩容？

    /**
     * 初始化table或者将table扩容未两倍
     */
    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; // 扩容后数组的长度，扩容后的阀值 = （扩容后数组的长度，扩容后的阀值）*2
        }
       
        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.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }