程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言的HashTable簡單實現

C語言的HashTable簡單實現

編輯:關於C語言

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_delete_node(hashtable h, const char *key);

二,數據結構

hash接點的結構:

[cpp]
typedef struct hashnode_struct{ 
      struct hashnode_struct *next; 
      const char *key; 
      void *val; 
}*hashnode,_hashnode; 
 這個結構還是很容易理解的,除了必須的key-value之外,包含一個用於沖突的鏈表結構。

hashtable的數據結構:

[cpp] 
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

代碼如下:

[cpp] 
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的函數。

[cpp] 
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<len;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函數。
代碼如下:

[cpp] 
void hashtable_put(hashtable h, const char *key, void *val) 

    if(h == NULL || key == NULL)  
<span>  </span>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中已經存在,實現很簡單,如下:
[cpp] 
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接點如下:
[cpp]
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中找到指定的接點或者接點鏈表。如下:

[cpp] 
void *hashtable_get(hashtable h, const char *key) 

    if(h == NULL || key == NULL)  
<span>  </span>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的釋放就比較簡單了,因為我們所有的內存申請都在內存池上完成的,就只需要釋放內存池,如下:
 view plaincopy
void hashtable_free(hashtable h) 

    if(h != NULL) 
        pool_free(h->p); 

七,釋放單個hash接點
代碼如下:

[cpp] 
void hashtable_delete_node(hashtable h, const char *key) 

    if(h == NULL || key == NULL)  
<span>  </span>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數組是可以遍歷,但如果只包含一個接點,也要遍歷所有的數組,如下遍歷:

[cpp] 
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數據結構做簡單的改動,增加兩個域:

[cpp]
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函數,先初始化,如下:

[cpp]
int hashtable_iter_first(hashtable h) { 
    if(h == NULL)  
<span>  </span>return 0; 
    h->bucket = -1; 
    h->node = NULL; 
    return hashtable_iter_next(h); 

hashtable_iter_next用於獲取下一個接點,如果這時游標已經確定,那下一個接點就會被很快的被確定,定義如下:
[cpp]
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; 

有了上面兩個方法之後,遍歷操作如下:
[cpp] 
hashtable ht 
if(hashtable_iter_first(ht))   //取第一個接點。  
do{ 
    // 此時可以處理ht->node,表示當前的接點。 
}while(hashtable_iter_next(ht));  //取下一個接點 
這樣處理的話, 是不是高效多了。當然在第一遍的時候,還是需要遍歷整個數組和數組下的桶中接點。不過這樣操作之後,在刪除一個結點的時候,就需要做一些操作。刪除一個接點時,需要考慮當前的h->node是不是當前被刪除的接點,如果是,就把h->node稱至下一個接點。就是刪除之後,要作如下處理,假如刪除了。
假如被刪除的接點為node,需要如下處理:

[cpp]
if(h->node == n) 
    hashtable_iter_next(h); 
將h->node移動到下一個接點。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved