安装Wordpress个人网站,上海住房和城乡建设局网站,国内网站建设需要多少钱,贸易公司网站建设#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负 目录
前言
1.概念
2.哈希冲突…
樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
每一个不曾起舞的日子都是对生命的辜负 目录
前言
1.概念
2.哈希冲突
3.解决哈希冲突
3.1闭散列
3.2开散列哈希桶
4.模拟实现
4.1闭散列的模拟实现
4.1.1哈希表结构设计 4.1.2插入
4.1.3删除
4.2哈希桶的模拟实现
4.2.1哈希桶结构设计
4.2.2插入
4.2.3查找
4.2.4删除 前言
本篇文章我们共同学习哈希结构哈希结构追求更极致的搜索效率。
之前学习的结构中搜索的效率取决于搜索过程中元素的比较次数因此顺序结构中查找的时间复杂度为O(N)平衡树中查找的时间复杂度为树的高度O(logN)。
那我们能不能构建一种数据结构让搜索效率达到O(1)呢。
如果构造一种存储结构该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时就能通过该函数很快找到该元素进而达到O(1)的查找效率。
接下来就让我们共同学习哈希结构。 欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码樊飞 (fanfei_c) - Gitee.com 1.概念
哈希结构的本质就是利用了『 映射关系』。
向该结构当中插入和搜索元素的过程如下
插入元素 根据待插入元素的关键码用此函数计算出该元素的存储位置并将元素存放到此位置。搜索元素 对元素的关键码进行同样的计算把求得的函数值当作元素的存储位置在结构中按此位置取元素进行比较若关键码相等则搜索成功。
该方式即为哈希散列方法 哈希方法中使用的转换函数称为哈希散列函数构造出来的结构称为哈希表散列表。
例如集合{1, 7, 6, 4, 5, 9}
哈希函数设置为hash( key ) key % capacity 其中capacity为存储元素底层空间的总大小。 用该方法进行存储在搜索时就只需通过哈希函数判断对应位置是否存放的是待查找元素而不必进行多次关键码的比较因此搜索的速度比较快。
2.哈希冲突
不同关键字通过相同哈希函数计算出相同的哈希地址这种现象称为哈希冲突或哈希碰撞。我们把关键码不同而具有相同哈希地址的数据元素称为“同义词”。
例如在上述例子中再将元素11插入当前的哈希表就会产生哈希冲突。 因为元素11通过该哈希函数得到的哈希地址与元素1相同都是下标为1的位置。
hash( 11 ) 11 % 10 1。
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则 哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单 常见哈希函数
一、直接定址法(常用)
取关键字的某个线性函数为散列地址HashKey A*Key B
优点简单、均匀
缺点需要事先知道关键字的分布情况
使用场景适合查找比较小且连续的情况
面试题字符串中第一个只出现一次字符
二、除留余数法(常用)
设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址
三、平方取中法(了解)
假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址
再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合不知道关键字的分布而位数又不是很大的情况
四、折叠法(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况
五、随机数法(了解)
选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数。通常应用于关键字长度不等时采用此法
六、数学分析法(了解)
设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如 假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是相同的那么我们可以选择后面的四位作为哈希地址。
如果这样的抽取方式还容易出现冲突还可以对抽取出来的数字进行反转如1234改成4321、右环位移如1234改成4123、左环位移如1234改成2341、前两数与后两数叠加如1234改成123446等操作。
数字分析法通常适合处理关键字位数比较大的情况或事先知道关键字的分布且关键字的若干位分布较均匀的情况。
注意无法避免哈希冲突哈希函数设计的越精妙产生哈希冲突的可能性越低。 3.解决哈希冲突
3.1闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢
1. 线性探测 如图现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 插入
通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素
删除
采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。 // 哈希表每个空间给个标记
// EMPTY此位置空 EXIST此位置已经有元素 DELETE元素已经删除
enum State{EMPTY, EXIST, DELETE};
我们将数据插入到有限的空间那么空间中的元素越多插入元素时产生冲突的概率也就越大冲突多次后插入哈希表的元素在查找时的效率必然也会降低。介于此哈希表当中引入了负载因子载荷因子。 负载因子 表中有效数据个数 / 空间的大小 虽然负载因子越小冲突概率就会变低查找效率会变高但是负载因子越小也就意味着空间的利用率越低此时大量的空间实际上都被浪费了。对于闭散列开放定址法来说负载因子是特别重要的因素一般控制在0.7~0.8以下超过0.8会导致在查表时CPU缓存不命中cache missing按照指数曲线上升。
因此一些采用开放定址法的hash库如JAVA的系统库限制了负载因子为0.75当超过该值时会对哈希表进行增容。
优点实现非常简单。缺点一旦发生冲突所有的冲突连在一起容易产生数据『 堆积』即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要多次比较踩踏效应导致搜索效率降低。
2.二次探测
线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为 Hi(H0 i^2) % m (i1,2,3,...) H0通过哈希函数对元素的关键码进行计算得到的位置。Hi冲突元素通过二次探测后得到的存放位置。m表的大小。
如图如果要插入44产生冲突使用解决后的情况为 研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容。 采用二次探测为产生哈希冲突的数据寻找下一个位置相比线性探测而言采用二次探测的哈希表中元素的分布会相对稀疏一些不容易导致数据堆积但也因此闭散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷。 3.2开散列哈希桶
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。 这样看来对于开散列来说不同哈希值的元素之间不会互相干扰。
并且哈希桶的负载因子可以更大空间利用率高。
极端情况所有元素的哈希值均相同最终都放到了同一个哈希桶中此时该哈希表增删查改的效率就退化成了O(N)对于这种情况有这样一种解决方案『 桶中种树』。 为了避免出现这种极端情况当桶当中的元素个数超过一定长度有些地方就会选择将该桶中的单链表结构换成红黑树结构。
但有些地方也会选择不做此处理因为随着哈希表中数据的增多该哈希表的负载因子也会逐渐增大最终会触发哈希表的增容条件此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表此时同一个桶当中冲突的数据个数也会减少因此不做处理问题也不大。 4.模拟实现
4.1闭散列的模拟实现
4.1.1哈希表结构设计
前面在讲解线性探测的部分时提到过我们不能直接删除哈希表中的元素而是采用伪标记的删除法这里我们展开讲解一下
闭散列又称开放定址法当两个元素的哈希值冲突时我们采用线性探测的方式来解决冲突。
那么查找某个元素时如何判断可以找到还是找不到
根据线性探测的思想明显是当遇到空时就证明找不到了。
可当我们要删除某个元素时如果直接删除他所在的位置变成空值那将来在查找『 因为它而产生的哈希冲突后移的元素』时可能会受到该位置为空的影响提前结束查找操作。
所以这里不能简单的直接删除并且也不能用某个具体的值代表空值这样会导致哈希表存储不了这个值所以最有效的方式就是给每个元素设置一个状态。 EMPTY无数据的空位置。EXIST已存储数据。DELETE原本有数据但现在被删除了。 //枚举标识每个位置的状态
enum State
{EMPTY,EXIST,DELETE
};//哈希表每个位置存储的结构
templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY; //状态
}; 并且为了在插入元素时好计算当前哈希表的负载因子我们还应该时刻存储整个哈希表中的有效元素个数当负载因子过大时就应该进行哈希表的增容。
//哈希表
templateclass K, class V
class HashTable
{
public://...
private:vectorHashDataK, V _table; //哈希表size_t _n 0; //哈希表中的有效元素个数
}; 4.1.2插入
向哈希表中插入数据的步骤如下
查看哈希表中是否存在该键值的键值对若已存在则插入失败。判断是否需要调整哈希表的大小若哈希表的大小为0或负载因子过大都需要对哈希表的大小进行调整。将键值对插入哈希表。哈希表中的有效元素个数加一。
其中哈希表的调整方式如下
若哈希表的大小为0则将哈希表的初始大小设置为10在构造时完成。若哈希表的负载因子大于0.7则先创建一个新的哈希表该哈希表的大小为原哈希表的两倍之后遍历原哈希表将原哈希表中的数据插入到新哈希表最后将原哈希表与新哈希表交换即可。 注意 在将原哈希表的数据插入到新哈希表的过程中需要重新计算哈希值不能只是简单的将原哈希表中的数据对应的挪到新哈希表中而是需要根据新哈希表的大小重新计算每个数据在新哈希表中的位置然后再进行插入。 将键值对插入哈希表的具体步骤如下
通过哈希函数计算出对应的哈希地址。若产生哈希冲突则从哈希地址处开始采用线性探测向后寻找一个状态为EMPTY或DELETE的位置。将键值对插入到该位置并将该位置的状态设置为EXIST。 注意 产生哈希冲突向后进行探测时一定会找到一个合适位置进行插入因为哈希表的负载因子是控制在0.7以下的也就是说哈希表永远都不会被装满。 //插入函数
bool Insert(const pairK, V kv)
{//1、查看哈希表中是否存在该键值的键值对HashDataK, V* ret Find(kv.first);if (ret) //哈希表中已经存在该键值的键值对不允许数据冗余{return false; //插入失败}if _n * 10 / _table.size() 7) //负载因子大于0.7需要增容{//增容//a、创建一个新的哈希表新哈希表的大小设置为原哈希表的2倍HashTableK, V newHT;newHT._table.resize(2 * _table.size());//b、将原哈希表当中的数据插入到新哈希表for (auto e : _table){if (e._state EXIST){newHT.Insert(e._kv);}}//c、vector的交换函数swap交换这两个哈希表_table.swap(newHT._table);}//3、将键值对插入哈希表//a、通过哈希函数计算哈希地址size_t hashi kv.first%_table.size(); //除数不能是capacity//b、找到一个状态为EMPTY或DELETE的位置while (_table[hashi]._state EXIST){hashi;hashi % _table.size(); //防止下标超出哈希表范围}//c、将数据插入该位置并将该位置的状态设置为EXIST_table[hashi]._kv kv;_table[hashi]._state EXIST;//4、哈希表中的有效元素个数加一_n;return true;
} 4.1.3删除
删除哈希表中的元素非常简单我们只需要进行伪标记的删除法即可也就是将待删除元素所在位置的状态设置为DELETE。
在哈希表中删除数据的步骤如下
查看哈希表中是否存在该键值的键值对若不存在则删除失败。若存在则将该键值对所在位置的状态改为DELETE即可。哈希表中的有效元素个数减一。
注意 虽然删除元素时没有将该位置的数据清0只是将该元素所在状态设为了DELETE但是并不会造成空间的浪费因为我们在插入数据时是可以将数据覆盖到状态为DELETE的位置的。
//删除函数
bool Erase(const K key)
{//1、查看哈希表中是否存在该键值的键值对HashDataK, V* ret Find(key);if (ret){//2、若存在则将该键值对所在位置的状态改为DELETE即可ret-_state DELETE;//3、哈希表中的有效元素个数减一_n--;return true;}return false;
} 4.2哈希桶的模拟实现
4.2.1哈希桶结构设计
在开散列的哈希表中哈希表的每个位置存储的实际上是某个单链表的头结点即每个哈希桶中存储的数据实际上是一个结点类型该结点类型除了存储所给数据之外还需要存储一个结点指针用于指向下一个结点。
//每个哈希桶中存储数据的结构
templateclass K, class V
struct HashNode
{pairK, V _kv;HashNodeK, V* _next;//构造函数HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}
}; 注意哈希桶的结构设计中不需要状态字因为不同哈希值的元素不会互相影响。 哈希表的开散列实现方式在插入数据时也需要根据负载因子判断是否需要增容所以我们也应该时刻存储整个哈希表中的有效元素个数当负载因子过大时就应该进行哈希表的增容。
//哈希表
templateclass K, class V
class HashTable
{
public://...
private:vectorNode* _table; //哈希表size_t _n 0; //哈希表中的有效元素个数
};
4.2.2插入
向哈希表中插入数据的步骤如下
查看哈希表中是否存在该键值的键值对若已存在则插入失败。判断是否需要调整哈希表的大小若哈希表的大小为0或负载因子过大都需要对哈希表的大小进行调整。将键值对插入哈希表。哈希表中的有效元素个数加一。
其中哈希表的调整方式如下
若哈希表的大小为0则将哈希表的初始大小设置为10构造时完成。若哈希表的负载因子已经等于1了则先创建一个新的哈希表该哈希表的大小为原哈希表的两倍之后遍历原哈希表将原哈希表中的数据插入到新哈希表最后将原哈希表与新哈希表交换即可。 注意我们只需要遍历原哈希表的每个哈希桶通过哈希函数将每个旧哈希桶中的结点重新挂到新哈希表即可不用进行结点的创建与释放。 //插入函数
bool Insert(const pairK, V kv)
{//1、查看哈希表中是否存在该键值的键值对if (Find(kv.first)) //哈希表中已经存在该键值的键值对不允许数据冗余{return false; //插入失败}//2、判断是否需要调整哈希表的大小if (_n _table.size()) //负载因子超过1{//增容//a、创建一个新的哈希表新哈希表的大小设置为原哈希表的2倍vectorNode* newTables(_tables.size()*2, nullptr);//b、将原哈希表当中的结点插入到新哈希表for (size_t i 0; i _table.size(); i){//取出旧表中的节点重新计算挂到新表桶中Node* cur _table[i];while (cur){Node* next cur-_next;size_t hashi cur-_kv.first % newTables.size(); //将该结点头插到新哈希表中编号为index的哈希桶中cur-_next newTables[hashi ];newTables[hashi] cur;cur next;}_table[i] nullptr; //该桶取完后将该桶置空}//c、交换这两个哈希表_table.swap(newTables);}//3、将键值对插入哈希表size_t hashi kv.first % _table.size(); //通过哈希函数计算出对应的哈希桶编号index除数不能是capacityNode* newnode new Node(kv); //根据所给数据创建一个待插入结点//将该结点头插到新哈希表中编号为index的哈希桶中newnode-_next _table[hashi];_table[hashi] newnode;//4、哈希表中的有效元素个数加一_n;return true;
}
4.2.3查找
在哈希表中查找数据的步骤如下
先判断哈希表的大小是否为0若为0则查找失败。通过哈希函数计算出对应的哈希地址。通过哈希地址找到对应的哈希桶中的单链表遍历单链表进行查找即可。
//查找函数
HashNodeK, V* Find(const K key)
{if (_table.size() 0) //哈希表大小为0查找失败{return nullptr;}size_t hashi key % _table.size();//遍历编号为index的哈希桶HashNodeK, V* cur _table[hashi];while (cur) //直到将该桶遍历完为止{if (cur-_kv.first key) //key值匹配则查找成功{return cur;}cur cur-_next;}return nullptr; //直到该桶全部遍历完毕还没有找到目标元素查找失败
}
4.2.4删除
在哈希表中删除数据的步骤如下
通过哈希函数计算出对应的哈希桶编号。遍历对应的哈希桶寻找待删除结点。若找到了待删除结点则将该结点从单链表中移除并释放。删除结点后将哈希表中的有效元素个数减一。
//删除函数
bool Erase(const K key)
{//1、通过哈希函数计算出对应的哈希桶编号hashi除数不能是capacitysize_t hashi key % _table.size();//2、在编号为index的哈希桶中寻找待删除结点Node* prev nullptr;Node* cur _table[hashi];while (cur) //直到将该桶遍历完为止{if (cur-_kv.first key) //key值匹配则查找成功{//3、若找到了待删除结点则删除该结点if (prev nullptr) //待删除结点是哈希桶中的第一个结点{_table[hashi] cur-_next; //将第一个结点从该哈希桶中移除}else //待删除结点不是哈希桶的第一个结点{prev-_next cur-_next; //将该结点从哈希桶中移除}delete cur; //释放该结点//4、删除结点后将哈希表中的有效元素个数减一_n--;return true; //删除成功}prev cur;cur cur-_next;}return false; //直到该桶全部遍历完毕还没有找到待删除元素删除失败
} 思考 除留余数法是映射哈希值的有效方法但是这里我们考虑的都是整型情况下那如果是字符串呢如果key值是字符串字符串可没办法取余数而我们最终是一定要实现泛型编程的我们怎样才能构建出一个通用的映射关系呢 如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
