知識點：Java HashMap 原理與原始碼分析(下)

本文可以讓你學到：

1.HashMap resize原理 重要知識點
2.HashMap 特性總結

回顧

上篇中講了HashMap的特點、常用方法、作業原理以及hash值是怎樣計算的；
上篇《知識點： Java HashMap 原理與原始碼分析(上)》

資料結構

HashMap索引使用陣列結構進行管理(圖中的table欄位),陣列的型別為Node<K,V>[]；Node是interface；Node實際有兩個型別，分別為鏈表與紅黑樹；
Node中存盤key、value、hash以及指向下一個元素的next，
Node定義如下：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}

關鍵常量引數

1. DEFAULT_INITIAL_CAPACITY 初始化時默認容量；大小為1<<4（16）
2. MAXIMUM_CAPACITY 最大容量；大小為1<<30
3. DEFAULT_LOAD_FACTOR 默認填充系數 大小為0.75

resize() 分析

什么情況下需要resize()操作

1. 初始化時指定容量為0
2. 容量超過臨界點時

擴容流程如下圖：

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) {
            //是否已經超過最大容量；超過則不擴容；但臨界值修改為Integer.MAX_VALUE
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                     //進行兩倍的擴容
                newThr = oldThr << 1; // double threshold
        }
        // 老的臨界點大于0 擴容到老的臨界點
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
        //老的容量為0臨界值也為0時擴容至默認容量
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //新臨界值為0時，通過新的容量*填充系數獲得新的臨界值
        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];
        //將新的tab賦值給老的table
        table = newTab;
        //老的table中有資料是對老的資料進行分裂
        if (oldTab != null) {
            //回圈老的table，將老的資料通過hash值重新在新的table中找出索引位置
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //e.next==null 表中結點上只有一個物件；沒有hash沖突的情況
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                    //老的節點為紅黑樹時重新分裂到新的table上；分裂的方式和鏈接基本相同
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                    //將鏈表中的元素重新分配到新的table中
                        Node<K,V> loHead = null, loTail = null;//元素hash中在原table長度的二進制高位為0
                        Node<K,V> hiHead = null, hiTail = null;//元素hash中在原table長度的二進制高位為1
                        Node<K,V> next;
                        do {
                        //遍歷鏈表中的所有元素，通過老table長度的高位對鏈表拆分
                            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);
                        //將高位為0的放到新table中，索引和原來相同
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //將高位為1的放到新table中，索引為j+oldCap;
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

擴容時使用二次冪進行；每次將當前table容量大小size向右移位；比如16、32、64、128；這樣在進行擴容時也可以使用二分法減少資料的移動；
例1：
當前容量大小為16，現進行擴容；一次擴容后的容量大小為32
如有一個物件的hash值二進制為：
e.hash的二進制值
1111 1010 0000 1111 0000 1111 1100 1111
table.size的二進制值
0000 0000 0000 0000 0000 0000 0001 0000
這時e物件的索引就會保持在原來的位置上

例2：
當前容量大小為16，現進行擴容；一次擴容后的容量大小為32
如有一個物件的hash值二進制為：
e.hash的二進制值
1111 1010 0000 1111 0000 1111 1101 1111
table.size的二進制值
0000 0000 0000 0000 0000 0000 0001 0000
這時e物件的索引將會是原來的索引加上原tabal.size，結果為newIndex=j+oldCap

總結

1.使用陣列存盤結點Node，最大容量為1的30次冪1<<30
2.中的結點Node有鏈表與紅黑樹兩種型別（Java 1.8后加入鏈表）
3.每次擴容后的容量均為2的次冪
4.是執行緒不安全的集合類
5.有最大索引值1<<30；但理論上可以存盤無限數量的物件
6.計算hash值會呼叫物件的hashCode()方法
7.查找值時會呼叫物件的equal()方法
8.允許存在空的key與value值
9.元素是無序的，且會隨容量的變化而變化
10.遍歷整個 Map 需要的時間與 桶(陣列) 的長度成正比，因此初始化時桶的容量不宜過大

公眾號閱讀 碼農杰森