利用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接点的结构:
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语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
- 在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似key/value的键值对...2020-06-25