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

hashMap

        JAVA7 hashMap 結構如下圖所示：

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

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

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

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

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

        JAVA8 hashMap 結構如下圖所示：

ConcurrentHashMap

        ConcurrentHashMap 和 HashMap 思路是(shì)差不多的，但(dàn)是(shì)因爲它支持并發操作，所以要複雜(zá)一些。整個 ConcurrentHashMap 由一個個 Segment 組成，Segment 代表”部分“或”一段“的意思，所以很多地方都會将其描述爲分段鎖。注意，行文中，我很多地方用了“槽”來代表一個 segment。 

線(xiàn)程安全（Segment 繼承 ReentrantLock 加鎖）簡單理解就是(shì)，ConcurrentHashMap 是(shì)一個 Segment 數組，Segment 通過繼承 ReentrantLock 來進行加鎖，所以每次需要加鎖的操作鎖住的是(shì)一個 segment，這樣隻要保證每個 Segment 是(shì)線(xiàn)程安全的，也就實現(xiàn)了全局的線(xiàn)程安全。

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

        Java8 實現(xiàn) （引入了紅黑樹(shù)） Java8 對 ConcurrentHashMap 進行了比較大的改動,Java8 也引入了紅黑樹(shù)。