一个简单的HashMap C语言实现

一个简单的HashMap C语言实现

cheungmine

用C语言实现一个简单实用的hashmap，具有一定的实际意义。尤其我们不想使用STL里面的map<...>类的时候。我实现的这个hashmap，用来做key---value的映射，key必须是有效的字符串，value是调用者分配的任意类型的数据。这个hashmap适合在一些简单的场合下，消耗极少的资源。

首先定义头文件如下：

/*
*hashmap.h
*Generichashmap:key(string)-value(anytype).
*cheungmine
*Sep.22,2007.Allrightsreserved.
*/
#ifndefHASHMAP_H_INCLUDED
#defineHASHMAP_H_INCLUDED

#include"unistd.h"

/*Youshouldalwaysuse1024*/
#defineHASHMAP_SIZE1024

/*Opaquestructpointerto_hash_map_t*/
typedefstruct_hash_map_t*hash_map;

typedefvoid(*pfcb_hmap_value_free)(void*value);

/*Anexampleoffreevaluefunctionimplementedbycaller:
voidmy_hmap_free_value(void*pv)
{
free(pv);
}
*/


/*Createbeforeuse.eg:
*hash_maphm;
*hmap_create(&hm,HASHMAP_SIZE);
*assert(hm);//outofmemoryifhm==NULL
*void*mydata=malloc(n);
*hmap_insert(hm,"shanghai",-1,mydata);
...
*hmap_destroy(hm,my_hmap_free_value);
*/
externvoid
hmap_create(hash_map*hmap,intsize);

/*Destroyafteruse*/
externvoid
hmap_destroy(hash_maphmap,pfcb_hmap_value_free);

/*Insertakey-valueintohashmap.valueisapointertocallee-allocatedmemory*/
externvoid
hmap_insert(hash_maphmap,constchar*key,intkey_len/*-1forstrlentobecalled*/,void*value);

/*Searchahashmapforvalueofgivenkeystring*/
externvoid*
hmap_search(hash_maphmap,constchar*key);


#endif/*HASHMAP_H_INCLUDED*/

实现文件如下：

/*
*hashmap.c
*Generichashmapimplementation.
*amapforpairofkey-value.keymustbeanull-endstring,valueisanytypeofdata.
*cheungmine
*Sep.22,2007.Allrightsreserved.
*/

#include"hashmap.h"
#include"list.h"

typedefstruct_hash_map_t
{
size_tsize;
listnode_t**key;
listnode_t**value;
}hash_map_t;

/*Hashastring,returnahashkey*/
staticulonghash_string(constchar*s,intlen)
{
ulongh=0;
inti=0;
assert(s);
if(len<0)
len=(s?(int)strlen(s):0);
while(i++<len){h=17*h+*s++;}
returnh;
}

staticvoid_free_map_key(listnode_t*node)
{
listnode_t*old;
while(node)
{
old=node;
node=node->next;

free(old->data);
free(old);
}
}

staticvoid_free_map_value(listnode_t*node,pfcb_hmap_value_freepfunc)
{
listnode_t*old;
while(node)
{
old=node;
node=node->next;

if(pfunc)
(*pfunc)(old->data);
free(old);
}
}

/*=============================================================================
PublicFunctions
=============================================================================*/
/*Createbeforeuse*/
void
hmap_create(hash_map*hmap,intsize)
{
(*hmap)=(hash_map_t*)malloc(sizeof(hash_map_t));
(*hmap)->size=size;
(*hmap)->key=(listnode_t**)calloc(size,sizeof(listnode_t*));
(*hmap)->value=(listnode_t**)calloc(size,sizeof(listnode_t*));
}

/*Destroyafteruse*/
externvoid
hmap_destroy(hash_maphmap,pfcb_hmap_value_freepfunc)
{
size_ti;
for(i=0;i<hmap->size;i++){
_free_map_key(hmap->key[i]);
_free_map_value(hmap->value[i],pfunc);
}

free(hmap->key);
free(hmap->value);
free(hmap);
}


/*Insertakey-valueintohashmap.valueisapointertocallee-allocatedmemory*/
void
hmap_insert(hash_maphmap,constchar*key,intkey_len,void*value)
{
listnode_t*node_key,*node_val;
ulongh;
char*s;
assert(key);

if(key_len<0)key_len=(int)strlen(key);
s=(char*)malloc(key_len+1);
assert(s);

#pragmawarning(push)/*C4996*/
#pragmawarning(disable:4996)
strncpy(s,key,key_len);
#pragmawarning(pop)/*C4996*/
s[key_len]=0;

node_key=list_node_create((void*)s);
node_val=list_node_create(value);
assert(node_key&&node_val);

h=hash_string(s,key_len)%hmap->size;

node_key->next=hmap->key[h];
hmap->key[h]=node_key;

node_val->next=hmap->value[h];
hmap->value[h]=node_val;
}

/*Searchahashmapforvalueofgivenkeystring*/
void*
hmap_search(hash_maphmap,constchar*key)
{
ulongh=hash_string(key,-1)%hmap->size;
listnode_t*pk=hmap->key[h];
listnode_t*pv=hmap->value[h];

while(pk)
{
if(strcmp(key,pk->str)==0)
returnpv->data;
pk=pk->next;
pv=pv->next;
}

returnNULL;
}

好了，其中用到的其他文件（unistd.h，list.h，list.c）看我下一篇文章！

C语言实现一个简单的单向链表list