C语言实现HashMap
C语言实现HashMap在做算法题时,需要使用到HashMap提高效率，虽然高级语言中大豆实现了这种数据结构，但是高级语言的效率低，于是打算自己实现HashMap，加深理解，使用C语言实现了HashMap的创建（CreateHashMap）、取<k,v>对（Get）、插入<k,v>对（Put）输出（PrintHashMap）以及销毁（DestoryHashMap）,具体程序如下：
1.类型定义如下：
typedef struct{
int key;
int val;
}DataType;
typedef struct{
DataType data;
struct HashNode *next;
}HashNode;
typedef struct{
int size;
HashNode *table;
}HashMap,*hashmap;
2.CreateHashMap
//f1_createHashMap
HashMap *CreateHashMap(int *nums,int size){
HashMap *hashmap=(HashMap*)malloc(sizeof(HashMap));
hashmap->size=2*size;
hashmap->table=(HashNode *)malloc(sizeof(HashNode)*hashmap->size);
int j=0;
for(j=0;j<hashmap->size;j++){
hashmap->table[j].data.val=INT_MIN;
hashmap->table[j].next=NULL;
}
int i=0;
while(i<size){
int pos=abs(nums[i])%hashmap->size;
if(hashmap->table[pos].data.val==INT_MIN){
hashmap->table[pos].data.key=i;
hashmap->table[pos].data.val=nums[i];
}
else{
HashNode *lnode=(HashNode*)malloc(sizeof(HashNode)),*hashnode;
lnode->data.key=i;
lnode->data.val=nums[i];
lnode->next=NULL;
hashnode=&(hashmap->table[pos]);
while(hashnode->next!=NULL){
hashnode=hashnode->next;
}
hashnode->next=lnode;
}
i++;
}
return hashmap;
}
对于hashmap->size=2*size; hashmap中table的长度为什么是给定数组长度的2倍？这涉及到hash表的冲突因子，也可以选取别的数值；详细可以参考严蔚敏《数据结构》中的相关章节；
3.GetKeyValue
//f3_GetHashNode
int Get(int value,HashMap hashmap){
int pos=abs(value)%hashmap.size;
HashNode *pointer=&(hashmap.table[pos]);
while(pointer!=NULL){
if(pointer->data.val==value)
return pointer->data.key;
else
pointer=pointer->next;
}
return -1;
}
4.PutKeyValue
//f4_Put
int Put(int key,int value,HashMap hashmap){
int pos=abs(value)%hashmap.size;
HashNode *pointer=&(hashmap.table[pos]);
if(pointer->data.val==INT_MIN)
{
pointer->data.val=value;
pointer->data.key=key;
}
else{
while(pointer->next!=NULL)
pointer=pointer->next;
HashNode *hnode=(HashNode *)malloc(sizeof(HashNode));
hnode->data.key=key;
hnode->data.val=value;
hnode->next=NULL;
pointer->next=hnode;
}
return 1;
}
5.PrintHashMap
//f2_PrintHashMap
void PrintHashMap(HashMap* hashmap){
printf("%===========PrintHashMap==========\n");
int i=0;
HashNode *pointer;
while(i<hashmap->size){
pointer=&(hashmap->table[i]);
while(pointer!=NULL){
if(pointer->data.val!=INT_MIN)
printf("%10d",pointer->data.val);
else
printf(" [ ]");
pointer=pointer->next;
}
printf("\n---------------------------------");
i++;
printf("\n");
}
printf("===============End===============\n");
}
6.DestoryHashMap
//f5_DestoryHashMap
void DestoryHashMap(HashMap *hashmap){
int i=0;
HashNode *hpointer;
while(i<hashmap->size){
hpointer=hashmap->table[i].next;
while(hpointer!=NULL){
hashmap->table[i].next=hpointer->next;
free(hpointer);
hpointer=hashmap->table[i].next;
}
i++;
}
free(hashmap->table);
free(hashmap);
printf("Destory hashmap Success!");
}
