C++——深部解析哈希

好久不见给大家分享一张图片吧

目录

前言

二、库文件

1、哈希冲突

2 哈希函数

3、闭散列

三 、闭散列的实现和底层逻辑

1、哈希表(闭散列)的定义

2、哈希表(闭散列)的插入

3、哈希表(闭散列)的查找

4.哈希表(闭散列)的删除

四、哈希桶

1、开散列

2、哈希桶(开散列)的定义

3、哈希桶(开散列)的析构

4、哈希桶(开散列)的插入

 5、哈希桶(开散列)的删除

 6、哈希桶(开散列)的查找

总结


相关博客
x​​​​​​​c++——map、set底层之AVL树(动图演示旋转)

vector

c语言顺序表+链表​​​​​​​


前言

在我们前面的学习中,我们知道了set和map相关的多个库文件和数据结构,今天我们我们将学习基础的哈希表和哈希桶。

学习set和map时,我们非常清楚它们都是树状结构,set为key类型,而map的为key、value类型,而哈希是一种顺序结构,那么就让我们来感受一下哈希表和哈希桶吧!!


一、哈希是什么?

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素 时,必须要经过关键码的多次比较。顺序查找时间复杂度为O(N),平衡树中为树的高度,即 O($log_2 N$),搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。

如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

当向该结构中:

插入元素

根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放

 搜索元素

对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置 取元素比较,若关键码相等,则搜索成功 该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称 为哈希表(Hash Table)(或者称散列表)

二、库文件

在学习哈希底层之前我们先了解一下大佬是怎么实现的哈希;

unordered_set

unordered_map

在这里我们理解几个和哈希相关的概念

1、哈希冲突

对于两个数据元素的关键字$k_i$和 $k_j$(i != j),有$k_i$ != $k_j$,但有:Hash($k_i$) == Hash($k_j$),即:不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突 或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢?

2 哈希函数

引起哈希冲突的一个原因可能是

哈希函数设计不够合理。

哈希函数设计原则: 哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址时,其值 域必须在0到m-1之间 哈希函数计算出来的地址能均匀分布在整个空间中

哈希函数应该比较简单

常见哈希函数

1. 直接定址法--(常用)

取关键字的某个线性函数为散列地址:Hash(Key)= A*Key + B

优点:简单、均匀

缺点:需要事先知道关键字的分布情况

使用场景:适合查找比较小且连续的情况

2. 除留余数法--(常用)

设散列表中允许的地址数为m,取一个不大于m,但最接近或者等于m的质数p作为除数, 按照哈希函数:Hash(key) = key% p(p<=m),将关键码转换成哈希地址

3. 平方取中法--(了解)

假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址; 再比如关键字为4321,对它平方就是18671041,抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合:不知道关键字的分布,而位数又不是很大的情况

4. 折叠法--(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些),然后将这 几部分叠加求和,并按散列表表长,取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况

5. 随机数法--(了解) 选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key) = random(key),其中 random为随机数函数。 通常应用于关键字长度不等时采用此法

6. 数学分析法--(了解)

设有n个d位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定 相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小,选择其中各种符号分布均匀的若干位作为散 列地址。

哈希冲突解决

解决哈希冲突两种常见的方法是:闭散列开散列

3、闭散列

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有 空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢?

1. 线性探测

比如现在需要插入元素44,先通过哈希函数计算哈希地址,hashAddr为4, 因此44理论上应该插在该位置,但是该位置已经放了值为4的元素,即发生哈希冲突。

线性探测:从发生冲突的位置开始,依次向后探测,直到寻找到下一个空位置为止。

插入

通过哈希函数获取待插入元素在哈希表中的位置 如果该位置中没有元素则直接插入新元素,如果该位置中有元素发生哈希冲突, 使用线性探测找到下一个空位置,插入新元素

删除

采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素 会影响其他元素的搜索。比如删除元素4,如果直接删除掉,44查找起来可能会受影 响。因此线性探测采用标记的伪删除法来删除一个元素。

三 、闭散列的实现和底层逻辑

我们在学习二叉树和set和map时,我们存储数据有一个规律,那就是如果插入一个树,当这个数据比根大,那么我们就往右走,比根小我们就往左走,通过这个规律,我们就可以把一个节点放到正确的位置上去;

在闭散列的概念中我们略有了解,那就是我们的哈希存储是在一个顺序表里面的,当让这个数据和顺序表建立某种映射关系,这样我们就可以轻松找到了。

这里可能有人会问了,我们既然借助了顺序表为什么不直接用顺序表呢,这里可以参考上面的哈希的优点;再说说个人看法,当我们在顺序表里面去找一个数据的时候我们需要将整个顺序表给遍历一遍,而哈希找一个数据只需要在一个小的范围里去查找

1、哈希表(闭散列)的定义

我们这里存储的算法为除留余数

enum Status//将状态进行枚举
{EMPTY,//空EXIST,//存在DELETE//删除
};template<class K,class V>
struct HashData
{pair<K, V> _kv;//存储数据Status _state= EMPTY;//状态
};
template<class K,class V>
struct HashData
{
public:bool Insert(const pair<K, V>& kv)//插入函数{}HashData<K, V>* Find(const K& key)//查找函数{}bool Erase(const K& key)//删除函数{}
private:vector<HashData<K, V>> _tables;//这里我们用的是顺序表size_t _n = 0; // 存储的数据个数
};

 现在我们知道了哈希表的基本结构;

现在然我们用图片理解哈希表吧

我们以前在顺序表里面存储数据的时候都是一个数据一个数据挨着存储,而现在我们在存储时,我们直接对要存储的数据进行取余,余数就是我们要存储的位置了,以后要是向对某个数据进行操作,我们只需要在这个数据的余数处去找这个数据

现在有一个问题那就是当我们的一个表里面要存储5、15,而表的长度为10,我们对5、15取余都是5,那怎么办呢?

这就是我们前面概念所提到过的哈希碰撞。这个时候我们只需要进行偏移一下就可以,也就是将hashi++(hashi=key%_tables.size());

2、哈希表(闭散列)的插入

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;// 负载因子超过0.7就扩容//if ((double)_n / (double)_tables.size() >= 0.7)if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);// 遍历旧表,重新映射到新表for (auto& data : _tables){if (data._state == EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hashi = kv.first % _tables.size();// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state == EXIST){index = hashi + i;index %= _tables.size();++i;}_tables[index]._kv = kv;_tables[index]._state = EXIST;_n++;return true;
}

 我们在插入的时候,是通过映射关系进入插入的,这个关系就是key对空间进行取余数,然后在对应的位置放元素,当某个位置有数据时,我们就进行偏移,将hashi++,就是向后移动一位;

思考,如果余数相同的数据太多了,我们++一圈,也就是一轮回来还是没有位置存放数据时因该怎么办?这种情况的时间复杂度是不是还不如vector呢?

解决方法那就是就行扩容,将我们的_table.size()的大小变大,那也就是进行扩容;我们解决方案是定义一个负载因子,当负载因子大于0.7时,我们就就行扩容,我们重新开辟一个顺序表,将原来的哈希表进行遍历一遍,重新进行映射一次,否则就有取余过后那个位置上找不到某一个数据;

例如:15% 10=5和15%20=15这样,我们扩容完我们15应给放在15的位置,然而我们不遍历重新映射就会导致查找时在15位置找不到15;

思考:哈希表什么情况下进行扩容?如何扩容?

3、哈希表(闭散列)的查找

HashData<K, V>* Find(const K& key)
{if (_tables.size() == 0){return false;}size_t hashi = key % _tables.size();// 线性探测size_t i = 1;size_t index = hashi;while (_tables[index]._state != EMPTY){if (_tables[index]._state == EXIST&& _tables[index]._kv.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();++i;// 如果已经查找一圈,那么说明全是存在+删除if (index == hashi){break;}}return nullptr;
}

 我们查找这里也是非常简单的,就是在取余过后到hashi的位置上去找,如果这个位置上的数据不是我们想要的数据,那么我们就往它的后面去找,直到什么时候结束呢?

我们在hashi过面一直找到数据状态为空的时候停止,因为我们插入的时候为空的位置放上了偏移或没偏移的数据,若这段空间不连续有空的的时候,那么就说明没有找到;

4.哈希表(闭散列)的删除

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}else{return false;}
}

这个函数就更简单了,我们只需要将这个位置的状态改为删除就可以了,然后让_n--,就可以了;

四、哈希桶

1、开散列

开散列概念

开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地 址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链 接起来,各链表的头结点存储在哈希表中。

大家看这幅图好看嘛,我们的哈希桶(开散列)也就是长这个样子的,屋檐呢就相当于顺序表,然后呢每个挂件呢也就相当于hashi相同的数据串在一起的样子。

2、哈希桶(开散列)的定义

template<class K, class V>
struct HashNode
{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}
};template<class K, class V>
class HashTable
{typedef HashNode<K, V> Node;
public:~HashTable(){}Node* Find(const K& key){}bool Erase(const K& key){}bool Insert(const pair<K, V>& kv){}private:vector<Node*> _tables; // 指针数组size_t _n = 0; // 存储有效数据个数
};

 我们之前的哈希表呢是直接将数据放在顺序表上的,而现在呢,我们是在顺序表上放hashi相同节点的一个节点的地址,然后将剩下相同节点一个一个的串联在下面,也就是链表一样;

相当于在顺序表里面放每个链表的头节点;

桶的个数是一定的,随着元素的不断插入,每个桶中元素的个数不断增多,极端情况下,可 能会导致一个桶中链表节点非常多,会影响的哈希表的性能,因此在一定条件下需要对哈希 表进行增容,那该条件怎么确认呢?开散列最好的情况是:每个哈希桶中刚好挂一个节点, 再继续插入元素时,每一次都会发生哈希冲突,因此,在元素个数刚好等于桶的个数时,可 以给哈希表增容。

3、哈希桶(开散列)的析构

这里的析构就不只是将顺序表给销毁了,我们要将链表的每一个节点进行delete

~HashTable()
{for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}
}

4、哈希桶(开散列)的插入

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first)){return false;}// 负载因因子==1时扩容if (_n == _tables.size()){size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newtables(newsize, nullptr);//for (Node*& cur : _tables)for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = kv.first % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

我们在每个hashi相同位置进行链表的链接,为了节省效率呢,我们就在链表的头部进行头插,然后顺序表里面就存放这个新进来元素的地址;

当我们的hashi不够用的时候呢,我们就将它进行扩容。扩容完以后呢,我们不能再像哈希表一样遍历原来表进行开空间释放空间了,这样非常麻烦。

我们通常是将他们的指针指向位置改变,定义一个next进行记录工作节点下一个节点的位置,以便于后续的更新,然后在新的顺序表里重新进行头插cur。

 5、哈希桶(开散列)的删除

bool Erase(const K& key)
{size_t hashi = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;
}

删除呢也就是我们链表的删除一样,我们找到hashi=key%size()的位置,然后在这个串上找key的位置,但是要定义一个prev来记录key的上一个节点的位置,便于链接;

 6、哈希桶(开散列)的查找

查找呢也就像链表一样,到key取完余数以后相同的链表上去找key即可;

非常简单,上菜

Node* Find(const K& key)
{if (_tables.size() == 0)return nullptr;size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

下期进行unordered的封装


总结

哈希表是在一个顺序表里面去找hashi(key%size())的位置,存在向后偏移,空就存储。

和哈希桶在顺序表里面存放单链表,把hashi相同的数据串联在一起;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/423534.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Unity踩坑】No cloud project ID was found by the Analytics SDK

在编译默认的URP 2D项目时&#xff0c;出现这样一个错误&#xff1a;No cloud project ID was found by the Analytics SDK. This means Analytics events will not be sent. Please make sure to link your cloud project in the Unity editor to fix this problem. 原因&…

JavaScript 基础 - 第16天_AJAX入门

文章目录 Day01_Ajax入门目录学习目标01.AJAX 概念和 axios 使用目标讲解小结 02.认识 URL目标讲解小结 03.URL 查询参数目标讲解小结 04.案例-查询-地区列表目标讲解小结 05.常用请求方法和数据提交目标讲解小结 06.axios 错误处理目标讲解小结 07.HTTP 协议-请求报文目标讲解…

【TabBar嵌套Navigation案例-cell重用 Objective-C语言】

一、我们来说这个cell重用(重复使用)的问题啊 1.我们这个比分直播推送页面, 这个里边呢,现在这个cell,涉及到两个样式,上面呢,是Default的,下面呢,是Value1的,然后,我们在这个里边啊,我们每一组就一个cell啊,然后呢,我把这个组,多给它复制几份儿,现在是三个组…

如何利用 CSS 渐变实现多样化背景效果

前言 总在平常看到像这样的图片 背景是如何实现的呢 背景效果的多样性和美观性直接影响用户体验。CSS 渐变为设计师提供了一种强大且灵活的方法来创建引人注目的背景。渐变是颜色之间平滑过渡的效果&#xff0c;通过调整渐变类型和设置&#xff0c;你可以轻松实现从简单到复杂…

灵雀云DevOps:加速应用交付,点燃业务创新引擎

导语 近日&#xff0c;国际知名咨询机构Gartner发布了2024年度DevOps平台魔力象限报告&#xff08;Gartner Magic Quadrant for DevOps Platforms&#xff09;&#xff0c;为信息化决策者在技术战略层面提供了选型和评估DevOps平台供应商的全面视角。报告中&#xff0c;中国云…

UEC++学习(十七)利用SceneCaptureComponent2d进行截图

最近有个需求是需要将场景中的actor进行截图&#xff0c;并且将截图保存成png&#xff0c;png中需要将场景背景忽略掉&#xff0c;只显示特定的actor。 这里是通过SceneCapture2d组件捕捉场景后&#xff0c;将背景的alpha通道设置为0&#xff0c;实现背景透明的功能。 &#x…

计算机网络:概述 - 计算机网络概述

目录 一. 互联网概述 1.1 网络 1.2 互联网 1.3 因特网 二. 互联网发展的三个阶段 三. 互联网的标准化工作 四. 互联网的组成 五. 计算机网络的类别 5.1 计算机网络的定义 5.2 计算机网络的不同类别 一. 互联网概述 起源于美国的互联网现如今已…

力扣213-打家劫舍 II(Java详细题解)

题目链接&#xff1a;213. 打家劫舍 II - 力扣&#xff08;LeetCode&#xff09; 前情提要&#xff1a; 本体是打家劫舍的一个变形题&#xff0c;希望大家能先做198. 打家劫舍 - 力扣&#xff08;LeetCode&#xff09;&#xff0c;并看一下我上题的讲解力扣198-打家劫舍&…

sheng的学习笔记-AI-规则学习(rule learning)

AI目录&#xff1a;sheng的学习笔记-AI目录-CSDN博客 什么是规则学习 机器学习中的“规则”(rule)通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成“若……&#xff0c;则……”形式的逻辑规则。​“规则学习”(rule learning)是从训练数据中学习出一组能…

Lua发邮件:实现自动化邮件发送教程指南!

Lua发邮件高级技巧有哪些&#xff1f;如何利用Lua发送电子邮件&#xff1f; 自动化邮件发送是一个非常实用的功能&#xff0c;广泛应用于各种场景&#xff0c;如通知、提醒、报告生成等。Lua作为一种轻量级脚本语言&#xff0c;因其简洁和高效而受到广泛欢迎。AokSend将详细介…

OpenCV class2-C#+winfrom显示控件使用窗口大小并内存管理

一.控件效果说明 二.代码声明&#xff08;已经循环读取10000次&#xff09; 全局 OpenCvSharp.Point point new OpenCvSharp.Point(0, 0); OpenCvSharp.Size size2; Mat src new Mat(); 初始化 size2 new OpenCvSharp.Size(pictureBox1.Size.Width, pictureBox1.Size.Hei…

PHP智驭未来悦享生活智慧小区物业管理小程序系统源码

智驭未来&#xff0c;悦享生活 —— 探索智慧小区物业管理小程序 一、引言&#xff1a;智慧生活的新篇章 在这个日新月异的时代&#xff0c;科技正以前所未有的速度改变着我们的生活。从智能家居到智慧城市&#xff0c;每一处都闪耀着智慧的光芒。而今天&#xff0c;我要带大家…

elementui Cascader 级联选择器的使用总结

实现效果 技术要点总结如下&#xff1a; 1、点击添加自动增加多行&#xff0c;实现自主选择增加多条节点数据 2、节点地址使用的是Cascader 级联选择器&#xff0c;需要动态生成&#xff0c;涉及到一个技术要点是&#xff1a;因v-modal只能获取value不能获取label&#xff0c;故…

汇编实现从1加到1000(《X86汇编语言 从实模式到保护模式(第2版》) 第135页第2题解答)

题目: 编写一段主引导扇区程序,计算从1加到1000的和,并在屏幕上显示结果 输出结果: 代码: jmp near start text db 123...1000 start:mov ax,0x07c0mov ds,ax ;数据段从主引导区开始mov ax,0xb800mov es,ax ;显存地址从B8000物理地址开始mov si,text ;si指向text的第…

极狐GitLab 新一代容器镜像仓库正式上线啦!

从极狐GitLab 17.3 开始&#xff0c;私有化部署实例也可以使用新一代容器镜像仓库啦&#xff01;新一代容器镜像仓库具有更高效的零宕机垃圾收集功能和其他优势。 从去年开始&#xff0c;极狐GitLab 就启动了重构容器镜像仓库的计划&#xff0c;用以构建具有更强功能的镜像仓库…

什么是测试驱动开发?

测试驱动开发&#xff08;Test-Driven Development&#xff0c;简称TDD&#xff09;是一种软件开发方法&#xff0c;它强调在编写功能代码之前&#xff0c;先编写测试代码。这种方法的核心思想是通过测试来推动整个开发过程的进行&#xff0c;确保代码的质量和可维护性。 一、基…

Hibernate QueryPlanCache 查询计划缓存引发的内存溢出

目录 1.排查方式2.结论3.解决办法 前言&#xff1a;在生产环境中有一个后端程序多次报oom然后导致程序中断。 1.排查方式 通过下载后端程序产生的oom文件&#xff0c;将oom文件导入MemoryAnalyzer程序分析程序堆内存使用情况。 1、将oom文件导入MemoryAnalyzer后可以看到概览信…

玩转扩展库,温湿度传感器篇!—合宙Air201资产定位模组LuatOS快速入门05

随着LuatOS快速入门系列教程的推出&#xff0c;小伙伴们学习热情高涨。 合宙Air201不仅支持三种定位方式&#xff0c;还具有丰富的扩展功能&#xff0c;通过外扩BTB链接方案&#xff0c;最多可支持21个IO接口&#xff1a;SPI、I2C、UART等多种接口全部支持。 本期&#xff0c…

uniapp小程序富文本编辑器 简单不需要下载插件 复制代码直接复用

题外话&#xff1a;富文本编辑器搞了好久&#xff0c;下载好几个插件&#xff0c;都没成功&#xff0c;最后复制这篇文章的代码&#xff0c;我又修改了一点东西&#xff0c;就成功了&#xff1a;&#xff08;买下面的css文件还花了2块钱&#xff0c;现在我免费给大家&#xff0…

STM32常用数据采集滤波算法

例如&#xff0c;STM32进行滤波处理时&#xff0c;主要目的是处理数据采集过程中可能产生的噪声和尖刺信号。这些噪声可能来自电源干扰、传感器自身的不稳定性或其他外部因素。 1.一阶互补滤波 方法&#xff1a;取a0~1,本次滤波结果&#xff08;1-a&#xff09;本次采样值a上…