HashMap的原理和內部存儲結構介紹

這篇文章主要介紹“HashMap的原理和內部存儲結構介紹”，在日常操作中，相信很多人在HashMap的原理和內部存儲結構介紹問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”HashMap的原理和內部存儲結構介紹”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

本文將通過如下簡單的代碼來分析HashMap的內部數據結構的變化過程。

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    for (int i = 0; i < 50; i++) {
        map.put("key" + i, "value" + i);
    }
}

1 數據結構說明

HashMap中本文需要用到的幾個字段如下：

下面說明一下幾個字段的含義

1.1 table

// HashMap內部使用這個數組存儲所有鍵值對
transient Node<K,V>[] table;

Node的結構如下：

可以發現，Node其實是一個鏈表，通過next指向下一個元素。

1.2 size

記錄了HashMap中鍵值對的數量

1.3 modCount

記錄了HashMap在結構上更改的次數，包括可以更改鍵值對數量的操作，例如put、remove，還有可以修改內部結構的操作，例如rehash。

1.4 threshold

記錄一個臨界值，當已存儲鍵值對的個數大于這個臨界值時，需要擴容。

1.5 loadFactor

負載因子，通常用于計算threshold，threshold=總容量*loadFactor。

2 new HashMap

new HashMap的源碼如下：

/**
* The load factor used when none specified in constructor.
* 負載因子，當 已使用容量 > 總容量 * 負載因子 時，需要擴容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

此時，HashMap只初始化了負載因子（使用默認值0.75），并沒有初始化table數組。 其實HashMap使用的是延遲初始化策略，當第一次put的時候，才初始化table（此時table是null）。

3 table數組的初始化

當第一次put的時候，HashMap會判斷當前table是否為空，如果是空，會調用resize方法進行初始化。 resize方法會初始化一個容量大小為16 的數組，并賦值給table。

并計算threshold=16*0.75=12。

此時table數組的狀態如下：

4 put過程

map.put("key0", "value0");

首先計算key的hash值，hash("key0") = 3288451

計算這次put要存入數組位置的索引值：index=(數組大小 - 1) & hash = 3

判斷 if (table[index] == null) 就new一個Node放到這里，此時為null，所以直接new Node放到3上，此時table如下：

然后判斷當前已使用容量大小(size)是否已經超過臨界值threshold，此時size=1，小于12，不做任何操作，put方法結束（如果超過臨界值，需要resize擴容）。

繼續put。。。

map.put("key1", "value1");

map.put("key1", "value1");
map.put("key2", "value2");
map.put("key3", "value3");
map.put("key4", "value4");
map.put("key5", "value5");
map.put("key6", "value6");
map.put("key8", "value7");
map.put("key9", "value9");
map.put("key10", "value10");
map.put("key11", "value11");

此時size=12，下一次put后size為13，大于當前threshold，將觸發擴容（resize）

map.put("key12", "value12");

計算Key的hash值，hash("key12")=101945043，計算要存入table位置的索引值 = (總大小 - 1) & hash = (16 - 1) & 101945043 = 3

從目前的table狀態可知，table[3] != null，但此時要put的key與table[3].key不相等，我們必須要把他存進去，此時就產生了哈希沖突（哈希碰撞）。

這時鏈表就派上用場了，HashMap就是通過鏈表解決哈希沖突的。

HashMap會創建一個新的Node，并放到table[3]鏈表的最后面。

此時table狀態如下：

5 resize擴容

此時table中一共有13個元素，已經超過了threshold(12)，需要對table調用resize方法擴容。

HashMap會創建一個容量為之前兩倍(162=32)的table，并將舊的Node復制到新的table中，新的臨界值(threshold)為24(320.75)。

下面主要介紹一下復制的過程（并不是原封不動的復制，Node的位置可能發生變化）

先來看源碼：

for (int j = 0; j < oldCap; ++j) { // oldCap：舊table的大小 =16
    Node<K,V> e;
    if ((e = oldTab[j]) != null) { // oldTab：舊table的備份
        oldTab[j] = null;
        // 如果數組中的元素沒有后繼節點，直接計算新的索引值，并將Node放到新數組中
        if (e.next == null)
            newTab[e.hash & (newCap - 1)] = e;
        // 忽略這個else if。其實，如果鏈表的長度超過8，HashMap會把這個鏈表變成一個樹結構，樹結構中的元素是TreeNode
        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;
                // 【說明1】
                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;
                //【說明2】
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}

【說明1】遍歷鏈表，計算鏈表每一個節點在新table中的位置。

計算位置的方式如下：

1）如果節點的 (hash & oldCap) == 0，那么該節點還在原來的位置上，為什么呢？

因為oldCap=16，二進制的表現形式為0001 0000，任何數&16，如果等于0，那么這個數的第五個二進制位必然為0。

以當前狀態來說，新的容量是32，那么table的最大index是31，31的二進制表現形式是00011111。

計算index的方式是 hash & (容量 - 1)，也就是說，新index的計算方式為 hash & (32 - 1)

假設Node的hash = 01101011，那么

  01101011
& 00011111
----------
  00001011 = 11

2）下面再對比(hash & oldCap) != 0的情況

如果節點的(hash & oldCap) != 0，那么該節點的位置=舊index + 舊容量大小

假設Node的hash = 01111011，那么

  01111011
& 00011111
----------
  00011011 = 27

上一個例子的hash值01101011跟這個例子的hash值01111011只是在第5位二進制上不同，可以發現，這兩個值在舊的table中，是在同一個index中的，如下：

  01101011
& 00001111
----------
  00001011 = 11

  01111011
& 00001111
----------
  00001011 = 11

由于擴容總是以2倍的方式進行，也就是：舊容量 << 1，這也就解釋了【說明2】，當(hash & oldCap) != 0時，這個Node的新index = 舊index + 舊容量大小。

擴容后，table狀態如下所示：

最終，重新分配完所有的Node后，擴容結束。

到此，關于“HashMap的原理和內部存儲結構介紹”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！