1. 哈希算法

如何選擇哈希算法：

1. 計算公式花費的時間
2. 關(guān)鍵字的長度
3. 散列表大小
4. 關(guān)鍵字分布情況
5. 記錄查找概率

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ù)法

對于散列表來說，我們事先準備多個散列函數(shù)：

指的是不同的散列函數(shù)。

2.3 鏈地址法

將所有的關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中。我們稱為這種同義詞子表。

在散列表中只存儲所有同義詞?表的頭指針(頭地址)。

簡單說，沖突的用一個鏈表存起來。

2.4 公共溢出法

另開一個公共的表存儲沖突的數(shù)據(jù)。基本表沒有查找到，就在溢出表中查找。空間浪費嚴重。

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;  // 當前數(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;
}