C語言的HashTable簡單實現

相關推薦

C語言的HashTable簡單實現

　　HashTable是在實際應用中很重要的一個結構，下面討論一個簡單的實現，雖然簡單，但是該有的部分都還是有的。

　　一，訪問接口

　　創建一個hashtable.

　　hashtable hashtable_new（int size） /其中size表示包含的接點個數。

　　存入key-value至hashtable中。

　　void hashtable_put（hashtable h,const char* key,void *val）；

　　根據key從hashtable中取出value值。

　　void * hashtable_get（hashtable h,const char *key）；

　　釋放hashtable。

　　void hashtable_free（hashtable h）；

　　釋放單個hash 接點

　　void hashtable__node（hashtable h, const char *key）；

　　二，數據結構

　　hash接點的結構：

　　復制代碼代碼如下:

　　typedef struct hashnode_struct{

　　struct hashnode_struct *next;

　　const char *key;

　　void *val;

　　}*hashnode,_hashnode;

　　這個結構還是很容易理解的，除了必須的key-value之外，包含一個用于沖突的鏈表結構。

　　hashtable的數據結構：

　　復制代碼代碼如下:

　　typedef struct hashtable_struct{

　　pool_t p;

　　int size;

　　int count;

　　struct hashnode_struct *z;

　　}*hashtable,_hashtable;

　　對這個結構說明如下：

　　pool_t：內存池結構管理hashtable使用的內存。結構參考"C語言內存池使用模型"

　　size：當前hash的接點空間大小。

　　count：用于表示當前接點空間中可用的hash接點個數

　　z：用于在接點空間中存儲接點。

　　三，創建hashtable

　　代碼如下：

　　復制代碼代碼如下:

　　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;

　　}

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

　　四，存入key-value值

　　在這個操作之前，先要定義一個根據KEY值計算hashcode的函數。

　　復制代碼代碼如下:

　　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位，當前字符ASCII存入hash

　　if （（g = （h & 0xF0000000UL））！=0）

　　h ^= （g 》 24）；

　　h &= ~g; //清空28-31位。

　　}

　　return （int）h;

　　}

　　這個函數采用精典的ELF hash函數。

　　代碼如下：

　　復制代碼代碼如下:

　　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） //如果已經存在，就替換成現在的值，因為現在的比較新。

　　{

　　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中已經存在，實現很簡單，如下：

　　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值] 所對應的HASH桶上遍歷尋找

　　if（node->key != NULL && （strlen（node->key）==len） && （strncmp（key, node->key, len） == 0））

　　return node;

　　return NULL;

　　}

　　新建一個HASH NODE接點如下：

　　復制代碼代碼如下:

　　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是空的，表明這個值已經沒有用了，就用它來替換為現在準備寫入的新接點。

　　return node;

　　node = pool_malloc（h->p, sizeof（_hashnode））； // 新建一個接點

　　node->next = h->z[i].next; // 加入到桶中，就是加到鏈表的第一個接點。

　　h->z[i].next = node;

　　return node;

　　}

　　五，從HASHTABLE中獲取接點

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

　　復制代碼代碼如下:

　　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;

　　}

　　這個函數就很容易理解了。

　　六，釋放HASHTABLE

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

　　復制代碼代碼如下:

　　void hashtable_free（hashtable h）

　　{

　　if（h != NULL）

　　pool_free（h->p）；

　　}

　　七，釋放單個hash接點

　　代碼如下：

　　復制代碼代碼如下:

　　void hashtable__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--;

　　}

　　這個就實現了一個簡單的HASHTABLE結構，當然后還是有不足的，比如遍歷HASHTABLE，如果用數組的方式來遍歷，效率肯定很低，下面討論一種實現方案，用于遍歷hashtable.

　　八，hashtable的遍歷討論

　　直接用數組，就是hashtable中的struct hashnode_struct數組是可以遍歷，但如果只包含一個接點，也要遍歷所有的數組，如下遍歷：

　　復制代碼代碼如下:

　　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域，可以用這個來實現遍歷。

　　需要對前面hashtable數據結構做簡單的改動，增加兩個域：

　　復制代碼代碼如下:

　　typedef struct hashtable_struct{

　　pool_t p;

　　int size;

　　int count;

　　struct hashnode_struct *z;

　　int bucket;

　　hashnode node;

　　}*hashtable,_hashtable;

　　就是增加了bucket和node兩個域，加這兩個域的思路是這樣的：

　　node表示當前遍歷的游標，在遍歷過程中，不斷的移動這個接點所指向的接點。

　　bucket是和node相關聯的，用于記錄當前的node在哪個桶上。

　　首先建立連接，就是將所有的接點都連接起來，按照慣例，也采用XXX_iter_first函數，先初始化，如下：

　　復制代碼代碼如下:

　　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用于獲取下一個接點，如果這時游標已經確定，那下一個接點就會被很快的被確定，定義如下：

　　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;

　　}

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

　　復制代碼代碼如下:

　　hashtable ht

　　if（hashtable_iter_first（ht）） //取第一個接點。

　　do{

　　// 此時可以處理ht->node，表示當前的接點。

　　}while（hashtable_iter_next（ht））； //取下一個接點

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

　　假如被刪除的接點為node,需要如下處理：

　　if（h->node == n）

　　hashtable_iter_next（h）；

　　將h->node移動到下一個接點。

【C語言的HashTable簡單實現】相關文章：

C語言程序的實現09-27

c語言入門：用qt實現簡單IDE09-26

簡單選擇排序（C語言實現）08-09

關于php中hashtable實現示例08-02