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接点的结构：

[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)
 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)
 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)
 return;
 hashnode node;
 int len = strlen(key);
 if(h == NULL || key == NULL || (node = hashtable_node_get(h, key, len

补充：软件开发 , C语言 ,