HashMap哈希表练习

一、练习要求

使用顺序表和单链表通过C语言实现一个HashMap的数据结构，实现以下功能：

1、PHashMap createHashMap(int size);

2、int putValue(PHashMap map, int key, EleType value);

3、EleType getValue(PHashMap map, int key);

4、printHashMap(PHashMap map);

5、int destroyHashMap(PHashMap map);

6、int hashCode(PHashMap map, int key);

二、关键结构体的定义

hash.h

typedef struct{int id;//学号char name[20];//姓名float score;//分数
}Stu, *PStu;typedef struct n{Stu stu;struct n *next;
}Node, *PNode;typedef struct{PNode* pTable;//指针数组int tableSize;//顺序表的大小int len;//元素数量
}HashMap, *PHashMap;PHashMap createHashMap(int tableSize);
int putValue(PHashMap map, int id, Stu stu);
int hashCode(int id, int tableSize);//计算hashcode
void printHashMap(PHashMap map);
void getValue(PHashMap map,int id);
void destroyHashMap(PHashMap map);

三、函数的实现

hash.c

#include "hash.h"PHashMap createHashMap(int tableSize){PHashMap map=(PHashMap)malloc(sizeof(HashMap));map->len=0;map->tableSize=tableSize;//PNode *p=(PNode*)malloc(sizeof(PNode)*tableSize);map->pTable=p;//清空新分配的数组空间for(int i=0;i<tableSize;i++){*(p+i)=NULL;}printf("HashMap创建成功\n");return map;
}int putValue(PHashMap map, int id, Stu stu){int index = hashCode(id, map->tableSize);//单链表头插法map->pTable[index];//PNode p=(PNode)malloc(sizeof(Node));memcpy(&p->stu, &stu, sizeof(stu));p->next=map->pTable[index];map->pTable[index]=p;map->len++;printf("[%d]数据存储成功,hashcode=[%d]\n", p->stu.id, index);return 1;
}int hashCode(int id, int tableSize){return id%tableSize;
}void printHashMap(PHashMap map){PNode *table=map->pTable;for(int i=0;i<map->tableSize;i++){printf("第[%d]行：\n", i);if(table[i] == NULL){printf("\tNULL:\n");continue;}//遍历单链表PNode p=table[i];while(p){printf("\tid=[%d],name=[%s],score=[%.1f]\n",p->stu.id, p->stu.name, p->stu.score);p=p->next;}}
}void getValue(PHashMap map, int id){int hashcode = hashCode(id, map->tableSize);	PNode p = map->pTable[hashcode];while(p){if(p->stu.id == id){printf("SUCCESS:找到了元素:id=[%d],name=[%s],score=[%.1f]\n",p->stu.id,p->stu.name,p->stu.score);return;}p=p->next;}printf("ERROR:没有找到id为[%d]的元素\n", id);
}void destroyHashMap(PHashMap map){//先销毁链表for(int i=0;i<map->tableSize;i++){PNode p = map->pTable[i];while(p){PNode temp=p;p=p->next;free(temp);}}//再销毁顺序表free(map);printf("销毁成功！\n");}

四、测试代码

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "hash.h"int main(int argc, const char *argv[])
{Stu a[]={{1,"aaa",1.1},{2,"bbb",2.2},{3,"ccc",3.3},{4,"ddd",4.4},{5,"eee",5.5},{6,"fff",6.6},{7,"ggg",7.7},{8,"hhh",8.8},{9,"iii",9.9},{10,"jjj",10.1}};int len=sizeof(a)/sizeof(Stu);//tableSize故意设置小一点，让hashcode碰撞printf(">>创建HashMap:\n");PHashMap map = createHashMap(5);//通过put往map里面存值printf(">>putValue:\n");for(int i=0;i<len;i++){putValue(map, a[i].id, a[i]);}//打印printf(">>打印HashMap:\n");printHashMap(map);//执行查找操作printf("\n>>执行查找id为8的元素\n");getValue(map, 8);printf("\n>>执行查找id为100的元素\n");getValue(map, 100);//销毁hashMapprintf("\n>>执行HashMap销毁\n");destroyHashMap(map);return 0;
}

五、运行结果

>>创建HashMap:
HashMap创建成功
>>putValue:
[1]数据存储成功,hashcode=[1]
[2]数据存储成功,hashcode=[2]
[3]数据存储成功,hashcode=[3]
[4]数据存储成功,hashcode=[4]
[5]数据存储成功,hashcode=[0]
[6]数据存储成功,hashcode=[1]
[7]数据存储成功,hashcode=[2]
[8]数据存储成功,hashcode=[3]
[9]数据存储成功,hashcode=[4]
[10]数据存储成功,hashcode=[0]
>>打印HashMap:
第[0]行：id=[10],name=[jjj],score=[10.1]id=[5],name=[eee],score=[5.5]
第[1]行：id=[6],name=[fff],score=[6.6]id=[1],name=[aaa],score=[1.1]
第[2]行：id=[7],name=[ggg],score=[7.7]id=[2],name=[bbb],score=[2.2]
第[3]行：id=[8],name=[hhh],score=[8.8]id=[3],name=[ccc],score=[3.3]
第[4]行：id=[9],name=[iii],score=[9.9]id=[4],name=[ddd],score=[4.4]>>执行查找id为8的元素
SUCCESS:找到了元素:id=[8],name=[hhh],score=[8.8]>>执行查找id为100的元素
ERROR:没有找到id为[100]的元素>>执行HashMap销毁
销毁成功！

六、需要继续研究的问题

1、hashcode的算法有哪些， 如果key是字符串如何预算，对比java里的hashcode的实现。

2、hashcode在代码中，对应的指针数组的下标，实际的应用中也是如此吗，我怎么记得java语言中的hashcode得到的是一个很长的字符串；

3、解决hashcode碰撞的常用方法有哪些，代码中运用到的是链表的方法；

4、当数据量不断地提升，hashmap本身怎么做动态的扩展；

5、在某些高级应用中，如果能预知或者通过统计知道某些key的查询率特别高，在发生hashcode碰撞的时候，如何把这些元素节点放在离根节点更近的地方，这样也可以提升查询效率。

也欢迎感兴趣的朋友一起讨论呀。