哈希表之处理哈希冲突的开散列方式

2024-04-17 10:18
文章标签 处理 方式 哈希 冲突 表之 开散列

本文主要是介绍哈希表之处理哈希冲突的开散列方式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在我的博客：哈希表之处理哈希冲突的闭散列方式 中详细介绍了哈希的概念以及处理哈希冲突的闭散列方式。在本文章中，主要介绍处理哈希冲突的另一种方式：开散列。

一.开散列的概念

开散列：又叫链地址法、开链法。首先对关键码集合用哈希函数计算哈希地址，具有相同哈希地址的关键码归于同一子集合中，每一个子集合称为一个桶，各个桶中的元素通过一个单链表的方式链接起来（可以头插的方式将桶中元素链接起来），链表的第一个节点存放在哈希表中。

举例：关键码集合={1,3,5,6,11,15,16,21,25,31}，哈希表大小为10，哈希函数：Hash(Key)=Key%10。下面通过画图将关键码集合中的数据元素以开散列的方式插入到哈希表中：

注：下图中每个单链表是以头插的方式链接的。大家可以根据自己的方式插入链表元素！


二.代码实现开散列的哈希表的插入查找删除

关于代码的编程思路，在具体代码中有详细的说明！

2.1 头文件hash.h

#pragma once
//为了打印函数名定义标识符                                                                                                                                   
#define HEADER printf("===========%s========\n",__FUNCTION__);
//定义关于哈希元素的结构体
typedef int KeyType;
typedef int ValType;
typedef struct HashElem{KeyType key;ValType value;struct HashElem* next;
}HashElem;
//定义哈希表的结构体
#define HashMaxSize 1000
typedef size_t (*HashFunc)(KeyType key);
typedef struct HashTable{HashElem* data[HashMaxSize];size_t size;HashFunc func;
}HashTable;
//函数声明
HashElem* HashBucketFind(HashElem* head,KeyType key);
int HashBucketFindEx(HashElem* head,KeyType key,HashElem** pre,HashElem** cur);

2.2 准备工作（包括节点的创建与销毁以及哈希表的初始化与销毁）

//0.创建节点以及销毁节点
HashElem* CreateElem(KeyType key,ValType value)                                                                            
{HashElem* new_node=(HashElem*)malloc(sizeof(HashElem));new_node->key=key;new_node->value=value;return new_node;
}
void DestroyElem(HashElem* cur)
{free(cur);
}
//1.初始化
//思路：初始化即将哈希表置为空哈希表
//故，将哈希表的有效元素size置为0并初始化哈希函数以及将哈希表中的数组元素置为NULL
void HashInit(HashTable* ht,HashFunc func)
{//非法输入if(ht==NULL)return;//1.将size置为0ht->size=0;//2.将哈希函数初始化ht->func=func;//3.将哈希表中的数组元素置为NULLsize_t i=0;for(i=0;i<HashMaxSize;i++){ht->data[i]=NULL;}
}
//2.销毁
//思路：将已创建好的哈希表恢复为空的哈希表
//故：将有效元素size置为0以及将哈希函数置为NULL，值得注意的是，需要将已创建好的节点均销毁
void HashDestroy(HashTable* ht)
{if(ht==NULL)return;ht->size=0;ht->func=NULL;size_t i=0;for(i=0;i<HashMaxSize;i++){HashElem* cur=ht->data[i];while(cur!=NULL){HashElem* next=cur->next;DestroyElem(cur);cur=next;}}                                                                                                                      
}

2.3 哈希表的插入操作

//3.插入
//思路：1.根据key值计算offset
//      2.在offset对应的链表中查看key是否存在？
//      (1)存在则约定插入失败
//      (2)不存在则使用头插法并将size++
void HashInsert(HashTable* ht,KeyType key,ValType value)
{//非法输入if(ht==NULL)return;//1.根据key值计算offset值size_t offset=ht->func(key);//2.在offset对应的链表中查看key是否存在？//利用一个函数完成查找工作，若没找到则返回NULL，若找到了则返回其节点的指向HashElem* ret=HashBucketFind(ht->data[offset],key);//(1)存在时表示插入失败if(ret!=NULL){//表示存在key值，则插入失败return;}//(2)不存在时进行头插法并将size++HashElem* new_node=(HashElem*)malloc(sizeof(HashElem));new_node->key=key;                                                                                                     new_node->value=value;new_node->next=ht->data[offset];ht->data[offset]=new_node;ht->size++;
}
HashElem* HashBucketFind(HashElem* head,KeyType key)
{HashElem* cur=head;for(;cur!=NULL;cur=cur->next){if(cur->key==key){break;}}return cur;
}

2.4 哈希表的查找操作

//4.查找
//思路：1.根据key值计算offset值
//      2.从offset桶中去依次查找key值
int HashFind(HashTable* ht,KeyType key,ValType* value)
{//非法输入if(ht==NULL&&value==NULL)return 0;  //返回0表示查找失败，返回1表示查找成功//判断哈希表是否为空if(ht->size==0)return 0;//1.根据key值计算offset值size_t offset=ht->func(key);//2.在offset桶中去依次查找key值HashElem* ret=HashBucketFind(ht->data[offset],key);//(1)ret为NULL表示没找到if(ret==NULL)return 0;//(2)ret不为NULL表示找到了*value=ret->value;return 1;
}

2.5 哈希表的删除操作

//5.删除
//思路：1.根据key值计算offset值
//      2.通过offset找到对应的链表并对key值进行删除
//      (1)找到了，则需要知道其对应key值的前一个key值的指向
//      (2)没找到，直接return
//      (3)进行销毁并将size--
void HashRemove(HashTable* ht,KeyType key)
{//非法输入if(ht==NULL)return;//哈希表为空时if(ht->size==0){return;}//1.根据key计算offsetsize_t offset=ht->func(key);//2.在offset对应的链表中查找其key//由于需要对链表进行删除，故需要知道要删除的元素的前一个元素的指向HashElem* pre=NULL;HashElem* cur=NULL;int ret=HashBucketFindEx(ht->data[offset],key,&pre,&cur);//(1)当ret为0时表示没找到，直接return                                                                                  if(ret==0)return;//(2)当ret不为0时表示找到了，需要判断要删除的元素是否为头结点if(pre==NULL){{//要删除的为头结点ht->data[offset]=cur->next;}else{//要删除的不是头结点pre->next=cur->next;}//销毁DestroyElem(cur);//最后对size--ht->size--;
}
int HashBucketFindEx(HashElem* head,KeyType key,HashElem** pre,HashElem** cur)
{HashElem* cur_node=head;HashElem* pre_node=NULL;for(;cur_node!=NULL;pre_node=cur_node,cur_node=cur_node->next){if(cur_node->key==key){break;}                                                                                                                  }*pre=pre_node;*cur=cur_node;if(cur_node==NULL)return 0;return 1;
}

3. 测试以上代码正确与否

以下代码仅供参考如何测试所编写的代码的正确与否！

/*===========测试代码块==========*/
size_t func(KeyType key)
{return key%HashMaxSize;
}
//测试HashInit
void Test_HashInit()
{HEADER;HashTable ht;HashInit(&ht,func);printf("expected 0 actual %d\n",ht.size);printf("expected %p actual %p\n",func,ht.func);
}
//测试HashDestroy
void Test_HashDestroy()
{HEADER;HashTable ht;HashInit(&ht,func);HashDestroy(&ht);printf("expected 0 actual %d\n",ht.size);printf("expected NULL actual %p\n",ht.func);
}                                                                                                                          
//测试HashInsert
//为了测试正确与否，写一个打印函数
void HashPrint(HashTable* ht,const char* msg)
{printf("%s\n",msg);//非法输入if(ht==NULL)return;//循环去打印哈希表size_t i=0;for(;i<HashMaxSize;i++){if(ht->data[i]==NULL)continue;printf("i=%d\n",i);HashElem* cur=ht->data[i];for(;cur!=NULL;cur=cur->next){printf("[%d:%d] ",cur->key,cur->value);}printf("\n");}
}
void Test_HashInsert()
{HEADER;HashTable ht;HashInit(&ht,func);                                                                                                    HashInsert(&ht,1,1);HashInsert(&ht,1001,1001);HashInsert(&ht,1,10);HashInsert(&ht,2,2);HashInsert(&ht,1002,1002);HashPrint(&ht,"插入元素");
}
//测试HashFind
void Test_HashFind()
{HEADER;HashTable ht;HashInit(&ht,func);HashInsert(&ht,1,1);HashInsert(&ht,1001,1001);HashInsert(&ht,1,10);HashInsert(&ht,2,2);HashInsert(&ht,1002,1002);int ret;ValType value;ret=HashFind(&ht,1001,&value);printf("expected 1,actual %d\n",ret);printf("expected 1001,actual %d\n",value);ret=HashFind(&ht,3,&value);printf("expected 0,actual %d\n",ret);
}
//测试HashRemove
void Test_HashRemove()
{                                                                                                                          HEADER;HashTable ht;HashInit(&ht,func);HashInsert(&ht,1,1);HashInsert(&ht,1001,1001);HashInsert(&ht,1,10);HashInsert(&ht,2,2);HashInsert(&ht,1002,1002);HashRemove(&ht,1);HashRemove(&ht,2);HashPrint(&ht,"删除");
}
/*=============主函数============*/
int main()
{Test_HashInit();Test_HashDestroy();Test_HashInsert();Test_HashFind();Test_HashRemove();return 0;
}


















这篇关于哈希表之处理哈希冲突的开散列方式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/911520。

相关文章

java实现docker镜像上传到harbor仓库的方式

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》：本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2
阅读更多...
springboot项目打jar制作成镜像并指定配置文件位置方式

springboot项目打jar制作成镜像并指定配置文件位置方式

《springboot项目打jar制作成镜像并指定配置文件位置方式》：本文主要介绍springboot项目打jar制作成镜像并指定配置文件位置方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录一、上传jar到服务器二、编写dockerfile三、新建对应配置文件所存放的数据卷目录四、将配置文
阅读更多...
gitlab安装及邮箱配置和常用使用方式

gitlab安装及邮箱配置和常用使用方式

《gitlab安装及邮箱配置和常用使用方式》：本文主要介绍gitlab安装及邮箱配置和常用使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1.安装GitLab2.配置GitLab邮件服务3.GitLab的账号注册邮箱验证及其分组4.gitlab分支和标签的
阅读更多...
电脑提示xlstat4.dll丢失怎么修复? xlstat4.dll文件丢失处理办法

电脑提示xlstat4.dll丢失怎么修复? xlstat4.dll文件丢失处理办法

《电脑提示xlstat4.dll丢失怎么修复?xlstat4.dll文件丢失处理办法》长时间使用电脑，大家多少都会遇到类似dll文件丢失的情况，不过，解决这一问题其实并不复杂，下面我们就来看看xls... 在Windows操作系统中，xlstat4.dll是一个重要的动态链接库文件，通常用于支持各种应用程序
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
SQL Server数据库死锁处理超详细攻略

SQL Server数据库死锁处理超详细攻略

《SQLServer数据库死锁处理超详细攻略》SQLServer作为主流数据库管理系统,在高并发场景下可能面临死锁问题,影响系统性能和稳定性,这篇文章主要给大家介绍了关于SQLServer数据库死... 目录一、引言二、查询 Sqlserver 中造成死锁的 SPID三、用内置函数查询执行信息1. sp_w
阅读更多...
Java对异常的认识与异常的处理小结

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。（1）简单定义-什么是
阅读更多...
Linux脚本(shell)的使用方式

Linux脚本(shell)的使用方式

《Linux脚本(shell)的使用方式》：本文主要介绍Linux脚本(shell)的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录概述语法详解数学运算表达式Shell变量变量分类环境变量Shell内部变量自定义变量：定义、赋值自定义变量：引用、修改、删
阅读更多...
python判断文件是否存在常用的几种方式

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,：本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用
阅读更多...
Mybatis的分页实现方式

Mybatis的分页实现方式

《Mybatis的分页实现方式》MyBatis的分页实现方式主要有以下几种,每种方式适用于不同的场景,且在性能、灵活性和代码侵入性上有所差异,对Mybatis的分页实现方式感兴趣的朋友一起看看吧... 目录​1. 原生 SQL 分页（物理分页）​​2. RowBounds 分页（逻辑分页）​​3. Page
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2