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;  
这个结构还是很容易理解的，除了必须的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语言内存池使用模型"

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. }  
  • 1
  • 2
  • 下一页

相关内容