詳解哈希表的查找
哈希表和哈希函數
在記錄的存儲位置和它的關鍵字之間是建立一個確定的對應關係（映射函數），使每個關鍵字和一個存儲位置能唯一對應。
這個映射函數稱為哈希函數，根據這個原則建立的表稱為哈希表(Hash Table)，也叫散列表。
以上描述，如果通過數學形式來描述就是：
若查找關鍵字為 key，則其值存放在 f(key) 的存儲位置上。由此，不需比較便可直接取得所查記錄。
註：哈希查找與線性表查找和樹表查找最大的區別在於，不用數值比較。
衝突
若 key1 ≠ key2 ，而 f(key1) = f(key2)，這種情況稱為衝突(Collision)。
根據哈希函數f(key)和處理衝突的方法將一組關鍵字映射到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的「像」作為記錄在表中的存儲位置，這一映射過程稱為構造哈希表。
構造哈希表這個場景就像汽車找停車位，如果車位被人佔了，只能找空的地方停。
構造哈希表
由以上內容可知，哈希查找本身其實不費吹灰之力，問題的關鍵在於如何構造哈希表和處理衝突。
常見的構造哈希表的方法有 5 種：
（1）直接定址法
說白了，就是小學時學過的一元一次方程。
即 f(key) = a * key + b。其中，a和b 是常數。
（2）數字分析法
假設關鍵字是R進位數（如十進位）。並且哈希表中可能出現的關鍵字都是事先知道的，則可選取關鍵字的若干數位組成哈希地址。
選取的原則是使得到的哈希地址盡量避免衝突，即所選數位上的數字儘可能是隨機的。
（3）平方取中法
取關鍵字平方後的中間幾位為哈希地址。通常在選定哈希函數時不一定能知道關鍵字的全部情況，僅取其中的幾位為地址不一定合適；
而一個數平方後的中間幾位數和數的每一位都相關， 由此得到的哈希地址隨機性更大。取的位數由表長決定。
（4）除留餘數法
取關鍵字被某個不大於哈希表表長 m 的數 p 除後所得的餘數為哈希地址。
即 f(key) = key % p (p ≤ m)
這是一種最簡單、最常用的方法，它不僅可以對關鍵字直接取模，也可在摺疊、平方取中等運算之後取模。
注意：p的選擇很重要，如果選的不好，容易產生衝突。根據經驗，一般情況下可以選p為素數。
（5）隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即 f(key) = random(key)。
通常，在關鍵字長度不等時採用此法構造哈希函數較為恰當。
解決衝突
設計合理的哈希函數可以減少衝突，但不能完全避免衝突。
所以需要有解決衝突的方法，常見有兩類
（1）開放定址法
如果兩個數據元素的哈希值相同，則在哈希表中為後插入的數據元素另外選擇一個表項。
當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程序就會繼續往後查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項。
例子
若要將一組關鍵字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。
採用除留餘數法構造哈希表；採用開放定址法處理衝突。
不妨設選取的p和m為13，由 f(key) = key % 13 可以得到下表。
需要注意的是，在上圖中有兩個關鍵字的探查次數為 2 ，其他都是1。
這個過程是這樣的：
a. 12 % 13 結果是12，而它的前面有個 25 ，25 % 13 也是12，存在衝突。
我們使用開放定址法 (12 + 1) % 13 = 0，沒有衝突，完成。
b. 35 % 13 結果是 9，而它的前面有個 9，9 % 13也是 9，存在衝突。
我們使用開放定址法 (9 + 1) % 13 = 10，沒有衝突，完成。
（2）拉鏈法
將哈希值相同的數據元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須採用線性查找方法。
在這種方法中，哈希表中每個單元存放的不再是記錄本身，而是相應同義詞單鏈表的頭指針。
例子
如果對開放定址法例子中提到的序列使用拉鏈法，得到的結果如下圖所示：
實現一個哈希表
假設要實現一個哈希表，要求
a. 哈希函數採用除留餘數法，即 f(key) = key % p (p ≤ m)
b. 解決衝突採用開放定址法，即 f2(key) = (f(key)+i) % size (p ≤ m)
（1）定義哈希表的數據結構
class HashTable {
public int key = 0; // 關鍵字
public int data = 0; // 數值
public int count = 0; // 探查次數
}
（2）在哈希表中查找關鍵字key
根據設定的哈希函數，計算哈希地址。如果出現地址衝突，則按設定的處理衝突的方法尋找下一個地址。
如此反覆，直到不衝突為止（查找成功）或某個地址為空（查找失敗）。
/**
* 查找哈希表
* 構造哈希表採用除留取余法，即f(key) = key mod p (p ≤ size)
* 解決衝突採用開放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
* ha為哈希表，p為模，size為哈希表大小，key為要查找的關鍵字
*/
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
int addr = key % p; // 採用除留取余法找哈希地址
// 若發生衝突，用開放定址法找下一個哈希地址
while (ha[addr].key != KEY && ha[addr].key != key) {
addr = (addr + 1) % size;
}
if (ha[addr].key == key) {
return addr; // 查找成功
} else {
return FAILED; // 查找失敗
}
}
（3）刪除關鍵字為key的記錄
在採用開放定址法處理衝突的哈希表上執行刪除操作，只能在被刪記錄上做刪除標記，而不能真正刪除記錄。
找到要刪除的記錄，將關鍵字置為刪除標記DELKEY。
public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
int addr = 0;
addr = searchHashTable(ha, p, size, key);
if (FAILED != addr) { // 找到記錄
ha[addr].key = DELKEY; // 將該位置的關鍵字置為DELKEY
return SUCCESS;
} else {
return KEY; // 查找不到記錄，直接返回KEY
}
}
（4）插入關鍵字為key的記錄
將待插入的關鍵字key插入哈希表
先調用查找演算法，若在表中找到待插入的關鍵字，則插入失敗；
若在表中找到一個開放地址，則將待插入的結點插入到其中，則插入成功。
public void insertHashTable(HashTable[] ha, int p, int size, int key) {
int i = 1;
int addr = 0;
addr = key % p; // 通過哈希函數獲取哈希地址
if (ha[addr].key == KEY || ha[addr].key == DELKEY) { // 如果沒有衝突，直接插入
ha[addr].key = key;
ha[addr].count = 1;
} else { // 如果有衝突，使用開放定址法處理衝突
do {
addr = (addr + 1) % size; // 尋找下一個哈希地址
i++;
} while (ha[addr].key != KEY && ha[addr].key != DELKEY);
ha[addr].key = key;
ha[addr].count = i;
}
}
（5）建立哈希表
先將哈希表中各關鍵字清空，使其地址為開放的，然後調用插入演算法將給定的關鍵字序列依次插入。
public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
int i = 0;
// 將哈希表中的所有關鍵字清空
for (i = 0; i < ha.length; i++) {
ha[i].key = KEY;
ha[i].count = 0;
}
// 將關鍵字序列依次插入哈希表中
for (i = 0; i < list.length; i++) {
this.insertHashTable(ha, p, size, list[i]);
}
}
完整代碼
class HashTable {
public int key = 0; // 關鍵字
public int data = 0; // 數值
public int count = 0; // 探查次數
}
public class HashSearch {
private final static int MAXSIZE = 20;
private final static int KEY = 1;
private final static int DELKEY = 2;
private final static int SUCCESS = 0;
private final static int FAILED = 0xFFFFFFFF;
/**
* 查找哈希表
* 構造哈希表採用除留取余法，即f(key) = key mod p (p ≤ size)
* 解決衝突採用開放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
* ha為哈希表，p為模，size為哈希表大小，key為要查找的關鍵字
*/
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
int addr = key % p; // 採用除留取余法找哈希地址
// 若發生衝突，用開放定址法找下一個哈希地址
while (ha[addr].key != KEY && ha[addr].key != key) {
addr = (addr + 1) % size;
}
if (ha[addr].key == key) {
return addr; // 查找成功
} else {
return FAILED; // 查找失敗
}
}
/**
* 刪除哈希表中關鍵字為key的記錄
* 找到要刪除的記錄，將關鍵字置為刪除標記DELKEY
*/
public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
int addr = 0;
addr = searchHashTable(ha, p, size, key);
if (FAILED != addr) { // 找到記錄
ha[addr].key = DELKEY; // 將該位置的關鍵字置為DELKEY
return SUCCESS;
} else {
return KEY; // 查找不到記錄，直接返回KEY
}
}
/**
* 將待插入的關鍵字key插入哈希表
* 先調用查找演算法，若在表中找到待插入的關鍵字，則插入失敗；
* 若在表中找到一個開放地址，則將待插入的結點插入到其中，則插入成功。
*/
public void insertHashTable(HashTable[] ha, int p, int size, int key) {
int i = 1;
int addr = 0;
addr = key % p; // 通過哈希函數獲取哈希地址
if (ha[addr].key == KEY || ha[addr].key == DELKEY) { // 如果沒有衝突，直接插入
ha[addr].key = key;
ha[addr].count = 1;
} else { // 如果有衝突，使用開放定址法處理衝突
do {
addr = (addr + 1) % size; // 尋找下一個哈希地址
i++;
} while (ha[addr].key != KEY && ha[addr].key != DELKEY);
ha[addr].key = key;
ha[addr].count = i;
}
}
/**
* 創建哈希表
* 先將哈希表中各關鍵字清空，使其地址為開放的，然後調用插入演算法將給定的關鍵字序列依次插入。
*/
public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
int i = 0
// 將哈希表中的所有關鍵字清空
for (i = 0; i < ha.length; i++) {
ha[i].key = KEY;
ha[i].count = 0;
}
// 將關鍵字序列依次插入哈希表中
for (i = 0; i < list.length; i++) {
this.insertHashTable(ha, p, size, list[i]);
}
}
/**
* 輸出哈希表
*/
public void displayHashTable(HashTable[] ha) {
int i = 0;
System.out.format("pos: ", "pos");
for (i = 0; i < ha.length; i++) {
System.out.format("%4d", i);
}
System.out.println;
System.out.format("key: ");
for (i = 0; i < ha.length; i++) {
if (ha[i].key != KEY) {
System.out.format("%4d", ha[i].key);
} else {
System.out.format(" ");
}
}
System.out.println;
System.out.format("count: ");
for (i = 0; i < ha.length; i++) {
if (0 != ha[i].count) {
System.out.format("%4d", ha[i].count);
} else {
System.out.format(" ");
}
}
System.out.println;
}
public static void main(String[] args) {
int list = { 3, 112, 245, 27, 44, 19, 76, 29, 90 };
HashTable ha = new HashTable[MAXSIZE];
for (int i = 0; i < ha.length; i++) {
ha[i] = new HashTable;
}
HashSearch search = new HashSearch;
search.createHashTable(ha, list, 19, MAXSIZE);
search.displayHashTable(ha);
}
}
參考資料
《數據結構習題與解析》（B級第3版）
轉自：靜默虛空
http://www.cnblogs.com/jingmoxukong/p/4332252.html
-----這裡是數學思維的聚集地------
「超級數學建模」（微信號supermodeling），每天學一點小知識，輕鬆了解各種思維，做個好玩的理性派。50萬數學精英都在關注！
※歐拉在各個數學領域遍地開花，都稱之為「歐拉公式」卻完全不一樣
※繼相對論、量子論之後，它的出現，給牛頓又來了致命一刀
TAG:超級數學建模 |