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