利用C语言实现HashTable
利用C语言实现HashTable
发布时间:2016-12-28 来源:查字典编辑
摘要:HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的。一,访问接口创建一个hasht...

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

复制代码 代码如下:

typedef struct hashnode_struct{

struct hashnode_struct *next;

const char *key;

void *val;

}*hashnode,_hashnode;

这个结构还是很容易理解的,除了必须的key-value之外,包含一个用于冲突的链表结构。

hashtable的数据结构:

复制代码 代码如下:

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

代码如下:

复制代码 代码如下:

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的函数。

复制代码 代码如下:

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

{

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函数。

代码如下:

复制代码 代码如下:

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中已经存在,实现很简单,如下:

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接点如下:

复制代码 代码如下:

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中找到指定的接点或者接点链表。如下:

复制代码 代码如下:

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的释放就比较简单了,因为我们所有的内存申请都在内存池上完成的,就只需要释放内存池,如下:

复制代码 代码如下:

void hashtable_free(hashtable h)

{

if(h != NULL)

pool_free(h->p);

}

七,释放单个hash接点

代码如下:

复制代码 代码如下:

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, hashcode(key,len))) == NULL) //没有这个接点

return;

node->key = NULL;

node->val = NULL;

h->count--;

}

这个就实现了一个简单的HASHTABLE结构,当然后还是有不足的,比如遍历HASHTABLE,如果用数组的方式来遍历,效率肯定很低,下面讨论一种实现方案,用于遍历hashtable.

八,hashtable的遍历讨论

直接用数组,就是hashtable中的struct hashnode_struct数组是可以遍历,但如果只包含一个接点,也要遍历所有的数组,如下遍历:

复制代码 代码如下:

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数据结构做简单的改动,增加两个域:

复制代码 代码如下:

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函数,先初始化,如下:

复制代码 代码如下:

int hashtable_iter_first(hashtable h) {

if(h == NULL)

return 0;

h->bucket = -1;

h->node = NULL;

return hashtable_iter_next(h);

}

hashtable_iter_next用于获取下一个接点,如果这时游标已经确定,那下一个接点就会被很快的被确定,定义如下:

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;

}

有了上面两个方法之后,遍历操作如下:

复制代码 代码如下:

hashtable ht

if(hashtable_iter_first(ht)) //取第一个接点。

do{

// 此时可以处理ht->node,表示当前的接点。

}while(hashtable_iter_next(ht)); //取下一个接点

这样处理的话, 是不是高效多了。当然在第一遍的时候,还是需要遍历整个数组和数组下的桶中接点。不过这样操作之后,在删除一个结点的时候,就需要做一些操作。删除一个接点时,需要考虑当前的h->node是不是当前被删除的接点,如果是,就把h->node称至下一个接点。就是删除之后,要作如下处理,假如删除了。

假如被删除的接点为node,需要如下处理:

if(h->node == n)

hashtable_iter_next(h);

将h->node移动到下一个接点。

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新C语言学习
热门C语言学习
编程开发子分类