烟台网络公司网站建设,长沙专业建设网站企业,杭州互助盘网站开发,铺面怎样做放上网站文章目录#x1f4d6; 前言1. STL中哈希表的两个应用⚡1.1 #x1f31f;unordered_set1.2 #x1f31f;unordered_map2. 常见查找的性能对比#x1f4a5;3. 哈希表模拟实现#x1f3c1;3.1 哈希的概念#xff1a;3.2 哈希函数#xff1a;3.3 哈希冲突#xff1a;3.4 闭…
文章目录 前言1. STL中哈希表的两个应用⚡1.1 unordered_set1.2 unordered_map2. 常见查找的性能对比3. 哈希表模拟实现3.1 哈希的概念3.2 哈希函数3.3 哈希冲突3.4 闭散列 — 开放地址法3.5 开散列 — 哈希桶、拉链法开链法前言
哈希表在日常生活中我们一定略有耳闻作为STL中我们所必须学习和了解的容器首先哈希查找的时间复杂度为〇1是一种一一映射的存储方式其次它在日常生活中的应用范围也是很广的例如位图海量数据筛选中用到的布隆过滤器等等……
下面我们就来先学习一下STL中的应用哈希表的两个容器再了解一下底层结构 两个关联式容器unordered_map和unordered_setunordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构最后再来模拟实现一下…… 1. STL中哈希表的两个应用⚡
在STL中对应的容器分别是unordered_map和unordered_set这两个关联式容器。 只要我们会用set那么我们就会用unordered_set但不是任何场景下unordered_map/set都能将map/set替换掉。 哈希是一种映射有的地方也叫散列存储关键字跟存储位置建立关联关系
1.1 unordered_set
unordered_set 文档介绍
我们简单的试用一下unordered_set如下代码
void test_set()
{unordered_setint s;//setint s;s.insert(1);s.insert(3);s.insert(4);s.insert(2);s.insert(10);//unordered_setint::iterator it s.begin();auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;
}结果是无序的
由上图和查阅资料得知
map和set 去重 排序unordered_map和unordered_set 只有去重
其余函数接口和之前所学的容器使用起来大致相同不再一一赘述。
unordered_map和unordered_set都是单向迭代器 值得注意的是unordered_map和unordered_set的迭代器都是单项迭代器而我们之前学的map和set则是单项迭代器。 unordered_set和set的性能对比
void test_op()
{
//对比插入的效率int n 1000000;vectorint v;v.reserve(n);srand(time(0));for (int i 0; i n; i){//v.push_back(i);//v.push_back(rand()i); //重复少v.push_back(rand()); //重复多}size_t begin1 clock();setint s;for (auto e : v){s.insert(e);}size_t end1 clock();size_t begin2 clock();unordered_setint us;for (auto e : v){us.insert(e);}size_t end2 clock();cout s.size() endl;cout set insert: end1 - begin1 endl;cout unordered_set insert: end2 - begin2 endl;//扩容重新哈希是有消耗的 -- 数据量多的时候没有那么多重复的数据的时候也不一定//对比查找的效率size_t begin3 clock();for (auto e : v){s.find(e);}size_t end3 clock();size_t begin4 clock();for (auto e : v){us.find(e);}size_t end4 clock();cout set find: end3 - begin3 endl;cout unordered_set find: end4 - begin4 endl;//对比删除的效率size_t begin5 clock();for (auto e : v){s.erase(e);}size_t end5 clock();size_t begin6 clock();for (auto e : v){us.erase(e);}size_t end6 clock();cout set erase: end5 - begin5 endl;cout unordered_set erase: end6 - begin6 endl;
}因为生成随机数的个数有个最大值不能生成无限多个随机数这就导致了有很多数字的重复。
当重复的数字很多时 当没有重复的数字时 总结
总的来说unordered_map和unordered_set要比map和set的性能要好的但是也并不是一定的当数据量很大的时候扩容重新哈希是有消耗的。
1.2 unordered_map
unordered_map文档介绍 void test_map()
{unordered_mapstring, string dict;dict.insert(make_pair(sort, 排序));dict.insert(make_pair(left, 左边));dict.insert(make_pair(left, 剩余));dict[string];dict[left] 剩余;dict[string] 字符串;unordered_mapstring, string::iterator it dict.begin();while (it ! dict.end()){cout (*it).first (*it).second endl;it;}
}2. 常见查找的性能对比 暴力查找 时间复杂度〇(N) 二分查找 时间复杂度〇(logN) 缺点 — 有序、数组结构 搜索二叉树 时间复杂度〇(N)缺点 — 极端场景退化成单支 平衡二叉搜索树 时间复杂度〇(logN) AVLTree: 左右子树高度差不超过1 红黑树最长路径不超过最短路径的2倍 哈希 B树系列 多叉平衡搜索树 — 数据库原理 跳表
备注 红黑树高度略高一些但是跟AVL树是同一数量级对于现代计算机没有差别但是红黑树相对而言近似平衡旋转少。 3. 哈希表模拟实现
3.1 哈希的概念
普通查找
我们之前查找一个数据时一般都是通过比较查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为〇(N)平衡树中为树的高度即〇(logN)。
理想的搜索方法
可以不经过任何比较一次直接从表中得到要搜索的元素。如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。该中存储结构可以实现 插入元素时 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。 查找元素时 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置 取元素比较若关键码相等则搜索成功。
哈希表就由此而来… 3.2 哈希函数
我们如何一一将键值转换为对应的关键码值并映射到对应序号的存储位置呢
直接映射法
直接建立映射关系问题: 1、数据范围分布很广、不集中可能存在空间浪费严重的问题 2、key的数据不是整数是字符串怎么办是自定义类型对象怎么办
此时我们就需要一个函数对特殊非整数类型的数据进行处理使其返回一个特定的整数这个函数我们叫做 —— 哈希函数。
常见的哈希函数
直接定址法常用 取关键字的某个线性函数为散列地址 使用场景适合查找比较小且连续的情况 除留余数法常用 直接用该值除以表的大小然后取余数 字符串哈希算法常用 参考文献 3.3 哈希冲突
不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
按照上述哈希函数计算出键值对应的关键码值但是算出来的这些码值当中有很大的可能会出现关键码值相同的情况这种情况就叫作哈希冲突。 哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。 解决哈希冲突两种常见的方法是闭散列和开散列 3.4 闭散列 — 开放地址法
闭散列 也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的下一个空位置中去。
线性探测依次去找空位置 从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。
插入
通过哈希函数获取待插入元素在哈希表中的位置线性探测找到空位置将值插入
查找
挨个遍历哈希表直到找到空为止
删除
通过关键码值再用线性探测找到该值直接删除注意 删除要是直接删除的话有可能会影响查找的准确性 如图删除了10要去找60就会找不到 所以我们给每个键值提供一个状态采取伪删除的方法 线性探测的缺点
一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。
二次探测跳跃着找空位置 对上面方法的优化
不那么拥堵
闭散列哈希表并不能太满
太满就会导致线性探测时找不到位置更不能放满那样探测就会陷入死循环所以要控制一下存储的数据我们引入了一个变量n来记录存储数据的个数
散列表的载荷因子定义为: a 填入表中的元素个数 / 散列表的长度
所以我们要控制一下负载因子
代码如下
templateclass K
struct DefaultHash
{size_t operator()(const K key){return (size_t)key;}
};//字符串哈希算法
template
struct DefaultHashstring
{size_t operator()(const string key){//BKDRsize_t hash 0;for (auto ch : key){hash hash * 131 ch;}return hash;}
};//闭散列开放地址法
namespace CloseHash
{enum State{EMPTY,EXITS,DELETE};templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;};templateclass K, class V, class HashFunc DefaultHashKclass HashTable{typedef HashDataK, V Data;public:bool Insert(const pairK, V kv){//去重if (Find(kv.first)){return false;}//负载因子到0.7及以上就扩容if (_tables.size() 0 || _n * 10 / _tables.size() 7){size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;//扩容以后需要重新映射HashTableK, V, HashFunc newHT;newHT._tables.resize(newSize);//遍历旧表插入newHTfor (auto e : _tables){if (e._state EXITS){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);}HashFunc hf;size_t starti hf(kv.first);//调用仿函数获取整数starti % _tables.size();//求模取余 -- 但是不能除0size_t hashi starti;size_t i 1;//线性探测/二次探测while (_tables[hashi]._state EXITS){hashi starti i;i;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._state EXITS;_n;//有效数据个数return true;}Data* Find(const K key){//空表直接返回空指针if (_tables.size() 0){return nullptr;}HashFunc hf;size_t starti hf(key);starti % _tables.size();size_t hashi starti;size_t i 1;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];}hashi starti i;i;hashi % _tables.size();}return nullptr;}bool Erase(const K key){Data* ret Find(key);if (ret){ret-_state DELETE;_n--;return true;}else{return false;}}private:vectorData _tables;size_t _n 0; //存储关键字个数};
}扩容时我们不能直接将原来的数据拷贝过去
因为哈希是映射的关系关键码值是通过数据和表的大小计算出来的如果直接拷贝的话全都乱套了这时我们需要重新映射 如图所示也不是特别麻烦直接建立一个新表然后遍历旧表一次映射到新表中不过扩容时会有不少的消耗
补充
映射的时候取模应该是对表的size()取模而不是capacity()因为对capacity取模的话可能取到超出size的位置operator[]会对超出size的检查不过有的也不检查根据不同版本的库里定 3.5 开散列 — 哈希桶、拉链法开链法
开散列 开散列法又叫链地址法哈希桶首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接来各链表的头结点存储在哈希表中。 从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。
很显然哈希桶中每个元素是个地址所以哈希桶的底层原理就是一个指针数组每个结点再挂着一个单链表这样冲突就很容易解决了。
namespace Bucket
{templateclass K, class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};templateclass K, class V, class HashFunc DefaultHashKclass HashTable{typedef HashNodeK, V Node;public:~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;}//新方法转移结点//*原来单链表中的结点得到了利用就不用去开新的结点了//负载因子 1 扩容HashFunc hf;if (_tables.size() _n){size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;vectorNode* newTable;newTable.resize(newSize, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;size_t hashi hf(cur-_kv.first) % newSize;cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_tables[i] nullptr;}newTable.swap(_tables);}size_t hashi hf(kv.first);hashi % _tables.size();//头插到对应的桶即可单链表的尾插效率不高但是头插效率高Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}//定位到桶然后在同中挨个找一遍Node* Find(const K key){if (_tables.size() 0){return nullptr;}HashFunc hf;size_t hashi hf(key);//size_t hashi HashFunc()(key);hashi % _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){if (_tables.size() 0){return false;}HashFunc hf;size_t hashi hf(key);hashi % _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;}prev cur;cur cur-_next;}return false;}private://指针数组vectorNode* _tables;size_t _n 0;};
}扩容我们有两种方案
方案一 方案二 很显然我们更倾向于方案二
以为方案二中是将原来单链表中的结点得到了利用就不用去开新的结点了而方案一则是又开了一遍新的结点效率不高方案一是拷贝创建新的结点方案二是转移结点
哈希表的析构 虽然vector自己的析构函数可以释放哈希表但是哈希桶中挂着的每个结点是不能释放的需要我们手动释放掉。
