【算法】哈希表介绍 | 哈希表的链式地址法代码实现(C/C++)

这篇具有很好参考价值的文章主要介绍了【算法】哈希表介绍 | 哈希表的链式地址法代码实现(C/C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步!
更多算法分析与设计知识专栏:算法分析🔥
给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

哈希地址法实现,【数据结构与算法】,算法,散列表,c语言,笔记,学习,c++,数据结构


一、哈希表介绍

哈希表(HashMap、unordered_map)又称为散列表,是一种可以对已经存储的数据进行快速查找的数据结构,它可以根据键(Key)值直接进行访问。
举几个栗子:

在电话簿中,每个电话号码对应一个名字,在查找某个人的电话号码时根据姓名即可进行快速查找,这实际上就利用了哈希思想,键是电话号码,值是名字。

如果要对某字符串进行反复搜索的操作,每次都遍历字符串效率太低,使用哈希思想将字符进行分组(例如分为256组),然后将每个字符按照规则存储(将字符串中的每个字符通过哈希函数进行映射),在后续对字符查找时即可通过关键字key进行快速查找到字符的存储位置,可以在常数时间内进行查找、插入和删除操作。

哈希表主要利用了分组的思想,采用散列(映射)技术

哈希表的增删查时间复杂度都是O(1)

散列技术

散列技术是一种可以用于快速查找的存储技术,通过散列函数(哈希函数)将一组数据按照特征建立对应关系。查找时只需要根据对应关系找到关键字key的映射,映射到内存中的一个位置。

二、哈希表的创建

1.确定哈希函数

哈希函数可以根据数据的情况不同进行不同的设计,最好要满足容易计算并且根据数据特征均匀分布

例如:
按照数据类型分组:

  • 将字符按照ASCLL码分为256组
  • 将班级同学按照省份分组

取余法:
通过将关键字除以一个素数取余数作为哈希表中的位置

p = key%m

2.哈希冲突的解决方案

在理想情况下,不同的键值能够映射到不同的索引,但是在实际中,可能存在不同的键值映射到相同的索引的情况,这种情况称为哈希冲突

举个栗子:
如果现在要存放Tianxi这个字符串,通过对取余法存入到哈希表中,如下图所示:
T i a n 都依次正常存入了,到字符x时发现索引0已经被字符T占用了:哈希地址法实现,【数据结构与算法】,算法,散列表,c语言,笔记,学习,c++,数据结构

这就是不同的键映射到相同的索引,即哈希冲突,要解决哈希冲突有例如下面的方法:

i.开放定址法

当发生冲突时,使用某种探查技术在散列表中形成一个探查序列
可以分为:

  • 线性探测

发生冲突时,线性探测会按照步长依次探测下一个位置,直到找到空位或找到目标元素为止

  • 线性补偿探测

线性补偿探测是线性探测的一种改进版本。它同样按照一定的步长探测哈希表中的下一个位置,但是当连续探测若干个位置都发生冲突时,它会增加步长的大小(每次增加一定大小),能够加快探测速度

沿此序列逐个单元地查找,直到找到一个开放的地址为止,例如可以将上面的x存入key = 5中
哈希地址法实现,【数据结构与算法】,算法,散列表,c语言,笔记,学习,c++,数据结构

ii.链式地址法

拉链法中,哈希表中每个键对应的值都为一个链表的头节点,当发生哈希冲突时,新的键值对会被插入到相应的链表中。
如下图所示,字符x发生哈希冲突时将其加入到链表头节点中:
哈希地址法实现,【数据结构与算法】,算法,散列表,c语言,笔记,学习,c++,数据结构

当哈希冲突较为频繁时,链表可能会变得很长,导致查找效率下降


链式地址取余法代码实现(C/C++)

  • 1.申请表头 表头初始化
  • 2.取余获得索引位置 元素入表
  • 3.节点空间申请 头添加
#define MOD 6

typedef struct Node
{
	int val;
	struct Node* pNextNode;
}ListNode;

ListNode** createHash(int arr[], int length)
{
	if (arr == NULL || length <= 0) return NULL;
	//申请表头
	ListNode** pHash = (ListNode**)malloc(sizeof(ListNode*) * MOD);
	memset(pHash, 0, sizeof(ListNode*) * MOD);
	//元素入表
	int nIndex;
	for (int i = 0; i < length; i++)
	{
		//获得索引位置
		nIndex = arr[i] % MOD;
		//节点空间申请
		ListNode* pTempNode = NULL;
		pTempNode = (ListNode*)malloc(sizeof(ListNode));
		pTempNode->val = arr[i];

		//头添加
		pTempNode->pNextNode = pHash[nIndex];
		pHash[nIndex] = pTempNode;
	}
	return pHash;
}

三、哈希表的使用

  • 1.取余获得索引位置
  • 2.遍历链表
void HashSearch(ListNode** pHash, int target)
{
	if (pHash == NULL)return;
	int nIndex = target % MOD;
	ListNode* pTempNode = pHash[nIndex];
	while (pTempNode)
	{
		if (pTempNode->val == target)
		{
			printf("success!\n");
			return;
		}
		else
		{
			pTempNode = pTempNode->pNextNode;
		}
	}
	printf("fail!\n");
	return;
}

测试代码:

110查询成功,100查询失败

哈希地址法实现,【数据结构与算法】,算法,散列表,c语言,笔记,学习,c++,数据结构
哈希地址法实现,【数据结构与算法】,算法,散列表,c语言,笔记,学习,c++,数据结构文章来源地址https://www.toymoban.com/news/detail-793936.html

大家的点赞、收藏、关注将是我更新的最大动力! 欢迎留言或私信建议或问题。
大家的支持和反馈对我来说意义重大,我会继续不断努力提供有价值的内容!如果本文哪里有错误的地方还请大家多多指出(●'◡'●)

到了这里,关于【算法】哈希表介绍 | 哈希表的链式地址法代码实现(C/C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包