一 哈希介绍
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
四 运行图例
删除节点前:
删除节点后:
相关推荐
**哈希技术**是一种广泛应用于计算机科学中的高效数据结构和技术,主要用于快速查找、存储和检索数据。在大数据时代,随着数据量的急剧增长,如何高效地处理这些数据变得尤为重要。哈希技术在解决大规模数据集的相似...
7. **应用实例**:谷歌图片搜索是一个典型的感知哈希应用案例。当用户上传一张图片,谷歌会使用感知哈希算法计算其指纹,然后与数据库中其他图像的指纹进行比对,找出相似或相同的图片。 8. **指纹验证**:在版权...
深度学习哈希是一种结合了深度学习技术和传统哈希方法的先进技术,主要应用...此外,研究如何在有限的计算资源和内存下实现更快速的哈希编码和检索,以及如何将深度学习哈希应用于实时和动态数据流也是重要的研究课题。
在哈希表的简单应用中,我们通常会关注以下几个方面: 1. **哈希函数**:哈希函数是哈希表的核心,它负责将输入(键)转换为数组的索引。一个好的哈希函数应该尽量让不同的键产生不同的哈希值,以减少冲突。常见的...
哈希函数的应用 哈希函数是一种常用的数据结构技术,用于高效地存储和查找数据。哈希函数的应用广泛,包括数据库索引、数据压缩、加密算法等。在本文中,我们将探讨哈希函数的应用的一些方面,并设计一个基于哈希...
在这个简单的应用实例中,我们将探讨如何在C#环境下使用哈希表,并通过Visual Studio 2010进行开发。 哈希表的基本工作原理是通过一个哈希函数将键转化为数组的下标,这个过程称为哈希化。理想的哈希函数能够确保...
在学习和使用这样的源码时,你可以从中学习到如何在易语言中实现哈希计算,以及如何将哈希应用于实际问题。同时,也可以借此机会深入理解哈希函数的工作原理和应用范围,提升你的编程技能。如果你打算进一步研究,...
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;...}
### 哈希表及其应用 #### 一、定义与基本原理 哈希表是一种高效的数据结构,用于存储键值对数据。它通过一个特定的函数(哈希函数)将键映射到一个固定的范围内,进而定位到具体的存储位置。哈希表的主要优势在于...
Linux内核哈希链表是一种高效的数据结构,广泛应用于内核及用户态程序,用于解决数据查找、添加和删除的问题。哈希链表结合了哈希表的快速查找特性和链表的灵活插入删除功能,使得在大规模数据操作时能保持较高的...
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2...
近邻搜索是哈希算法应用的一个主要领域,其基本任务是为给定的查询检索条目找到目标数据库中最相似的条目。哈希函数设计通常包括两个关键步骤:投影和量化。投影过程涉及数据降维,而量化过程则将降维后的数据二值化...
以上就是关于C++ STL中的哈希表及其应用的基本知识,它在很多场景下提供了高效的数据处理能力,是C++编程中不可或缺的一部分。通过理解和熟练掌握这些概念和用法,能有效提升程序的效率和可读性。
哈希表的应用广泛,如数据库索引、缓存、编程语言的字典和集合等。通过理解和实现哈希表,学生可以深入理解数据结构和算法,提升问题解决能力。在`main.cpp`中,学生们将有机会亲手实现这些概念,进一步巩固他们的...
4. **信息学竞赛中的哈希应用**: - 在解决实际问题时,如例题1所示的多维匹配问题,哈希函数可以用于快速预筛选,降低比较次数,从而提高算法效率。即使在高维情况下,通过巧妙设计哈希函数和递推公式,仍可以在...
以下是对JS模拟实现哈希表及其应用的详细说明。 首先,了解一些与哈希表相关的基础知识点: 1. **属性的枚举**:在JavaScript中,我们可以使用`for...in`循环来枚举对象的所有可枚举属性。例如,给定一个名为`...
然而,实际应用中,哈希表的性能受到冲突率的影响,冲突过多可能导致性能退化至接近O(n)。 了解并熟练掌握哈希表的构造方法,不仅能够提高程序的运行效率,还能帮助解决许多实际问题,如数据库索引、缓存系统、数据...
设计散列表实现身份证查找系统,对身份证号进行Hash。 [基本要求] (1) 设每个记录有下列数据项:身份证号码(虚构,位数和编码规则与真实一致即可)、姓名、地址; (2) 从键盘或文件输入各记录,至少50个以上...
在详细讲解二叉搜索树、B树、Skiplist跳表和哈希表的过程中,我们首先需要了解数据结构的定义及其特性,然后针对不同数据结构在大数据环境下的应用进行探究。 1. 二叉搜索树(BST): 二叉搜索树是一种特殊的二叉树...