為什麼要使用哈希表
查找和插入是查找表的兩項基本操作，對于單純使用連結清單，數組，或二叉樹實作的查找表來說，這兩項操作在時間消耗上仍顯得比較昂貴。 以查找為例：在數組實作的查找表中，需要用二分等查找方式進行一系列的比較後，才能找到給定的鍵值對的位置。而二叉樹的實作中也存在着一個向左右子樹遞歸查找的過程。 而現在，我們希望在查找/插入/删除這三項基本操作裡， 能不通過比較，而是通過一個哈希函數的映射，直接找到鍵對應的位置，進而取得時間上的大幅優化， 這就是我們選用哈希表的原因。
相比起哈希表，其他的查找表中并沒有特定的“鍵”和“鍵的位置”之間的對應關系。是以需要在鍵的查找上付出較大的開銷。而哈希表則通過一個映射函數（哈希函數）建立起了“鍵”和“鍵的位置”（即哈希位址）間的對應關系，是以大大減小了這一層開銷
回到頂部
哈希表的取舍
所謂選擇，皆有取舍。哈希表在查找/插入/删除等基本操作上展現的優越性能，是在它舍棄了有序性操作的基礎上實作的。因為哈希表并不維護表的有序性，是以在哈希表中實作有序操作的性能會很糟糕。例如：max(取最大鍵)，min(取最小鍵), rank(取某個鍵的排名), select(取給定排名的鍵)，
floor(向下取整) ceiling(向上取整)。 而相對的， 用二叉樹等結構實作的查找表中，因為在動态操作（插入/删除）中一直維護着表的有序性，是以這些資料結構中實作的有序操作開銷會小很多。
回到頂部
使用哈希表的前提
使用哈希表的前提是： 這個表存儲的鍵是無序的，或者不需要考慮其有序性
回到頂部
哈希函數的構造
哈希函數有許多不同的構造方法，包括：1.直接定址法 2.數字分析法 3.平方取中法 4.折疊法 5. 除留取餘法
1.直接定址法
取鍵或鍵的某個線性函數值為哈希位址。設 f 為哈希函數，key為輸入的鍵，則f(key) = key或者 f(key) = k*key+b (k,b為常數)
例如，有一個解放後的人口調查表， 鍵為年份，則可設定哈希函數為： f(key) = key+ （-1948），如下圖所示：
1949對應的哈希函數值為1， 1950對應的為2，依次類推
2.數字分析法
如下圖所示，有80個記錄，每一行為一個記錄中的鍵，假設表長為100，則可取兩位十進制數組成哈希位址。
通過觀察可以得出，第1,2列對應的數字都是相同的，而第3列和第8列存在大量重複的數字（分别是3和2,7），不能選做哈希位址。而中間4位可以看作是随機的，可以從中任選兩位作為哈希位址
3. 平方取中法
取關鍵字平方後的中間幾位為哈希位址，這種方法叫做平方取中法。它彌補了數字分析法的一些缺陷，因為我們有時并不能知道鍵的全部情況，取其中幾位也不一定合适，而一個數平方後的中間幾個數和原數的每一位都相關，由此我們就能得到随機性更強的哈希位址取的位數由表長決定。
4.折疊法
将關鍵字分成位數相同的幾部分（最後一位可以不同），然後取疊加和作為哈希位址，這一方法被稱為折疊法。當表的鍵位數很多，而且每一位上數字分布比較均勻的時候， 可以考慮采用這一方法。 折疊法有移位疊加和間位疊加兩種方法例如國際标準圖書編号0-442-20586-4的哈希位址可以用這兩種方法表示為
5.除留餘數法
除留餘數法是最基礎的，最常用的取得哈希函數的方法。標明一個統一的基數， 對所有的鍵取餘，進而得到對應的哈希位址。下圖中的M就表示這個統一的基數，在實作上，它一般是數組的長度
這也是我們接下來實作哈希表時采用的哈希函數方法。
回到頂部
哈希位址的沖突
一個經常會碰到的問題是; 不同的鍵經過哈希函數的映射後，得到了一個同樣的哈希位址。這種現象叫做沖突（或者碰撞）如下圖所示。
回到頂部
解決沖突的方法
沖突并不是一件嚴重的事情，因為我們可以用一些方式去解決它
解決沖突的方式有三種： 拉鍊法，線性探測法和再哈希法
回到頂部
拉鍊法
拉鍊法是基于連結清單實作的查找表去實作的，關于連結清單查找表可以看下我之前寫的這篇文章：
無序連結清單實作查找表
拉鍊法處理沖突的思路是： 利用連結清單數組實作查找表。即建立一個數組， 每個數組元素都是一條連結清單。當不同的鍵映射到同一個哈希位址（數組下标）上時， 将它們挂到這個哈希位址（數組下标）對應的連結清單上， 讓它們成為這條連結清單上的不同結點。
在拉鍊法中，哈希表的任務是根據給定鍵計算哈希值，然後找到對應位置的連結清單對象。剩下的查找/插入/删除的操作，就委托給連結清單查找表的查找/插入/删除接口去做。
即：
哈希表的查找操作 = 計算哈希值 + 連結清單查找表的查找操作
哈希表的插入操作 = 計算哈希值 + 連結清單查找表的插入操作
哈希表的删除操作 = 計算哈希值 + 連結清單查找表的删除操作
編寫哈希函數
在Java中, 預設的hashCode方法傳回了一個32位的整數哈希值，因為hashCode可能為負，是以要通過hashCode() & 0x7fffffff)屏蔽符号位，将一個32位整數變成一個31位非負整數。同時因為我們要将其運用到數組中，是以要再用數組大小M對其取餘。這樣的話就能取到在0和M-1間（數組下标範圍内）分布的哈希值。
/**
* @description: 根據輸入的鍵擷取對應的哈希值
*/
private int hash (Key key) {
return (key.hashCode() & 0x7fffffff) % M;
} 下面給出拉鍊法的具體實作
- SeparateChainingHashST.java: 拉鍊法實作的哈希表
- SequentialSearchST.java: 連結清單查找表
- Test.java: 測試代碼
SeparateChainingHashST.java(哈希表)
public class SeparateChainingHashST<Key,Value> {
private int M; // 數組的大小
private SequentialSearchST<Key, Value> [] st; // 連結清單查找表對象組成的數組
public SeparateChainingHashST (int M) {
st= new SequentialSearchST [M];
this.M = M;
// 初始化數組st中的連結清單對象
for (int i=0;i<st.length;i++) {
st[i] = new SequentialSearchST();
}
}
/**
* @description: 根據輸入的鍵擷取對應的哈希值
*/
private int hash (Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
/**
* @description: 根據給定鍵擷取值
*/
public Value get (Key key) {
return st[hash(key)].get(key);
}
/**
* @description: 向表中插入鍵值對
*/
public void put (Key key, Value val) {
st[hash(key)].put(key, val);
}
/**
* @description: 根據給定鍵删除鍵值對
*/
public void delete (Key key) {
st[hash(key)].delete(key);
}
} SequentialSearchST.java （連結清單查找表）
public class SequentialSearchST<Key, Value> {
Node first; // 頭節點
int N = 0; // 連結清單長度
private class Node {
Key key;
Value value;
Node next; // 指向下一個節點
public Node (Key key,Value value,Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public int size () {
return N;
}
public void put (Key key, Value value) {
for(Node n=first;n!=null;n=n.next) { // 周遊連結清單節點
if(n.key == key) { // 查找到給定的key，則更新相應的value
n.value = value;
return;
}
}
// 周遊完所有的節點都沒有查找到給定key
// 1. 建立新節點，并和原first節點建立“next”的聯系，進而加傳入連結表
// 2. 将first變量修改為新加入的節點
first = new Node(key,value,first);
N++; // 增加字典（連結清單）的長度
}
public Value get (Key key) {
for(Node n=first;n!=null;n=n.next) {
if(n.key.equals(key)) return n.value;
}
return null;
}
public void delete (Key key) {
if (N == 1) {
first = null;
return ;
}
for(Node n =first;n!=null;n=n.next) {
if(n.next.key.equals(key)) {
n.next = n.next.next;
N--;
return ;
}
}
}
} 測試代碼
Test.java:
public class Test {
public static void main (String args[]) {
SeparateChainingHashST<String, Integer> hashST = new SeparateChainingHashST<>(16);
hashST.put("A",1); // 插入鍵值對 A - 1
hashST.put("B",2); // 插入鍵值對 B - 2
hashST.delete("B"); // 删除鍵值對 B - 2
System.out.println(hashST.get("A")); // 輸出 1
System.out.println(hashST.get("B")); // 輸出 null
}
} 回到頂部
線性探測法
解決沖突的另一個方法是線性探測法，當沖突發生的時候，我們檢查沖突的哈希位址的下一位（數組下标加一），判斷能否插入，如果不能則再繼續檢查下一個位置。
【注意】線性探測法屬于開放定址法的一種。 開放定址法還包括二次探測，随機探測等其他方法
實作類的結構如下：
public class LinearProbingHashST<Key, Value> {
private int M; // 數組的大小
private int N; // 鍵值對對數
private Key [] keys;
private Value [] vals;
public LinearProbingHashST (int M) {
this.M = M;
keys = (Key []) new Object[M];
vals = (Value[]) new Object[M];
}
/**
* @description: 擷取哈希值
*/
private int hash (Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
/**
* @description: 插入操作
*/
public void put (Key key, Value val) // 具體代碼下文給出
/**
* @description: 根據給定鍵擷取值
*/
public Value get (Key key) // 具體代碼下文給出
/**
* @description: 删除操作
*/
public void delete (Key key) // 具體代碼下文給出
} 為了較好地了解， 下面我将線性探測表的實作比喻為一個“警察抓小偷”的遊戲。把被插入的鍵值對看成”小偷“，把數組元素看成”小偷“躲藏的箱子。 則：
- 插入操作是小偷藏進箱子的過程；
- 查找操作是警察尋找某個小偷的過程；
- 删除操作是小偷被警察抓獲，同時離開箱子的過程
插入操作
對某個位置進行插入操作時候，可分三種情況處理：
- 該位置鍵為空，則插入鍵值對
- 該位置鍵不為空，但已有鍵和給定鍵相等，則更新對應的值
- 該位置鍵和給定鍵不同，則繼續檢查下一個鍵
将插入鍵值對的過程比作遊戲中小偷藏進箱子的過程，那麼情況1和情況3可用下圖表示：
情況1：
情況3：
插入操作代碼
/**
* @description: 調整數組大小
*/
private void resize (int max) {
Key [] temp = (Key [])new Object[max];
for (int i =0;i<keys.length;i++) {
temp[i] = keys[i];
}
keys = temp;
}
/**
* @description: 插入操作
*/
public void put (Key key, Value val) {
// 當鍵值對數量已經超過數組一半時，将數組長度擴大一倍
if(N>(M/2)) resize(2*M);
// 計算哈希值,求出鍵的位置
int i = hash(key);
// 判斷該位置鍵是否為空
while(keys[i]!=null) {
if(key.equals(keys[i])) {
// 該位置的鍵和給定key相同，則更新對應的值
vals[i] = val;
return;
} else {
// 該位置的鍵和給定key不同，則檢查下一個位置的鍵
i = (i+1) % M;
}
}
// 該位置鍵為空則插入鍵值對
keys[i] = key;
vals[i] = val;
N++;
return;
} 可循環的哈希表
i = (i+1) % M這一語句使得線性探測的哈希表是可循環的
i = (i+1) % M的作用表現為兩方面：
1. 如果目前的元素不是keys數組的最後一個元素， 那麼遊标i會移動到數組下一個元素的位置
2. 如果目前的元素是keys數組的最後一個元素， 那麼遊标i會移動到數組的頭部，即第一個元素,這樣就避免了當哈希值恰好為數組尾部元素而尾部元素非空時候插入失敗
如下圖所示：
及時調整數組大小的必要性
1. 在拉鍊法實作的哈希表中，因為連結清單的存在，可以彈性地容納鍵值對，而對于線性探測法實作的哈希表，其容納鍵值對的數量是直接受到數組大小的限制的。是以必須在數組充滿以前調整數組的大小
2. 在另一方面，即使數組尚未充滿，随着鍵值對的增加，線性探測的哈希表的性能也會不斷下降。可以用鍵值對對數 / 數組大小來量化地衡量其對性能的影響， 如下圖所示：
簡單思考下就能明白為什麼随着鍵值對占數組長度的比例的增加， 哈希表的性能會下降： 因為在這個過程中，将更容易形成長的鍵簇（一段連續的非空鍵的組合）。而哈希表的查找/插入等一般都是遇到空鍵才能結束， 是以，長鍵簇越多，查找/插入的時間就越長，哈希表的性能也就越差
是以，我們要及時地擴大數組的大小。如我們上面的代碼中， 每當總鍵值對的對數達到數組的一半後，我們就将整個數組的大小擴大一倍。
查找操作
線性探測的查找過程也分三種情況處理
1.該位置鍵為空，則停止查找
2.該位置鍵不為空，且和給定鍵相等，則傳回相應的值
3.該位置鍵不為空，且和給定鍵不同，則繼續檢查下一個鍵
如下圖A，B， 将查找操作比喻成警察尋找某個小偷的過程：
圖A：
圖B：
為什麼遇到空鍵就傳回？
因為插入操作是遇到空的位置就插入， 是以如果不考慮删除操作的話，哈希值相同的鍵一定是分布在連續的非空的鍵簇上的。 反之，遇到空的位置， 就說明這後面沒有哈希值相同的鍵了， 是以這時就停止了查找操作
查找操作代碼如下
/**
* @description: 根據給定鍵擷取值
*/
public Value get (Key key) {
for (int i=hash(key);keys[i]!=null;i=(i+1)%M) {
if (key.equals(keys[i])) {
return vals[i];
}
}
return null;
} 删除操作
能直接删除某個鍵值對而不做後續處理嗎？ 這是不能的。因為在查找操作中，我們在查找到一個空的鍵的時候就會停止查找， 是以如果直接删除某個位置的鍵值對，會導緻從該位置的下一個鍵到鍵簇末尾的鍵都不能被查找到了，如下圖1,2所示， 将删除操作比喻成警察抓獲某個小偷， 并讓小偷離開箱子的過程
圖1：
圖2：
删除操作的正确方法
删除操作的正确方法是： 删除某個鍵值對，并對被删除鍵後面鍵簇的所有鍵都進行删除并重新插入
代碼如下：
/**
* @description: 删除操作
*/
public void delete (Key key) {
// 給定鍵不存在，不進行删除
if (get(key) == null) return ;
// 計算哈希值， 求得鍵的位置
int i = hash(key);
// 擷取給定鍵的下标
while (!key.equals(keys[i])) {
i = (i+1) % M;
}
// 删除鍵值對
keys[i] = null;
vals[i] = null;
// 對被删除鍵後面鍵簇的所有鍵都進行删除并重新插入
i = (i+1)%M;
while (keys[i]!=null) {
Key redoKey = keys[i];
Value redoVal = vals[i];
keys[i] = null;
vals[i] = null;
put(redoKey,redoVal);
i = (1+1) % M;
}
N--;
} 線性探測全部代碼：
public class LinearProbingHashST<Key, Value> {
private int M; // 數組的大小
private int N; // 鍵值對對數
private Key [] keys;
private Value [] vals;
public LinearProbingHashST (int M) {
this.M = M;
keys = (Key []) new Object[M];
vals = (Value[]) new Object[M];
}
/**
* @description: 擷取哈希值
*/
private int hash (Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
/**
* @description: 調整數組大小
*/
private void resize (int max) {
Key [] temp = (Key [])new Object[max];
for (int i =0;i<keys.length;i++) {
temp[i] = keys[i];
}
keys = temp;
}
/**
* @description: 插入操作
*/
public void put (Key key, Value val) {
// 當鍵值對數量已經超過數組一半時，将數組長度擴大一倍
if(N>(M/2)) resize(2*M);
// 計算哈希值,求出鍵的位置
int i = hash(key);
// 判斷該位置鍵是否為空
while(keys[i]!=null) {
if(key.equals(keys[i])) {
// 該位置的鍵和給定key相同，則更新對應的值
vals[i] = val;
return;
} else {
// 該位置的鍵和給定key不同，則檢查下一個位置的鍵
i = (i+1) % M;
}
}
// 該位置鍵為空則插入鍵值對
keys[i] = key;
vals[i] = val;
N++;
return;
}
/**
* @description: 根據給定鍵擷取值
*/
public Value get (Key key) {
for (int i=hash(key);keys[i]!=null;i=(i+1)%M) {
if (key.equals(keys[i])) {
return vals[i];
}
}
return null;
}
/**
* @description: 删除操作
*/
public void delete (Key key) {
// 給定鍵不存在，不進行删除
if (get(key) == null) return ;
// 計算哈希值， 求得鍵的位置
int i = hash(key);
// 擷取給定鍵的下标
while (!key.equals(keys[i])) {
i = (i+1) % M;
}
// 删除鍵值對
keys[i] = null;
vals[i] = null;
// 對被删除鍵後面鍵簇的鍵的位置進行删除并重新插入
i = (i+1)%M;
while (keys[i]!=null) {
Key redoKey = keys[i];
Value redoVal = vals[i];
keys[i] = null;
vals[i] = null;
put(redoKey,redoVal);
i = (1+1) % M;
}
N--;
}
} 測試代碼：
public class Test {
public static void main (String args[]) {
LinearProbingHashST<String, Integer> lst = new LinearProbingHashST<>(10);
lst.put("A",1);
lst.put("B",2);
lst.delete("A");
System.out.println(lst.get("A")); // 輸出null
System.out.println(lst.get("B")); // 輸出 2
}
} 回到頂部
再哈希法
設計多個哈希函數作為備份，如果發目前的哈希函數的計算會草成沖突，那麼就選擇另一個哈希函數進行計算，依次類推。這種方式不易産生鍵簇聚集的現象， 但會增加計算的時間
什麼是好的哈希函數
在介紹完了解決沖突的方式後，我們再回過頭來看什麼是“好”的哈希函數， 一個“好”的哈希函數應該是均勻的， 即對于鍵的集合中的任意一個鍵，映射到哈希值集合中的的任意一個值的機率是相等的。
這樣的哈希函數的效果進一步表現為兩個方面：
1. 當沖突可以不發生的時候（如線性探測實作的哈希表），能盡可能地減少沖突的發生
2. 當沖突不可避免地要發生的時候（如拉鍊法實作的哈希表）， 能使不同的哈希值發生沖突的機率大緻相等， 進而保證哈希表動态變化時仍能保持較為良好的結構（各條連結清單的長度大緻相等）
最後用一張圖總結下文章内容：