15泄朴、HashMap工作原理和擴容機制

1. HashMap工作原理

HashMap作為優(yōu)秀的Java集合框架中的一個重要的成員晶姊，在很多編程場景下為我們所用。HashMap作為數(shù)據(jù)結(jié)構(gòu)散列表的一種實現(xiàn)伪货，就其工作原理來講單獨列出一篇博客來講都是不過分的们衙。由于本文主要是簡單總結(jié)其擴容機制，因此對于HashMap的實現(xiàn)原理僅做簡單的概述碱呼。

HashMap內(nèi)部實現(xiàn)是一個桶數(shù)組蒙挑，每個桶中存放著一個單鏈表的頭結(jié)點。其中每個結(jié)點存儲的是一個鍵值對整體（Entry）窗市，HashMap采用拉鏈法解決哈希沖突（關(guān)于哈希沖突后面會介紹）稻据。

由于Java8對HashMap的某些地方進行了優(yōu)化蕾域，以下的總結(jié)和源碼分析都是基于Java7。

示意圖如下：

20171119123859600.png

HashMap提供兩個重要的基本操作馋袜，put(K, V)和get(K)。

當(dāng)調(diào)用put操作時舶斧，HashMap計算鍵值K的哈希值欣鳖，然后將其對應(yīng)到HashMap的某一個桶(bucket)上；此時找到以這個桶為頭結(jié)點的一個單鏈表茴厉，然后順序遍歷該單鏈表找到某個節(jié)點的Entry中的Key是等于給定的參數(shù)K泽台；若找到，則將其的old V替換為參數(shù)指定的V矾缓；否則直接在鏈表尾部插入一個新的Entry節(jié)點怀酷。

put函數(shù)大致的思路為：

1、對key的hashCode()做hash而账，然后再計算index;
2胰坟、如果沒碰撞直接放到bucket里；
3、如果碰撞了笔横，以鏈表的形式存在buckets后竞滓；
4、如果碰撞導(dǎo)致鏈表過長(大于等于5吹缔、TREEIFY_THRESHOLD)商佑，就把鏈表轉(zhuǎn)換成紅黑樹；
5厢塘、如果節(jié)點已經(jīng)存在就替換old value(保證key的唯一性)
6茶没、如果bucket滿了(超過load factor*current capacity)，就要resize晚碾。

public V put(K key, V value) {
    // HashMap允許存放null鍵和null值抓半。
    // 當(dāng)key為null時，調(diào)用putForNullKey方法格嘁，將value放置在數(shù)組第一個位置笛求。
    if (key == null)
        return putForNullKey(value);
    // 根據(jù)key的keyCode重新計算hash值。
    int hash = hash(key.hashCode());
    // 搜索指定hash值在對應(yīng)桶中的索引糕簿。
    int i = indexFor(hash, table.length);
    // 如果 i 索引處的 Entry 不為 null探入，通過遍歷桶外掛的單鏈表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            // 如果發(fā)現(xiàn)已有該鍵值，則存儲新的值懂诗，并返回原始值
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引處的Entry為null蜂嗽，表明此處還沒有Entry。
    modCount++;
    //遍歷單鏈表完畢殃恒，沒有找到與鍵相對的Entry植旧，需要新建一個Entry放在單鏈表中，
    //如果該桶不為空且數(shù)量達到筏值芋类，有可能觸發(fā)擴容
    addEntry(hash, key, value, i);
    return null;
}

對于get(K)操作類似于put操作隆嗅，HashMap通過計算鍵的哈希值，先找到對應(yīng)的桶侯繁，然后遍歷桶存放的單鏈表通過比照Entry的鍵來找到對應(yīng)的值胖喳。

get函數(shù)大致的思路為

1、桶里的第一個節(jié)點（不存在單鏈表）贮竟，直接獲壤龊浮；
2咕别、如果有沖突技健，則通過key.equals(k)去查找對應(yīng)的entry
若為樹，則在樹中通過key.equals(k)查找惰拱，O(logn)雌贱；
若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)欣孤。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != 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) {
            // 在樹中g(shù)et
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 在鏈表中g(shù)et
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

頻繁產(chǎn)生哈希沖突最重要的原因就像是要存儲的Entry太多馋没，而桶不夠，這和供不應(yīng)求的矛盾類似降传。因此篷朵，當(dāng)HashMap中的存儲的Entry較多的時候，我們就要考慮增加桶的數(shù)量婆排，這樣對于后續(xù)要存儲的Entry來講声旺，就會大大緩解哈希沖突。

因此就涉及到HashMap的擴容段只，上面算是回答了為什么擴容腮猖，那么什么時候擴容？擴容多少赞枕？怎么擴容缚够？便是第二部分要總結(jié)的了

2. HashMap擴容

2.1 HashMap的擴容時機

在使用HashMap的過程中，我們經(jīng)常會遇到這樣一個帶參數(shù)的構(gòu)造方法鹦赎。

public HashMap(int initialCapacity, float loadFactor) ;

第一個參數(shù)：初始容量，指明初始的桶的個數(shù)误堡；相當(dāng)于桶數(shù)組的大小古话。
第二個參數(shù)：裝載因子，是一個0-1之間的系數(shù)锁施，根據(jù)它來確定需要擴容的閾值陪踩，默認(rèn)值是0.75。
阿里巴巴開發(fā)手冊中就有這么一條說明：

image.png

還記得上面講解put函數(shù)時悉抵，如果遍歷單鏈表都沒有找到對應(yīng)的Entry嗎肩狂？這時候調(diào)用了一個addEntry(hash, key, value, i)函數(shù)，在單鏈表中增加一個Entry姥饰。

 void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
          //當(dāng)size大于等于某一個閾值thresholdde時候且該桶并不是一個空桶傻谁；
          /*這個這樣說明比較好理解：因為size 已經(jīng)大于等于閾 值了，說明Entry數(shù)量較多列粪，哈希沖突嚴(yán)重审磁， 
            那么若該Entry對應(yīng)的桶不是一個空桶，這個Entry的加入必然會把原來的鏈表拉得更長岂座，因此需要擴容态蒂；
            若對應(yīng)的桶是一個空桶，那么此時沒有必要擴容费什。*/
            //將容量擴容為原來的2倍
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            //擴容后的钾恢，該hash值對應(yīng)的新的桶位置
            bucketIndex = indexFor(hash, table.length);
        }
        //在指定的桶位置上，創(chuàng)建一個新的Entry
        createEntry(hash, key, value, bucketIndex);
    }
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);//鏈表的頭插法插入新建的Entry
       //更新size
        size++;
    }

size記錄的是map中包含的Entry的數(shù)量
而threshold記錄的是需要resize的閾值且 threshold = loadFactor * capacity
capacity 其實就是桶的長度

threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

因此現(xiàn)在總結(jié)出擴容的時機：

當(dāng)map中包含的Entry的數(shù)量大于等于threshold = loadFactor * capacity的時候，且新建的Entry剛好落在一個非空的桶上瘩蚪，此刻觸發(fā)擴容機制泉懦，將其容量擴大為2倍。

當(dāng)size大于等于threshold的時候募舟，并不一定會觸發(fā)擴容機制(比如增加的entry對應(yīng)的是一個空桶祠斧，那直接加載空桶里面，如果對應(yīng)的不是空桶拱礁，會將鏈表拉長琢锋，就會觸發(fā)擴容)，但是會很可能就觸發(fā)擴容機制呢灶，只要有一個新建的Entry出現(xiàn)哈希沖突吴超，則立刻resize。

3. 總結(jié)

我們現(xiàn)在可以回答開始的幾個問題鸯乃，加深對HashMap的理解：

什么時候會使用HashMap鲸阻？他有什么特點？
是基于Map接口的實現(xiàn)缨睡，存儲鍵值對時鸟悴，它可以接收null的鍵值，是非同步的奖年，HashMap存儲著Entry(hash, key, value, next)對象细诸。
你知道HashMap的工作原理嗎？
HashMap 實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)陋守，即數(shù)組和鏈表的結(jié)合體震贵。它是基于哈希表的 Map 接口的非同步實現(xiàn)。
他是基于hashing算法的原理水评，通過put(key猩系，value)和get(key)方法儲存和獲取值的。

存：我們將鍵值對K/V 傳遞給put()方法中燥，它調(diào)用K對象的hashCode()方法來計算hashCode從而得到bucket位置寇甸，之后儲存Entry對象。（HashMap是在bucket中儲存鍵對象和值對象褪那，作為Map.Entry）
扔姆住：獲取對象時，我們傳遞鍵給get()方法博敬，然后調(diào)用K的hashCode()方法從而得到hashCode進而獲取到bucket位置友浸，再調(diào)用K的equals()方法從而確定鍵值對，返回值對象偏窝。

碰撞：當(dāng)兩個對象的hashcode相同時收恢，它們的bucket位置相同武学，‘碰撞’就會發(fā)生。如何解決伦意，就是利用鏈表結(jié)構(gòu)進行存儲火窒，即HashMap使用LinkedList存儲對象。但是當(dāng)鏈表長度大于8（默認(rèn)）時驮肉，就會把鏈表轉(zhuǎn)換為紅黑樹熏矿，在紅黑樹中執(zhí)行插入獲取操作。

擴容：如果HashMap的大小超過了負(fù)載因子定義的容量离钝，就會進行擴容票编。默認(rèn)負(fù)載因子為0.75。就是說卵渴，當(dāng)一個map填滿了75%的bucket時候慧域，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組（jdk1.6，但不超過最大容量）浪读，來重新調(diào)整map的大小昔榴，并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing碘橘，因為它調(diào)用hash方法找到新的bucket位置互订。

3、為什么擴容要以2的倍數(shù)擴容痘拆？
答案當(dāng)然是為了性能屁奏。在HashMap通過鍵的哈希值進行定位桶位置的時候，調(diào)用了一個indexFor(hash, table.length);方法错负。

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

&為位與運算符
可以看到這里是將哈希值h與桶數(shù)組的length-1（實際上也是map的容量-1）進行了一個與操作得出了對應(yīng)的桶的位置，h & (length-1)勇边。

但是為什么不采用h % length這種計算方式呢犹撒？
因為Java的%、/操作比&慢10倍左右粒褒，因此采用&運算會提高性能识颊。

通過限制length是一個2的冪數(shù)，h & (length-1)和h % length結(jié)果是一致的奕坟。這就是為什么要限制容量必須是一個2的冪的原因祥款。

舉個簡單的例子說明這兩個操作的結(jié)果一致性：

假設(shè)有個hashcode是311，對應(yīng)的二進制是(1 0011 0111)

length為16月杉，對應(yīng)的二進制位(1 0000)

%操作：311 = 16*19 + 7刃跛；所以結(jié)果為7，二進制位(0111)苛萎；

&操作：(1 0011 0111) & (0111) = 0111 = 7, 二進制位(0111)

1 0011 0111 = (1 0011 0000) + (0111) = (12^4 + 1 2^5 + 02^6 + 02^7 + 12^8 ) + 7 = 2^4(1 + 2 + 0 + 0 + 16) + 7 = 16 * 19 + 7; 和%操作一致桨昙。
如果length是一個2的冪的數(shù)检号，那么length-1就會變成一個mask, 它會將hashcode低位取出來，hashcode的低位實際就是余數(shù)蛙酪，和取余操作相比齐苛，與操作會將性能提升很多。
總體來說就是規(guī)定lengh是2的冪數(shù)桂塞，可以在調(diào)用indexFor方法獲取桶的角標(biāo)時凹蜂，采用位與運算，位與運算比取余運算性能會高很多阁危。

15、HashMap工作原理和擴容機制