散列表（Hash table）——將條目的關(guān)鍵碼視作其在映射結(jié)構(gòu)中的存放位置
散列表由兩個要素構(gòu)成：桶數(shù)組與散列函數(shù)
桶數(shù)組
散列表使用的桶數(shù)組（Bucket array ），其實就是一個容量為 N 的普通數(shù)組 A[0..N-1]，只不過在這里，我們將其中的每個單元都想象為一個“桶”（Bucket），每個桶單元里都可以存放一個條目。
另外我們還需要某一函數(shù)，將任意關(guān)鍵碼轉(zhuǎn)換為介于 0 與 N-1 之間的整數(shù)??這個函數(shù)就是所謂的散列函數(shù)（Hash function）。
散列函數(shù)
為了將散列技術(shù)推廣至一般類型的關(guān)鍵碼，我們需要借助散列函數(shù) h，將關(guān)鍵碼 key映射為一個整數(shù) h(key) ∈ [0..N-1]，并將對應(yīng)的條目存放至第 h(key)號桶內(nèi)，其中 N 為桶數(shù)組的容量。
如果將桶數(shù)組記作 A[ ]，這一技術(shù)就可以總結(jié)為“將條目 e = (key, value)存放至 A [ h ( key ) ] 中”。
反過來，為了查找關(guān)鍵碼為 key 的條目，只需取出桶單元 A[h(key)]中存放的對象。因此，h(key)也被稱作 e 的散列地址。
不過，若要兌現(xiàn)上述構(gòu)思，還需要滿足另一個條件—— h( )是一個單射，即不同的關(guān)鍵碼key1 ≠ key2 必然對應(yīng)于不同的散列地址h(key1) ≠ h(key2)。不幸的是，在絕大多數(shù)應(yīng)用問題中，這一條件都很難滿足。如果不同關(guān)鍵碼的散列地址相同，我們就說該散列發(fā)生了沖（Collision）。
一個好的散列函數(shù) h()必須兼顧以下兩條基本要求：
- h( )應(yīng)該盡可能接近單射；
- 對于任何關(guān)鍵碼 key，h(key)的計算必須能夠在 O(1)時間內(nèi)完成。
關(guān)于散列函數(shù)的計算，Java有其特有的習慣。Java將h(key)的計算劃分為兩步：
- （1）將一般性的關(guān)鍵碼key轉(zhuǎn)換為一個稱作“散列碼”的整數(shù)；
- （2）然后再通過所謂的“壓縮函數(shù)”將該整數(shù)映射至區(qū)間[0..N-1]內(nèi)。
散列碼
Java 可以幫助我們將任意類型的關(guān)鍵碼 key 轉(zhuǎn)換為一個整數(shù)，稱作 key 的散列碼（Hash code）。請注意，散列碼距離我們最終所需的散列地址還有很大距離??它不見得落在區(qū)間[0..N-1]內(nèi)，甚至不見得是正的整數(shù)。
不過這并不要緊，在這一階段我們最關(guān)心的是：各關(guān)鍵碼的散列碼之間，應(yīng)盡可能地減少沖突。顯然，要是在這一階段就發(fā)生沖突，后面的沖突就無法避免。
此外，從判等器的判等效果來看，散列碼必須與關(guān)鍵碼對象相互一致：被判等器 EqualityTester 判定為相等的兩個關(guān)鍵碼，對應(yīng)的散列碼也應(yīng)該相等。
Java 的通用類 Object 提供了一個默認的散列碼轉(zhuǎn)換方法 hashCode()，利用它可以將任意對象實例映射為“代表”該對象的某個整數(shù)。具體來說，hashCode()方法的返回值是一個 32 位 int 型整數(shù)（實際上，這一默認 hashCode()方法所返回的不過就是對象在內(nèi)存中的存儲地址）。
遺憾的是，這一看似再自然不過的方法，實際上存在著嚴重的缺
陷，因此我們在使用時需格外小心。
比如，這種散列碼的轉(zhuǎn)換辦法對字符串型關(guān)鍵碼就極不適用。若兩個字符串對象完全相等，本應(yīng)該將它們轉(zhuǎn)換為同一散列碼，但由于它們的內(nèi)存地址不同，由 hashCode()得到的散列碼將絕對不會一樣。
實際上，在實現(xiàn) String 類時，Java 已經(jīng)將 Object 類的 hashCode()方法改寫為一種更加適宜于字符串關(guān)鍵碼的方法。
壓縮函數(shù)
（1）模余法
最簡單的壓縮辦法，就是取 N 為素數(shù)，并將散列碼 i 映射為：
** | i | mod N **
之所以將 N 選取為素數(shù)，是為了最大程度地將散列碼均勻地映射至[0..N-1]區(qū)間內(nèi)。
比如，對于散列碼集合{200, 205, 210, 215, …, 690, 695, 700}，若選取 N = 100，則其中的每個散列碼都會與另外的至少四個關(guān)鍵碼相沖突；而若改用 N = 101，則不會有任何沖突。
（2）MAD 法
采用一種將乘法（Mutiply）、加法（Add）和除法（Divide）結(jié)合起來的方法，該方法也因此得名。具體來說，對于散列碼 i，MAD 法會將 i 映射為：
** | a×i + b | mod N **
其中 N 仍為素數(shù)，a>0，b>0，a mod N ≠ 0，它們都是在確定壓縮函數(shù)時隨機選取的常數(shù)。
基于散列表實現(xiàn)映射類
我們給出基于散列表實現(xiàn)的映射結(jié)構(gòu)：
package dsa.Map;
import dsa.Iterator.Iterator;
import dsa.Iterator.IteratorElement;
import dsa.List.List;
import dsa.List.List_DLNode;
import dsa.PriorityQueue.Entry;
public class Map_HashTable implements Map {
/*
* 基于散列表實現(xiàn)的映射結(jié)構(gòu) 采用分離鏈策略解決沖突
*/
private Map[] A;// 桶數(shù)組，每個桶本身也是一個（基于列表實現(xiàn)的）映射結(jié)構(gòu)
private int N;// 散列表長
private final double maxLemda = 0.75;// 裝填因子上限
private int size;// 映射結(jié)構(gòu)的規(guī)模
private EqualityTester T;// 判等器
// 默認構(gòu)造方法
public Map_HashTable() {
this(0, new EqualityTesterDefault());
}
// 構(gòu)造方法
public Map_HashTable(int n, EqualityTester t) {
T = t;
N = p(n);// 桶數(shù)組容量取為不小于n的最小素數(shù)
A = new Map[N];
for (int i = 0; i < N; i++)
A[i] = new Map_DLNode(T);
size = 0;
}
/***************************** 輔助方法 *****************************/
// 散列定址函數(shù)（采用模余法）
private int h(Object key) {
return key.hashCode() % N;
}
// 判斷n是否為素數(shù)
private static boolean prime(int n) {
for (int i = 3; i < 1 + Math.sqrt(n); i++)
if (n / i * i == n)
return false;
return true;
}
// 取不小于n的最小素數(shù)
private static int p(int n) {
if (3 > n)
n = 3;
n = n | 1;// 奇數(shù)化
while (!prime(n))
n += 2;
return n;
}
/***************************** ADT方法 *****************************/
// 查詢映射結(jié)構(gòu)當前的規(guī)模
public int getSize() {
return size;
}
// 判斷映射結(jié)構(gòu)是否為空
public boolean isEmpty() {
return 0 == size;
}
// 若M中存在以key為關(guān)鍵碼的條目，則返回該條目的數(shù)據(jù)對象；否則，返回null
public Object get(Object key) {
return A[h(key)].get(key);
}
// 若M中不存在以key為關(guān)鍵碼的條目，則將條目(key, value)加入到M中并返回null
// 否則，將已有條目的數(shù)據(jù)對象替換為value，并返回原先的數(shù)據(jù)對象
public Object put(Object key, Object value) {
Object oldValue = A[h(key)].put(key, value);
if (null == oldValue) {// 若插入的條目未出現(xiàn)于原散列表中，則
size++;// 更新規(guī)模記錄
if (size > N * maxLemda)
rehash();// 若裝填因子過大，則重散列
}
return oldValue;
}
// 若M中存在以key為關(guān)鍵碼的條目，則刪除之并返回其數(shù)據(jù)對象；否則，返回null
public Object remove(Object key) {
Object oldValue = A[h(key)].remove(key);
if (null != oldValue)
size--;
return oldValue;
}
// 返回M中所有條目的一個迭代器
// 將各桶對應(yīng)的映射結(jié)構(gòu)的迭代器串接起來，構(gòu)成整體的迭代器
public Iterator entries() {
List L = new List_DLNode();
for (int i = 0; i < N; i++) {
Iterator it = A[i].entries();
while (it.hasNext())
L.insertLast(it.getNext());
}
return new IteratorElement(L);
}
// 重散列
private void rehash() {
Iterator it = this.entries();
N = p(N << 1);
A = new Map[N];// 桶數(shù)組容量至少加倍
for (int i = 0; i < N; i++)
A[i] = new Map_DLNode(T);// 為每個桶分配一個子映射
while (it.hasNext()) {// 將其對應(yīng)的映射結(jié)構(gòu)中的
Entry e = (Entry) it.getNext();// 各條目逐一取出，將其
Object k = e.getKey();// 關(guān)鍵碼和
Object v = e.getValue();// 數(shù)據(jù)對象
A[h(k)].put(k, v);// 整合為新的條目，插入對應(yīng)的子映射中
}
}
}
裝填因子
對于散列表的性能而言，裝填因子λ = n/N是最重要的影響因素。
如果λ > 1，則沖突在所難免。
實際上，關(guān)于散列表平均復(fù)雜度的分析結(jié)果指出：
- 采取分離鏈策略時應(yīng)該保持λ < 0.9，
- 采取開放定址策略時則應(yīng)該保持λ < 0.5
這些都得到了實驗統(tǒng)計的證明。
若采用分離鏈策略，則在發(fā)生沖突的桶中，對條目的查找將退化為對鏈表的查找。因此，隨著λ不斷接近于 1，發(fā)生沖突的概率也將不斷接近于 100%，從而導(dǎo)致更多的時間消耗于對鏈表的查找，使得各種操作的效率下降。
當采用開放定址策略時，隨著λ超過 0.5 并不斷提高，條目在桶數(shù)組中聚集的程度將急速加劇，于是，需要經(jīng)過越來越多次的探測才能完成一次查找。
重散列
通常都采用重散列的方法??將所有條目全部取出，將桶數(shù)組的規(guī)模
加倍，然后將各條目重新插入其中。
例如，Java 內(nèi)建的 java.util.HashMap 類實現(xiàn)了映射結(jié)構(gòu)的 ADT，在創(chuàng)建該類的對象時，程序員可以指定裝填因子的上限（默認設(shè)置為 0.75）。一旦裝填因子超出這一范圍，java.util.HashMap會自動進行重散列（Rehashing）。
