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

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。

相关文章

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整
阅读更多...
Java枚举类实现Key-Value映射的多种实现方式

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co
阅读更多...
C#使用SQLite进行大数据量高效处理的代码示例

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入：从乌龟到猎豹的蜕变分页查询：加载百万数据异步处理：拒绝界面
阅读更多...
使用Sentinel自定义返回和实现区分来源方式

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》：本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定
阅读更多...
Springboot处理跨域的实现方式(附Demo)

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》：本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.
阅读更多...
springboot security使用jwt认证方式

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》：本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一
阅读更多...
springboot security之前后端分离配置方式

springboot security之前后端分离配置方式

《springbootsecurity之前后端分离配置方式》：本文主要介绍springbootsecurity之前后端分离配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的... 目录前言自定义配置认证失败自定义处理登录相关接口匿名访问前置文章总结前言spring boot secu
阅读更多...
SpringBoot中封装Cors自动配置方式

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》：本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties
阅读更多...
Flutter打包APK的几种方式小结

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte
阅读更多...
python+opencv处理颜色之将目标颜色转换实例代码

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,：本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV： 关于颜色总是要转HSV的掩膜再标注总结 目标：将红色的部分滤
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2