C语言的HashTable简单达成
发布时间:2021-12-14 21:23:10 所属栏目:PHP教程 来源:互联网
导读:HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的。 一,访问接口 创建一个hashtable. hashtable hashtable_new(int size) // size表示包含的接点个数。 存入key-value至hashtable中。 void 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语言内存池使用模型" http://www.linuxidc.com/Linux/2012-09/71368.htm 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<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函数。 代码如下: 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; } (编辑:云计算网_泰州站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |