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

二，數據結構

hash接點的結構：

1. typedef struct hashnode_struct{  
2.       struct hashnode_struct *next;  
3.       const char *key;  
4.       void *val;  
5. }*hashnode,_hashnode;  

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

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

hashtable的數據結構：

1. typedef struct hashtable_struct{  
2.      pool_t p;  
3.      int size;  
4.      int count;  
5.      struct hashnode_struct *z;  
6. }*hashtable,_hashtable;  

對這個結構說明如下：

pool_t：內存池結構管理hashtable使用的內存。結構參考"C語言內存池使用模型" http://www.linuxidc.com/Linux/2012-09/71368.htm

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

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

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

三，創建hashtable

代碼如下：

1. hashtable hashtable_new(int size)  
2. {  
3.     hashtable ht;  
4.     pool_t p;  
5.   
6.     p = _pool_new_heap(sizeof(_hashnode)*size + sizeof(_hashtable));  
7.     ht= pool_malloc(p, sizeof(_hashtable));  
8.     ht->size = size;  
9.     ht->p = p;  
10.     ht->z = pool_malloc(p, sizeof(_hashnode)*prime);  
11.     return ht;  
12. }  

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

四，存入key-value值

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

1. static int hashcode(const char *s, int len)  
2. {  
3.     const unsigned char *name = (const unsigned char *)s;  
4.     unsigned long h = 0, g;  
5.     int i;  
6.   
7.     for(i=0;i<len;i++)  
8.     {  
9.         h = (h << 4) + (unsigned long)(name[i]); //hash左移4位，當前字符ASCII存入hash     
10.         if ((g = (h & 0xF0000000UL))!=0)       
11.             h ^= (g >> 24);  
12.         h &= ~g;  //清空28-31位。    
13.     }  
14.   
15.     return (int)h;  
16. }  

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

代碼如下：

1. void hashtable_put(hashtable h, const char *key, void *val)  
2. {  
3.     if(h == NULL || key == NULL)   
4.   return;  
5.   
6.     int len = strlen(key);  
7.     int index = hashcode(key,len);  
8.     hashtable node;  
9.     h->dirty++;  
10.   
11.     if((node = hashtable_node_get(h, key,len, index)) != NULL)  //如果已經存在，就替換成現在的值，因為現在的比較新。   
12.     {  
13.         n->key = key;  
14.         n->val = val;  
15.         return;  
16.     }  
17.   
18.     node = hashnode_node_new(h, index);  // 新建一個HASH NODE接點。   
19.     node->key = key;  
20.     node->val = val;  
21. }  

hashtable_node_get用於查找該KEY是否在HASH中已經存在，實現很簡單，如下：

1. static hashnode hashtable_node_get(hashtable h, const char *key, int len, int index)  
2. {  
3.     hashnode node;  
4.     int i = index % h->size;  
5.     for(node = &h->z[i]; node != NULL; node = node->next) // 在index值 [HASH值] 所對應的HASH桶上遍歷尋找   
6.         if(node->key != NULL && (strlen(node->key)==len) && (strncmp(key, node->key, len) == 0))  
7.             return node;  
8.     return NULL;  
9. }