一 哈希介绍
1、若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数,按这个思想建立的表为散列表。
2、对不同的关键字可能得到同一散列地址,即k1≠k2,而f(k1)=f(k2),这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数f(k)和处理碰撞的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。
3、若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少碰撞。
二 应用举例
/********************************************************************* * 哈希表算法实现 **********************************************************************/ #include <stdio.h> #include <stdlib.h> /********************************************************************* * 宏定义 **********************************************************************/ /********************************************************************* * 数据类型重定义 **********************************************************************/ #define uint8_t unsigned char #define uint16_t unsigned short #define uint32_t unsigned long /********************************************************************* * 哈希表长度 **********************************************************************/ #define HASH_TABLE_LEN 97 /********************************************************************* * 数据结构 **********************************************************************/ //链表节点 typedef struct _Link_Node { uint16_t id; uint16_t data; struct _Link_Node *next; }Link_Node,*Link_Node_Ptr; //哈希表头 typedef struct _Hash_Header { struct _Link_Node *next; }Hash_Header,*Hash_Header_Ptr; /********************************************************************* * 全局变量 **********************************************************************/ //哈希表 Hash_Header_Ptr Hash_Table[HASH_TABLE_LEN]; /********************************************************************* * 函数 **********************************************************************/ /********************************************************************* * 哈希表函数 *说明: *1.用哈希函数生成id对应的哈希表中的位置 输入:id 返回:位置 **********************************************************************/ uint8_t hash_func(uint16_t id) { uint8_t pos = 0; pos = id % HASH_TABLE_LEN; return pos; } /********************************************************************* * 初始化节点 *返回:结点指针 **********************************************************************/ Link_Node_Ptr init_link_node(void) { Link_Node_Ptr node; //申请节点 node = (Link_Node_Ptr) malloc(sizeof(Link_Node)); //初始化长度为0 node->next = NULL; return node; } /********************************************************************* * 初始化哈希表头结点 *返回哈希表头结点指针 **********************************************************************/ Hash_Header_Ptr init_hash_header_node(void) { Hash_Header_Ptr node; //申请节点 node = (Hash_Header_Ptr) malloc(sizeof(Hash_Header)); //初始化长度为0 node->next = NULL; return node; } /********************************************************************* * 哈希表初始化 *说明: *1.初始化哈希表Hash_Table *2.哈希表长度最大不能超过256 **********************************************************************/ void init_hash_table(void) { uint8_t i = 0; for (i = 0;i < HASH_TABLE_LEN;i++) { Hash_Table[i] = init_hash_header_node(); Hash_Table[i]->next = NULL; } } /********************************************************************* * 在哈希表增加节点 *说明: *1.在哈希表的某个链表末增加数据 输入:new_node:新节点 **********************************************************************/ void append_link_node(Link_Node_Ptr new_node) { Link_Node_Ptr node; uint8_t pos = 0; //新节点下一个指向为空 new_node->next = NULL; //用哈希函数获得位置 pos = hash_func(new_node->id); //判断是否为空链表 if (Hash_Table[pos]->next == NULL) { //空链表 Hash_Table[pos]->next = new_node; } else { //不是空链表 //获取根节点 node = Hash_Table[pos]->next; //遍历 while (node->next != NULL) { node = node->next; } //插入 node->next = new_node; } } /********************************************************************* * 在哈希表查询节点 *说明: *1.知道在哈希表某处的单链表中,并开始遍历. *2.返回的是查询节点的前一个节点指针.这么做是为了做删除操作. 输入:pos:哈希表数组位置,从0开始计数 id:所需要查询节点的id root:如果是根节点,则*root = 1,否则为0 返回:所需查询的节点的前一个节点指针,如果是根节点则返回根节点,失败返回0 **********************************************************************/ Link_Node_Ptr search_link_node(uint16_t id,uint8_t *root) { Link_Node_Ptr node; uint8_t pos = 0; //用哈希函数获得位置 pos = hash_func(id); //获取根节点 node = Hash_Table[pos]->next; //判断单链表是否存在 if (node == NULL) { return 0; } //判断是否是根节点 if (node->id == id) { //是根节点 *root = 1; return node; } else { //不是根节点 *root = 0; //遍历 while (node->next != NULL) { if (node->next->id == id) { return node; } else { node = node->next; } } return 0; } } /********************************************************************* * 在哈希表删除节点 *说明: *1.删除的不是当前节点,而是当前节点后的一个节点 输入:node:删除此节点后面的一个节点 new_node:新节点 **********************************************************************/ void delete_link_node(Link_Node_Ptr node) { Link_Node_Ptr delete_node; //重定向需要删除的前一个节点 delete_node = node->next; node->next = delete_node->next; //删除节点 free(delete_node); delete_node = NULL; } /********************************************************************* * 在哈希表删除根节点 输入:node:根节点 **********************************************************************/ void delete_link_root_node(Link_Node_Ptr node) { uint8_t pos = 0; //用哈希函数获得位置 pos = hash_func(node->id); //哈希表头清空 if (node != NULL) { Hash_Table[pos]->next = node->next; //删除节点 free(node); node = NULL; } } /********************************************************************* * 获得哈希表中所有节点数 输入:node:根节点 **********************************************************************/ uint16_t get_node_num(void) { Link_Node_Ptr node; uint16_t i = 0; uint16_t num = 0; //遍历 for (i = 0;i < HASH_TABLE_LEN;i++) { //获取根节点 node = Hash_Table[i]->next; //遍历 while (node != NULL) { num++; node = node->next; } } return num; } /********************************************************************* * 从哈希表中获得对应序号的节点 *参数:index:序号.从1开始,最大值为节点总数值 * root:如果是根节点,则*root = 1,否则为0 返回:所需查询的节点的前一个节点指针,如果是根节点则返回根节点,失败返回0 **********************************************************************/ Link_Node_Ptr get_node_from_index(uint16_t index,uint8_t *root) { Link_Node_Ptr node; uint16_t i = 0; uint16_t num = 0; //遍历 for (i = 0;i < HASH_TABLE_LEN;i++) { //获取根节点 node = Hash_Table[i]->next; //判断单链表是否存在 if (node == NULL) { continue; } //根节点 num++; if (num == index) { //是根节点 *root = 1; return node; } //遍历 while (node->next != NULL) { num++; if (num == index) { //不是根节点 *root = 0; return node; } node = node->next; } } return 0; } /********************************************************************* * 删除hash表中所有节点 **********************************************************************/ void drop_hash() { Link_Node_Ptr node; uint16_t i = 0; Link_Node_Ptr node_next; //遍历 for (i = 0;i < HASH_TABLE_LEN;i++) { //获取根节点 node = Hash_Table[i]->next; while (1) { //判断单链表是否存在 if (node == NULL) { //不存在 Hash_Table[i]->next = NULL; break; } //根节点下一个节点 node_next = node->next; //删除根节点 free(node); //重指定根节点 node = node_next; } } } /********************************************************************* * 输出所有节点 **********************************************************************/ void printf_hash() { Link_Node_Ptr node; uint8_t root = 0; uint8_t i = 0; uint8_t num = 0; printf("-------------printf hash table-------------\n"); num = get_node_num(); for (i = 1;i <= num;i++) { node = get_node_from_index(i,&root); if (node != 0) { if (root) { printf("root node:node num:%d,id:%d\n",i,node->id); } else { printf("normal node:node num:%d,id:%d\n",i,node->next->id); } } } } /********************************************************************* * 主函数 *说明:实现对哈希表的新建,建立节点,查询及增加,删除节点的操作 **********************************************************************/ int main() { Link_Node_Ptr node; uint8_t temp = 0; uint8_t root = 0; uint8_t i = 0; init_hash_table(); //插入数据id = 1,data = 2; node = init_link_node(); node->id = 1; node->data = 2; append_link_node(node); //查询节点数 printf("the number of nodes %d\n",get_node_num()); node = init_link_node(); node->id = 100; node->data = 101; append_link_node(node); node = init_link_node(); node->id = 97; node->data = 1001; append_link_node(node); node = init_link_node(); node->id = 98; node->data = 10001; append_link_node(node); node = init_link_node(); node->id = 3; node->data = 10001; append_link_node(node); node = init_link_node(); node->id = 2; node->data = 10001; append_link_node(node); //查询节点数 printf("the number of nodes %d\n",get_node_num()); //查询id = 100; node = search_link_node(100,&temp); if (node != 0) { if (temp == 0) { printf("delte normal note :id num is %d,data is %d\n",node->next->id,node->next->data); //删除 delete_link_node(node); } else { //根节点 printf("delte root note :id num is %d,data is %d\n",node->id,node->data); //删除 delete_link_root_node(node); } } else { printf("query fail\n"); } //查询id = 2; node = search_link_node(2,&temp); if (node != 0) { if (temp == 0) { printf("data is %d\n",node->next->data); } else { //根节点 printf("data is %d\n",node->data); } } else { printf("query fail\n"); } //查询节点数 printf("the num of nodes is %d\n",get_node_num()); printf_hash(); getchar(); return 0; }
三 运行结果
[root@localhost test]# gcc -o hashtest hashtest.c
[root@localhost test]#./hashtest
the number of nodes 1
the number of nodes 6
delte root note :id num is 100,data is 101
data is 10001
the num of nodes is 5
-------------printf hash table-------------
root node:node num:1,id:97
root node:node num:2,id:1
normal node:node num:3,id:98
root node:node num:4,id:2
root node:node num:5,id:3
四 运行图例
删除节点前:
删除节点后:
相关推荐
希综述的简单整理 特别全的关于哈希的整理 给有需要的朋友
int H1(char *key) { int temp[10]; long k,d=0,e; int c,f,g; while(*key) d+=*key++; d*=d; e=d; for(c=0;d!=0;c++) { d/=10; } g=c; for(f=c;f>=0;f--) { temp[--g]=e; e/=10;...}
哈希表应用C++_STL_hash 哈希表应用C++_STL_hash 哈希表应用C++_STL_hash
哈希表的简单应用,包括演讲实例
哈希表简单应用实例,实现代码是c#,开发工具vs2010
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2...
详细讲解了哈希表的原理,并通过案例来讲述哈希的实现
设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; (2) 从键盘或文件输入各记录,至少50个以上...
数据结构课程设计-哈希表及其应用:散列表的设计与实现,仅供大家参考!
数据结构哈希表的实现,很值得初学者的学习与应用,看完代买能够掌握基本哈希表的应用
二叉搜索树 B树 Skiplist跳表 哈希表 大数据哈希表应用,注意:此资源上传文件错误(选成快捷方式了),请移除,我没有找到删除按钮。
linux内核哈希链表的添删查在用户态应用,通过简单的实例表现出来
这是一个哈希函数的应用及MD5算法的介绍
对于原地哈希算法的一些案例应用,三个,分别是查找缺失的最小整数,寻找数组中错误的元素和给出对应的正确元素,寻找重复数。
深度学习在哈希算法的应用.pdf
上海交通大学计算机系数据结构作业,以哈希表为基础,输入单词进行映射。
设计散列表实现手机号码查找系统,对手机号码进行Hash。...(4)输入手机号码,对该手机号码进行哈希查找,显示散列的次数,若号码存在,则显示号码对应的人名、性别以及邮件地址,否则提示该号码不存在
本文首先介绍了哈希表的有关知识,然后介绍了电信公用电话客户流失分析中为了实现合并表所采用的哈希表、冲突解决方法,接着介绍了合并表的处理流程,最后简介了应用中的关键算法。 本文收录于计算机工程与设计>>...
这个资源是一个zip压缩包,内含一个哈希建表查找程序的全部源代码(基于C#编码),所有的资源文件,帮助文档,符合CDIO的软件开发文档。本资源为云南大学软件学院数据结构实验课程的课程成果,仅供大家参考思路,...
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...