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

2023-12-17 11:30:07

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

在这里插入图片描述

一、哈希表介绍

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

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

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

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

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

散列技术

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

二、哈希表的创建

1.确定哈希函数

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

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

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

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

p = key%m

2.哈希冲突的解决方案

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

举个栗子：
如果现在要存放Tianxi这个字符串，通过对取余法存入到哈希表中，如下图所示：
T i a n 都依次正常存入了，到字符x时发现索引0已经被字符T占用了：

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

i.开放定址法

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

线性探测

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

线性补偿探测

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

沿此序列逐个单元地查找，直到找到一个开放的地址为止，例如可以将上面的x存入key = 5中

ii.链式地址法

拉链法中，哈希表中每个键对应的值都为一个链表的头节点，当发生哈希冲突时，新的键值对会被插入到相应的链表中。
如下图所示，字符x发生哈希冲突时将其加入到链表头节点中：

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

链式地址取余法代码实现（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查询失败