网站二级菜单模板,全网视频合集网站建设,重庆网站推广 软件,公司网站建设策划欢迎来到Cefler的博客#x1f601; #x1f54c;博客主页#xff1a;那个传说中的man的主页 #x1f3e0;个人专栏#xff1a;题目解析 #x1f30e;推荐文章#xff1a;题目大解析#xff08;3#xff09; 目录 #x1f449;#x1f3fb;unordered系列关联式容器un… 欢迎来到Cefler的博客 博客主页那个传说中的man的主页 个人专栏题目解析 推荐文章题目大解析3 目录 unordered系列关联式容器unordered_mapunordered_set 哈希概念哈希函数哈希冲突 哈希冲突解决方法闭散列线性探测 哈希闭散列模拟实现哈希数据和哈希状态返回哈希值的key哈希插入含扩容和线性探测哈希查找哈希的伪删除哈希打印哈希闭散列完整代码附测试代码 哈希开散列哈希桶模拟实现概念哈希节点哈希插入含扩容析构函数返回哈希值的key哈希查找哈希删除显示哈希的一些情况桶的数量、长度等哈希开散列完整代码附测试代码 unordered系列关联式容器
在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到 l o g 2 N log_2 N log2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同(unordered系列底层是哈希表)
unordered_map
unordered_map官方文档 unordered_map
unordered_map是存储key, value键值对的关联式容器其允许通过keys快速的索引到与 其对应的value。在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此 键关联。键和映射值的类型可能不同。在内部,unordered_map没有对kye, value按照任何特定的顺序排序, 为了能在常数范围内 找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭 代方面效率较低。unordered_maps实现了直接访问操作符(operator[])它允许使用key作为参数直接访问 value。它的迭代器至少是前向迭代器
unordered_set
unordered_set官方文档unordered_set
1.无序集合是存储没有特定顺序的唯一元素的容器它允许基于它们的值快速检索单个元素。
2.在unordered_set中元素的值同时也是唯一标识它的键。键是不可变的因此在容器中不能修改unordered_set中的元素——但是可以插入和删除它们。
3.在内部unordered_set中的元素没有按照任何特定的顺序排序而是根据它们的散列值组织到bucket中以便通过它们的值直接快速访问单个元素(平均时间复杂度为常数)。
4.Unordered_set容器在按键访问单个元素时比set容器快尽管它们在通过其元素子集进行范围迭代时通常效率较低。
5.容器中的迭代器至少是前向迭代器。
哈希概念
顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即O( l o g 2 N log_2 N log2N)搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。
如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中
插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置取元素比较若关键码相等则搜索成功
该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)(或者称散列表) 哈希/散列映射关键字和另一个值建立一个关联关系 哈希表/散列表映射关键字和存储位置建立一个关联关系 哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。 哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
☃️常见的哈希函数有 直接定址法–(常用) 取关键字的某个线性函数为散列地址HashKey A*Key B 优点简单、均匀关键字—存储位置是一对一的关系不存在哈希冲突 缺点需要事先知道关键字的分布情况 使用场景关键字范围集中量不大的情况 除留余数法–(常用) 设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数 按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址 其关键字-存储位置是多对一的关系多个关键字对应一个位置存在哈希冲突 使用场景关键字可以很分散量可以很大 例如该下面这个就是采取除留余数法
数据集合{176459} 哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。 用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快 问题按照上述哈希方式向集合中插入元素44会出现什么问题
哈希冲突 概念 概念 概念 对于两个数据元素的关键字 k i k_i ki和 k j k_j kj(i ! j)有 k i k_i ki ! k j k_j kj但有Hash( k i k_i ki) Hash( k j k_j kj)即不同关键字通过相同哈希哈数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。 发生哈希冲突该如何处理呢 哈希冲突解决方法
闭散列
闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢
线性探测
比如刚刚的场景中现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4 因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突。 线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止。 线性探测向后找可以表示为hashii(i0)
即线性探测的插入和删除表现为
插入 1.通过哈希函数获取待插入元素在哈希表中的位置 2.如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素 删除 采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响因为我们查找到4时此时4的位置为空我们就停下来了不往后找自然就找不到44了。因此线性探测采用标记的伪删除法(标记状态为DELETE)来删除一个元素。 哈希闭散列模拟实现
哈希数据和哈希状态
enum Status{EMPTY,EXIST,DELETE};template class K, class Vstruct HashData{pairK, V _kv;Status _s;};返回哈希值的key
1.常规类型返回如int、double等
template class Kstruct HashFunc{operator()(const K key){return (size_t)key;}};2.字符串类型返回 这个就不能直接返回字符串因为字符串是不能用于取余的但是我们可以将字符串中的每一个字符的ASCII码值全部相加以整型的形式返回即可。 但是我们知道字符串的组合是无数种的可size_t的值却是有上限的那么多字符串最终会有很多字符串相加的ASCII码值会相等这就会发生哈希冲突。对于哈希冲突我们不可避免但是在这个基础上有算法大佬提供了牛逼的算法可以减少这之间的哈希冲突的产生。 以下是一个著名的BRDK算法 我们借鉴这个算法进行将字符串转换为整型返回
templatestruct HashFuncstring{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 31 e;}return hash;}};我们观察到针对于这两种情况我们都是采用了模板进行实例化而字符串类型返回比较特殊这边用了全特化。 有人可能会问为什么不把写成类的函数重载而是用模板特化 答案是这里会出现坑当我们进行函数重载时如果传进来的K是string,此时类中就会有两个size_t operator()(const string key)发生冲突。 而特化就可以解决这个问题。
哈希插入含扩容和线性探测
扩容
//如果空间不够//负载因子0.7就扩容if (_n * 10 / _tables.capacity() 7){//不能原地扩容因为原地扩容会使映射关系发生变化比如size(10)-size(20),原本3的位置会变到13去//所以我们开辟新空间size_t newSize _tables.size() * 2;HashTableK, V,Hash newHT;newHT._tables.resize(newSize);//遍历旧表将旧表的值插入到新表中for (int i 0; i _tables.size(); i){if (_tables[i]._s EXIST){newHT.Insert(_tables[i]._kv);}}//最后旧表变新表_tables.swap(newHT._tables);}线性探测:
Hash hf;//HashFuncsize_t hashi hf(kv.first) % _tables.size();//size_t可以解决负数问题负数隐式类型转换为无符号while (_tables[hashi]._s EXIST) {//存在则找下一个空位置hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._s EXIST;_n;return true;整体插入代码
bool Insert(const pairK, V kv){if (Find(kv.first))return false;//如果空间不够//负载因子0.7就扩容if (_n * 10 / _tables.capacity() 7){//不能原地扩容因为原地扩容会使映射关系发生变化比如size(10)-size(20),原本3的位置会变到13去//所以我们开辟新空间size_t newSize _tables.size() * 2;HashTableK, VHash newHT;newHT._tables.resize(newSize);//遍历旧表将旧表的值插入到新表中for (int i 0; i _tables.size(); i){if (_tables[i]._s EXIST){newHT.Insert(_tables[i]._kv);}}//最后旧表变新表_tables.swap(newHT._tables);}//线性探测Hash hf;//HashFuncsize_t hashi hf(kv.first) % _tables.size();//size_t可以解决负数问题负数隐式类型转换为无符号while (_tables[hashi]._s EXIST) {//存在则找下一个空位置hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._s EXIST;_n;return true;}哈希查找
//哈希查找HashDataK, V* Find(const K key){Hash hf;size_t hashi hf(key) % _tables.size();while (_tables[hashi]._s ! EMPTY){if (_tables[hashi]._s EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}哈希的伪删除
伪删除就很简单直接找到对应的位置将该位置的状态改为DELETE,然后_n减一即可。
//伪删除bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_s DELETE;_n--;return true;}elsereturn false;}哈希打印
//打印void Print(){for (size_t i 0; i _tables.size(); i){if (_tables[i]._s EXIST){//printf([%d]-%d\n, i, _tables[i]._kv.first);cout [ i ]- _tables[i]._kv.first : _tables[i]._kv.second endl;}else if (_tables[i]._s EMPTY){printf([%d]-\n, i);}else{printf([%d]-D\n, i);}}cout endl;}哈希闭散列完整代码附测试代码
#pragma once
#includeiostream
#includevector
using namespace std;
namespace close_address
{enum Status{EMPTY,EXIST,DELETE};template class K, class Vstruct HashData{pairK, V _kv;Status _s;};//返回哈希的key//1.常规类型template class Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//2.字符串转换为整型返回templatestruct HashFuncstring{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 31 e;}return hash;}};template class K,class V,class Hash HashFuncKclass HashTable{public:HashTable(){_tables.resize(10);//一开始扩容为10}bool Insert(const pairK, V kv){if (Find(kv.first))return false;//如果空间不够//负载因子0.7就扩容if (_n * 10 / _tables.capacity() 7){//不能原地扩容因为原地扩容会使映射关系发生变化比如size(10)-size(20),原本3的位置会变到13去//所以我们开辟新空间size_t newSize _tables.size() * 2;HashTableK, V,Hash newHT;newHT._tables.resize(newSize);//遍历旧表将旧表的值插入到新表中for (int i 0; i _tables.size(); i){if (_tables[i]._s EXIST){newHT.Insert(_tables[i]._kv);}}//最后旧表变新表_tables.swap(newHT._tables);}//线性探测Hash hf;//HashFuncsize_t hashi hf(kv.first) % _tables.size();//size_t可以解决负数问题负数隐式类型转换为无符号while (_tables[hashi]._s EXIST) {//存在则找下一个空位置hashi;hashi % _tables.size();}_tables[hashi]._kv kv;_tables[hashi]._s EXIST;_n;return true;}//哈希查找HashDataK, V* Find(const K key){Hash hf;size_t hashi hf(key) % _tables.size();while (_tables[hashi]._s ! EMPTY){if (_tables[hashi]._s EXIST _tables[hashi]._kv.first key){return _tables[hashi];}hashi;hashi % _tables.size();}return nullptr;}//伪删除bool Erase(const K key){HashDataK, V* ret Find(key);if (ret){ret-_s DELETE;_n--;return true;}elsereturn false;}//打印void Print(){for (size_t i 0; i _tables.size(); i){if (_tables[i]._s EXIST){//printf([%d]-%d\n, i, _tables[i]._kv.first);cout [ i ]- _tables[i]._kv.first : _tables[i]._kv.second endl;}else if (_tables[i]._s EMPTY){printf([%d]-\n, i);}else{printf([%d]-D\n, i);}}cout endl;}private:vectorHashDataK,V _tables;size_t _n 0;//存储关键字的个数};void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Print();}void TestHT2(){string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };//HashTablestring, int, HashFuncString ht;HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashDatastring, int* ret ht.Find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair(apple, 1));ht.Insert(make_pair(sort, 1));ht.Insert(make_pair(abc, 1));ht.Insert(make_pair(acb, 1));ht.Insert(make_pair(aad, 1));ht.Print();}
}哈希开散列哈希桶模拟实现
概念
开放寻址法Open Addressing是一种解决哈希冲突的方法。在开放寻址法中当发生冲突时会通过一定的探测序列如线性探测、二次探测等在哈希表中的其他位置继续寻找空闲槽来存储冲突的元素。
而开散列Open Hashing也被称为链地址法Chaining是另一种解决哈希冲突的方法。在开散列中具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶当发生哈希冲突时冲突的元素会被链接成一个链表或其他数据结构存储在同一个桶中。 哈希节点
templateclass K,class Vstruct HashNode{HashNodeK, V* _next;pairK, V _kv;HashNode(const HashNodeK,V kv):_kv(kv._kv),_next(nullptr){}};哈希插入含扩容
bool Insert(const pairK, V kv){if (Find(kv.first))return false;//扩容这里负载因子可以最大到1if (_n _tables.size()){size_t newSize() _tables.size() * 2;HashTableK,V newHT;newHT._tables.resize(newSize);//遍历旧表插入新表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){newHT.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newHT._tables);}//插入的新节点头插Hash hf;size_t hashi hf(kv.first) % _tables.size();Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}扩容方法2
if (_n _tables.size()){vectorNode* newTables;newTables.resize(_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 hf(cur-_kv.first) % newTables.size();cur-_next newTables[i];newTables[i] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}析构函数
~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;}}返回哈希值的key
//返回哈希的key//1.常规类型template class Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//2.字符串转换为整型返回templatestruct HashFuncstring{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 31 e;}return hash;}};哈希查找
//哈希查找Node* Find(const K key){Hash hf;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_next key){return cur;}cur cur-_next;}return nullptr;}哈希删除
//哈希删除bool Erase(const K key){Hash hf;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;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;}显示哈希的一些情况桶的数量、长度等
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(all bucketSize:%d\n, _tables.size());printf(bucketSize:%d\n, bucketSize);printf(maxBucketLen:%d\n, maxBucketLen);printf(averageBucketLen:%lf\n\n, averageBucketLen);}哈希开散列完整代码附测试代码
#pragma once
#includeiostream
#includevector
#includeunordered_set
#includeset
using namespace std;
namespace hash_bucket
{templateclass K,class Vstruct HashNode{HashNodeK, V* _next;pairK, V _kv;HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}};//返回哈希的key//1.常规类型template class Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};//2.字符串转换为整型返回templatestruct HashFuncstring{size_t operator()(const string key){size_t hash 0;for (auto e : key){hash hash * 31 e;}return hash;}};templateclass K,class V,class Hash HashFuncKclass HashTable{public:typedef HashNodeK, V Node;HashTable(){_tables.resize(10);}~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;//扩容这里负载因子可以最大到1if (_n _tables.size()){size_t newSize _tables.size() * 2;HashTableK,V newHT;newHT._tables.resize(newSize);//遍历旧表插入新表for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){newHT.Insert(cur-_kv);cur cur-_next;}}_tables.swap(newHT._tables);}//插入的新节点头插Hash hf;size_t hashi hf(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 hf;size_t hashi hf(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 hf;size_t hashi hf(key) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;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;}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(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 0;};void TestHT1(){HashTableint, int ht;int a[] { 4,14,24,34,5,7,1,15,25,3 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(13, 13));cout ht.Find(4) endl;ht.Erase(4);cout ht.Find(4) endl;}void TestHT2(){string arr[] { 香蕉, 甜瓜,苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };HashTablestring, int ht;for (auto e : arr){//auto ret ht.Find(e);HashNodestring, int* ret ht.Find(e);if (ret){ret-_kv.second;}else{ht.Insert(make_pair(e, 1));}}}//测试效率void TestHT3(){const size_t N 10000;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); // 没有重复有序}// 21:15size_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;}//结果HashTable尽显优势
}如上便是本期的所有内容了如果喜欢并觉得有帮助的话希望可以博个点赞收藏关注❤️ ,学海无涯苦作舟,愿与君一起共勉成长
