散列表（也叫哈希表）是一種查找算法，與鏈表、樹等算法不同的是，散列表算法在查找時不需要進行一系列和關鍵字（關鍵字是數據元素中某個數據項的值，用以標識一個數據元素）的比較操作。
散列表算法希望能盡量做到不經過任何比較，通過一次存取就能得到所查找的數據元素，因而必須要在數據元素的存儲位置和它的關鍵字（可用key表示）之間建立一個確定的對應關系，使每個關鍵字和散列表中一個唯一的存儲位置相對應。因此在查找時，只要根據這個對應關系找到給定關鍵字在散列表中的位置即可。這種對應關系被稱為散列函數(可用h(key)表示)。
根據設定的散列函數h(key)和處理沖突的方法將一組關鍵字key映像到一個有限的連續的地址區間上，并以關鍵字在地址區間中的像作為數據元素在表中的存儲位置，這種表便被稱為散列表，這一映像過程稱為散列，所得存儲位置稱為散列地址。
關鍵字、散列函數以及散列表的關系如下圖所示：
1、散列函數
散列函數是從關鍵字到地址區間的映像。
好的散列函數能夠使得關鍵字經過散列后得到一個隨機的地址，以便使一組關鍵字的散列地址均勻地分布在整個地址區間中，從而減少沖突。
常用的構造散列函數的方法有：
（1）、直接定址法
取關鍵字或關鍵字的某個線性函數值為散列地址，即：
h(key) = key 或 h(key) = a * key + b
其中a和b為常數。
（2）、數字分析法
（3）、平方取值法
取關鍵字平方后的中間幾位為散列地址。
（4）、折疊法
將關鍵字分割成位數相同的幾部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為散列地址。
（5）、除留余數法
取關鍵字被某個不大于散列表表長m的數p除后所得的余數為散列地址，即：
h(key) = key MOD p p ≤ m
（6）、隨機數法
選擇一個隨機函數，取關鍵字的隨機函數值為它的散列地址，即：
h(key) = random(key)
其中random為隨機函數。
2、處理沖突
對不同的關鍵字可能得到同一散列地址，即key1 ≠ key2，而h(key1)= h(key2)，這種現象稱為沖突。具有相同函數值的關鍵字對該散列函數來說稱作同義詞。
在一般情況下，散列函數是一個壓縮映像，這就不可避免地會產生沖突，因此，在創建散列表時不僅要設定一個好的散列函數，而且還要設定一種處理沖突的方法。
常用的處理沖突的方法有：
（1）、開放定址法
hi =(h(key) + di) MOD m i =1,2,…,k(k ≤ m-1)
其中，h(key)為散列函數，m為散列表表長，di為增量序列，可有下列三種取法：
1)、di = 1,2,3,…,m-1，稱線性探測再散列；
2）、di = 12,-12,22,-22,32,…,±k2 (k ≤m/2)，稱二次探測再散列；
3）、di = 偽隨機數序列，稱偽隨機探測再散列。
（2）、再散列法
hi = rhi(key) i = 1,2,…,k
rhi均是不同的散列函數。
（3）、鏈地址法
將所有關鍵字為同義詞的數據元素存儲在同一線性鏈表中。假設某散列函數產生的散列地址在區間[0,m-1]上，則設立一個指針型向量void *vec[m],其每個分量的初始狀態都是空指針。凡散列地址為i的數據元素都插入到頭指針為vec[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾，也可以在表的中間，以保持同義詞在同一線性鏈表中按關鍵字有序排列。
（4）、建立一個公共溢出區
相關的C語言解釋
hash.h
哈希表數據結構&&接口定義頭文件
#ifndef HASH_H #define HASH_H #define HASH_TABLE_INIT_SIZE 7 #define SUCCESS 1 #define FAILED 0 /** * 哈希表槽的數據結構 */ typedef struct Bucket { char *key; void *value; struct Bucket *next; } Bucket; /** * 哈希表數據結構 */ typedef struct HashTable { int size; // 哈希表大小 int elem_num; // 哈希表已經保存的數據元素個數 Bucket **buckets; } HashTable; int hashIndex(HashTable *ht, char *key); int hashInit(HashTable *ht); int hashLookup(HashTable *ht, char *key, void **result); int hashInsert(HashTable *ht, char *key, void *value); int hashRemove(HashTable *ht, char *key); int hashDestory(HashTable *ht); #endif
hash.c
哈希表操作函數具體實現
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "hash.h" /** * 初始化哈希表 * * T = O(1) * */ int hashInit(HashTable *ht) { ht->size = HASH_TABLE_INIT_SIZE; ht->elem_num = 0; ht->buckets = (Bucket **)calloc(ht->size, sizeof(Bucket *)); if (ht->buckets == NULL) return FAILED; else return SUCCESS; } /** * 散列函數 * * T = O(n) * */ int hashIndex(HashTable *ht, char *key) { int hash = 0; while (*key != '/0') { hash += (int)*key; key ++; } return hash % ht->size; } /** * 哈希查找函數 * * T = O(n) * */ int hashLookup(HashTable *ht, char *key, void **result) { int index = hashIndex(ht, key); Bucket *bucket = ht->buckets[index]; while (bucket) { if (strcmp(bucket->key, key) == 0) { *result = bucket->value; return SUCCESS; } bucket = bucket->next; } return FAILED; } /** * 哈希表插入操作 * * T = O(1) * */ int hashInsert(HashTable *ht, char *key, void *value) { int index = hashIndex(ht, key); Bucket *org_bucket, *tmp_bucket; org_bucket = tmp_bucket = ht->buckets[index]; // 檢查key是否已經存在于hash表中 while (tmp_bucket) { if (strcmp(tmp_bucket->key, key) == 0) { tmp_bucket->value = value; return SUCCESS; } tmp_bucket = tmp_bucket->next; } Bucket *new = (Bucket *)malloc(sizeof(Bucket)); if (new == NULL) return FAILED; new->key = key; new->value = value; new->next = NULL; ht->elem_num += 1; // 頭插法 if (org_bucket) { new->next = org_bucket; } ht->buckets[index] = new; return SUCCESS; } /** * 哈希刪除函數 * * T = O(n) * */ int hashRemove(HashTable *ht, char *key) { int index = hashIndex(ht, key); Bucket *pre, *cur, *post; pre = NULL; cur = ht->buckets[index]; while (cur) { if (strcmp(cur->key, key) == 0) { post = cur->next; if (pre == NULL) { ht->buckets[index] = post; } else { pre->next = post; } free(cur); return SUCCESS; } pre = cur; cur = cur->next; } return FAILED; } /** * 哈希表銷毀函數 * * T = O(n) */ int hashDestory(HashTable *ht) { int i; Bucket *cur, *tmp; cur = tmp = NULL; for (i = 0; i < ht->size; i ++) { cur = ht->buckets[i]; while (cur) { tmp = cur->next; free(cur); cur = tmp; } } free(ht->buckets); return SUCCESS; }
test.c
單元測試文件
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include "hash.h" int main(int argc, char **argv) { HashTable *ht = (HashTable *)malloc(sizeof(HashTable)); int result = hashInit(ht); assert(result == SUCCESS); /* Data */ int int1 = 10; int int2 = 20; char str1[] = "Hello World!"; char str2[] = "Value"; char str3[] = "Hello New World!"; /* to find data container */ int *j = NULL; char *find_str = NULL; /* Test Key Insert */ printf("Key Insert:/n"); hashInsert(ht, "FirInt", &int1); hashInsert(ht, "FirStr", str1); hashInsert(ht, "SecStr", str2); printf("Pass Insert/n"); /* Test Key Lookup*/ printf("Key Lookup:/n"); result = hashLookup(ht, "FirStr", &find_str); assert(result == SUCCESS); printf("pass lookup, the value is %s/n", find_str); /* Test Update */ printf("Key Update:/n"); hashInsert(ht, "FirStr", str3); result = hashLookup(ht, "FirStr", &find_str); assert(result == SUCCESS); printf("pass update, the value is %s/n", find_str); return 0; }
編譯方法
gcc -Wall -g -o main test.c hash.c
運行結果
開放尋址法
在開放尋址法（open addressing）中，所有的元素都存放在散列表里。亦即，每個表項或包含動態集合的一個元素，或包含NIL。當查找一個元素時，要檢查所有的表項，直到找到所需的元素，或者最終發現該元素不在表中。不像在鏈接法中，這沒有鏈表，也沒有元素存放在散列表外。在這種方法中，散列表可能會被填滿，以致于不能插入任何新的元素，但裝載因子a是絕對不會超過1的
線性探測法
第一次沖突移動1個單位，再次沖突時，移動2個，再次沖突，移動3個單位，依此類推
它的散列函數是：H(x) = (Hash(x) + F(i)) mod TableSize, 且F(0) = 0
舉例（騰訊面試題目）
已知一個線性表（38, 25, 74, 63, 52, 48），假定采用散列函數 h(key) = key % 7 計算散列地址，并散列存儲在散列表 A[0..6]中，若采用線性探測方法解決沖突，則在該散列表上進行等概率成功查找的平均長度為 ？
下邊模擬線性探測：
38 % 7 == 3, 無沖突， ok
25 % 7 == 4, 無沖突， ok
74 % 7 == 4, 沖突， （4 + 1）% 7 == 5, 無沖突，ok
63 % 7 == 0, 無沖突， ok
52 % 7 == 3, 沖突， （3 + 1） % 7 == 4. 沖突， （4 + 1） % 7 == 5, 沖突， （5 + 1）%7 == 6,無沖突，ok
48 % 7 == 6, 沖突， （6 + 1） % 7 == 0, 沖突， （0 + 1） % 7 == 1,無沖突，ok
畫圖如下：
平均查找長度 = （1 + 3 + 1 + 1 + 2 + 3） % 6 = 2
線性探測方法比較容易實現，但它卻存在一個問題，稱為一次群集(primary clustering).隨著時間的推移，連續被占用的槽不斷增加，平均查找時間也隨著不斷增加。集群現象很容易出現，這是因為當一個空槽前有i個滿的槽時，該空槽為下一個將被占用的槽的概率是 （i + 1） / n.連續占用的槽的序列會變得越來越長，因而平均查找時間也會隨之增加
平方探測
為了避免上面提到的一個群集的問題：第一次沖突時移動1（1的平方）個單位，再次沖突時，移動4（2的平方）個單位，還沖突，移動9個單位，依此類推。F（i） = i * i
新聞熱點
疑難解答
圖片精選
