创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步!
更多算法分析与设计知识专栏:算法分析🔥
给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ
一、哈希表介绍
哈希表(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查询失败文章来源:https://www.toymoban.com/news/detail-793936.html
文章来源地址https://www.toymoban.com/news/detail-793936.html
大家的点赞、收藏、关注将是我更新的最大动力! 欢迎留言或私信建议或问题。 |
大家的支持和反馈对我来说意义重大,我会继续不断努力提供有价值的内容!如果本文哪里有错误的地方还请大家多多指出(●'◡'●) |
到了这里,关于【算法】哈希表介绍 | 哈希表的链式地址法代码实现(C/C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!