3.3 Map

Map是一種由多組key-value（鍵值對）集合在一起的結構，其中，key值是不能重復的，而value值則無此限定。其基本接口為java.util.Map，該接口提供了Map結構的關鍵方法，比如常見的put和get，下面將分別介紹Map的多種不同的實現類。

3.3.1 HashMap

HashMap是最常用的Map結構，Map的本質是鍵值對。它使用數組來存放這些鍵值對，鍵值對與數組下標的對應關系由key值的hashcode來決定，這種類型的數據結構可以稱之為哈希桶。

在Java語言中，hashCode是個int值，雖然int的取值范圍是[-232，231-1]，但是Java的數組下標只能是正數，所以該哈希桶能存儲[0,231-1]區間的哈希值。這個存儲區間可以存儲的數據足足有20億之多，可是在實際應用中，hashCode會傾向于集中在某個區域內，這就導致了大量的hashCode重復，這種重復又被稱為哈希沖突。

下面的代碼介紹了hashCode在HashMap中的作用：

程序的運行結果為：

從上述運行結果可以觀察到三個現象：

1）hashCode一致的HS類并沒有發生沖突，兩個HS對象都被正常的存入了HashMap；

2）hashCode一致，同時equals返回true的對象發生了沖突，第三個HS對象替代了第一個；

3）重寫了hashCode使之不一致，同時equals返回true的對象，也沒有發生沖突，被正確的存入了HashMap。

這三個現象說明，當且僅當hashCode一致，且equals比對一致的對象，才會被HashMap認為是同一個對象。

這似乎和之前介紹的哈希沖突的概念有些矛盾，下面將通過對HashMap的源碼進行分析，以闡述HashMap的實現原理和哈希沖突的解決方案。

需要注意的是，Java8對HashMap做過重大修改，下面將分別解析兩種實現的區別。

3.3.2 Java8之前的HashMap

在Java7及之前的版本中，HashMap的底層實現是數組和鏈表，結構如3-4所示：

HashMap采用Entry數組來存儲key-value對，每一個鍵值對組成了一個Entry實體，Entry類實際上是一個單向的鏈表結構，它具有Next指針，可以連接下一個Entry實體，以此來解決Hash沖突的問題，因為HashMap是按照key的hash值來計算Entry在HashMap中存儲的位置的，如果hash值相同，而key內容不相等，那么就用鏈表來解決這種hash沖突。

在HashMap中，數據都是以鍵值對的形式存在的，其鍵值所對應的hashcode將會作為其在數組里的下標。例如，字符串“1”的hashcode經過計算得到51，那么，在它被作為鍵值存入HashMap后，table[51]對應的Entry.key就是“1”。

思考一個問題，如果另一個Object對象對應的hashcode也是51，那么它和上面的字符串同時存入HashMap的時候，會怎么處理？

答案是，它會被存入鏈表里，和之前的字符串同時存在。當需要查找指定對象的時候，會先找到hashcode對應的下標，然后遍歷鏈表，調用對象的equals方法進行比較從而找到對應的對象。

由于數組的查找比鏈表要快，于是，可以得出一個結論：

盡可能使鍵值的hashcode分散，這樣可以提高HashMap的查詢效率。

當添加鍵值對的時候，如果鍵值對將要占用的位置不是null，并且size>=threshold，那么會啟動HashMap的擴容方法resize(2*table.length)，擴容之后會重新計算一次hash和下標。

擴容resize()主要完成以下工作：

1）根據新的容量，確定新的擴容閾值（threshold）大小。如果當前的容量已經達到了最大容量（1<<30)，那么把threshold設為Integer最大值；反之，則用新計算出來的容量乘以加載因子（loadFactor），計算結果和最大容量+1比較大小，取較小者為新的擴容閾值。

Integer最大值為0x7fffffff，如果threshold被設置為最大整型數，那么它必然大于size，擴容操作不會再次觸發。而容量*加載因子得到的是一個小于容量的數（加載因子必須小于1大于0），以它為閾值則說明，加載因子的大小對HashMap影響很大，太小了會導致HashMap頻繁擴容，太大了會導致空間的浪費。0.75是Java提供的建議值。

2）重新計算當前所有結點轉移到新table數組后的下標。

通過上面的分析可以得出下面的結論：

1）HashMap執行寫操作（put）的時候，比較消耗資源的是遍歷鏈表，擴容數組操作；

2）HashMap執行讀操作（get）的時候，比較消耗資源的是遍歷鏈表。

影響遍歷鏈表的因素是鏈表的長度，在HashMap中，鏈表的長度由哈希碰撞的頻率決定。

哈希碰撞的頻率受數組長度所決定，長度越長，則碰撞的概率越小，但長度越長，閑置的內存空間越多。所以，擴容數組操作的結果也會影響哈希碰撞的頻率，需要在時間和空間上取得一個平衡點。

哈希碰撞的頻率又受key值的hashCode()方法影響，所計算得出的hashCode的獨特性越高，哈希碰撞的概率也會變低。

鏈表的遍歷中，需要調用key值的equals方法，不合理的equals實現會導致HashMap效率低下甚至調用異常。

因此，要提高HashMap的使用效率，可以從以下幾個方面入手：

1）根據實際的業務需求，測試出合理的loadFactor，否則會始終使用Java建議的0.75；

2）合理的重寫鍵值對象的hashCode和equals方法，equals和hashCode方法的主要特性見表3-1，可以參考《Effective Java中文版》一書中的建議。

3.3.3 Java8提供的HashMap

Java8的HashMap數據結構發生了較大的變化，之前的HashMap使用的數組+鏈表來實現，新的HashMap里，雖然依然使用的是table數組，但是數據類型發生了變化：Java8里的HashMap使用的是數組+樹+鏈表的結構。如圖3-5所示（R表示紅色，B表示黑色）：

在添加鏈表結點后，如果鏈表深度達到或超過建樹閾值（TREEIFY_THRESHOLD-1)，那么會把整個鏈表重構為樹。注意，TREEIFY_THRESHOLD是一個常量，值固定為8。也就是說，當鏈表長度達到7的時候，會轉化為樹結構，為什么要這樣設計？該樹是一棵紅黑樹，由于鏈表的查找的時間復雜度是O(n)，而紅黑樹的查找的時間復雜度是O(log2n)的，數值太小的時候，它們的查找效率相差無幾，Java8認為7是一個合適的閾值，因此這個值被用來決定是否要從鏈表結構轉化為樹結構。

綜上所述，HashMap采用hash算法來決定Map中key的存儲，hash表里可以存儲元素的位置稱為桶，如果通過key計算hash值發生沖突時，那么將采用鏈表（或樹）的形式來存儲元素。HashMap的擴容操作是一項很耗時的任務，所以如果能估算Map的容量，最好給它一個默認初始值，避免進行多次擴容。HashMap的線程是不安全的，多線程環境中推薦使用ConcurrentHashMap。

3.3.4 TreeMap

與HashMap組合了數組、鏈表和紅黑樹相比，TreeMap是完全由紅黑樹實現的。HashMap通過hashcode對其內容進行快速查找，而TreeMap中所有的元素都保持著某種固定的順序，當需要得到一個有序的結果的時候就應該使用TreeMap。下面將簡要介紹一下TreeMap的實現原理。

（1）成員變量

TreeMap的主要成員變量包括：

（2）構造方法

TreeMap有四個構造方法：

1）public TreeMap()。無參構造，初始化comparator=null；

2）public TreeMap(Comparator<? super K>comparator)。比較器構造，使用外部傳入的比較器；

3）public TreeMap(Map<? extends K, ? extends V>m)。使用傳入的Map初始化TreeMap的內容；

4）public TreeMap(SortedMap<K, ? extends V>m)。使用SortedMap初始化TreeMap內容，同時使用SortedMap的比較器來初始化TreeMap比較器。

（3）put方法

put的實現思路非常清晰：

1）如果TreeMap是空的，那么使用指定數據作為根結點；

2）反之，如果comparetor不為空，那么使用comparetor來決定插入位置；如果comparetor為空，那么認為key值實現了Comparable，直接調用compareTo方法來決定插入位置；如果key沒有實現Comparable，那么拋出ClassCastException；

3）插入完成后，修復紅黑樹。

TreeMap的使用示例代碼如下：

程序運行結果為：

3.3.5 LinkedhashMap

通過上面的講解可以看出HashMap中存儲元素的位置是根據hashcode來決定的，以此數據的存儲是無序的，也就是說迭代HashMap的順序并不是HashMap放置的順序。顯然，在需要保持順序的場景中HashMap就不可用了。LinkedHashMap的出現恰好可以解決這個順序的問題，它雖然增加了時間和空間上的開銷，但是通過維護一個額外雙向鏈表，LinkedHashMap保證了元素迭代的順序。該迭代順序可以是插入順序或者是訪問順序。下面簡要地介紹它的內部實現原理。

3.3.6 Java8之前的LinkedHashMap

（1）成員變量

除了與HashMap類似的部分實現外，LinkedHashMap有以下兩個需要特別注意的成員變量：

LinkedHashMap的存儲中包含了一個額外的雙向鏈表結構，header既是頭又是尾，可以視作一個環狀鏈表，但它本身只是個表頭標記，不包含數據域。其結構如圖所示3-6所示。

由圖3-6可知，LinkedHashMap可以像HashMap一樣的使用，同時它為每個數據結點的引用多維護了一份鏈表，從而可以達到有序訪問的目的。

（2）createEntry(hash,key,value,index)方法

LinkedHashMap和HashMap的第一個主要區別體現在createEntry方法上。

HashMap的createEntry執行的是創建Hash桶里的鏈表結點，代碼如下所示：

LinkedHashMap的createEntry除了完成HashMap的功能外，還把該鏈表結點的引用插入到了header環形鏈表里，實現源碼如下所示：

（3）如何使用LinkedHashMap

查閱LinkedHashMap的API，可以注意到LinkedHashMap沒有提供新的公開方法。那么，它的鏈表特性怎么體現呢？

參考下面三種方法：

這三種方法分別提供給keySet()、values()和entrySet()使用。

LinkedHashMap通過對這三種方法進行重寫使上述三種方法產生的集合可以按照插入順序排列。

3.3.7 Java8中的LinkedHashMap

關鍵變量有以下三個：

與歷史版本的LinkedHashMap的實現方法不同，head和tail分別維護在了兩個引用里，這讓LinkedHashMap的結構發生了變化，實現原理如圖3-7所示。

由圖3-7可以發現，LinkedHashMap新版本的實現與HashMap新版本的實現類似，也是采用了鏈表與二叉樹組合的方式來實現。原理上與歷史版本的LinkedHashMap并沒有區別。

（1）linkNodeLast方法

newNode方法與newTreeNode方法源自HashMap，是用來新建結點的。在LinkedHashMap中，重寫了這兩個方法，負責在創建結點的同時插入鏈表，實現了保存數據結點副本到雙向鏈表里的功能。

在這兩個方法的實現中，關鍵實現是對linkNodeLast方法的調用。

linkNodeLast方法源碼如下所示，參數p為新創建的結點：

（2）transferLinks方法

replacementNode方法和replacementTreeNode方法負責替換指定結點，對這兩個方法的重寫保證了在結點替換時，同時維護好它們在雙向鏈表里的原始插入順序。

在LinkedHashMap里，它們會額外調用transferLinks方法。該方法源碼如下所示：

（3）如何使用LinkedHashMap

得益于Java8的Function包的引入，從Java8開始，LinkedHashMap有了更方便的使用方式，以下是forEach和replaceAll方法源碼：

對LinkedHashMap的遍歷可以采用更簡便的方法實現，示例代碼如下所示：

運行結果為：

常見面試筆試真題：

如何用LinkedHashMap實現LRU？

答案：LRU是Least Recently Used的縮寫，表示最近最少使用，它是一種緩存策略。當緩存有大小限制而數據量比較大的時候，就無法把所有數據都放在緩存中，因此就需要一種策略來把緩存中的部分數據置換出去。LRU就是其中的一種思路，其主要思路為：

1）新訪問的數據插入到緩存隊列中；

2）當有新數據要加入到緩存中，但是緩存已滿，這時候就淘汰隊尾數據；

3）如果緩存中的數據被再次訪問，則將數據移到隊列首。

LinkedHashMap自身已經實現了順序存儲，而且通過Hash的方法把數據分配到不同的槽中，從而提高了訪問效率。正常情況下是按照元素的添加順序存儲，當然也可以指定按照訪問的順序來存儲，最近被訪問的數據會放在最前面，而且LinkedHashMap還有一個判斷是否刪除最老數據的方法，默認是返回false，表示不刪除數據，可以通過重寫這個方法來修改刪除策略。下面首先介紹為了實現LRU而需要使用到的兩種重要的方法：

從這兩個方法的描述可以看出，要通過LinkedHashMap實現LRU，只需要做到下面兩點：

1）使用構造方法的時候，第三個參數指定true表示按照訪問順序存儲；

2）重寫removeEldestEntry方法使得當Map達到LRU的容量的時候返回true從而能刪除最老的數據。

示例代碼如下：

程序運行結果為：

3.3.8 Hashtable

Hashtable的實現與HashMap很類似，Java8的Hashtable稍有不同，但整體流程是沒有變化的。

Hashtable的put過程大致如下所示：

1）計算key值的hashcode；

2）根據hashcode計算下標；

3）如果存在hashcode和key值完全相等的value，那么替換它并返回；

4）反之，如果總數據數超出了擴容閾值，那么對數組擴容，并重新計算所有的數據結點的下標；

5）為新數據創建新結點。

可以看出，Hashtable和HashMap基本put流程是一致的，那么它們的區別在哪里？

下面以put方法為例來介紹Hashtable的實現源碼如下所示：

作為對比，看看HashMap的put實現：

從源碼可以看出Hashtable的實現方式被synchronized修飾，由此可見Hashtable是線程安全的，而HashMap是線程不安全的；此外Hashtable不能存放null作為key值，HashMap會把null key存放在下標0位置。

雖然Hashtable是“線程安全”的，但在多線程環境下并不推薦使用。因為采用synchronized方式實現的多線程安全的容器在高并發量的情況下效率比較低，Java還引入了專門在高并發量的情況下使用的并發容器，這種容器由于在實現的時候采用了更加細粒度的鎖，由此在高并發量的情況下有著更好的性能。在后面的章節中，將會對部分并發容器的詳細解析。

3.3.9 WeakHashMap

WeakHashMap是一種弱引用的HashMap，弱引用指的是WeakHashMap中的key值如果沒有外部強引用，那么在垃圾回收的時候，WeakHashMap的對應內容也會被移除掉。

在講解WeakHashMap之前，需要了解Java中與引用相關的類：

ReferenceQueue（引用隊列），與某個引用類綁定，當引用死亡后，會進入這個隊列。

HardReference（強引用），任何以類似String str=new String()建立起來的引用，都是強引用。在str指向另一個對象或者null之前，該String對象都不會被GC（Garbage Collector垃圾回收器）回收；

WeakReference（弱引用），可以通過java.lang.ref.WeakReference來建立弱引用，當GC要求回收對象時，它不會阻止對象被回收，也就是說即使有弱引用存在，該對象也會立刻被回收；

SoftReference（軟引用），可以通過java.lang.ref.SoftReference來建立，與弱引用類似，當GC要求回收時，它不會阻止對象被回收，但不同的是它對回收過程會被延遲，必須要等到JVM heap內存不夠用，接近產生OutOfMemory錯誤時，才會被回收；

PhantomReference（虛引用），可以通過java.lang.ref.PhantomPeference來建立，這種類型的引用很特別，在大多數時間里，無法通過它拿到其引用的對象，但是，當這個對象消失的時候，該引用還是會進入ReferenceQueue隊列。

下面提供一個例子來分別說明它們的作用：

在這個例子里，分別創建了弱引用、虛引用和軟引用，get()方法用于獲取它們引用的Ref對象，可以注意到，Ref對象在外部并沒有任何引用，所以，在某個時間點，GC應當會回收對象。來看看代碼執行的結果：

可以看到，弱引用和軟引用的對象還是可達的，但是虛引用是不可達的。被回收的引用沒有內容，說明GC還沒有回收它們。

這證實了虛引用的性質：虛引用非常弱，以至于它自己也找不到自己的引用內容。

對之前的代碼進行修改，在輸出內容前加入代碼：

再執行一次，得到結果：

現在可達的引用只剩下Soft了，引用隊列里多出了兩個引用，說明WeakReference和PhantomReference的對象被回收。

再修改一次代碼，讓WeakPeference和PhantomReference去引用一個強引用對象：

輸出結果如下所示：

這證實了弱引用的性質：弱引用的對象，如果沒有被強引用，那么在垃圾回收后，引用對象會不可達。

WeakHashMap的實現方式

WeakHashMap利用了ReferenceQueue和WeakReference來實現它的核心功能：當key值沒有強引用的時候，會從WeakHashMap里移除。

在源碼實現中，WeakHashMap維護了一個ReferenceQueue，保存了所有存在引用的Key對象。WeakHashMap.Entry<K,V>中并沒有保存Key，只是將Key與ReferenceQueue進行了關聯。

下面首先介紹WeakHashMap的鍵值對實體類WeakHashMap.Entry的實現：

對于這個類有以下兩個需要注意的方面：

1）Entry繼承自WeakReference；

2）Entry本身沒有保存key值，而是把key直接交給了父類WeakReference來構造。

參考通常的WeakReference，Entry的key值是一個弱引用，只能通過WeakHashMap#get來獲取。獲取代碼如下所示：

WeakHashMap實現清除無強引用實體的方法是expungStaleEntries()，它會將ReferenceQueue中所有失效的引用從Map中去除。其源碼實現如下所示：

這個去除操作的主要原理為：當WeakHashMap中的某個弱引用被GC回收時，被回收的這個弱引用會被添加到WeakHashMap維護了的ReferenceQueue（queue）中。因此，當expungeStaleEntries方法被調用的時候，就可以遍歷queue中所有的key，然后在WeakReference的table中找到與key對應的鍵值對并從table中刪除。

expungStaleEntries()方法會在resize、put、get、forEach方法中被調用。

3.3.10 HashMap、HashTable、TreeMap和WeakHashMap的區別

Java為數據結構中的映射定義了一個接口java.util.Map，它有三個主要的實現類：HashMap、Hashtable和TreeMap。Map是用來存儲鍵值對的數據結構，在數組中通過數組下標來對其內容索引的，而在Map中，則是通過對象來進行索引，用來索引的對象稱為key，其對應的對象稱為value。

HashMap是一個最常用的Map，它根據鍵的hashCode值存儲數據，根據鍵可以直接獲取它的值，具有很快的訪問速度。由于HashMap與HashTable都采用了hash方法進行索引，因此二者具有許多相似之處，它們主要有如下的一些區別：

1）HashMap是Hashtable的輕量級實現（非線程安全的實現），它們都完成了Map接口，主要區別在于HashMap允許空（null）鍵值（key）（但需要注意，最多只允許一條記錄的鍵為null，不允許多條記錄的值為null），而Hashtable不允許。

2）HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因為contains方法容易讓人引起誤解。Hashtable繼承自Dictionary類，而HashMap是Java1.2引進的Map interface的一個實現。

3）Hashtable的方法是線程安全的，而HashMap由于不支持線程的同步，所以它不是線程安全的。在多個線程訪問Hashtable時，不需要開發人員對它進行同步，而對于HashMap，開發人員必須提供額外的同步機制。所以，效率上HashMap可能高于Hashtable。

4）HashTable使用Enumeration，HashMap使用Iterator。

5）Hashtable和HashMap采用的hash/rehash算法都幾乎一樣，所以性能上不會有很大的差異。

6）HashTable中hash數組默認大小是11，增加的方式是old*2+1。在HashMap中，hash數組的默認大小是16，而且一定是2的指數。

7）hash值的使用不同，HashTable直接使用對象的hashCode，而HashMap則在key的hashCode基礎上重寫計算了一個新的hash值。

以上三種類型中，使用最多的是HashMap。HashMap里面存入的鍵值對在取出的時候沒有固定的順序，是隨機的。一般而言，在Map中插入、刪除和定位元素，HashMap是最好的選擇。由于TreeMap實現了SortMap接口，能夠把它保存的記錄按照鍵排序，所以，取出來的是排序后的鍵值對，如果需要按自然順序或自定義順序遍歷鍵，那么TreeMap會更好。LinkedHashMap是HashMap的一個子類，如果需要輸出的順序和輸入的相同，那么用LinkedHashMap可以實現，它還可以按讀取順序來排列。

WeakHashMap與HashMap類似，不同之處在于WeakHashMap中key采用的是“弱引用”的方式，只要WeakHashMap中的key不再被外部引用，它就可以被垃圾回收器回收。而HashMap中key采用的是“強引用的方式”，當HashMap中的key沒有被外部引用時，只有在這個key從HashMap中刪除后，才可以被垃圾回收器回收。

3.3.11 用自定義類型作為HashMap或Hashtable的key需要注意的問題

HashMap與Hashtble是用來存放鍵值對的一種容器，在使用這兩個容器的時候有個限制：不能用來存儲重復的鍵，也就是說每個鍵只能唯一映射一個值，當有重復的鍵出現，則不會創建新的映射關系，而會使用先前的鍵。示例代碼如下。

程序運行結果為：

從上面的例子可以看出，首先向HashMap中添加<"aaa", "bbb">，接著添加<"aaa", "ccc">的時候由于與前面已經添加的數據有相同的key："aaa"，因此會用新的值"ccc"替換"bbb"。

但是當用自定義的類的對象作為HashMap的key的時候，有時候會造成一種假象：key是可以重復的。如下例所示。

程序運行結果為：

從表面上看，向HashMap中添加的兩個鍵值對的key值是相同的，可是為什么在后面添加的鍵值對沒有覆蓋前面的value呢？為了說明這個問題，下面首先介紹HashMap添加元素的操作過程。具體而言，在向HashMap中添加鍵值對<key，value>的時候，需要經過如下幾個步驟：首先，調用key的hashCode()方法生成一個哈希值h1，如果這個h1在HashMap中不存在，那么直接將<key，value>添加到HashMap中，如果這個h1已經存在，那么找出HashMap中所有哈希值為h1的key，然后分別調用key的equls()方法判斷當前添加的key值是否與已經存在的key值相同，如果equals()方法返回true，說明當前需要添加的key已經存在，那么HashMap會使用新的value值來覆蓋掉舊的value值。如果equals()方法返回false，說明新增加的key在HashMap中不存在，因此會在HashMap中創建新的映射關系。當新增加的key的hash值已經在HashMap中存在的時候，就會產生沖突。一般而言，對于不同的key值可能會得到相同的hash值，因此就需要對沖突進行處理。一般而言，處理沖突的方法有開放地址法、再哈希法、鏈地址法等。HashMap使用的是鏈地址法來解決沖突（為了容易理解，這里以Java8之前的實現方式為例），具體操作方法如圖3-8（一）所示。

向HashMap中添加元素時，當有沖突產生的時候，其實現方式如圖3-9（二）所示：

從HashMap中通過key查找value的時候，首先調用的是key的hashCode()方法來獲取到key對應的hash值h，這樣就可以確定鍵為key的所有值存儲的首地址。如果h對應的key值有多個，那么程序接著會遍歷所有的key，通過調用key的equals()方法來判斷key的內容是否相等。只有當equals()方法的返回值為true時，對應的value才是正確的結果。

在上例中，由于使用自定義的類作為HashMap的key，而沒有重寫hashCode()方法和equals()方法，默認使用的是Object類的hashCode()方法和equals()方法。Object類的equals()方法的比較規則為：當參數obj引用的對象與當前對象為同一個對象時，就返回true，否則返回false。hashCode()方法會返回對象存儲的內存地址。由于在上例中創建了兩個對象，雖然它們擁有相同的內容，但是存儲在內存中不同的地址，因此在向HashMap中添加對象的時候，調用equals()方法的返回值為false，HashMap會認為它們是兩個不同的對象，會分別創建不同的映射關系。因此為了實現在向HashMap中添加鍵值對的時候，可以根據對象的內容來判斷兩個對象是否相等，就需要重寫hashCode()方法和equals()方法。如下例所示。

程序輸出結果為：

由此可以看出，在使用自定義類作為HashMap的key的時候需要注意以下幾個問題：

1）如果想根據對象的相關屬性來自定義對象是否相等的邏輯，此時就需要重寫equals()方法，一旦重寫了equals()方法，那么就必須重寫hashCode()方法。

2）當自定義類想作為HashMap(HashTable)的key時，最好把這個類設計為不可變類。

3）從hashMap的工作原理可以看出，如果兩個對象相等，那么這兩個對象有著相同的hashCode。反之則不成立。

3.3.12 ConcurrentHashMap

ConcurrentHashMap是HashMap中支持高并發、高吞吐量的線程安全的版本。它由Segment數組結構和HashEntry數組結構組成。Segment在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵值對數據。一個ConcurrentHashMap里包含一個Segment數組，Segment的結構和HashMap類似，是一種數組和鏈表結構，一個Segment里包含一個HashEntry數組，每個HashEntry是一個鏈表結構的元素，每個Segment守護著一個HashEntry數組里的元素，當對HashEntry數組的數據進行修改時，必須首先獲得它對應的Segment鎖。

Hashtable和ConcurrentHashMap存儲的內容為鍵值對（key-value），且它們都是線程安全的容器，下面通過簡要介紹它們的實現方式來對比它們的不同點。

Hashtable所有的方法都是同步的，因此，它是線程安全的。它的定義如下所示：

Hashtable是通過“拉鏈法”實現的哈希表，因此，它使用數組+鏈表（或鏈表+二叉樹）的方式來存儲實際的元素。這里以“數組+鏈表”的實現方式為例，如圖3-10所示。

在圖3-10中，最頂部標數字的部分是一個Entry數組，而Entry又是一個鏈表。當向Hashtable中插入數據的時候，首先通過鍵的hashcode和Entry數組的長度來計算這個值應該存放在數組中的位置index，如果index對應的位置沒有存放值，那么直接存放到數組的index位置即可，當index有沖突的時候，則采用“拉鏈法”來解決沖突。假如想往Hashtable中插入"aaa"、"bbb"、"eee"、"fff"，如果"aaa"和"fff"所得到的index是相同的，那么插入后Hashtable的結構如圖3-11所示。

Hashtable的實現類圖如圖3-12所示。

為了使Hashtable擁有比較好的性能，數組的大小也需要根據實際插入數據的多少來進行動態地調整，Hashtable類中定義了一個rehash方法，該方法可以用來動態地擴充Hashtable的容量，該方法被調用的時機為：Hashtable中的鍵值對超過某一閥值。默認情況下，該閥值等于Hashtable中Entry數組的長度*0.75。Hashtable默認的大小為11，當達到閥值后，每次按照下面的公式對容量進行擴充：newCapacity=oldCapacity*2+1。

Hashtable通過使用synchronized修飾方法的方式來實現多線程同步，因此，Hashtable的同步會鎖住整個數組，在高并發的情況下，性能會非常差，Java5中引入java.util.concurrent.ConcurrentHashMap作為高吞吐量的線程安全HashMap實現，它采用了鎖分離的技術允許多個修改操作并發進行。它們在多線程鎖的使用方式如圖3-13和圖3-14所示。

ConcurrentHashMap采用了更細粒度的鎖來提高在高并發情況下的效率。ConcurrentHashMap將Hash表默認分為16個桶（每一個桶可以被看作是一個Hashtable），大部分操作都沒有用到鎖，而對應的put、remove等操作也只需要鎖住當前線程需要用到的桶，而不需要鎖住整個數據。采用這種設計方式以后，在高并發的情況下，同時可以有16個線程來訪問數據。顯然，大大提高了并發性。

只有個別方法（例如：size()方法和containsValue()方法）可能需要鎖定整個表而不僅僅是某個桶，在實現的時候，需要“按順序”鎖定所有桶，操作完畢后，又“按順序”釋放所有桶，“按順序”的好處是能防止死鎖的發生。

假設一個線程在讀取數據的時候，另外一個線程在Hash鏈的中間添加或刪除元素或者修改某一個結點的值，此時必定會讀取到不一致的數據。那么如何才能實現在讀取的時候不加鎖卻又不會讀取到不一致的數據呢？ConcurrentHashMap使用不變量的方式實現，它通過把Hash鏈中的結點HashEntry設計成幾乎不可變的方式來實現，HashEntry的定義如下所示：

從以上這個定義可以看出，除了變量value以外，其他變量都被定義為final類型。因此，增加結點（put方法）的操作只能在Hash鏈的頭部增加。對于刪除操作，則無法直接從Hash鏈的中間刪除結點，因為next也被定義為不可變量。因此，remove操作的實現方式如下所示：把需要刪除的結點前面所有的結點都復制一遍，然后把復制后的Hash鏈的最后一個結點指向待刪除結點的后繼結點，由此可以看出，ConcurrentHashMap刪除操作是比較耗時的。此外，使用volatile修飾value的方式使這個值被修改后對所有線程都可見（編譯器不會進行優化），采用這種方式的好處如下所示：一方面，避免了加鎖；另一方面，如果把value也設計為不可變量（用final修飾），那么每次修改value的操作都必須刪除已有結點，然后插入新的結點，顯然，此時的效率會非常低下。

由于volatile只能保證變量所有的寫操作都能立即反映到其他線程之中，也就是說volatile變量在各個線程中是一致的，但是由于volatile不能保證操作的原子性，因此它不是線程安全的。如下例所示：

程序的運行結果如下。

從上述運行結果可以看出，單線程運行的時候map.put(1, map.get(1) + 1);會被執行100次，因此運行結果是100。當使用多線程運行的時候，在上述代碼中使用了5個線程，也就是說map.put(1, map.get(1)+1);會被調用500次，如果這個容器是多線程安全的，那么運行結果應該是500，但是實際的運行結果并不都是500。說明在ConcurrentHashMap在某種情況下還是線程不安全的，這個例子中導致線程不安全的主要原因為：

map.put(1, map.get(1)+1);不是一個原子操作，而是包含了下面三個操作：

1）map.get(1)；這一步是原子操作，由CocurrentHashMap來保證線程安全；

2）+1操作；

3）map.put操作。這一步也是原子操作，由CocurrentHashMap來保證線程安全。

假設map中的值為<1,5>。線程1在執行map.put(1, map.get(1) + 1)的時候首先通過get操作讀取到map中的值為5，此時線程2也在執行map.put(1, map.get(1) + 1)，從map中讀取到的值也是5，接著線程1執行+1操作，然后把運算結果通過put操作放入map中，此時map中的值為<1,6>；接著線程2執行+1操作，然后把運算結果通過put操作放入map中，此時map中的值還是<1,6>。由此可以看出，兩個線程分別執行了一次map.put(1, map.get(1)+1)，map中的值卻值增加了1。

因此在訪問ConcurrentHashMap中value的時候，為了保證多線程安全，最好使用一些原子操作。如果要使用類似map.put(1, map.get(1)+1)的非原子操作，那么需要通過加鎖來實現多線程安全。

在上例中，為了保證多線程安全，可以把run方法改為：