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

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 Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

JAVA保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4