作者： 一字馬胡
轉(zhuǎn)載標(biāo)志 【2017-11-03】

更新日志

零、閱讀說明

文章 Java HashMap源碼深度分析 深度分析了HashMap的源碼，其中也分析了在并發(fā)環(huán)境下HashMap會發(fā)生什么情況。

一、Map概述

我們都知道HashMap是線程不安全的，但是HashMap的使用頻率在所有map中確實(shí)屬于比較高的。因?yàn)樗梢詽M足我們大多數(shù)的場景了。

Map類繼承圖

上面展示了java中Map的繼承圖，Map是一個(gè)接口，我們常用的實(shí)現(xiàn)類有HashMap、LinkedHashMap、TreeMap，HashTable。HashMap根據(jù)key的hashCode值來保存value，需要注意的是，HashMap不保證遍歷的順序和插入的順序是一致的。HashMap允許有一條記錄的key為null，但是對值是否為null不做要求。HashTable類是線程安全的，它使用synchronize來做線程安全，全局只有一把鎖，在線程競爭比較激烈的情況下hashtable的效率是比較低下的。因?yàn)楫?dāng)一個(gè)線程訪問hashtable的同步方法時(shí)，其他線程再次嘗試訪問的時(shí)候，會進(jìn)入阻塞或者輪詢狀態(tài)，比如當(dāng)線程1使用put進(jìn)行元素添加的時(shí)候，線程2不但不能使用put來添加元素，而且不能使用get獲取元素。所以，競爭會越來越激烈。相比之下，ConcurrentHashMap使用了分段鎖技術(shù)來提高了并發(fā)度，不在同一段的數(shù)據(jù)互相不影響，多個(gè)線程對多個(gè)不同的段的操作是不會相互影響的。每個(gè)段使用一把鎖。所以在需要線程安全的業(yè)務(wù)場景下，推薦使用ConcurrentHashMap，而HashTable不建議在新的代碼中使用，如果需要線程安全，則使用ConcurrentHashMap，否則使用HashMap就足夠了。

LinkedHashMap屬于HashMap的子類，與HashMap的區(qū)別在于LinkedHashMap保存了記錄插入的順序。TreeMap實(shí)現(xiàn)了SortedMap接口，TreeMap有能力對插入的記錄根據(jù)key排序，默認(rèn)按照升序排序，也可以自定義比較強(qiáng)，在使用TreeMap的時(shí)候，key應(yīng)當(dāng)實(shí)現(xiàn)Comparable。

二、HashMap的實(shí)現(xiàn)

java7和java8在實(shí)現(xiàn)HashMap上有所區(qū)別，當(dāng)然java8的效率要更好一些，主要是java8的HashMap在java7的基礎(chǔ)上增加了紅黑樹這種數(shù)據(jù)結(jié)構(gòu)，使得在桶里面查找數(shù)據(jù)的復(fù)雜度從O(n)降到O(logn)，當(dāng)然還有一些其他的優(yōu)化，比如resize的優(yōu)化等。
介于java8的HashMap較為復(fù)雜，本文將基于java7的HashMap實(shí)現(xiàn)來說明，主要的實(shí)現(xiàn)部分還是一致的，java8的實(shí)現(xiàn)上主要是做了一些優(yōu)化，內(nèi)容還是沒有變化的，依然是線程不安全的。
HashMap的實(shí)現(xiàn)使用了一個(gè)數(shù)組，每個(gè)數(shù)組項(xiàng)里面有一個(gè)鏈表的方式來實(shí)現(xiàn)，因?yàn)镠ashMap使用key的hashCode來尋找存儲位置，不同的key可能具有相同的hashCode，這時(shí)候就出現(xiàn)哈希沖突了，也叫做哈希碰撞，為了解決哈希沖突，有開放地址方法，以及鏈地址方法。HashMap的實(shí)現(xiàn)上選取了鏈地址方法，也就是將哈希值一樣的entry保存在同一個(gè)數(shù)組項(xiàng)里面，可以把一個(gè)數(shù)組項(xiàng)當(dāng)做一個(gè)桶，桶里面裝的entry的key的hashCode是一樣的。

HashMap的結(jié)構(gòu)模型（java8）

上面的圖片展示了我們的描述，其中有一個(gè)非常重要的數(shù)據(jù)結(jié)構(gòu)Node<K,V>，這就是實(shí)際保存我們的key-value對的數(shù)據(jù)結(jié)構(gòu)，下面是這個(gè)數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容：

        final int hash;    
        final K key;
        V value;
        Node<K,V> next;   

一個(gè)Node就是一個(gè)鏈表節(jié)點(diǎn)，也就是我們插入的一條記錄，明白了HashMap使用鏈地址方法來解決哈希沖突之后，我們就不難理解上面的數(shù)據(jù)結(jié)構(gòu)，hash字段用來定位桶的索引位置，key和value就是我們的數(shù)據(jù)內(nèi)容，需要注意的是，我們的key是final的，也就是不允許更改，這也好理解，因?yàn)镠ashMap使用key的hashCode來尋找桶的索引位置，一旦key被改變了，那么key的hashCode很可能就會改變了，所以隨意改變key會使得我們丟失記錄（無法找到記錄）。next字段指向鏈表的下一個(gè)節(jié)點(diǎn)。

HashMap的初始桶的數(shù)量為16，loadFact為0.75,當(dāng)桶里面的數(shù)據(jù)記錄超過閾值的時(shí)候，HashMap將會進(jìn)行擴(kuò)容則操作，每次都會變?yōu)樵瓉泶笮〉?倍，直到設(shè)定的最大值之后就無法再resize了。

下面對HashMap的實(shí)現(xiàn)做簡單的介紹，具體實(shí)現(xiàn)還得看代碼，對于java8中的HashMap實(shí)現(xiàn)，還需要能理解紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。

1、根據(jù)key的hashCode來決定應(yīng)該將該記錄放在哪個(gè)桶里面，無論是插入、查找還是刪除，這都是第一步，計(jì)算桶的位置。因?yàn)镠ashMap的length總是2的n次冪，所以可以使用下面的方法來做模運(yùn)算：

h&(length-1)

h是key的hashCode值，計(jì)算好hashCode之后，使用上面的方法來對桶的數(shù)量取模，將這個(gè)數(shù)據(jù)記錄落到某一個(gè)桶里面。當(dāng)然取模是java7中的做法，java8進(jìn)行了優(yōu)化，做得更加巧妙，因?yàn)槲覀兊膌ength總是2的n次冪，所以在一次resize之后，當(dāng)前位置的記錄要么保持當(dāng)前位置不變，要么就向前移動(dòng)length就可以了。所以java8中的HashMap的resize不需要重新計(jì)算hashCode。我們可以通過觀察java7中的計(jì)算方法來抽象出算法，然后進(jìn)行優(yōu)化，具體的細(xì)節(jié)看代碼就可以了。

2、HashMap的put方法

HashMap的put方法處理邏輯（java8）

上圖展示了java8中put方法的處理邏輯，比java7多了紅黑樹部分，以及在一些細(xì)節(jié)上的優(yōu)化，put邏輯和java7中是一致的。

3、resize機(jī)制

HashMap的擴(kuò)容機(jī)制就是重新申請一個(gè)容量是當(dāng)前的2倍的桶數(shù)組，然后將原先的記錄逐個(gè)重新映射到新的桶里面，然后將原先的桶逐個(gè)置為null使得引用失效。后面會講到，HashMap之所以線程不安全，就是resize這里出的問題。

三、為什么HashMap線程不安全

上面說到，HashMap會進(jìn)行resize操作，在resize操作的時(shí)候會造成線程不安全。下面將舉兩個(gè)可能出現(xiàn)線程不安全的地方。

1、put的時(shí)候?qū)е碌亩嗑€程數(shù)據(jù)不一致。
這個(gè)問題比較好想象，比如有兩個(gè)線程A和B，首先A希望插入一個(gè)key-value對到HashMap中，首先計(jì)算記錄所要落到的桶的索引坐標(biāo)，然后獲取到該桶里面的鏈表頭結(jié)點(diǎn)，此時(shí)線程A的時(shí)間片用完了，而此時(shí)線程B被調(diào)度得以執(zhí)行，和線程A一樣執(zhí)行，只不過線程B成功將記錄插到了桶里面，假設(shè)線程A插入的記錄計(jì)算出來的桶索引和線程B要插入的記錄計(jì)算出來的桶索引是一樣的，那么當(dāng)線程B成功插入之后，線程A再次被調(diào)度運(yùn)行時(shí)，它依然持有過期的鏈表頭但是它對此一無所知，以至于它認(rèn)為它應(yīng)該這樣做，如此一來就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為。

2、另外一個(gè)比較明顯的線程不安全的問題是HashMap的get操作可能因?yàn)閞esize而引起死循環(huán)（cpu100%），具體分析如下：

下面的代碼是resize的核心內(nèi)容：

void transfer(Entry[] newTable, boolean rehash) {  
        int newCapacity = newTable.length;  
        for (Entry<K,V> e : table) {  
  
            while(null != e) {  
                Entry<K,V> next = e.next;           
                if (rehash) {  
                    e.hash = null == e.key ? 0 : hash(e.key);  
                }  
                int i = indexFor(e.hash, newCapacity);   
                e.next = newTable[i];  
                newTable[i] = e;  
                e = next;  
            } 
        }  
    }  

這個(gè)方法的功能是將原來的記錄重新計(jì)算在新桶的位置，然后遷移過去。

多線程HashMap的resize

我們假設(shè)有兩個(gè)線程同時(shí)需要執(zhí)行resize操作，我們原來的桶數(shù)量為2，記錄數(shù)為3，需要resize桶到4，原來的記錄分別為：[3,A],[7,B],[5,C]，在原來的map里面，我們發(fā)現(xiàn)這三個(gè)entry都落到了第二個(gè)桶里面。
假設(shè)線程thread1執(zhí)行到了transfer方法的Entry next = e.next這一句，然后時(shí)間片用完了，此時(shí)的e = [3,A], next = [7,B]。線程thread2被調(diào)度執(zhí)行并且順利完成了resize操作，需要注意的是，此時(shí)的[7,B]的next為[3,A]。此時(shí)線程thread1重新被調(diào)度運(yùn)行，此時(shí)的thread1持有的引用是已經(jīng)被thread2 resize之后的結(jié)果。線程thread1首先將[3,A]遷移到新的數(shù)組上，然后再處理[7,B]，而[7,B]被鏈接到了[3,A]的后面，處理完[7,B]之后，就需要處理[7,B]的next了啊，而通過thread2的resize之后，[7,B]的next變?yōu)榱薣3,A]，此時(shí)，[3,A]和[7,B]形成了環(huán)形鏈表，在get的時(shí)候，如果get的key的桶索引和[3,A]和[7,B]一樣，那么就會陷入死循環(huán)。

如果在取鏈表的時(shí)候從頭開始取（現(xiàn)在是從尾部開始?。┑脑挘瑒t可以保證節(jié)點(diǎn)之間的順序，那樣就不存在這樣的問題了。

綜合上面兩點(diǎn)，可以說明HashMap是線程不安全的。