HashMap 夺命 14 问！

final Node<K,V>[] resize() {  
        //oldTab：引用扩容前的哈希表  
        Node<K,V>[] oldTab = table;  
        //oldCap：表示扩容前的table数组的长度  
        int oldCap = (oldTab == null) ? 0 : oldTab.length;  
        //获得旧哈希表的扩容阈值  
        int oldThr = threshold;  
        //newCap:扩容之后table数组大小  
        //newThr:扩容之后下次触发扩容的条件  
        int newCap, newThr = 0;  
        //条件成立说明hashMap中的散列表已经初始化过了，是一次正常扩容  
        if (oldCap > 0) {  
            //判断旧的容量是否大于等于最大容量，如果是，则无法扩容，并且设置扩容条件为int最大值，  
            //这种情况属于非常少数的情况  
            if (oldCap >= MAXIMUM_CAPACITY) {  
                threshold = Integer.MAX_VALUE;  
                return oldTab;  
            }//设置newCap新容量为oldCap旧容量的二倍（<<1）,并且<最大容量，而且>=16，则新阈值等于旧阈值的两倍  
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                     oldCap >= DEFAULT_INITIAL_CAPACITY)  
                newThr = oldThr << 1; // double threshold  
        }  
        //如果oldCap=0并且边界值大于0，说明散列表是null，但此时oldThr>0  
        //说明此时hashMap的创建是通过指定的构造方法创建的,新容量直接等于阈值  
        //1.new HashMap(intitCap,loadFactor)  
        //2.new HashMap(initCap)  
        //3.new HashMap(map)  
        else if (oldThr > 0) // initial capacity was placed in threshold  
            newCap = oldThr;  
        //这种情况下oldThr=0;oldCap=0，说明没经过初始化，创建hashMap  
        //的时候是通过new HashMap()的方式创建的  
        else {               // zero initial threshold signifies using defaults  
            newCap = DEFAULT_INITIAL_CAPACITY;  
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
        }  
        //newThr为0时，通过newCap和loadFactor计算出一个newThr  
        if (newThr == 0) {  
            //容量*0.75  
            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指向新创建的数组  
        table = newTab;  
        //本次扩容之前table不为null  
        if (oldTab != null) {  
            //对数组中的元素进行遍历  
            for (int j = 0; j < oldCap; ++j) {  
                //设置e为当前node节点  
                Node<K,V> e;  
                //当前桶位数据不为空，但不能知道里面是单个元素，还是链表或红黑树，  
                //e = oldTab[j]，先用e记录下当前元素  
                if ((e = oldTab[j]) != null) {  
                    //将老数组j桶位置为空，方便回收  
                    oldTab[j] = null;  
                    //如果e节点不存在下一个节点，说明e是单个元素，则直接放置在新数组的桶位  
                    if (e.next == null)  
                        newTab[e.hash & (newCap - 1)] = e;  
                    //如果e是树节点，证明该节点处于红黑树中  
                    else if (e instanceof TreeNode)  
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
                    //e为链表节点，则对链表进行遍历  
                    else { // preserve order  
                        //低位链表：存放在扩容之后的数组的下标位置，与当前数组下标位置一致  
                        //loHead：低位链表头节点  
                        //loTail低位链表尾节点  
                        Node<K,V> loHead = null, loTail = null;  
                        //高位链表，存放扩容之后的数组的下标位置，=原索引+扩容之前数组容量  
                        //hiHead:高位链表头节点  
                        //hiTail:高位链表尾节点  
                        Node<K,V> hiHead = null, hiTail = null;  
                        Node<K,V> next;  
                        do {  
                            next = e.next;  
                            //oldCap为16:10000，与e.hsah做&运算可以得到高位为1还是0  
                            //高位为0，放在低位链表  
                            if ((e.hash & oldCap) == 0) {  
                                if (loTail == null)  
                                    //loHead指向e  
                                    loHead = e;  
                                else  
                                    loTail.next = e;  
                                loTail = e;  
                            }  
                            //高位为1，放在高位链表  
                            else {  
                                if (hiTail == null)  
                                    hiHead = e;  
                                else  
                                    hiTail.next = e;  
                                hiTail = e;  
                            }  
                        } while ((e = next) != null);  
                        //低位链表已成，将头节点loHead指向在原位  
                        if (loTail != null) {  
                            loTail.next = null;  
                            newTab[j] = loHead;  
                        }  
                        //高位链表已成，将头节点指向新索引  
                        if (hiTail != null) {  
                            hiTail.next = null;  
                            newTab[j + oldCap] = hiHead;  
                        }  
                    }  
                }  
            }  
        }  
        return newTab;  
    }  

 * Because TreeNodes are about twice the size of regular nodes, we  
 * use them only when bins contain enough nodes to warrant use  
 * (see TREEIFY_THRESHOLD). And when they become too small (due to  
 * removal or resizing) they are converted back to plain bins.  In  
 * usages with well-distributed user hashCodes, tree bins are  
 * rarely used.  Ideally, under random hashCodes, the frequency of  
 * nodes in bins follows a Poisson distribution  
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a  
 * parameter of about 0.5 on average for the default resizing  
 * threshold of 0.75, although with a large variance because of  
 * resizing granularity. Ignoring variance, the expected  
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /  
 * factorial(k)).  

 * 0:    0.60653066  
 * 1:    0.30326533  
 * 2:    0.07581633  
 * 3:    0.01263606  
 * 4:    0.00157952  
 * 5:    0.00015795  
 * 6:    0.00001316  
 * 7:    0.00000094  
 * 8:    0.00000006  
 * more: less than 1 in ten million