1. 哈希算法
如何選擇哈希算法：
- 計算公式花費的時間
- 關(guān)鍵字的長度
- 散列表大小
- 關(guān)鍵字分布情況
- 記錄查找概率
1.1 直接定址法
key是線性的，如年齡敬尺、年份等害幅。
1.2 數(shù)字分析法
找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址榴徐。
比如一個地區(qū)手機號守问，前面很多位都相同，不同可能是最后4位數(shù)坑资，將這部分作為散列算法的依據(jù)耗帕。
1.3 平方取中法
取關(guān)鍵字平方后的中間幾位作為散列地址。
先通過求關(guān)鍵字的平方值擴大相近數(shù)的差別袱贮，然后根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值仿便。又因為一個乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以由此產(chǎn)生的散列地址較為均勻字柠。
1.4 折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分探越，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址窑业。
1.5 取余法
取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址钦幔。
1.6 隨機數(shù)法
選擇一隨機函數(shù)，取關(guān)鍵字的隨機值作為散列地址常柄，通常用于關(guān)鍵字長度不同的場合鲤氢。
2. 哈希沖突解決
2.1 開放定址法
就是一旦發(fā)?了沖突，就去尋找下?個空的散列地址西潘。
只有散列表?夠大卷玉，空的散列地址總能找到，并將記錄存入喷市。
2.2 再散列函數(shù)法
對于散列表來說相种，我們事先準(zhǔn)備多個散列函數(shù)：
RHi指的是不同的散列函數(shù)。
2.3 鏈地址法
將所有的關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中品姓。我們稱為這種同義詞子表寝并。
在散列表中只存儲所有同義詞?表的頭指針(頭地址)。
簡單說腹备，沖突的用一個鏈表存起來衬潦。
2.4 公共溢出法
另開一個公共的表存儲沖突的數(shù)據(jù)≈菜郑基本表沒有查找到镀岛，就在溢出表中查找∮淹裕空間浪費嚴(yán)重漂羊。
3. 哈希表的實現(xiàn)
typedef int Status;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 //存儲空間初始分配量
#define SUCCESS 1
#define UNSUCCESS 0
//定義散列表長為數(shù)組的長度
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct {
int *elem; // 存儲哈希key的數(shù)組
int size; // 哈希表數(shù)組大小
int count; // 當(dāng)前數(shù)據(jù)元素個數(shù)
} HashTable;
// 1.初始化散列表
Status InitHashTable(HashTable *H) {
H->size = HASHSIZE;
H->elem = (int *)malloc(sizeof(int) * H->size);
H->count = 0;
// 數(shù)組初始化
for (int i = 0; i < H->size; i++)
H->elem[i] = NULLKEY;
return OK;
}
//2. 散列函數(shù)
int Hash(HashTable H, int key) {
return key % H.size; //除留余數(shù)法
}
//3. 插入關(guān)鍵字進散列表
Status InsertHash(HashTable *H, int key) {
if (H->count >= H->size) { // 滿了，可以考慮擴容
return UNSUCCESS;
}
int addr = Hash(*H, key); // 求散列地址
while (H->elem[addr] != NULLKEY) { // 如果不為空卸留，則沖突
addr = (addr + 1) % H->size; // 開放定址法的線性探測
}
H->elem[addr] = key; // 直到有空位后插入關(guān)鍵字
H->count++;
return SUCCESS;
}
//4. 散列表查找關(guān)鍵字
Status SearchHash(HashTable H, int key, int *addr) {
*addr = Hash(H, key); // 求散列地址
while (H.elem[*addr] != key) { // 如果不為空拨与，則沖突
*addr = (*addr+1) % H.size; // 開放定址法的線性探測
if (H.elem[*addr] == NULLKEY // 開放定地后為空
|| *addr == Hash(H, key)) // 循環(huán)有回到了原點
return UNSUCCESS; // 關(guān)鍵字不存在
}
return SUCCESS;
}
