HashMap底層原理及jdk1.8原始碼解讀

底層結構範例圖

三、原始碼分析之常用變數解讀

/**
 * 預設初始容量 - 必須是 2 的冪。
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量，如果一個更高的值被任何一個帶引數的建構函式隱式指定使用。必須是 2 <= 1<<30 的冪。
 * 簡單理解為：最大容量2的30次冪，如果帶容量也會轉化為2的次冪
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 建構函式中未指定時使用的負載因子。經過官方測試測出減少hash碰撞的最佳值
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 使用紅黑樹的計數閾值，超過8則轉化為紅黑樹
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 使用紅黑樹的計數閾值，低於6則轉化為連結串列
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 連結串列轉化為紅黑樹，除了有閾值的限制，還有另外一個限制，需要陣列容量至少達到64，才會轉化為紅黑樹。
 * 這是為了避免，陣列擴容和樹化閾值之間的衝突。
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 在首次使用時初始化，並根據需要調整大小。分配時，長度始終是 2 的冪。
 * （我們還在某些操作中允許長度為零，以允許當前不需要的引導機制）
 */
transient Node<K,V>[] table;

/**
 * 儲存快取的 entrySet()，也就是存放的鍵值對
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 此對映中包含的鍵值對映的數量，就是陣列的大小
 */
transient int size;

/**
 * 記錄集合的結構變化和操作次數（例如remove一次進行modCount++）。
 * 該欄位用於使 HashMap 的 Collection-views 上的迭代器快速失敗。如果失敗也就是我們常見的CME
 * （ConcurrentModificationException）異常
 */
transient int modCount;

/**
 * 陣列擴容的大小
 * 計算方法 capacity * load factor  容量 * 載入因子
 * @serial
 */
int threshold;

/**
 * 雜湊表的負載因子。
 * @serial
 */
final float loadFactor;

四、原始碼分析之構造方法解讀

/**
 * 構造一個具有指定初始容量和負載因子的構造方法
 * 不建議使用這個構造方法，載入因子經過官方測試是效率最好的，所以為了效率應該保持預設
 */
public HashMap(int initialCapacity, float loadFactor) {
	// 引數為負數會丟擲IllegalArgumentException異常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 傳的值超過最大值則使用預設最大值                                     
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 雜湊表的負載因子。                                      
    this.loadFactor = loadFactor;
    // 初始化的引數預設如果不是2的次冪，直接給你轉化為2的次冪
    // 傳的引數為11，會自動轉化為比引數大的最近的2的次冪的值，也就是16。
    // 我們後面會詳細說這個方法怎麼進行轉化的
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 構造一個只有指定初始容量的方法
 */
public HashMap(int initialCapacity) {
    // 我們會發現還是呼叫上面兩個引數的構造方法，自動幫我們設定了載入因子
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 構造一個具有預設初始容量(16) 和預設負載因子(0.75)的構造方法
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 指定map集合，轉化為HashMap的構造方法
 */
public HashMap(Map<? extends K, ? extends V> m) {
	// 使用預設載入因子
    this.loadFactor = DEFAULT_LOAD_FACTOR;
	//呼叫PutMapEntries()來完成HashMap的初始化賦值過程
    putMapEntries(m, false);
}
/**
 * 將傳入的子Map中的全部元素逐個新增到HashMap中
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
	// 獲得引數Map的大小，並賦值給s
    int s = m.size();
    // 判斷大小是否大於0
    if (s > 0) {
    	// 證明有元素來插入HashMap
    	// 判斷table是否已經初始化  如果table=null一般就是建構函式來呼叫的putMapEntries，或者構造後還沒放過任何元素
        if (table == null) { // pre-size
        	// 如果未初始化，則計算HashMap的最小需要的容量（即容量剛好不大於擴容閾值）。這裡Map的大小s就被當作HashMap的擴容閾值，然後用傳入Map的大小除以負載因子就能得到對應的HashMap的容量大小（當前m的大小 / 負載因子 = HashMap容量）
            // ((float)s / loadFactor)但這樣會算出小數來，但作為容量就必須向上取整，所以這裡要加1。此時ft可以臨時看作HashMap容量大小
            float ft = ((float)s / loadFactor) + 1.0F;
            // 判斷ft是否超過最大容量大小，小於則用ft，大於則取最大容量
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 暫時存放到擴容閾值上,tableSizeFor會把t重新計算到2的次冪給擴容陣列大小
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 如果當前Map已經初始化,且這個map中的元素個數大於擴容的閥值就得擴容
        // 這種情況屬於預先擴大容量，再put元素
        else if (s > threshold)
        	// 後面展開說
            resize();
        // 遍歷map,將map中的key和value都新增到HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // 呼叫HashMap的put方法的具體實現方法putVal來對資料進行存放。該方法的具體細節在後面會進行講解
            // putVal可能也會觸發resize
            putVal(hash(key), key, value, false, evict);
        }
    }
}

五、原始碼分析之常用方法解讀

1、tableSizeFor方法解讀

/**
 * 返回給定目標容量的 2 次方。
 */
static final int tableSizeFor(int cap) {
	// cap = 10
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 小於0就是1，如果大於0在判斷是不是超過最大容量就是n=15+1 = 16，超過就按最大容量
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

以cap為10為例：（右移規則為：無符號位右移）

10的二進位制為：0000 0000 0000 0000 0000 0000 0000 1010

執行int n = cap - 1;

二進位制結果為：0000 0000 0000 0000 0000 0000 0000 1001

執行n |= n >>> 1;（先進行右移，結果和原來的數進行或運算[==有1則1==]）

0000 0000 0000 0000 0000 0000 0000 1001
0000 0000 0000 0000 0000 0000 0000 0100 n>>1結果
————————————————————
0000 0000 0000 0000 0000 0000 0000 1101 n |= n >> 1 結果

二進位制結果為：0000 0000 0000 0000 0000 0000 0000 1101

執行n |= n >>> 2;

0000 0000 0000 0000 0000 0000 0000 1101

0000 0000 0000 0000 0000 0000 0000 0011 n>>2結果

————————————————————
0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 2 結果

二進位制結果為：0000 0000 0000 0000 0000 0000 0000 1111

執行n |= n >>> 4;

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 0000 0000 n>>4結果

————————————————————
0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 4 結果

二進位制結果為：0000 0000 0000 0000 0000 0000 0000 1111

執行n |= n >>> 8;

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 0000 0000 n>>8結果

————————————————————
0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 8 結果

二進位制結果為：0000 0000 0000 0000 0000 0000 0000 1111

執行n |= n >>> 16;

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 0000 0000 n>>16結果

————————————————————
0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 16 結果

二進位制結果為：0000 0000 0000 0000 0000 0000 0000 1111

我們會發現，當數小的的時候進行到4時就不會變了我們得到的值為15，即輸入10，經過此方法後得到15。遇到大的數才會明顯，大家可以找個大的數位進行試試就是先右移在進行或運算。最後進行三門運算進行+1操作，最後結果為16=2^4

2、hash方法解讀

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

先判斷key是否為空，若為空則返回0。上面說了HashMap僅支援一個key為null的。若非空，則先計算key的hashCode值，賦值給h，然後把h右移16位元，並與原來的h進行互斥或處理（相同為1，不同為0）。
註釋進行谷歌翻譯：
計算 key.hashCode() 並傳播（XOR）更高位的雜湊降低。 由於該表使用二次冪掩碼，因此僅在當前掩碼之上位變化的雜湊集將始終發生衝突。 （已知的例子是在小表中儲存連續整數的 Float 鍵集。）因此，我們應用了一種變換，將高位的影響向下傳播。 在位擴充套件的速度、實用性和質量之間存在折衷。 因為許多常見的雜湊集已經合理分佈（所以不要從傳播中受益），並且因為我們使用樹來處理 bin 中的大量衝突，我們只是以最簡單的方式對一些移位的位進行互斥或，以減少系統損失， 以及合併最高位的影響，否則由於表邊界，這些最高位將永遠不會用於索引計算。

總結：使用最簡易的方式，及減少系統損失又減少了hash碰撞。

3、put方法解讀

/**
* 將指定的值與此對映中的指定鍵相關聯。即當前key應該存放在陣列的哪個下標位置
* 如果對映先前包含鍵的對映，則替換舊的值。
*/
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
* 這才是真正的儲存方法
* @param hash   			經過hash運算後的key
* @param key    			你要新增的key
* @param value  			你要新增的value
* @param onlyIfAbsent 		如果為真，則不要更改現有值，本次為FALSE，可以替換更改
* @param evict 				如果為 false，則表處於建立模式。我們為true
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
   Node<K,V>[] tab; Node<K,V> p; int n, i;
   // 判斷table是否為空
   if ((tab = table) == null || (n = tab.length) == 0)
   	   // 如果空的話，會先呼叫resize擴容,resize我們後面展開講解
       n = (tab = resize()).length;
   // 把通過hash得到的值與陣列大小-1進行與運算，這個運算就可以實現取模運算，而且位運算還有個好處，就是速度比較快。
   // 得到key所對應的陣列的節點，然後把該陣列節點賦值給p,然後判斷這個位置是不是有元素
   if ((p = tab[i = (n - 1) & hash]) == null)
   	   // key、value包裝成newNode節點，直接新增到此位置。
       tab[i] = newNode(hash, key, value, null);
   // 如果當前陣列下標位置已經有元素了，又分為三種情況。
   else {
       Node<K,V> e; K k;
       // 當前位置元素的hash值等於傳過來的hash，並且他們的key值也相等
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           // 則把p賦值給e，後續需要新值把舊值替換
           e = p;
       // 來到這裡說明該節點的key與原來的key不同，則看該節點是紅黑樹，還是連結串列
       else if (p instanceof TreeNode)
       	   // 如果是紅黑樹，則通過紅黑樹的方式，把key-value存到紅黑樹中。後面再講解這個方法
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       else {
       	   // 來到這裡說明結構為連結串列，把key-value使用尾插法插到連結串列尾。
           // jdk1.7 連結串列是頭插入法，在並行擴容時會造成死迴圈
           // jdk1.8 就把頭插入法換成了尾插入法，雖然效率上有點稍微降低一些，但是不會出現死迴圈
           for (int binCount = 0; ; ++binCount) {
           	   // 遍歷該連結串列，知道知道下一個節點為null。
               if ((e = p.next) == null) {
               	   // 說明到連結串列尾部，然後把尾部的next指向新生成的物件
                   p.next = newNode(hash, key, value, null);
                   // 如果連結串列的長度大於等於8
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                   	   // 則連結串列轉化成為紅黑樹 後面再補充
                       treeifyBin(tab, hash);
                   break;
               }
               // 如果在連結串列中找到了相同key的話，直接退出迴圈
               if (e.hash == hash &&
                   ((k = e.key) == key || (key != null && key.equals(k))))
                   break;
               p = e;
           }
       }
       // 說明發生了碰撞，e代表的是舊值，需要替換為新值
       if (e != null) { // existing mapping for key
           V oldValue = e.value;
           // 判斷是不是允許覆蓋舊值，和舊值是否為空
           if (!onlyIfAbsent || oldValue == null)
           		// 把舊值替換
               e.value = value;
           // hashmap沒有任何實現，我們先不考慮
           afterNodeAccess(e);
           // 返回新值
           return oldValue;
       }
   }
   // fail-fast機制每次對結構改變進行+1
   ++modCount;
   // 判斷HashMap中的存的資料大小，如果大於陣列長度*0.75，就要進行擴容
   if (++size > threshold)
       resize();
   // 也是一個空的實現
   afterNodeInsertion(evict);
   return null;
}

4、resize方法解讀

看不清檢視原連結：高清圖連結

/**
 * 初始化或者是將table大小加倍,如果為空，則按threshold分配空間，
 * 否則加倍後，每個容器中的元素在新table中要麼呆在原索引處，要麼有一個2的次冪的位移
 */
final Node<K,V>[] resize() {
	// 原來的資料
    Node<K,V>[] oldTab = table;
    // 獲取原來的陣列大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 舊陣列的擴容閾值，注意看，這裡取的是當前物件的 threshold 值，下邊的第2種情況會用到。
    int oldThr = threshold;
    // 初始化新陣列的容量和閾值
    int newCap, newThr = 0;
    // 1.當舊陣列的容量大於0時，說明在這之前肯定呼叫過 resize擴容過一次，才會導致舊容量不為0。
    if (oldCap > 0) {
    	// 容量達到最大
        if (oldCap >= MAXIMUM_CAPACITY) {
        	// 擴容的大小設定為上限
            threshold = Integer.MAX_VALUE;
            // 直接返回預設原來的，無法在擴了
            return oldTab;
        }
        // 如果舊容量是在16到上限之間
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新陣列的容量和閾值都擴大原來的2倍
            newThr = oldThr << 1; // double threshold
    }
    // 2. 到這裡 oldCap <= 0， oldThr(threshold) > 0，這就是 map 初始化的時候，
    // 第一次呼叫 resize的情況
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 3. 到這裡，說明 oldCap 和 oldThr 都是小於等於0的。也說明我們的map是通過預設無參構造來建立的
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;// 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 12
    }
    // 只有經過2.才會進入
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        // 把計算後的ft符合大小，則賦值newThr 
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 最後得到要擴容的大小
    threshold = newThr;
    // 用於抑制編譯器產生警告資訊
    @SuppressWarnings({"rawtypes","unchecked"})
    	// 在建構函式時，並沒有建立陣列，在第一次呼叫put方法，導致resize的時候，才會把陣列建立出來。
    	// 這是為了延遲載入，提高效率。
        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;
                // 如果第一個元素的下一個元素為null，說明連結串列只有一個
                if (e.next == null)
                	// 則直接用它的hash值和新陣列的容量取模就行(這樣運算效率高)，得到新的下標位置
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是紅黑樹
                else if (e instanceof TreeNode)
                	// 則拆分紅黑樹，這個小編就不帶著往下深究了,感興趣可以自己點進去看看
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 說明是連結串列且長度大於1
                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值和oldCap做與運算為0，則原位置不變
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 不為0則把資料移動到新位置
                        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;
}

5、get和containsKey方法解讀

/**
* 根據key獲取對應的value
*/
public V get(Object key) {
    Node<K,V> e;
    // 呼叫後存在就獲取元素的value返回
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 判斷key是否在map中存在
*/
public boolean containsKey(Object key) {
	// 呼叫方法存在及不為null
    return getNode(hash(key), key) != null;
}
/**
* 我們發現底層都是getNode來進行幹活的
*/
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 判斷陣列不能為空，然後取到當前hash值計算出來的下標位置的第一個元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果hash值和key都相等並不為null，則說明我們要找的就是第一個元素
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            // 返回第一個元素
            return first;
        // 如果不是第一個就接著往下找
        if ((e = first.next) != null) {
        	// 如果是紅黑樹
            if (first instanceof TreeNode)
                // 則以紅黑樹的查詢方式進行獲取到我們想要的key對應的值
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 這裡說明為普通連結串列，我們依次往下找即可
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 找不到key對應的值，返回null
    return null;
}

6、remove方法解讀

/**
 * 如果key存在，就把元素刪除
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * 刪除方法的具體實現
* @param hash   			經過hash運算後的key
* @param key    			你要移除的key
* @param value  			你要移除的value
 * @param matchValue 		如果為真，則僅在值相等時刪除，我們為FALSE，key相同即刪除
 * @param movable 			如果為假，則在刪除時不要移動其他節點，我們為TRUE，刪除移動其他節點
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 判斷table不為空，連結串列不為空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 陣列中的第一個節點就是我們要刪除的節點
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 要刪除的節點給node
            node = p;
        // 第一個不是，並且後面還有節點
        else if ((e = p.next) != null) {
            // 如果是紅黑樹
            if (p instanceof TreeNode)
            	// 在紅黑樹中找到返回
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
            	// 遍歷連結串列
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        // 找到要刪除的node
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 這裡說明我們要刪除的節點已找到
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果為紅黑樹，就按紅黑樹進行刪除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //我們要刪除的是頭節點
            else if (node == p)
                 tab[index] = node.next;// 由於刪除的是首節點，那麼直接將節點陣列對應位置指向到第二個節點即可
            //不是頭節點，將當前節點指向刪除節點的下一個節點
            else
                p.next = node.next;// p的下一個節點指向到node的下一個節點即可把node從連結串列中刪除了
            // 操作+1
            ++modCount;
            // map大小-1
            --size;
            // 空的實現
            afterNodeRemoval(node);
            // 返回刪除的節點
            return node;
        }
    }
    return null;
}

六、總結

Has和Map得底層還是很多的，裡面用的一些邏輯和演演算法，都是很牛皮的、耐人琢磨的。oracle裡的人才還是厲害啊，你看都看不明白，人家就能設計出來，實現出來。真的是你我皆為螻蟻，只不過是一個個搬磚工具人呀。哈哈，對自己的一個自嘲哈，共勉！！看到這裡了，點個贊吧，小編碼字實屬不易呀！！謝謝了！！

環境大家關注小編的微信公眾號！謝謝大家!

推廣自己網站時間到了！！！

點選存取！歡迎存取，裡面也是有很多好的文章哦！