文章目录哈希表一、哈希存储散列存储的基本概念二、哈希表三、链地址法哈希表的C语言实现3.1 创建哈希表3.2 设计哈希函数3.3 哈希数据插入3.4 遍历哈希表3.5 哈希表的查找3.6 销毁哈希表哈希表一、哈希存储散列存储的基本概念定义将要存储的数据中的关键字和存储位置之间建立对应的映射关系。存储数据时按照映射关系寻找存储位置查找数据时同样根据关键字和映射关系寻找原数据的存储位置。哈希函数存储数据的映射关系。哈希函数f(key);目的为了快速检索数据。二、哈希表哈希表遵循哈希算法的连续内存空间。我们通过下面这串数据来解释它的哈希函数就是f(key) key % 10通过求余法来使数据存储到一个容器中。这时候就会有人发现如果有多个余数相同的树怎么办这时候我们就会引入哈希冲突这个专业名词了。哈希冲突哈希矛盾key1 ! key2; f(key1) f(key2)解决方法1. 开放定址法核心思想所有元素都存放在哈希表数组本身里面不额外开链表。如果算出的位置被占了就按照某种规则向后另一个位置再找下一个空闲位置存放。2. 链地址法核心思想哈希表每个数组位置存一条链表。哈希地址相同的所有元素全部挂到同一个链表上。就像下图所示数组的每个位置都相当于一条链表的头指针。三、链地址法哈希表的C语言实现API:1. 创建哈希表2. 设计哈希函数3. 哈希表数据插入4. 哈希表的查找5. 销毁哈希表6. 遍历哈希表3.1 创建哈希表宏定义哈希表数组容量为 27创建用于存放姓名与电话号码的联系人信息结构体Info_t以及包含数据域和后继指针的链表结点结构体Hnode_t头文件#ifndef__HASH_H__#define__HASH_H__#defineHASH_SIZE27typedefstructinfo_p{charname[32];chartel[16];}Info_t;typedefstructhnode{Info_t data;structhnode*pnext;}Hnode_t;随后在主函数中定义了一个长度为 27、初始值全为空的全局指针数组hash_table采用拉链法构建哈希表通过链表来处理哈希冲突。Hnode_t*hash_table[HASH_SIZE]{NULL};3.2 设计哈希函数设计哈希函数接收姓名字符串name取出字符串第一个字符若为首字母小写则返回小写字母对应的下标若为首字母大写则返回大写字母对应的下标其余情况返回哈希表最后一个桶的下标以此计算出该联系人数据在哈希表数组中对应的存储位置。计算规则a/A→0b/B→1 … z/Z→25其他字符→26。intget_addr(char*name){if(name[0]aname[0]z){returnname[0]-a;}elseif(name[0]Aname[0]Z){returnname[0]-A;}else{returnHASH_SIZE-1;}}3.3 哈希数据插入先调用哈希函数算出数据对应的桶下标地址动态分配一个新哈希结点并存放传入的数据采用头插法将新结点插入对应链表的表头位置新结点原先指向的链表头再更新为当前结点插入成功返回 0内存申请失败则打印提示并返回‑1。intinsert_hash_table(Hnode_t**hash_table,Info_t data){intaddrhash_function(data.name);Hnode_t*pnodemalloc(sizeof(Hnode_t));if(NULLpnode){printf(malloc error\n);return-1;}pnode-datadata;pnode-pnextNULL;pnode-pnexthash_table[addr];//pheadhash_table[addr]pnode;return0;}3.4 遍历哈希表外层循环依次访问哈希表数组里的每一个桶取出当前桶链表的头指针再通过内层 while 循环顺着链表逐个遍历结点输出每个联系人的姓名和电话号码直至链表遍历结束最终完成整张哈希表所有元素的打印展示。voidshow_hash(Hnode_t**hash_table){for(inti0;iHASH_SIZE;i){Hnode_t*ptmphash_table[i];while(ptmp!NULL){printf(%s %s\n,ptmp-data.name,ptmp-data.tel);ptmpptmp-pnext;}}}3.5 哈希表的查找先调用哈希函数算出目标姓名对应的桶下标取出该桶链表的头指针顺着链表逐个结点遍历使用字符串比较函数比对结点内的姓名找到匹配数据后打印姓名与电话号码并返回 0链表遍历完毕仍未找到则返回‑1表示查找失败。intfind_hash(Hnode_t**hash_table,char*name){intaddrget_addr(name);Hnode_t*ptmphash_table[addr];while(NULL!ptmp){if(!strcmp(ptmp-data.name,name)){printf(successfully find: %s %s\n,ptmp-data.name,ptmp-data.tel);return0;}ptmpptmp-pnext;}return-1;}3.6 销毁哈希表外层循环遍历哈希表的每一个桶取出当前桶链表的头指针在内层循环中先用临时指针保存下一个结点的地址再释放当前链表头结点并将桶头指针更新为下一个结点循环直至当前桶整条链表全部释放完毕最终完成整张哈希表所有结点内存的回收。voiddestroy_hash(Hnode_t**hash_table){for(inti0;iHASH_SIZE;i){Hnode_t*ptmphash_table[i];while(ptmp!NULL){ptmpptmp-pnext;free(hash_table[i]);hash_table[i]ptmp;}}}