Java -- 每日一問：對比 Hashtable、HashMap、TreeMap 有什麼不同？

典型回答

Hashtable、HashMap、TreeMap 都是最常見的一些 Map 實作，是以鍵值對的形式存儲和操作資料的容器類型。

Hashtable 是早期 Java 類庫提供的一個哈希表實作，本身是同步的，不支援 null 鍵和值，由于同步導緻的性能開銷，是以已經很少被推薦使用。

HashMap 是應用更加廣泛的哈希表實作，行為上大緻上與 HashTable 一緻，主要差別在于 HashMap 不是同步的，支援 null 鍵和值等。通常情況下，HashMap 進行 put 或者 get 操作，可以達到常數時間的性能，是以它是絕大部分利用鍵值對存取場景的首選，比如，實作一個使用者 ID 和使用者資訊對應的運作時存儲結構。

TreeMap 則是基于紅黑樹的一種提供順序通路的 Map，和 HashMap 不同，它的 get、put、remove 之類操作都是 O（log(n)）的時間複雜度，具體順序可以由指定的 Comparator 來決定，或者根據鍵的自然順序來判斷。

高手回答

三者均實作了Map接口，存儲的内容是基于key-value的鍵值對映射，一個映射不能有重複的鍵，一個鍵最多隻能映射一個值。

（1） 元素特性

HashTable中的key、value都不能為null；HashMap中的key、value可以為null，很顯然隻能有一個key為null的鍵值對，但是允許有多個值為null的鍵值對；TreeMap中當未實作 Comparator 接口時，key 不可以為null；當實作 Comparator 接口時，若未對null情況進行判斷，則key不可以為null，反之亦然。

（2）順序特性

HashTable、HashMap具有無序特性。TreeMap是利用紅黑樹來實作的（樹中的每個節點的值，都會大于或等于它的左子樹種的所有節點的值，并且小于或等于它的右子樹中的所有節點的值），實作了SortMap接口，能夠對儲存的記錄根據鍵進行排序。是以一般需要排序的情況下是選擇TreeMap來進行，預設為升序排序方式（深度優先搜尋），可自定義實作Comparator接口實作排序方式。

（3）初始化與增長方式

初始化時：HashTable在不指定容量的情況下的預設容量為11，且不要求底層數組的容量一定要為2的整數次幂；HashMap預設容量為16，且要求容量一定為2的整數次幂。

擴容時：Hashtable将容量變為原來的2倍加1；HashMap擴容将容量變為原來的2倍。

（4）線程安全性

HashTable其方法函數都是同步的（采用synchronized修飾），不會出現兩個線程同時對資料進行操作的情況，是以保證了線程安全性。也正因為如此，在多線程運作環境下效率表現非常低下。因為當一個線程通路HashTable的同步方法時，其他線程也通路同步方法就會進入阻塞狀态。比如當一個線程在添加資料時候，另外一個線程即使執行擷取其他資料的操作也必須被阻塞，大大降低了程式的運作效率，在新版本中已被廢棄，不推薦使用。

HashMap不支援線程的同步，即任一時刻可以有多個線程同時寫HashMap;可能會導緻資料的不一緻。如果需要同步（1）可以用 Collections的synchronizedMap方法；（2）使用ConcurrentHashMap類，相較于HashTable鎖住的是對象整體， ConcurrentHashMap基于lock實作鎖分段技術。首先将Map存放的資料分成一段一段的存儲方式，然後給每一段資料配置設定一把鎖，當一個線程占用鎖通路其中一個段的資料時，其他段的資料也能被其他線程通路。ConcurrentHashMap不僅保證了多線程運作環境下的資料通路安全性，而且性能上有長足的提升。