HashMap 根據鍵的(de) hashCode 值存儲數據，大(dà)多(duō)數情況下(xià)可(kě)以直接定位到它的(de)值，因而具有很快(kuài)的(de)訪問速度，但遍曆順序卻是不确定的(de)。 HashMap 最多(duō)隻允許一條記錄的(de)鍵爲 null，允許多(duō)條記錄的(de)值爲 null。HashMap 非線程安全，即任一時(shí)刻可(kě)以有多(duō)個(gè)線程同時(shí)寫 HashMap，可(kě)能會導緻數據的(de)不一緻。如果需要滿足線程安全，可(kě)以用(yòng) Collections 的(de) synchronizedMap 方法使 HashMap 具有線程安全的(de)能力，或者使用(yòng) ConcurrentHashMap。我們用(yòng)下(xià)面這(zhè)張圖來(lái)介紹 HashMap 的(de)結構。

hashMap

        JAVA7 hashMap 結構如下(xià)圖所示：

        大(dà)方向上，HashMap 裏面是一個(gè)數組，然後數組中每個(gè)元素是一個(gè)單向鏈表。上圖中，每個(gè)綠色的(de)實體是嵌套類 Entry 的(de)實例，Entry 包含四個(gè)屬性：key, value, hash 值和(hé)用(yòng)于單向鏈表的(de) next。 

1. capacity：當前數組容量，始終保持 2^n，可(kě)以擴容，擴容後數組大(dà)小爲當前的(de) 2 倍。

2. loadFactor：負載因子，默認爲 0.75。

3. 3. threshold：擴容的(de)阈值，等于 capacity * loadFactor

        Java8 對(duì) HashMap 進行了(le)一些修改，最大(dà)的(de)不同就是利用(yòng)了(le)紅黑(hēi)樹，所以其由 數組+鏈表+紅黑(hēi)樹 組成。根據 Java7 HashMap 的(de)介紹，我們知道，查找的(de)時(shí)候，根據 hash 值我們能夠快(kuài)速定位到數組的(de)具體下(xià)标，但是之後的(de)話(huà)，需要順著(zhe)鏈表一個(gè)個(gè)比較下(xià)去才能找到我們需要的(de)，時(shí)間複雜(zá)度取決于鏈表的(de)長(cháng)度，爲 O(n)。爲了(le)降低這(zhè)部分(fēn)的(de)開銷，在 Java8 中，當鏈表中的(de)元素超過了(le) 8 個(gè)以後，會将鏈表轉換爲紅黑(hēi)樹，在這(zhè)些位置進行查找的(de)時(shí)候可(kě)以降低時(shí)間複雜(zá)度爲 O(logN)。 

        JAVA8 hashMap 結構如下(xià)圖所示：

ConcurrentHashMap

        ConcurrentHashMap 和(hé) HashMap 思路是差不多(duō)的(de)，但是因爲它支持并發操作，所以要複雜(zá)一些。整個(gè) ConcurrentHashMap 由一個(gè)個(gè) Segment 組成，Segment 代表”部分(fēn)“或”一段“的(de)意思，所以很多(duō)地方都會将其描述爲分(fēn)段鎖。注意，行文中，我很多(duō)地方用(yòng)了(le)“槽”來(lái)代表一個(gè) segment。 

線程安全（Segment 繼承 ReentrantLock 加鎖）簡單理(lǐ)解就是，ConcurrentHashMap 是一個(gè) Segment 數組，Segment 通(tōng)過繼承 ReentrantLock 來(lái)進行加鎖，所以每次需要加鎖的(de)操作鎖住的(de)是一個(gè) segment，這(zhè)樣隻要保證每個(gè) Segment 是線程安全的(de)，也(yě)就實現了(le)全局的(de)線程安全。

        concurrencyLevel：并行級别、并發數、Segment 數，怎麽翻譯不重要，理(lǐ)解它。默認是 16， 也(yě)就是說 ConcurrentHashMap 有 16 個(gè) Segments，所以理(lǐ)論上，這(zhè)個(gè)時(shí)候，最多(duō)可(kě)以同時(shí)支 持 16 個(gè)線程并發寫，隻要它們的(de)操作分(fēn)别分(fēn)布在不同的(de) Segment 上。這(zhè)個(gè)值可(kě)以在初始化(huà)的(de)時(shí) 候設置爲其他(tā)值，但是一旦初始化(huà)以後，它是不可(kě)以擴容的(de)。再具體到每個(gè) Segment 内部，其實 每個(gè) Segment 很像之前介紹的(de) HashMap，不過它要保證線程安全，所以處理(lǐ)起來(lái)要麻煩些。

        Java8 實現 （引入了(le)紅黑(hēi)樹） Java8 對(duì) ConcurrentHashMap 進行了(le)比較大(dà)的(de)改動,Java8 也(yě)引入了(le)紅黑(hēi)樹。