HashMap的原理和內(nèi)部存儲結(jié)構(gòu)介紹

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

本文將通過如下簡單的代碼來分析HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)的變化過程。

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 數(shù)據(jù)結(jié)構(gòu)說明

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

下面說明一下幾個(gè)字段的含義

1.1 table

// HashMap內(nèi)部使用這個(gè)數(shù)組存儲所有鍵值對
transient Node<K,V>[] table;

Node的結(jié)構(gòu)如下：

可以發(fā)現(xiàn)，Node其實(shí)是一個(gè)鏈表，通過next指向下一個(gè)元素。

1.2 size

記錄了HashMap中鍵值對的數(shù)量

1.3 modCount

記錄了HashMap在結(jié)構(gòu)上更改的次數(shù)，包括可以更改鍵值對數(shù)量的操作，例如put、remove，還有可以修改內(nèi)部結(jié)構(gòu)的操作，例如rehash。

1.4 threshold

記錄一個(gè)臨界值，當(dāng)已存儲鍵值對的個(gè)數(shù)大于這個(gè)臨界值時(shí)，需要擴(kuò)容。

1.5 loadFactor

負(fù)載因子，通常用于計(jì)算threshold，threshold=總?cè)萘?loadFactor。

2 new HashMap

new HashMap的源碼如下：

/**
* The load factor used when none specified in constructor.
* 負(fù)載因子，當(dāng) 已使用容量 > 總?cè)萘?nbsp;* 負(fù)載因子 時(shí)，需要擴(kuò)容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

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

此時(shí)，HashMap只初始化了負(fù)載因子（使用默認(rèn)值0.75），并沒有初始化table數(shù)組。 其實(shí)HashMap使用的是延遲初始化策略，當(dāng)?shù)谝淮蝡ut的時(shí)候，才初始化table（此時(shí)table是null）。

3 table數(shù)組的初始化

當(dāng)?shù)谝淮蝡ut的時(shí)候，HashMap會判斷當(dāng)前table是否為空，如果是空，會調(diào)用resize方法進(jìn)行初始化。 resize方法會初始化一個(gè)容量大小為16 的數(shù)組，并賦值給table。

并計(jì)算threshold=16*0.75=12。

此時(shí)table數(shù)組的狀態(tài)如下：

4 put過程

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

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

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

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

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

繼續(xù)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");

此時(shí)size=12，下一次put后size為13，大于當(dāng)前threshold，將觸發(fā)擴(kuò)容（resize）

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

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

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

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

HashMap會創(chuàng)建一個(gè)新的Node，并放到table[3]鏈表的最后面。

此時(shí)table狀態(tài)如下：

5 resize擴(kuò)容

此時(shí)table中一共有13個(gè)元素，已經(jīng)超過了threshold(12)，需要對table調(diào)用resize方法擴(kuò)容。

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

下面主要介紹一下復(fù)制的過程（并不是原封不動(dòng)的復(fù)制，Node的位置可能發(fā)生變化）

先來看源碼：

for (int j = 0; j < oldCap; ++j) { // oldCap：舊table的大小 =16
    Node<K,V> e;
    if ((e = oldTab[j]) != null) { // oldTab：舊table的備份
        oldTab[j] = null;
        // 如果數(shù)組中的元素沒有后繼節(jié)點(diǎn)，直接計(jì)算新的索引值，并將Node放到新數(shù)組中
        if (e.next == null)
            newTab[e.hash & (newCap - 1)] = e;
        // 忽略這個(gè)else if。其實(shí)，如果鏈表的長度超過8，HashMap會把這個(gè)鏈表變成一個(gè)樹結(jié)構(gòu)，樹結(jié)構(gòu)中的元素是TreeNode
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        // 有后繼節(jié)點(diǎn)的情況
        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】遍歷鏈表，計(jì)算鏈表每一個(gè)節(jié)點(diǎn)在新table中的位置。

計(jì)算位置的方式如下：

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

因?yàn)閛ldCap=16，二進(jìn)制的表現(xiàn)形式為0001 0000，任何數(shù)&16，如果等于0，那么這個(gè)數(shù)的第五個(gè)二進(jìn)制位必然為0。

以當(dāng)前狀態(tài)來說，新的容量是32，那么table的最大index是31，31的二進(jìn)制表現(xiàn)形式是00011111。

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

假設(shè)Node的hash = 01101011，那么

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

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

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

假設(shè)Node的hash = 01111011，那么

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

上一個(gè)例子的hash值01101011跟這個(gè)例子的hash值01111011只是在第5位二進(jìn)制上不同，可以發(fā)現(xiàn)，這兩個(gè)值在舊的table中，是在同一個(gè)index中的，如下：

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

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

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

擴(kuò)容后，table狀態(tài)如下所示：

最終，重新分配完所有的Node后，擴(kuò)容結(jié)束。

到此，關(guān)于“HashMap的原理和內(nèi)部存儲結(jié)構(gòu)介紹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！