HashMap扩容操作

一、如果容量大于MAXIMUM_CAPACITY，则不需要扩容了，添加元素后发生碰撞就发生碰撞吧。
二、如果可以扩容，则扩容一倍，将老数组中的数据放到新数组中。
由于老数组的元素位置是hash & oldCap-1得到的，新数组中的元素是hash & 2oldCap -1得到的，所得到的位置也许和以前一样也许是以前的位置+oldCap。所以使用循环将其分开。
如：以前长度为16，即1 0000，一个元素的hash & 1111 ，得到的是在原来数组的位置
它在新数组的位置是hash & 1 1111，1 1111的最高位 1 和hash&运算时，得到的可能是0，也可能是1，如果是0，则，该元素还在这个位置不变，如果是1，也就是说，它在新数组的位置是老位置+1 0000。即oldIndex+oldCap。通过e.hash & oldCap将这两组元素分开后，放到新表的相应位置。

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) {
            // 1.做边界判断，容量大于最大值，不再扩容了，直接返回原table     
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 2.容量扩大两倍小于最大值，则可以扩容，并且给阈值也随着扩大两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold 容量翻倍，阈值也翻倍
                
            // 这里的else省略了，其实是走到了5. 容量扩大两倍会大于最大值，则阈值设置为Integer.MAX_VALUE，以后会走：1. 即不会在扩容了。
                
        }
        // 3.初始化调用了初始化长度的构造方法，会得到大于长度的最小的2的n次方，最大为MAXIMUM_CAPACITY，并赋给threshold，到这里赋值给了newCap
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 4.默认构造方法，默认table大小为16，阈值为12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 5.走到这里说明：1.如果容量扩大两倍后超过最大值，阈值设为Integer.MAX_VALUE，以后不再扩容了。2.或则调用了初始化长度的构造方法后，第一次执行put操作。
        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.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;
                            // 之前hash & cap - 1，如cap = 10000，hash & 1111，现在是hash & 2cap -1，即hash & 1 1111，变化的是
                            // hash & length -1 高了一位，那么高的那一位，对应的hash值的那一位是0还是1呢？
                            // 这就是hash & oldCap的作用，如果为0，那么这个元素还放在这个位置即可，如果为1，那它在新数组的位置就是现在的位置+oldCap。                       
                            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;
    }