Hashtable 一個元老級的集合類，早在 JDK 1.0 就誕生了，今天小編想和大家一起來揭開它的面紗！
01、摘要
在集合系列的第一章，咱們瞭解到，Map 的實現類有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。
本文主要從數據結構和算法層面，探討 Hashtable 的實現，如果有理解不當之處，歡迎指正。
02、簡介
Hashtable 一個元老級的集合類，早在 JDK 1.0 就誕生了，而 HashMap 誕生於 JDK 1.2，在實現上，HashMap 吸收了很多 Hashtable 的思想，雖然二者的底層數據結構都是 數組 + 鏈表 結構，具有查詢、插入、刪除快的特點，但是二者又有很多的不同。
打開 Hashtable 的源碼可以看到，Hashtable 繼承自 Dictionary，而 HashMap 繼承自 AbstractMap。
<code>public class Hashtableextends Dictionary /<code>implements Map , Cloneable, java.io.Serializable { .....}
HashMap 繼承自 AbstractMap，HashMap 類的定義如下：
<code>public class HashMapextends AbstractMap /<code>implements Map , Cloneable, Serializable { .....}
其中 Dictionary 類是一個已經被廢棄的類，翻譯過來的意思是
這個類已經過時，新的實現應該實現 Map 接口而不是擴展此類，這一點我們可以從它代碼的註釋中可以看到：<code>/** * NOTE: This class is obsolete. New implementations should * implement the Map interface, rather than extending this class. */public abstractclass Dictionary{ ......} /<code>
Hashtable 和 HashMap 的底層是以數組來存儲，同時，在存儲數據通過key計算數組下標的時候，是以哈希算法為主，因此可能會產生哈希衝突的可能性。
通俗的說呢，就是不同的key，在計算的時候，可能會產生相同的數組下標，這個時候，如何將兩個對象放入一個數組中呢？
而解決哈希衝突的辦法，有兩種，一種開放地址方式（當發生 hash 衝突時，就繼續以此繼續尋找，直到找到沒有衝突的hash值），另一種是拉鍊方式（將衝突的元素放入鏈表）。
Java Hashtable 採用的就是第二種方式，拉鍊法！
於是，當發生不同的key通過一系列的哈希算法計算獲取到相同的數組下標的時候，會將對象放入一個數組容器中，然後將對象以單向鏈表的形式存儲在同一個數組下標容器中，就像鏈子一樣，掛在某個節點上，如下圖：
與 HashMap 類似，Hashtable 也包括五個成員變量：
<code>/**由Entry對象組成的數組*/private transient Entry[] table;/**Hashtable中Entry對象的個數*/private transient int count;/**Hashtable進行擴容的閾值*/private int threshold;/**負載因子，默認0.75*/private float loadFactor;/**記錄修改的次數*/private transient int modCount = 0;/<code>
具體各個變量含義如下：
- table：表示一個由 Entry 對象組成的鏈表數組，Entry 是一個單向鏈表，哈希表的key-value鍵值對都是存儲在 Entry 數組中的;
- count：表示 Hashtable 的大小，用於記錄保存的鍵值對的數量;
- threshold：表示 Hashtable 的閾值，用於判斷是否需要調整 Hashtable 的容量，threshold 等於容量 * 加載因子;
- loadFactor：表示負載因子，默認為 0.75；
- modCount：表示記錄 Hashtable 修改的次數，用來實現快速失敗拋異常處理；
接著來看看Entry這個內部類，Entry用於存儲鏈表數據，實現了Map.Entry接口，本質是就是一個映射（鍵值對），源碼如下：
<code> private static class Entryimplements Map.Entry /<code>{ /**hash值*/ final int hash; /**key表示鍵*/ final K key; /**value表示值*/ V value; /**節點下一個元素*/ Entry next; ......}
我們再接著來看看 Hashtable 初始化過程，核心源碼如下：
<code>public Hashtable() { this(11, 0.75f);}/<code>this 調用了自己的構造方法，核心源碼如下：
<code>public Hashtable(int initialCapacity, float loadFactor) { ..... //默認的初始大小為 11 //並且計算擴容的閾值 this.loadFactor = loadFactor; table = new Entry,?>[initialCapacity]; threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);}/<code>可以看到 HashTable 默認的初始大小為 11，如果在初始化給定容量大小，那麼 HashTable 會直接使用你給定的大小；
擴容的閾值threshold等於initialCapacity * loadFactor，我們在來看看 HashTable 擴容，方法如下：
<code>protected void rehash() { int oldCapacity = table.length; //將舊數組長度進行位運算，然後 +1 //等同於每次擴容為原來的 2n+1 int newCapacity = (oldCapacity << 1) + 1; //省略部分代碼...... Entry,?>[] newMap = new Entry,?>[newCapacity];}/<code>可以看到，HashTable 每次擴充為原來的 2n+1 。
我們再來看看 HashMap，如果是執行默認構造方法，會在擴容那一步，進行初始化大小，核心源碼如下：
<code>final Node[] resize() { int newCap = 0; //部分代碼省略...... newCap = DEFAULT_INITIAL_CAPACITY;//默認容量為 16 Node /<code>[] newTab = (Node [])new Node[newCap];}
可以看出 HashMap 的默認初始化大小為 16，我們再來看看，HashMap 擴容方法，核心源碼如下：
<code>final Node[] resize() { //獲取舊數組的長度 Node /<code>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int newCap = 0; //部分代碼省略...... //當進行擴容的時候，容量為 2 的倍數 newCap = oldCap << 1; Node [] newTab = (Node [])new Node[newCap];}
可以看出 HashMap 的擴容後的數組數量為原來的 2 倍；
也就是說 HashTable 會盡量使用素數、奇數來做數組的容量，而 HashMap 則總是使用 2 的冪作為數組的容量。
我們知道當哈希表的大小為素數時，簡單的取模哈希的結果會更加均勻，所以單從這一點上看，HashTable 的哈希表大小選擇，似乎更高明些。
Hashtable 的 hash 算法，核心代碼如下：
<code>//直接計算key.hashCode()int hash = key.hashCode();//通過除法取餘計算數組存放下標// 0x7FFFFFFF 是最大的 int 型數的二進制表示int index = (hash & 0x7FFFFFFF) % tab.length;/<code>
從源碼部分可以看出，HashTable 的 key 不能為空，否則報空指針錯誤！
但另一方面我們又知道，在取模計算時，如果模數是 2 的冪，那麼我們可以直接使用位運算來得到結果，效率要大大高於做除法。所以在 hash 計算數組下標的效率上，HashMap 卻更勝一籌，但是這也會引入了哈希分佈不均勻的問題， HashMap 為解決這問題，又對 hash 算法做了一些改動，具體我們來看看。
HashMap 的 hash 算法，核心代碼如下：
<code>/**獲取hash值方法*/static final int hash(Object key) {int h;// h = key.hashCode() 為第一步 取hashCode值（jdk1.7）// h ^ (h >>> 16) 為第二步 高位參與運算（jdk1.7）return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//jdk1.8}/**獲取數組下標方法*/static int indexFor(int h, int length) { //jdk1.7的源碼，jdk1.8沒有這個方法，但是實現原理一樣的 return h & (length-1); //第三步 取模運算}/<code> HashMap 由於使用了2的冪次方，所以在取模運算時不需要做除法，只需要位的與運算就可以了。但是由於引入的 hash 衝突加劇問題，HashMap 在調用了對象的 hashCode 方法之後，又做了一些高位運算，也就是第二步方法，來打散數據，讓哈希的結果更加均勻。
與此同時，在 jdk1.8 中 HashMap 還引進來紅黑樹實現，當衝突鏈表長度大於 8 的時候，會將鏈表結構改變成紅黑樹結構，讓查詢變得更快，具體實現可以參見《集合系列》中的 HashMap 分析。
03、常用方法介紹
3.1、put方法
put 方法是將指定的 key, value 對添加到 map 裡。
put 流程圖如下：
打開 HashTable 的 put 方法，源碼如下：
<code>public synchronized V put(K key, V value) { //當 value 值為空的時候，拋異常！ if (value == null) { throw new NullPointerException(); } Entry,?> tab[] = table; //通過key 計算存儲下標 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; //循環遍歷數組鏈表 //如果有相同的key並且hash相同，進行覆蓋處理 Entry entry = (Entry)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } //加入數組鏈表中 addEntry(hash, key, value, index); return null;} /<code>put 方法中的 addEntry 方法，源碼如下：
<code>private void addEntry(int hash, K key, V value, int index) { //新增修改次數 modCount++; Entry,?> tab[] = table; if (count >= threshold) { //數組容量大於擴容閥值，進行擴容 rehash(); tab = table; //重新計算對象存儲下標 hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; } //將對象存儲在數組中 Entry e = (Entry) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++;} /<code>addEntry 方法中的 rehash 方法，源碼如下：
<code>protected void rehash() { int oldCapacity = table.length; Entry,?>[] oldMap = table; //每次擴容為原來的 2n+1 int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) //大於最大閥值，不再擴容 return; newCapacity = MAX_ARRAY_SIZE; } Entry,?>[] newMap = new Entry,?>[newCapacity]; modCount++; //重新計算擴容閥值 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; //將舊數組中的數據複製到新數組中 for (int i = oldCapacity ; i-- > 0 ;) { for (Entry old = (Entry)oldMap[i] ; old != null ; ) { Entry e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry)newMap[index]; newMap[index] = e; } }} /<code>總結流程如下：
- 1、通過 key 計算對象存儲在數組中的下標；
- 2、如果鏈表中有 key，直接進行新舊值覆蓋處理；
- 3、如果鏈表中沒有 key，判斷是否需要擴容，如果需要擴容，先擴容，再插入數據；
有一個值得注意的地方是 put 方法加了synchronized關鍵字，所以，在同步操作的時候，是線程安全的。
3.2、get方法
get 方法根據指定的 key 值返回對應的 value。
get 流程圖如下：
打開 HashTable 的 get 方法，源碼如下：
<code>public synchronized V get(Object key) { Entry,?> tab[] = table; //通過key計算節點存儲下標 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null;}/<code>同樣，有一個值得注意的地方是 get 方法加了synchronized關鍵字，所以，在同步操作的時候，是線程安全的。
3.3、remove方法
remove 的作用是通過 key 刪除對應的元素。
remove 流程圖如下：
打開 HashTable 的 remove 方法，源碼如下：
<code>public synchronized V remove(Object key) { Entry,?> tab[] = table; //通過key計算節點存儲下標 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; Entry e = (Entry)tab[index]; //循環遍歷鏈表，通過hash和key判斷鍵是否存在 //如果存在，直接將改節點設置為空，並從鏈表上移除 for(Entry prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; } count--; V oldValue = e.value; e.value = null; return oldValue; } } return null;} /<code>同樣，有一個值得注意的地方是 remove 方法加了synchronized關鍵字，所以，在同步操作的時候，是線程安全的。
04、總結
總結一下 Hashtable 與 HashMap 的聯繫與區別，內容如下：
- 1、雖然 HashMap 和 Hashtable 都實現了 Map 接口，但 Hashtable 繼承於 Dictionary 類，而 HashMap 是繼承於 AbstractMap；
- 2、HashMap 可以允許存在一個為 null 的 key 和任意個為 null 的 value，但是 HashTable 中的 key 和 value 都不允許為 null；
- 3、Hashtable 的方法是同步的，因為在方法上加了 synchronized 同步鎖，而 HashMap 是非線程安全的；
儘管，Hashtable 雖然是線程安全的，但是我們一般不推薦使用它，因為有比它更高效、更好的選擇 ConcurrentHashMap，在後面我們也會講到它。
最後，引入來自 HashTable 的註釋描述：
If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.ConcurrentHashMap in place of Hashtable.
簡單來說就是，如果你不需要線程安全，那麼使用 HashMap，如果需要線程安全，那麼使用 ConcurrentHashMap。
HashTable 已經被淘汰了，不要在新的代碼中再使用它。
05、參考
1、JDK1.7&JDK1.8 源碼
2、博客園 - 程序員趙鑫 - HashMap和HashTable到底哪不同？
閱讀更多 科技伍小黑 的文章
