HashMap 和 Hashtable、HashSet

一.HashMap 和 Hashtable 的差別

1. 線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 内部的方法基本都經過

   synchronized 修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧！）；

2. 效率： 因為線程安全的問題，HashMap 要比 HashTable 效率高一點。另外，HashTable 基本被淘汰，不要在

   代碼中使用它；

3. 對Null key 和Null value的支援： HashMap 中，null 可以作為鍵，這樣的鍵隻有一個，可以有一個或多個鍵

   所對應的值為 null。。但是在 HashTable 中 put 進的鍵值隻要有一個 null，直接抛出 NullPointerException。 4. 初始容量大小和每次擴充容量大小的不同 ： ①建立時如果不指定容量初始值，Hashtable 預設的初始大小為

   11，之後每次擴充，容量變為原來的2n+1。HashMap 預設的初始化大小為16。之後每次擴充，容量變為原來

   的2倍。②建立時如果給定了容量初始值，那麼 Hashtable 會直接使用你給定的大小，而 HashMap 會将其擴充

   為2的幂次方大小（HashMap 中的 tableSizeFor() 方法保證，下面給出了源代碼）。也就是說 HashMap 總

   是使用2的幂作為哈希表的大小,後面會介紹到為什麼是2的幂次方。

4. 底層資料結構： JDK1.8 以後的 HashMap 在解決哈希沖突時有了較大的變化，當連結清單長度大于門檻值（預設為

   8）時，将連結清單轉化為紅黑樹，以減少搜尋時間。Hashtable 沒有這樣的機制。

二.HashMap 的長度為什麼是2的幂次方

為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把資料配置設定均勻。我們上面也講到了過了，Hash 值的範圍值-2147483648到2147483647，前後加起來大概40億的映射空間，隻要哈希函數映射得比較均勻松散，一般應

用是很難出現碰撞的。但問題是一個40億長度的數組，記憶體是放不下的。是以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的餘數才能用來要存放的位置也就是對應的數組下标。這個數組下标的計算

方法是“ (n - 1) & hash ”。（n代表數組長度）。這也就解釋了 HashMap 的長度為什麼是2的幂次方。

這個算法應該如何設計呢？

我們首先可能會想到采用%取餘的操作來實作。但是，重點來了：“取餘(%)操作中如果除數是2的幂次則等價于與其除數減一的與(&)操作（也就是說hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采

用二進制位操作 &，相對于%能夠提高運算效率，這就解釋了 HashMap 的長度為什麼是2的幂次方。

三.HashSet 和 HashMap 差別