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)  
<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移动到下一个接点。