詳解散列表算法與其相關(guān)的C語言實現(xiàn)
散列表（也叫哈希表）是一種查找算法，與鏈表、樹等算法不同的是，散列表算法在查找時不需要進行一系列和關(guān)鍵字（關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用以標識一個數(shù)據(jù)元素）的比較操作。
散列表算法希望能盡量做到不經(jīng)過任何比較，通過一次存取就能得到所查找的數(shù)據(jù)元素，因而必須要在數(shù)據(jù)元素的存儲位置和它的關(guān)鍵字（可用key表示）之間建立一個確定的對應(yīng)關(guān)系，使每個關(guān)鍵字和散列表中一個唯一的存儲位置相對應(yīng)。因此在查找時，只要根據(jù)這個對應(yīng)關(guān)系找到給定關(guān)鍵字在散列表中的位置即可。這種對應(yīng)關(guān)系被稱為散列函數(shù)(可用h(key)表示)。
根據(jù)設(shè)定的散列函數(shù)h(key)和處理沖突的方法將一組關(guān)鍵字key映像到一個有限的連續(xù)的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的像作為數(shù)據(jù)元素在表中的存儲位置，這種表便被稱為散列表，這一映像過程稱為散列，所得存儲位置稱為散列地址。
關(guān)鍵字、散列函數(shù)以及散列表的關(guān)系如下圖所示：
1、散列函數(shù)
散列函數(shù)是從關(guān)鍵字到地址區(qū)間的映像。
好的散列函數(shù)能夠使得關(guān)鍵字經(jīng)過散列后得到一個隨機的地址，以便使一組關(guān)鍵字的散列地址均勻地分布在整個地址區(qū)間中，從而減少沖突。
常用的構(gòu)造散列函數(shù)的方法有：
（1）、直接定址法
取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址，即：
h(key) = key 或 h(key) = a * key + b
其中a和b為常數(shù)。
（2）、數(shù)字分析法
（3）、平方取值法
取關(guān)鍵字平方后的中間幾位為散列地址。
（4）、折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）作為散列地址。
（5）、除留余數(shù)法
取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址，即：
h(key) = key MOD p p ≤ m
（6）、隨機數(shù)法
選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的散列地址，即：
h(key) = random(key)
其中random為隨機函數(shù)。
2、處理沖突
對不同的關(guān)鍵字可能得到同一散列地址，即key1 ≠ key2，而h(key1)= h(key2)，這種現(xiàn)象稱為沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱作同義詞。
在一般情況下，散列函數(shù)是一個壓縮映像，這就不可避免地會產(chǎn)生沖突，因此，在創(chuàng)建散列表時不僅要設(shè)定一個好的散列函數(shù)，而且還要設(shè)定一種處理沖突的方法。
常用的處理沖突的方法有：
（1）、開放定址法
hi =(h(key) + di) MOD m i =1,2,…,k(k ≤ m-1)
其中，h(key)為散列函數(shù)，m為散列表表長，di為增量序列，可有下列三種取法：
1)、di = 1,2,3,…,m-1，稱線性探測再散列；
2）、di = 12,-12,22,-22,32,…,±k2 (k ≤m/2)，稱二次探測再散列；
3）、di = 偽隨機數(shù)序列，稱偽隨機探測再散列。
（2）、再散列法
hi = rhi(key) i = 1,2,…,k
rhi均是不同的散列函數(shù)。
（3）、鏈地址法
將所有關(guān)鍵字為同義詞的數(shù)據(jù)元素存儲在同一線性鏈表中。假設(shè)某散列函數(shù)產(chǎn)生的散列地址在區(qū)間[0,m-1]上，則設(shè)立一個指針型向量void *vec[m],其每個分量的初始狀態(tài)都是空指針。凡散列地址為i的數(shù)據(jù)元素都插入到頭指針為vec[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾，也可以在表的中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序排列。
（4）、建立一個公共溢出區(qū)
相關(guān)的C語言解釋
hash.h
哈希表數(shù)據(jù)結(jié)構(gòu)&&接口定義頭文件
#ifndef HASH_H
#define HASH_H
#define HASH_TABLE_INIT_SIZE 7
#define SUCCESS 1
#define FAILED 0
/**
* 哈希表槽的數(shù)據(jù)結(jié)構(gòu)
*/
typedef struct Bucket {
char *key;
void *value;
struct Bucket *next;
} Bucket;
/**
* 哈希表數(shù)據(jù)結(jié)構(gòu)
*/
typedef struct HashTable {
int size; // 哈希表大小
int elem_num; // 哈希表已經(jīng)保存的數(shù)據(jù)元素個數(shù)
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
哈希表操作函數(shù)具體實現(xiàn)
#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;
}
/**
* 散列函數(shù)
*
* T = O(n)
*
*/
int hashIndex(HashTable *ht, char *key)
{
int hash = 0;
while (*key != '\0') {
hash += (int)*key;
key ++;
}
return hash % ht->size;
}
/**
* 哈希查找函數(shù)
*
* 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是否已經(jīng)存在于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;
}
/**
* 哈希刪除函數(shù)
*
* 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;
}
/**
* 哈希表銷毀函數(shù)
*
* 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
運行結(jié)果
開放尋址法
在開放尋址法（open addressing）中，所有的元素都存放在散列表里。亦即，每個表項或包含動態(tài)集合的一個元素，或包含NIL。當(dāng)查找一個元素時，要檢查所有的表項，直到找到所需的元素，或者最終發(fā)現(xiàn)該元素不在表中。不像在鏈接法中，這沒有鏈表，也沒有元素存放在散列表外。在這種方法中，散列表可能會被填滿，以致于不能插入任何新的元素，但裝載因子a是絕對不會超過1的
線性探測法
第一次沖突移動1個單位，再次沖突時，移動2個，再次沖突，移動3個單位，依此類推
它的散列函數(shù)是：H(x) = (Hash(x) + F(i)) mod TableSize, 且F(0) = 0
舉例（騰訊面試題目）
已知一個線性表（38, 25, 74, 63, 52, 48），假定采用散列函數(shù) 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
線性探測方法比較容易實現(xiàn)，但它卻存在一個問題，稱為一次群集(primary clustering).隨著時間的推移，連續(xù)被占用的槽不斷增加，平均查找時間也隨著不斷增加。集群現(xiàn)象很容易出現(xiàn)，這是因為當(dāng)一個空槽前有i個滿的槽時，該空槽為下一個將被占用的槽的概率是 （i + 1） / n.連續(xù)占用的槽的序列會變得越來越長，因而平均查找時間也會隨之增加
平方探測
為了避免上面提到的一個群集的問題：第一次沖突時移動1（1的平方）個單位，再次沖突時，移動4（2的平方）個單位，還沖突，移動9個單位，依此類推。F（i） = i * i
相關(guān)文章
這篇文章主要介紹了C++中的整形字節(jié)數(shù)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
C++調(diào)用matlab引擎實現(xiàn)三維圖的繪制
這篇文章主要為大家詳細介紹了C++如何調(diào)用matlab引擎實現(xiàn)三維圖的繪制，文中的示例代碼講解詳細，對我們學(xué)習(xí)C++和Matlab有一定的幫助，需要的可以參考一下2022-12-12
這篇文章主要給大家介紹了關(guān)于Qt兩種定時器使用實現(xiàn)方式的相關(guān)資料,Qt中的定時器類是QTimer,QTimer不是一個可見的界面組件,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01
指針在 C\C++ 語言中是很重要的內(nèi)容,并且和指針有關(guān)的內(nèi)容一向令初學(xué)者頭大,這篇文章主要給大家介紹了關(guān)于C/C++中指針的相關(guān)資料,需要的朋友可以參考下2021-09-09
這篇文章主要為大家詳細介紹了C++實現(xiàn)超市商品管理系統(tǒng)最新版，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
函數(shù)是一組一起執(zhí)行一個任務(wù)的語句。每個?C?程序都至少有一個函數(shù)，即主函數(shù)?main()?，所有簡單的程序都可以定義其他額外的函數(shù)，由于篇幅過大，分為兩篇講解，下面開始上篇2022-04-04
C語言數(shù)據(jù)結(jié)構(gòu)之棧和隊列的實現(xiàn)及應(yīng)用
棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實現(xiàn)方式。本文將以順序結(jié)構(gòu)實現(xiàn)棧，鏈表方式實現(xiàn)隊列，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一下吧2022-08-08
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。本文將用C語言實現(xiàn)雙向循環(huán)鏈表，需要的可以參考一下2022-06-06
C++ 11實現(xiàn)檢查是否存在特定的成員函數(shù)
C++11/14相比以往的C++98/03在很多方面做了簡化和增強，尤其是在泛型編程方面，讓C++的泛型編程的威力變得更加強大，下面這篇文章主要介紹了利用C++ 11實現(xiàn)檢查是否存在特定成員函數(shù)的相關(guān)資料，需要的朋友可以參考下。2017-02-02
這篇文章主要介紹了基于C++實現(xiàn)的線程休眠代碼,包括了Linux平臺及基于boost庫的兩種實現(xiàn)方法,有不錯的參考借鑒價值,需要的朋友可以參考下2014-10-10