在 Java 中與有兩個類都提供了一個多種用途的 hashTable 機制，他們都可以將可以 key 和 value 結(jié)合起來構(gòu)成鍵值對通過 put(key,value)方法保存起來，然后通過 get(key) 方法獲取相對應(yīng)的 value 值。一個是前面提到的 HashMap，還有一個就是馬上要講解的 HashTable。對于 HashTable 而言，它在很大程度上和 HashMap 的實現(xiàn)差不多，如果我們對 HashMap 比較了解的話，對 HashTable 的認知會提高很大的幫助。他們兩者之間只存在幾點的不同，這個后面會闡述。
HashTable 在 Java 中的定義如下：
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
從中可以看出 HashTable 繼承 Dictionary 類，實現(xiàn) Map 接口。其中 Dictionary 類是任何可將鍵映射到相應(yīng)值的類（如 Hashtable）的抽象父類。每個鍵和每個值都是一個對象。在任何一個 Dictionary 對象中，每個鍵至多與一個值相關(guān)聯(lián)。Map 是”key-value鍵值對”接口。
HashTable 采用”拉鏈法”實現(xiàn)哈希表，它定義了幾個重要的參數(shù)：table、count、threshold、loadFactor、modCount。
table：為一個 Entry[] 數(shù)組類型，Entry 代表了“拉鏈”的節(jié)點，每一個 Entry代表了一個鍵值對，哈希表的”key-value鍵值對”都是存儲在 Entry 數(shù)組中的。
count：HashTable 的大小，注意這個大小并不是 HashTable 的容器大小，而是他所包含 Entry 鍵值對的數(shù)量。
threshold：Hashtable 的閾值，用于判斷是否需要調(diào)整 Hashtable 的容量。threshold 的值=”容量*加載因子”。
loadFactor：加載因子。
modCount：用來實現(xiàn)“fail-fast”機制的（也就是快速失敗）。所謂快速失敗就是在并發(fā)集合中，其進行迭代操作時，若有其他線程對其進行結(jié)構(gòu)性的修改，這時迭代器會立馬感知到，并且立即拋出ConcurrentModificationException 異常，而不是等到迭代完成之后才告訴你（你已經(jīng)出錯了）。
在 HashTabel 中存在 5 個構(gòu)造函數(shù)。通過這 5 個構(gòu)造函數(shù)我們構(gòu)建出一個我想要的 HashTable。
public Hashtable() {
this(11, 0.75f);
}
默認構(gòu)造函數(shù)，容量為 11，加載因子為 0.75。
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
用指定初始容量和默認的加載因子 (0.75) 構(gòu)造一個新的空哈希表。
public Hashtable(int initialCapacity, float loadFactor) {
//驗證初始容量
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//驗證加載因子
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
//初始化table，獲得大小為initialCapacity的table數(shù)組
table = new Entry[initialCapacity];
//計算閥值
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//初始化HashSeed值
initHashSeedAsNeeded(initialCapacity);
}
用指定初始容量和指定加載因子構(gòu)造一個新的空哈希表。其中 initHashSeedAsNeeded 方法用于初始化 hashSeed 參數(shù)，其中 hashSeed 用于計算 key 的 hash 值，它與 key 的 hashCode 進行按位異或運算。這個 hashSeed 是一個與實例相關(guān)的隨機值，主要用于解決 hash 沖突。
private int hash(Object k) {
return hashSeed ^ k.hashCode();
}
構(gòu)造一個與給定的 Map 具有相同映射關(guān)系的新哈希表。
public Hashtable(Map<? extends K, ? extends V> t) {
//設(shè)置table容器大小，其值==t.size * 2 + 1
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
HashTable 的 API 對外提供了許多方法，這些方法能夠很好幫助我們操作 HashTable，但是這里我只介紹兩個最根本的方法：put、get。
首先我們先看 put 方法：將指定 key 映射到此哈希表中的指定 value。注意這里鍵 key 和值 value 都不可為空。
public synchronized V put(K key, V value) {
// 確保value不為null
if (value == null) {
throw new NullPointerException();
}
/*
* 確保key在table[]是不重復(fù)的
* 處理過程：
* 1、計算key的hash值，確認在table[]中的索引位置
* 2、迭代index索引位置，如果該位置處的鏈表中存在一個一樣的key，則替換其value，返回舊值
*/
Entry tab[] = table;
int hash = hash(key); //計算key的hash值
int index = (hash & 0x7FFFFFFF) % tab.length; //確認該key的索引位置
//迭代，尋找該key，替換
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) { //如果容器中的元素數(shù)量已經(jīng)達到閥值，則進行擴容操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 在索引位置處插入一個新的節(jié)點
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
//容器中元素+1
count++;
return null;
}
put 方法的整個處理流程是：計算 key 的 hash 值，根據(jù) hash 值獲得 key 在 table 數(shù)組中的索引位置，然后迭代該 key 處的 Entry 鏈表（我們暫且理解為鏈表），若該鏈表中存在一個這個的 key 對象，那么就直接替換其 value 值即可，否則在將改 key-value 節(jié)點插入該 index 索引位置處。如下：
首先我們假設(shè)一個容量為 5 的 table，存在 8、10、13、16、17、21。他們在 table 中位置如下：
http://wiki.jikexueyuan.com/project/java-enhancement/images/25-1.png" alt="fig.1" />
然后我們插入一個數(shù)：put(16,22)，key=16 在 table 的索引位置為 1，同時在 1 索引位置有兩個數(shù)，程序?qū)υ摗版湵怼边M行迭代，發(fā)現(xiàn)存在一個 key=16,這時要做的工作就是用 newValue=22 替換 oldValue16，并將 oldValue=16 返回。
http://wiki.jikexueyuan.com/project/java-enhancement/images/25-2.png" alt="fig.2" />
在 put(33,33)，key=33 所在的索引位置為 3，并且在該鏈表中也沒有存在某個 key=33 的節(jié)點，所以就將該節(jié)點插入該鏈表的第一個位置。
http://wiki.jikexueyuan.com/project/java-enhancement/images/25-3.png" alt="fig.3" />
在 HashTabled 的 put 方法中有兩個地方需要注意：
1、HashTable 的擴容操作，在 put 方法中，如果需要向 table[] 中添加 Entry 元素，會首先進行容量校驗，如果容量已經(jīng)達到了閥值， HashTable 就會進行擴容處理 rehash()，如下:
protected void rehash() {
int oldCapacity = table.length;
//元素
Entry<K,V>[] oldMap = table;
//新容量=舊容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
return;
newCapacity = MAX_ARRAY_SIZE;
}
//新建一個size = newCapacity 的HashTable
Entry<K,V>[] newMap = new Entry[];
modCount++;
//重新計算閥值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//重新計算hashSeed
boolean rehash = initHashSeedAsNeeded(newCapacity);
table = newMap;
//將原來的元素拷貝到新的HashTable中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
if (rehash) {
e.hash = hash(e.key);
}
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = newMap[index];
newMap[index] = e;
}
}
}
在這個 rehash() 方法中我們可以看到容量擴大兩倍 +1，同時需要將原來 HashTable 中的元素一一復(fù)制到新的 HashTable 中，這個過程是比較消耗時間的，同時還需要重新計算 hashSeed 的，畢竟容量已經(jīng)變了。這里對閥值啰嗦一下：比如初始值 11、加載因子默認 0.75，那么這個時候閥值 threshold=8，當(dāng)容器中的元素達到 8 時，HashTable 進行一次擴容操作，容量 = 8 2 + 1 =17，而閥值 threshold=170.75 = 13，當(dāng)容器元素再一次達到閥值時，HashTable 還會進行擴容操作，一次類推。
2、其實這里是我的一個疑問，在計算索引位置 index 時， HashTable 進行了一個與運算過程（hash & 0x7FFFFFFF），為什么需要做一步操作，這么做有什么好處？如果哪位知道，望指導(dǎo)，LZ 不勝感激！！下面是計算 key 的 hash 值，這里 hashSeed 發(fā)揮了作用。
private int hash(Object k) {
return hashSeed ^ k.hashCode();
}
相對于 put 方法，get 方法就會比較簡單，處理過程就是計算 key 的 hash 值，判斷在 table 數(shù)組中的索引位置，然后迭代鏈表，匹配直到找到相對應(yīng) key 的 value,若沒有找到返回 null。
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
HashTable 和 HashMap 存在很多的相同點，但是他們還是有幾個比較重要的不同點。
第一：我們從他們的定義就可以看出他們的不同，HashTable 基于 Dictionary 類，而 HashMap 是基于 AbstractMap。Dictionary 是什么？它是任何可將鍵映射到相應(yīng)值的類的抽象父類，而 AbstractMap 是基于 Map 接口的骨干實現(xiàn)，它以最大限度地減少實現(xiàn)此接口所需的工作。
第二：HashMap 可以允許存在一個為 null 的 key 和任意個為 null 的 value，但是 HashTable 中的 key 和 value 都不允許為 null。如下：
當(dāng) HashMap 遇到為 null 的 key 時，它會調(diào)用 putForNullKey 方法來進行處理。對于 value 沒有進行任何處理，只要是對象都可以。
if (key == null)
return putForNullKey(value);
而當(dāng) HashTable 遇到 null 時，他會直接拋出 NullPointerException異常信息。
if (value == null) {
throw new NullPointerException();
}
第三：Hashtable 的方法是同步的，而 HashMap 的方法不是。所以有人一般都建議如果是涉及到多線程同步時采用 HashTable，沒有涉及就采用 HashMap，但是在 Collections 類中存在一個靜態(tài)方法： synchronizedMap()，該方法創(chuàng)建了一個線程安全的 Map 對象，并把它作為一個封裝的對象來返回，所以通過 Collections 類的 synchronizedMap 方法是可以我們你同步訪問潛在的 HashMap。這樣君該如何選擇呢？？？
掃碼關(guān)注鍍金池微信號
手機訂課，優(yōu)惠多多