映射函数可选择的比较多，其实完全可以定义自己的映射函数，但是有时候为了降低冲突的概率设置了一些比较好的映射函数，比如求和取余，或者乘以一定的系数再求和取余等。
本文采用平方探测法解决了冲突问题，具体的实现如下所示：
1、结构体定义
#ifndef__HASHMAP_H_H_
#define__HASHMAP_H_H_
#includelist.h
#defineTABSIZE101
/*状态变量*/
typedefenumSTATE{EMPTY=0,ACTIVE=1,DELETED=2}State;
/*键值结构体*/
typedefstruct_pair
{
char*key;
char*value;
}Pair_t,*Pair_handle_t;
/*每一个实际的存储对象*/
typedefstruct_hashEntry
{
Pair_handle_tpair;
Statestate;
}HashEntry_t,*HashEntry_handle_t;
/*哈希表结构体，便于创建*/
typedefstruct_hashmap
{
HashEntry_t*map;
/*存储实际的存储量*/
intsize;
/*容量*/
intcapacity;
}Hashmap_t,*Hashmap_handle_t;
/*隐射函数类型定义*/
typedefint(*hashfunc)(constchar*,int);
#ifdef__cplusplus
externC
{
#endif
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity);
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity);
boolinsert_hashnode(Hashmap_handle_thashmap,constchar*key,constchar*value);
Pair_handle_tsearch_hashnode(Hashmap_handle_thashmap,constchar*key);
char*GetValue(Hashmap_handle_thashmap,constchar*key);
booldelete_hashnode(Hashmap_handle_thashmap,constchar*key);
intLength(Hashmap_handle_thashmap);
intCapacity(Hashmap_handle_thashmap);
voiddelete_hashmap(Hashmap_handle_thashmap);
voidfree_hashmap(Hashmap_handle_t*hashmap);
char*key_pair(Pair_handle_tpair);
char*value_pair(Pair_handle_tpair);
Hashmap_handle_tcopy_hashmap(Hashmap_handle_thashmap);
boolresize(Hashmap_handle_thashmap);
#ifdef__cplusplus
}
#endif
#endif
实现表的分配和创建，采用了动态分配的方式实现，这样可能在性能上比不上静态数据，但是为了实现数组大小的调整，我选择了动态分配的实现方式。
/*分配一个新的对象，可以实现自动分配*/
boolalloc_hashmap(Hashmap_handle_t*hashmap,intcapacity)
{
HashEntry_handle_ttemp=NULL;
Hashmap_t*map=NULL;
if(*hashmap==NULL)
{
/*分配一个散列对象*/
map=(Hashmap_handle_t)malloc(sizeof(Hashmap_t));
if(map==NULL)
returnfalse;
/*指针指向当前对象*/
*hashmap=map;
map=NULL;
/*分配一个数组空间，大小可以控制*/
temp=(HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp!=NULL)
{
/*散列对象的指针指向数组*/
(*hashmap)->map=temp;
temp=NULL;
/*设置参数*/
(*hashmap)->capacity=capacity;
(*hashmap)->size=0;
/*初始化分配的数组空间*/
Tabinital((*hashmap)->map,capacity);
returntrue;
}
}
returnfalse;
}
/*初始化一个新的对象，这个对象已经创建，只是没有初始化而已*/
boolinit_hashmap(Hashmap_handle_thashmap,intcapacity)
{
HashEntry_handle_ttemp=NULL;
if(hashmap!=NULL)
{
/*分配数组空间*/
temp=(HashEntry_handle_t)malloc(
sizeof(HashEntry_t)*capacity);
if(temp!=NULL)
{
/*完成对象的填充操作*/
hashmap->map=temp;
temp=NULL;
hashmap->capacity=capacity;
hashmap->size=0;
/*初始化数组对象*/
Tabinital(hashmap->map,capacity);
returntrue;
}
}
returnfalse;
}
关于数组中对象的创建，和释放操作，如下所示：
/*分配一个pair对象*/
staticboolmake_pair(Pair_handle_t*pair,constchar*key,constchar*value)
{
Pair_handle_tnewpair=(Pair_handle_t)malloc(sizeof(Pair_t));
char*newstr=NULL;
if(newpair==NULL)
returnfalse;
newstr=(char*)malloc(strlen(key)+1);
if(newstr==NULL)
returnfalse;
strcpy(newstr,key);
newstr[strlen(key)]='\0';
newpair->key=newstr;
newstr=NULL;
newstr=(char*)malloc(strlen(value)+1);
if(newstr==NULL)
returnfalse;
strcpy(newstr,value);
newstr[strlen(value)]='\0';
newpair->value=newstr;
newstr=NULL;
(*pair)=newpair;
returntrue;
}
/*释放一个对象pair*/
staticvoiddelete_pair(Pair_handle_t*pair)
{
Pair_handle_ttemp=NULL;
if(*pair==NULL)
return;
temp=*pair;
free(temp->key);
temp->key=NULL;
free(temp->value);
temp->value=NULL;
free(temp);
temp=NULL;
*pair=NULL;
}
数组元素的基本操作：
/*完成数组对象的初始化操作*/
staticvoidTabinital(HashEntry_t*tab,intsize)
{
inti=0;
for(;i
{
tab[i].pair=NULL;
tab[i].state=EMPTY;
}
}
staticvoiddelete_array(HashEntry_handle_t*array,intsize)
{
inti=0;
if(*array!=NULL)
{
for(i=0;i
{
if((*array)[i].state==ACTIVE)
{
delete_pair(&((*array)[i].pair));
(*array)[i].state=DELETED;
}
}
free(*array);
*array=NULL;
}
}
插入元素的操作、有两个函数的创建，其中一个为了便于后期大小的调整操作。
/*插入数据到散列中，采用了二次探测的实现方式，并设置了退出条件*/
staticboolinsert_data(Hashmap_handle_thashmap,
constchar*key,constchar*value,hashfuncfunc)
{
inthashval=func(key,hashmap->capacity);
intindex=0;
char*newstr=NULL;
Pair_handle_tnewpair=NULL;
while(hashmap->map[hashval].state!=EMPTY)
{
if((hashmap->map[hashval].state==ACTIVE)
&&(strcmp(hashmap->map[hashval].pair->key,key)==0))
break;
index++;
hashval+=index*index;
hashval%=hashmap->capacity;
if(index==200)
break;
}
if(hashmap->map[hashval].state==EMPTY)
{
if(make_pair(&newpair,key,value))
{
hashmap->map[hashval].state=ACTIVE;
hashmap->map[hashval].pair=newpair;
newpair=NULL;
hashmap->size++;
returntrue;
}
数据在计算机中存储的物理结构有四种：顺序、链表、散列与索引。散列是由单词Hash翻译过来的，有时也直接音译为“哈希”，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
