潍坊网站建设8年,网站建设三种方法,手机网站布局教程,wordpress添加小工具栏 作者#xff1a;დ旧言~ 座右铭#xff1a;松树千年终是朽#xff0c;槿花一日自为荣。 目标#xff1a;手撕哈希表的闭散列和开散列 毒鸡汤#xff1a;谁不是一边受伤#xff0c;一边学会坚强。 专栏选自#xff1a;C嘎嘎进阶 望小伙伴们… 作者დ旧言~ 座右铭松树千年终是朽槿花一日自为荣。 目标手撕哈希表的闭散列和开散列 毒鸡汤谁不是一边受伤一边学会坚强。 专栏选自C嘎嘎进阶 望小伙伴们点赞收藏✨加关注哟 前言
谈到哈希表大家都做过这样的题目统计字符串的字母个数像这样的题目可以创建一个数组每个字母采用 a[ch] 计入数组中这样的数组我们称之为哈希表这种哈希表也是最简单的如果说为了方便直接调用哈希表那这个哈希表该如何模拟呢这个问题也是今天我们所探讨的手撕哈希表。
⭐主体
学习手撕哈希表的闭散列和开散列咱们按照下面的图解 哈希概念
知识回顾
在顺序结构以及平衡树中由于元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较比如顺序表中需要从表头开始依次往后比对寻找查找时间复杂度为 O(N)平衡树中需要从第一层开始逐层往下比对寻找查找时间复杂度为 O(logN)即搜索的效率取决于搜索过程中元素的比较次数。
分析探讨
如果构造一种存储结构可以通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一对一的映射关系那么在查找时通过该函数就可以很快找到该元素当向该结构中
插入元素时根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素时对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功。
总结归纳
该方法即为 哈希 (散列) 方法哈希方法中使用的转换函数称为哈希 (散列) 函数构造出来的结构称为哈希表 (Hash Table) (或者称散列表)。
注意事项
我们上面提到的不管是顺序搜索、平衡树搜索还是哈希搜索其 key 值都是唯一的也就是说搜索树中不允许出现相同 key 值的节点哈希表中也不允许出现相同 key 值的元素我们下文所进行的所有操作也都是在这前提之上进行的。
哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。 哈希冲突有两种常见的解决办法 闭散列 (开放定址法)当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去开散列 (链地址法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码 (哈希冲突) 归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中也就是说当发生哈希冲突时把 key 直接链接在该位置的下面。 哈希函数
哈希函数有如下设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果哈希表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址要尽量能均匀分布在整个空间中哈希函数应该比较简单。 直接定址法
什么是直接定址法
直接定址就是根据 key 值直接得到存储位置最多再进行一个简单的常数之间的转换。
分析
直接定址法的优点是简单且不会引起哈希冲突 由于直接定址法的 key 值经过哈希函数转换后得到的值一定是唯一的所以不存在哈希冲突。直接定址法适用于数据范围集中的情况这样 key 值映射到哈希表后哈希表的空间利用率高浪费的空间较少
图解 除留余数法
什么是除留余数法
简单来说就是用 key 值除以哈希表的大小得到的余数作为哈希映射的地址将 key 保存到该地址中
分析
除留余数的优点是可以处理数据范围分散的数据缺点是会引发哈希冲突
图解 方法总结
直接定制法–(常用)
取关键字的某个线性函数为散列地址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种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。
闭散列哈希
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去那如何寻找下一个空位置呢有两种方法 – 线性探测法和二次探测法。 线性探测法
什么是线性探测
线性探测法是指从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止
图解 哈希表的基本框架
框架搭建步骤
在哈希表中我们使用了 vector 来存储数据并增加了一个变量 n 来记录表中有效数据的个数同时哈希表的每个下标位置存储的数据都是一个 KV 模型的键值对当key映射的下标位置被占用时key会向后寻找下一个空位置进行插入但如果key走到数组尾都还没找到空位置那么key就会从数组起始位置重新往后寻找在哈希表的每个位置的数据中还增加了一个 state 变量来记录该位置的状态 (存在、删除、空)
代码如下
//标识每个存储位置的状态--空、存在与删除
enum State {EMPTY,EXIST,DELETE
};//哈希表每个下标位置存储的数据的结构
templateclass K, class V
struct HashData {pairK, V _kv;State _state EMPTY; //默认为空
};templateclass K, class V
class HashTable {typedef HashDataK, V Data;
private:vectorData _tables;size_t _n; //记录表中有效数据的个数
};哈希表的插入删除与查找
插入
通过哈希函数得到余数即数组下标如果该下标的状态为删除或为空则插入如果为存在则向后寻找下一个状态为删除/空的位置进行插入。
查找
通过哈希函数得到余数即数组下标取出小标位置的key与目标key进行比较相等就返回该位置的地址不相等就继续往后查找如果查找到状态为空的下标位置就返回 nullptr。
删除
复用查找函数查找到就通过查找函数的返回值将小标位置数据的状态置为 删除找不到就返回 false。
代码实现
#pragma once#include vector
#include utility
using std::pair;
using std::vector;//标识每个存储位置的状态--空、存在与删除
enum State {EMPTY,EXIST,DELETE
};//哈希表每个下标位置存储的数据的结构
templateclass K, class V
struct HashData {pairK, V _kv;State _state EMPTY; //默认为空
};//哈希表
templateclass K, class V
class HashTable {typedef HashDataK, V Data;public:HashTable(): _n(0){//将哈希表的大小默认给为10_tables.resize(10);}bool insert(const pairK, V kv) {if (find(kv.first))return false;//除留余数法 线性探测法//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置如果该位置被占用往后放size_t hashi kv.first % _tables.size();//不能放在EXIST的位置DELETE和EMPTY都能放while (_tables[hashi]._state EXIST) {hashi;if (hashi _tables.size()) hashi 0; //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}//将find的返回值定义为Data的地址可以方便我们进行删除以及修改VData* find(const K key) {Hash hash; //仿函数对象size_t hashi hash(key) % _tables.size();//记录hashi的起始位置避免哈希表中元素全为EXIST和DELETE时导致死循环size_t starti hashi;//最多找到空while (_tables[hashi]._state ! EMPTY) {//key相等并且state为EXIST才表示找到if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST)return _tables[hashi];hashi;//如果找到尾还没找到就从0重新找if (hashi _tables.size()) hashi 0;//如果找一圈还没找到就跳出循环if (hashi starti) break;}return nullptr;}bool erase(const K key) {//找不到就不删找到就把状态置为DELETE即可Data* ret find(key);if (ret) {ret-_state DELETE;return true;}return false;}private:vectorData _tables;size_t _n; //记录表中有效数据的个数
};哈希表的扩容
哈希表的扩容和普通顺序表容器的扩容不同它不是容器满了才扩容而是会有一个负载因子也叫载荷因子当载荷因子超过一定大小时就立即扩容。
代码如下
bool insert(const pairK, V kv) {if (find(kv.first))return false;//如果大于标定的载荷因子就扩容这里我们将载荷因子标定为0.7//扩容现代写法--复用insert接口if ((1.0 * _n / _tables.size()) 0.7) {HashTableK, V newHT;newHT._tables.resize(_tables.size() * 2);for (auto e : _tables)newHT.insert(e._kv);_tables.swap(newHT._tables);}//除留余数法 线性探测法//将数据映射到 数据的key值除以哈希表的大小得到的余数 的位置如果该位置被占用往后放size_t hashi kv.first % _tables.size();//不能放在EXIST的位置DELETE和EMPTY都能放while (_tables[hashi]._state EXIST) {hashi;if (hashi _tables.size()) hashi 0; //如果探测到末尾则从头开始重新探测}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;
}哈希表的仿函数
模板参数是一个仿函数仿函数分为设计者提供的默认仿函数和用户提供的仿函数系统默认的仿函数可以将一些常见的 key 的类型全部转化为整形比如字符串、指针、整数而用户提供的仿函数则可以根据用户自己的 key 类型将其转化为整形比如 People 类 (身份证号)、Date 类 等等
代码如下
template
struct HashFuncstring {size_t operator()(const string key) {size_t sum 0;for (auto ch : key)sum ch;return sum;}
};细节分析
有了仿函数解决了传字符串的问题
闭散列整体代码实现
#include iostream
#include string
#include vector
#include map
#include set
#include unordered_set
using namespace std;// 哈希表的仿函数 通过上层容器提供的仿函数获取到元素的键值
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 类模板特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash e;hash * 131;}return hash;}
};// 闭散列哈希表
namespace open_address
{enum State{EMPTY, // 空EXIST, // 存在DELETE // 删除};// 哈希表每个下标的位置存储的数据的结构templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY; // 默认为空};// 哈希表templateclass K, class V, class Hash HashFuncKclass HashTable{public:// 默认开辟 10 个空间HashTable(size_t size 10){_tables.resize(size);}// 查找HashDataK, V* Find(const K key){// 仿函数对象Hash hs;// 线性探测size_t hashi hs(key) % _tables.size();while (_tables[hashi]._state ! EMPTY){// key相等并且state为EXIST存在才能表示找到if (key _tables[hashi]._kv.first _tables[hashi]._state EXIST){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}// 插入bool Insert(const pairK, V kv){// 为空就返回if (Find(kv.first))return false;// 扩容if (_n * 10 / _tables.size() 7){// 扩容HashTableK, V, Hash newHT(_tables.size() * 2);// 遍历旧表插入到新表for (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}// 交换_tables.swap(newHT._tables);}// 仿函数对象Hash hs;// 线性探测找需要插入的地方size_t hashi hs(kv.first) % _tables.size();while (_tables[hashi]._state EXIST){hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}// 删除bool Erase(const K key){// 查找HashDataK, V* ret Find(key);if (ret){_n--; // 元素减一ret-_state DELETE;// 状态改为删除return true;}else{return false;}}private:vectorHashDataK, V _tables;size_t _n 0; // 实际存储的数据个数};// 测试一void TestHT1(){int a[] { 1,4,24,34,7,44,17,37 };// 创建哈希表HashTableint, int ht;for (auto e : a){ht.Insert(make_pair(e, e)); // 插入元素}for (auto e : a){auto ret ht.Find(e);if (ret){cout ret-_kv.first :E endl;}else{cout ret-_kv.first :D endl;}}cout endl;ht.Erase(34);ht.Erase(4);for (auto e : a){auto ret ht.Find(e);if (ret){cout ret-_kv.first :E endl;}else{cout e :D endl;}}cout endl;}// 测试二struct Date{int _year;int _month;int _day;};struct HashFuncDate{// 2024/6/3// 2024/3/6size_t operator()(const Date d){size_t hash 0;hash d._year;hash * 131;hash d._month;hash * 131;hash d._day;hash * 131;return hash;}};void TestHT2(){HashTablestring, string dict;dict.Insert(make_pair(sort, 排序));dict.Insert(make_pair(string, 字符串));HashTableDate, string, HashFuncDate DateHash;}}
开散列哈希
什么是开散列哈希
开散列法又叫 链地址法 (开链法)首先对关键码集合用散列函数计算散列地址即 key 映射的下标位置具有相同地址的关键码 (哈希冲突) 归于同一子集合每一个子集合称为一个桶 (哈希桶)各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中也就是说当发生哈希冲突时把 key 作为一个节点直接链接到下标位置的哈希桶中。
图解 开散列的节点结构
由于开散列的不同冲突之间不会互相影响所以开散列不再需要 state 变量来记录每个下表位置的状态同时因为开散列每个下标位置链接的都是一个哈希桶所以 vector 中的每个元素都是一个节点的指针指向单链表的第一个元素所以 _tables 是一个指针数组最后为了是不同类型的 key 都能够计算出映射的下标位置所以我们这里也需要传递仿函数。
代码如下
//开散列
namespace hash_bucket {//哈希表的节点结构--单链表templateclass K, class Vstruct HashNode {pairK, V _kv;HashNodeK, V* next;HashNode(const pairK, V kv): _kv(kv), next(nullptr){}};//哈希表的仿函数templateclass Kstruct HashFunc {size_t operator()(const K key) {return key;}};//类模板特化templatestruct HashFuncstring {size_t operator()(const string key) {//BKDR字符串哈希算法size_t sum 0;for (auto ch : key)sum sum * 131 ch;return sum;}};//哈希表templateclass K, class V, class Hash HashFuncKclass HashTable {typedef HashNodeK, V Node;private:vectorNode* _tables; //指针数组size_t _n; //表中有效数据的个数};
}开散列的插入删除与查找
开散列的插入
开散列插入的前部分和闭散列一样根据 key 与哈希表大小得到映射的下标位置与闭散列不同的是由于哈希表中每个下标位置都是一个哈希桶即一个单链表那么对于发现哈希冲突的元素我们只需要将其链接到哈希桶中即可这里显然是选择将冲突元素进行头插因为尾插还需要找尾会导致效率降低
// 插入函数
bool Insert(const pairK, V kv)
{// 查看元素是否存在if (Find(kv.first))return false;// 仿函数对象Hash hs;// 负载因子到1就扩容if (_n _tables.size()){// 扩容vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){// 取出旧表中节点重新计算挂到新表桶中Node* cur _tables[i];while (cur){Node* next cur-_next;// 头插到新表size_t hashi hs(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}// 调用仿函数的匿名对象来将key转换为整数size_t hashi hs(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;
}
开散列的查找
开散列的查找也很简单根据余数找到下标由于下标位置存储的是链表首元素地址所以我们只需要取出首元素地址然后顺序遍历单链表即可
// 查找
Node* Find(const K key)
{// 仿函数对象Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;
}
开散列的删除
和闭散列不同的是开散列的删除不能直接通过查找函数的返回值来进行删除因为单链表在删除节点时还需要改变父节点的指向让其指向目标节点的下一个节点所以我们需要通过遍历单链表来进行删除
// 删除
bool Erase(const K key)
{// 仿函数对象Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){// 删除还要分是否为头节点if (cur-_kv.first key){// 删除if (prev){prev-_next cur-_next;}else{_tables[hashi] cur-_next;}delete cur;--_n;return true;}// 下一个结点prev cur;cur cur-_next;}return false;
}
开散列整体代码实现
#include iostream
#include string
#include vector
#include map
#include set
#include unordered_set
using namespace std;// 哈希表的仿函数 通过上层容器提供的仿函数获取到元素的键值
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 类模板特化
template
struct HashFuncstring
{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash e;hash * 131;}return hash;}
};// 开散列哈希表
namespace hash_bucket
{// 哈希表的节点结构 -- 单链表templateclass K, class Vstruct HashNode{HashNodeK, V* _next;pairK, V _kv;// 初始化列表HashNode(const pairK, V kv):_next(nullptr), _kv(kv){}};// 哈希表templateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:// 构造函数HashTable(){_tables.resize(10, nullptr); // 开空间_n 0;}// 析构函数~HashTable(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}// 插入函数bool Insert(const pairK, V kv){// 查看元素是否存在if (Find(kv.first))return false;// 仿函数对象Hash hs;// 负载因子到1就扩容if (_n _tables.size()){// 扩容vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){// 取出旧表中节点重新计算挂到新表桶中Node* cur _tables[i];while (cur){Node* next cur-_next;// 头插到新表size_t hashi hs(cur-_kv.first) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}// 调用仿函数的匿名对象来将key转换为整数size_t hashi hs(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}// 查找Node* Find(const K key){// 仿函数对象Hash hs;size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;}// 删除bool Erase(const K key){// 仿函数对象Hash hs;size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur){// 删除还要分是否为头节点if (cur-_kv.first key){// 删除if (prev){prev-_next cur-_next;}else{_tables[hashi] cur-_next;}delete cur;--_n;return true;}// 下一个结点prev cur;cur cur-_next;}return false;}// 测试void Some(){size_t bucketSize 0;size_t maxBucketLen 0;size_t sum 0;double averageBucketLen 0;for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];if (cur){bucketSize;}size_t bucketLen 0;while (cur){bucketLen;cur cur-_next;}sum bucketLen;if (bucketLen maxBucketLen){maxBucketLen bucketLen;}}averageBucketLen (double)sum / (double)bucketSize;printf(load factor:%lf\n, (double)_n / _tables.size());printf(all bucketSize:%d\n, _tables.size());printf(bucketSize:%d\n, bucketSize);printf(maxBucketLen:%d\n, maxBucketLen);printf(averageBucketLen:%lf\n\n, averageBucketLen);}private:vectorNode* _tables; // 指针数组size_t _n; // 元素个数};// 测试一void TestHT1(){HashTableint, int ht;int a[] { 1,4,24,34,7,44,17,37 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(5, 5));ht.Insert(make_pair(15, 15));ht.Insert(make_pair(25, 25));ht.Erase(5);ht.Erase(15);ht.Erase(25);ht.Erase(35);for (auto e : a){auto ret ht.Find(e);if (ret){cout ret-_kv.first :E endl;}else{cout ret-_kv.first :D endl;}}cout endl;HashTablestring, string dict;dict.Insert(make_pair(sort, 排序));dict.Insert(make_pair(string, 字符串));}// 测试二void TestHT2(){const size_t N 30000;unordered_setint us;setint s;HashTableint, int ht;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){//v.push_back(rand()); // N比较大时重复值比较多v.push_back(rand() i); // 重复值相对少//v.push_back(i); // 没有重复有序}size_t begin1 clock();for (auto e : v){s.insert(e);}size_t end1 clock();cout set insert: end1 - begin1 endl;size_t begin2 clock();for (auto e : v){us.insert(e);}size_t end2 clock();cout unordered_set insert: end2 - begin2 endl;size_t begin10 clock();for (auto e : v){ht.Insert(make_pair(e, e));}size_t end10 clock();cout HashTbale insert: end10 - begin10 endl endl;size_t begin3 clock();for (auto e : v){s.find(e);}size_t end3 clock();cout set find: end3 - begin3 endl;size_t begin4 clock();for (auto e : v){us.find(e);}size_t end4 clock();cout unordered_set find: end4 - begin4 endl;size_t begin11 clock();for (auto e : v){ht.Find(e);}size_t end11 clock();cout HashTable find: end11 - begin11 endl endl;cout 插入数据个数 us.size() endl endl;ht.Some();size_t begin5 clock();for (auto e : v){s.erase(e);}size_t end5 clock();cout set erase: end5 - begin5 endl;size_t begin6 clock();for (auto e : v){us.erase(e);}size_t end6 clock();cout unordered_set erase: end6 - begin6 endl;size_t begin12 clock();for (auto e : v){ht.Erase(e);}size_t end12 clock();cout HashTable Erase: end12 - begin12 endl endl;}
}结束语 今天内容就到这里啦时间过得很快大家沉下心来好好学习会有一定的收获的大家多多坚持嘻嘻成功路上注定孤独因为坚持的人不多。那请大家举起自己的小手给博主一键三连有你们的支持是我最大的动力回见。
