利用C語言實現(xiàn)HashTable

更新時間：2013年09月14日 09:09:39 作者：

根據(jù)KEY從hashtable中獲取接點，步驟是先根據(jù)KEY計算hash值，然后從hashtable中找到指定的接點或者接點鏈表

HashTable是在實際應(yīng)用中很重要的一個結(jié)構(gòu)，下面討論一個簡單的實現(xiàn)，雖然簡單，但是該有的部分都還是有的。

一，訪問接口
創(chuàng)建一個hashtable.
hashtable hashtable_new（int size） /其中size表示包含的接點個數(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）；

釋放單個hash 接點
void hashtable_delete_node（hashtable h, const char *key）；

二，數(shù)據(jù)結(jié)構(gòu)
hash接點的結(jié)構(gòu)：

復(fù)制代碼代碼如下:

typedef struct hashnode_struct{ 
struct hashnode_struct *next; 
const char *key; 
void *val; 
}*hashnode,_hashnode; 

這個結(jié)構(gòu)還是很容易理解的，除了必須的key-value之外，包含一個用于沖突的鏈表結(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; 

對這個結(jié)構(gòu)說明如下：
pool_t：內(nèi)存池結(jié)構(gòu)管理hashtable使用的內(nèi)存。結(jié)構(gòu)參考"C語言內(nèi)存池使用模型"
size：當(dāng)前hash的接點空間大小。
count：用于表示當(dāng)前接點空間中可用的hash接點個數(shù)
z：用于在接點空間中存儲接點。

三，創(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; 
} 

這個函數(shù)比較簡單，先定義并初始化一個內(nèi)存池，大小根據(jù)size而定，所以在實際使用時，我們的size應(yīng)該要分配的相對大點，比較好。

四，存入key-value值
在這個操作之前，先要定義一個根據(jù)KEY值計算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; 
} 

這個函數(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)在的值，因為現(xiàn)在的比較新。 
{ 
n->key = key; 
n->val = val; 
return; 
} 
node = hashnode_node_new（h, index）； // 新建一個HASH NODE接點。 
node->key = key; 
node->val = val; 
} 
hashtable_node_get用于查找該KEY是否在HASH中已經(jīng)存在，實現(xià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值] 所對應(yīng)的HASH桶上遍歷尋找 
if（node->key != NULL && （strlen（node->key）==len） && （strncmp（key, node->key, len） == 0）） 
return node; 
return NULL; 
} 

新建一個HASH NODE接點如下：

復(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桶中存在某個值，KEY是空的，表明這個值已經(jīng)沒有用了，就用它來替換為現(xiàn)在準(zhǔn)備寫入的新接點。 
return node; 
node = pool_malloc（h->p, sizeof（_hashnode））； // 新建一個接點 
node->next = h->z[i].next; // 加入到桶中，就是加到鏈表的第一個接點。 
h->z[i].next = node; 
return node; 
} 

五，從HASHTABLE中獲取接點
根據(jù)KEY從hashtable中獲取接點，步驟是先根據(jù)KEY計算hash值，然后從hashtable中找到指定的接點或者接點鏈表。如下：

復(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; 
} 

這個函數(shù)就很容易理解了。

六，釋放HASHTABLE
hashtable的釋放就比較簡單了，因為我們所有的內(nèi)存申請都在內(nèi)存池上完成的，就只需要釋放內(nèi)存池，如下：

復(fù)制代碼代碼如下:

void hashtable_free（hashtable h） 
{ 
if（h != NULL） 
pool_free（h->p）； 
} 

七，釋放單個hash接點
代碼如下：

復(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） //沒有這個接點 
return; 
node->key = NULL; 
node->val = NULL; 
h->count--; 
} 

這個就實現(xiàn)了一個簡單的HASHTABLE結(jié)構(gòu)，當(dāng)然后還是有不足的，比如遍歷HASHTABLE，如果用數(shù)組的方式來遍歷，效率肯定很低，下面討論一種實現(xiàn)方案，用于遍歷hashtable.

八，hashtable的遍歷討論
直接用數(shù)組，就是hashtable中的struct hashnode_struct數(shù)組是可以遍歷，但如果只包含一個接點，也要遍歷所有的數(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 // 這里是一些操作。 
} 

這樣效率很低，其實在接點中包含了next域，可以用這個來實現(xiàn)遍歷。
需要對前面hashtable數(shù)據(jù)結(jié)構(gòu)做簡單的改動，增加兩個域：

復(fù)制代碼代碼如下:

typedef struct hashtable_struct{ 
pool_t p; 
int size; 
int count; 
struct hashnode_struct *z; 
int bucket; 
hashnode node; 
}*hashtable,_hashtable; 

就是增加了bucket和node兩個域，加這兩個域的思路是這樣的：
node表示當(dāng)前遍歷的游標(biāo)，在遍歷過程中，不斷的移動這個接點所指向的接點。
bucket是和node相關(guān)聯(lián)的，用于記錄當(dāng)前的node在哪個桶上。
首先建立連接，就是將所有的接點都連接起來，按照慣例，也采用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用于獲取下一個接點，如果這時游標(biāo)已經(jīng)確定，那下一個接點就會被很快的被確定，定義如下： 
int xhash_iter_next（xht h） { 
if（h == NULL） return 0; 
while（h->node != NULL） { 
h->node = h->node->next; // 移向下一個接點，如果接點合法，返回成功 
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; // 不存在下一個接點。 
h->node = NULL; 
return 0; 
} 

有了上面兩個方法之后，遍歷操作如下：

復(fù)制代碼代碼如下:

hashtable ht 
if（hashtable_iter_first（ht）） //取第一個接點。 
do{ 
// 此時可以處理ht->node，表示當(dāng)前的接點。 
}while（hashtable_iter_next（ht））； //取下一個接點 

這樣處理的話，是不是高效多了。當(dāng)然在第一遍的時候，還是需要遍歷整個數(shù)組和數(shù)組下的桶中接點。不過這樣操作之后，在刪除一個結(jié)點的時候，就需要做一些操作。刪除一個接點時，需要考慮當(dāng)前的h->node是不是當(dāng)前被刪除的接點，如果是，就把h->node稱至下一個接點。就是刪除之后，要作如下處理，假如刪除了。

假如被刪除的接點為node,需要如下處理：
if（h->node == n）
hashtable_iter_next（h）；
將h->node移動到下一個接點。

您可能感興趣的文章: