利用C語(yǔ)言實(shí)現(xiàn)HashTable
更新時(shí)間：2013年09月14日 09:09:39 作者：
根據(jù)KEY從hashtable中獲取接點(diǎn)，步驟是先根據(jù)KEY計(jì)算hash值，然后從hashtable中找到指定的接點(diǎn)或者接點(diǎn)鏈表
HashTable是在實(shí)際應(yīng)用中很重要的一個(gè)結(jié)構(gòu)，下面討論一個(gè)簡(jiǎn)單的實(shí)現(xiàn)，雖然簡(jiǎn)單，但是該有的部分都還是有的。
一，訪問(wèn)接口
創(chuàng)建一個(gè)hashtable.
hashtable hashtable_new（int size） /其中size表示包含的接點(diǎn)個(gè)數(shù)。
存入key-value至hashtable中。
void hashtable_put（hashtable h,const char* key,void *val）；
根據(jù)key從hashtable中取出value值。
void * hashtable_get（hashtable h,const char *key）；
釋放hashtable。
void hashtable_free（hashtable h）；
釋放單個(gè)hash 接點(diǎn)
void hashtable_delete_node（hashtable h, const char *key）；
二，數(shù)據(jù)結(jié)構(gòu)
hash接點(diǎn)的結(jié)構(gòu)：
復(fù)制代碼 代碼如下:
typedef struct hashnode_struct{
struct hashnode_struct *next;
const char *key;
void *val;
}*hashnode,_hashnode;
這個(gè)結(jié)構(gòu)還是很容易理解的，除了必須的key-value之外，包含一個(gè)用于沖突的鏈表結(jié)構(gòu)。
hashtable的數(shù)據(jù)結(jié)構(gòu)：
復(fù)制代碼 代碼如下:
typedef struct hashtable_struct{
pool_t p;
int size;
int count;
struct hashnode_struct *z;
}*hashtable,_hashtable;
對(duì)這個(gè)結(jié)構(gòu)說(shuō)明如下：
pool_t：內(nèi)存池結(jié)構(gòu)管理hashtable使用的內(nèi)存。結(jié)構(gòu)參考"C語(yǔ)言內(nèi)存池使用模型"
size：當(dāng)前hash的接點(diǎn)空間大小。
count：用于表示當(dāng)前接點(diǎn)空間中可用的hash接點(diǎn)個(gè)數(shù)
z：用于在接點(diǎn)空間中存儲(chǔ)接點(diǎn)。
三，創(chuàng)建hashtable
代碼如下：
復(fù)制代碼 代碼如下:
hashtable hashtable_new（int size）
{
hashtable ht;
pool_t p;
p = _pool_new_heap（sizeof（_hashnode）*size + sizeof（_hashtable））；
ht= pool_malloc（p, sizeof（_hashtable））；
ht->size = size;
ht->p = p;
ht->z = pool_malloc（p, sizeof（_hashnode）*prime）；
return ht;
}
這個(gè)函數(shù)比較簡(jiǎn)單，先定義并初始化一個(gè)內(nèi)存池，大小根據(jù)size而定，所以在實(shí)際使用時(shí)，我們的size應(yīng)該要分配的相對(duì)大點(diǎn)，比較好。
四，存入key-value值
在這個(gè)操作之前，先要定義一個(gè)根據(jù)KEY值計(jì)算hashcode的函數(shù)。
復(fù)制代碼 代碼如下:
static int hashcode（const char *s, int len）
{
const unsigned char *name = （const unsigned char *）s;
unsigned long h = 0, g;
int i;
for（i=0;i
{
h = （h 《 4） + （unsigned long）（name[i]）； //hash左移4位，當(dāng)前字符ASCII存入hash
if （（g = （h & 0xF0000000UL））！=0）
h ^= （g 》 24）；
h &= ~g; //清空28-31位。
}
return （int）h;
}
這個(gè)函數(shù)采用精典的ELF hash函數(shù)。
代碼如下：
復(fù)制代碼 代碼如下:
void hashtable_put（hashtable h, const char *key, void *val）
{
if（h == NULL || key == NULL）
return;
int len = strlen（key）；
int index = hashcode（key,len）；
hashtable node;
h->dirty++;
if（（node = hashtable_node_get（h, key,len, index）） != NULL） //如果已經(jīng)存在，就替換成現(xiàn)在的值，因?yàn)楝F(xiàn)在的比較新。
{
n->key = key;
n->val = val;
return;
}
node = hashnode_node_new（h, index）； // 新建一個(gè)HASH NODE接點(diǎn)。
node->key = key;
node->val = val;
}
hashtable_node_get用于查找該KEY是否在HASH中已經(jīng)存在，實(shí)現(xiàn)很簡(jiǎn)單，如下：
static hashnode hashtable_node_get（hashtable h, const char *key, int len, int index）
{
hashnode node;
int i = index % h->size;
for（node = &h->z[i]; node != NULL; node = node->next） // 在index值 [HASH值] 所對(duì)應(yīng)的HASH桶上遍歷尋找
if（node->key != NULL && （strlen（node->key）==len） && （strncmp（key, node->key, len） == 0））
return node;
return NULL;
}
新建一個(gè)HASH NODE接點(diǎn)如下：
復(fù)制代碼 代碼如下:
static hashnode hashnode_node_new（hashtable h, int index）
{
hashnode node;
int i = index % h->size;
h->count++;
for（node = &h->z[i]; node != NULL; node = node->next）
if（node->key == NULL） //這里的處理是：如果在HASH桶中存在某個(gè)值，KEY是空的，表明這個(gè)值已經(jīng)沒(méi)有用了，就用它來(lái)替換為現(xiàn)在準(zhǔn)備寫(xiě)入的新接點(diǎn)。
return node;
node = pool_malloc（h->p, sizeof（_hashnode））； // 新建一個(gè)接點(diǎn)
node->next = h->z[i].next; // 加入到桶中，就是加到鏈表的第一個(gè)接點(diǎn)。
h->z[i].next = node;
return node;
}
五，從HASHTABLE中獲取接點(diǎn)
根據(jù)KEY從hashtable中獲取接點(diǎn)，步驟是先根據(jù)KEY計(jì)算hash值，然后從hashtable中找到指定的接點(diǎn)或者接點(diǎn)鏈表。如下：
復(fù)制代碼 代碼如下:
void *hashtable_get（hashtable h, const char *key）
{
if（h == NULL || key == NULL）
return NULL;
hashnode node;
int len = strlen（key）；
if（h == NULL || key == NULL || len <= 0 || （node = hashtable_node_get（h, key, len, hashcode（key,len））） == NULL）
{
return NULL;
}
return node->val;
}
這個(gè)函數(shù)就很容易理解了。
六，釋放HASHTABLE
hashtable的釋放就比較簡(jiǎn)單了，因?yàn)槲覀兯械膬?nèi)存申請(qǐng)都在內(nèi)存池上完成的，就只需要釋放內(nèi)存池，如下：
復(fù)制代碼 代碼如下:
void hashtable_free（hashtable h）
{
if（h != NULL）
pool_free（h->p）；
}
七，釋放單個(gè)hash接點(diǎn)
代碼如下：
復(fù)制代碼 代碼如下:
void hashtable_delete_node（hashtable h, const char *key）
{
if（h == NULL || key == NULL）
return;
hashnode node;
int len = strlen（key）；
if（h == NULL || key == NULL || （node = hashtable_node_get（h, key, len, hashcode（key,len））） == NULL） //沒(méi)有這個(gè)接點(diǎn)
return;
node->key = NULL;
node->val = NULL;
h->count--;
}
這個(gè)就實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的HASHTABLE結(jié)構(gòu)，當(dāng)然后還是有不足的，比如遍歷HASHTABLE，如果用數(shù)組的方式來(lái)遍歷，效率肯定很低，下面討論一種實(shí)現(xiàn)方案，用于遍歷hashtable.
八，hashtable的遍歷討論
直接用數(shù)組，就是hashtable中的struct hashnode_struct數(shù)組是可以遍歷，但如果只包含一個(gè)接點(diǎn)，也要遍歷所有的數(shù)組，如下遍歷：
復(fù)制代碼 代碼如下:
void hashtable_traverse（hashtable h）
{
int i;
hashnode node;
if（h == NULL）
return;
for（i = 0; i < h->prime; i++）
for（node = &h->z[i]; node != NULL; node = node->next）
if（node->key != NULL && node->val != NULL）
XXXXXXXXXXXXXXXXX // 這里是一些操作。
}
這樣效率很低，其實(shí)在接點(diǎn)中包含了next域，可以用這個(gè)來(lái)實(shí)現(xiàn)遍歷。
需要對(duì)前面hashtable數(shù)據(jù)結(jié)構(gòu)做簡(jiǎn)單的改動(dòng)，增加兩個(gè)域：
復(fù)制代碼 代碼如下:
typedef struct hashtable_struct{
pool_t p;
int size;
int count;
struct hashnode_struct *z;
int bucket;
hashnode node;
}*hashtable,_hashtable;
就是增加了bucket和node兩個(gè)域，加這兩個(gè)域的思路是這樣的：
node表示當(dāng)前遍歷的游標(biāo)，在遍歷過(guò)程中，不斷的移動(dòng)這個(gè)接點(diǎn)所指向的接點(diǎn)。
bucket是和node相關(guān)聯(lián)的，用于記錄當(dāng)前的node在哪個(gè)桶上。
首先建立連接，就是將所有的接點(diǎn)都連接起來(lái)，按照慣例，也采用XXX_iter_first函數(shù)，先初始化，如下：
復(fù)制代碼 代碼如下:
int hashtable_iter_first（hashtable h） {
if（h == NULL）
return 0;
h->bucket = -1;
h->node = NULL;
return hashtable_iter_next（h）；
}
hashtable_iter_next用于獲取下一個(gè)接點(diǎn)，如果這時(shí)游標(biāo)已經(jīng)確定，那下一個(gè)接點(diǎn)就會(huì)被很快的被確定，定義如下：
int xhash_iter_next（xht h） {
if（h == NULL） return 0;
while（h->node != NULL） {
h->node = h->node->next; // 移向下一個(gè)接點(diǎn)，如果接點(diǎn)合法，返回成功
if（h->node != NULL && h->node->key != NULL && h->node->val != NULL）
return 1;
}
for（h->bucket++; h->bucket < h->prime; h->bucket++） {
h->node = &h->z[h->bucket];
while（h->node != NULL） {
if（h->node->key != NULL && h->node->val != NULL）
return 1;
h->node = h->node->next;
}
}
h->bucket = -1; // 不存在下一個(gè)接點(diǎn)。
h->node = NULL;
return 0;
}
有了上面兩個(gè)方法之后，遍歷操作如下：
復(fù)制代碼 代碼如下:
hashtable ht
if（hashtable_iter_first（ht）） //取第一個(gè)接點(diǎn)。
do{
// 此時(shí)可以處理ht->node，表示當(dāng)前的接點(diǎn)。
}while（hashtable_iter_next（ht））； //取下一個(gè)接點(diǎn)
這樣處理的話， 是不是高效多了。當(dāng)然在第一遍的時(shí)候，還是需要遍歷整個(gè)數(shù)組和數(shù)組下的桶中接點(diǎn)。不過(guò)這樣操作之后，在刪除一個(gè)結(jié)點(diǎn)的時(shí)候，就需要做一些操作。刪除一個(gè)接點(diǎn)時(shí)，需要考慮當(dāng)前的h->node是不是當(dāng)前被刪除的接點(diǎn)，如果是，就把h->node稱至下一個(gè)接點(diǎn)。就是刪除之后，要作如下處理，假如刪除了。
假如被刪除的接點(diǎn)為node,需要如下處理：
if（h->node == n）
hashtable_iter_next（h）；
將h->node移動(dòng)到下一個(gè)接點(diǎn)。
相關(guān)文章
如何通過(guò)C++在Bing搜索引擎上進(jìn)行命令行搜索
這篇文章主要介紹了通過(guò)C++在Bing搜索引擎上進(jìn)行命令行搜索,在這篇文章中,我們將介紹一個(gè)簡(jiǎn)單的C++程序,允許用戶通過(guò)命令行輸入搜索詞,在Bing搜索引擎上執(zhí)行搜索,并在默認(rèn)瀏覽器中顯示搜索結(jié)果,需要的朋友可以參考下2023-12-12
簡(jiǎn)單舉例說(shuō)明C++中break和continue語(yǔ)句的用法
這篇文章主要介紹了簡(jiǎn)單舉例說(shuō)明C++中break和continue語(yǔ)句的用法,是C++入門學(xué)習(xí)中的基礎(chǔ)只是,需要的朋友可以參考下2015-09-09
這篇文章主要介紹了C++ 中循環(huán)鏈表和約瑟夫環(huán)的相關(guān)資料,需要的朋友可以參考下2017-06-06
編寫(xiě)C++程序使DirectShow進(jìn)行視頻捕捉
這篇文章主要介紹了如何編寫(xiě)C++程序來(lái)使DirectShow進(jìn)行視頻捕捉的方法,DirectShow是微軟公司在ActiveMovie和Video for Windows的基礎(chǔ)上推出的新一代基于COM(Component Object Model)的流媒體處理的開(kāi)發(fā)包,要的朋友可以參考下2016-03-03
C語(yǔ)言詳細(xì)講解循環(huán)語(yǔ)句的妙用
C語(yǔ)言循環(huán)控制語(yǔ)句是一個(gè)基于C語(yǔ)言的編程語(yǔ)句，該語(yǔ)句主要有while循環(huán)語(yǔ)句、do-while循環(huán)語(yǔ)句和for循環(huán)語(yǔ)句來(lái)實(shí)現(xiàn)循環(huán)結(jié)構(gòu)，在循環(huán)過(guò)程中還有關(guān)鍵字break、continue、do、break控制中斷繼續(xù)與結(jié)束等操作2022-04-04
C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換 先進(jìn)先出算法（FIFO）
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換，先進(jìn)先出算法（FIFO），文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要給大家分享了EC++虛函數(shù)注意事項(xiàng)，2022-01-01
這篇文章主要介紹了C++常用語(yǔ)句簡(jiǎn)介，文章將要介紹的常用語(yǔ)句有聲明變量、賦值語(yǔ)句、cin、cout語(yǔ)句、庫(kù)函數(shù)、自定義函數(shù),需要的朋友可以參考一下，希望對(duì)你有所幫助2021-11-11
這篇文章主要介紹了C++Fstream文件流與freopen重定向教程，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02
在C語(yǔ)言中，一個(gè)重要的思想就是分別編譯，即若干個(gè)源程序能夠在不一樣的時(shí)候單獨(dú)進(jìn)行編譯，而后在恰當(dāng)?shù)臅r(shí)候整合到一塊兒?？墒擎溄悠魍ǔＪ桥cC編譯器分離的，鏈接器如何作到把若干個(gè)C源程序合并成一個(gè)總體呢，我們一起來(lái)看看2022-03-03