中英文网站怎么做的,帮人做网站,上海网站企业,wap免费目录 1.关于unordered系列关联式容器
2.关于unordered_map 3.哈希#xff08;散列#xff09;表的实现
一#xff0c;直接定址法
二#xff0c;除留余数法
方法一#xff1a;闭散列#xff1a;开放定址法
方法二#xff1a;闭散列#xff1a;哈希桶/拉链法 4.哈希…目录 1.关于unordered系列关联式容器
2.关于unordered_map 3.哈希散列表的实现
一直接定址法
二除留余数法
方法一闭散列开放定址法
方法二闭散列哈希桶/拉链法 4.哈希表的封装
哈希表封装后
unordered_map简单封装
unordered_set简单封装 1.关于unordered系列关联式容器 在unordered系列关联式容器是C11中新增的一组关联式容器它们的 底层结构是哈希表 而不是红黑树我可以理解之前的map和set红黑树就是Tree_map Tree_set,这里的就是hash_map,hash_set 。这些容器包括 unordered_map、unordered_set 、 unordered_multimap 和 unordered_multiset 。 它们的使用方式与红黑树结构的关联式容器基本相同只是它们的底层结构不同。 相对于红黑树的Tree结构hash这里更加强调的是特性即unorder无序性。 unordered_map和unordered_set是最常用的两个容器它们的底层结构都是哈希unordered_map是存储key, value键值对的关联式容器它允许通过key快速的索引到与其对应的value。 在unordered_map中键值通常用于惟一地标识元素而映射值是一个对象其内容与此键关联。键和映射值的类型可能不同。在内部unordered_map没有对key, value按照任何特定的顺序排序为了能在常数范围内找到key所对应的valueunordered_map将相同哈希值的键值对放在相同的桶中。unordered_map容器通过key访问单个元素要比map快但它通常在遍历元素子集的范围迭代方面效率较低。 unordered_set是一个存储唯一元素的集合它的底层结构也是哈希表。它的元素是不可重复的因此它的查询速度非常快。
2.关于unordered_map
先来看看库中的介绍 对于map还是以key_value为数据模型的那么这里的key肯定也是不可以修改的unodered_map强调的是查找效率其次对于其迭代器是单向的。
对于它的接口也大差不差但是有两个我们没见过的实际上在实现unordered_map中引入了其他参数及接口如这里的负载因子(load_factor)哈希桶Buckts. 3.哈希散列表的实现 什么是哈希呢 通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系那么在查找时通过该函数可以很快找到该元素。 当向该结构中 插入元素-- 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放。 搜索元素-- 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置 取元素比较若关键码相等则搜索成功。 该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称 为哈希表(Hash Table)(或者称散列表)。 比如在做oj第一个出现的字符时就可以通过字符的ASCLL与下标建立一一映射的关系。 那么对于这种结构我们首先最重要的是就是去建立一一的映射关系 关键值-存储位置 。 线面说说两种定值方法 一直接定址法
所谓的直接定址法即直接用该值可以给这个值加或减或者不变作为关键值让每一个值都有一个唯一位置让他的存储位置与该值建立关系。用存储位置表示key值 但是当值太过于分散时那么在映射时就需要开辟足够大的空间去存储。 数据集中的时候我们开辟空间就小但太分散时,如2作为key值插入位置2,95作为key插入位置95,9999插入位置9999.那对于空间无疑是巨大的浪费那该怎么办呢
二除留余数法
有人就提出太大那就对这个数取模让它处在在一个合适的位置比如上面7个数据size为7那就对每个数据模7使它在这里个范围之内。
但是会出现新的问题可能有数据会冲突她两模完值是一样的但对应的value是不一样的这种问题被叫做哈希碰撞/哈希冲突那么如何解决哈希碰撞呢这时候有两种法案可以解决
方法一闭散列开放定址法
本质上就是如果新插入的数据的位置已经有数据了value不一样那就在这个开放的空间中重新找一个空位置。这里也会有两种查找新位置的方法--1.线性探测一个个往后找2.二次探测以2次方递增查找。
如果冲突我们就往后找没有被占的位置。可是当我们的后面空间快要满员时此时再往后找新的位置就可能位置存在不够的情况那么在实际上插入数据的个数在空间达到70%等的时候就需要扩容了这里我么就引入了一个参数-负载因子存储关键字的个数/空间大小来空间空间大小。
为什么会有两种探测或者其他方式来寻找都是避免多次冲突比如对于线性探测重新找位置的话如果有一部分数据是连续的一个位置被提前占了那么就会引起一片的哈希冲突面对这个问题因此有了的探测二次探测。
那么我们就先来实现一下哈希表 对于这里的负载因子即不能太大也不能太小太大容易发生冲突太小空间浪费太多。
这里我们一般使用0.7较为合适。
namespace myspace
{using namespace std;//如何去插入首先就需要对插入的每个位置做标记该位置下可能存在三种状态已经有数据为空之前有现在删除了enum State{EXIST,EMPTY,DELETE};//存放哈希表的数据的类型templateclass K,class Vstruct HashData{pairK, V _kv;State _staEMPTY;};//类型转换计算出key的大小来确定平衡因子templateclass Kstruct HahFunc{size_t operator()(const Kk){return size_t(k);}};templatestruct HahFuncstring{//如果是字符串,我们用所有字符的ascll的和表示key//但是字符串之和也是有很大可能重合很多人通过在数学方面的研究出了一些解决办法//这里最好的方式是采用的BKDR方法给每个字符乘以31131....这样的数 之后的和大概率不会重复size_t operator()(const string k){size_t sum 0;for (int i 0; i k.size(); i){sum sum * 31;sumsumk[i];}return sum;}};
templateclass K, class V,class HashHahFuncVclass HashTable
{
public:HashTable(){//初始化空间为tables.resize(10);}bool insert( const pairK,V kv){if (find(kv.first) ! NULL){return false;}//负载因子决定是否扩容if (_n * 10 / tables.size() 7){//扩容//注意这里的扩容不能直接扩容因为扩容之后size发生改变对应的位置发生改变因此需要重新开辟空间//在一个个重新映射插入之后释放旧空间size_t newsize tables.size() * 2;//扩二倍HashTableK, V newHaTa;newHaTa.tables.resize(newsize);//新表for (int i 0; i tables.size(); i){newHaTa.insert(tables[i]._kv);//重新走一遍映射再插入其中}//现在的需要的哈希表是新的交换过来tables.swap(newHaTa.tables);}//通过取模size使得对应的位置在该size内Hash hf;size_t hashi hf(kv.first % tables.size()) ;while (tables[hashi]._sta EXIST){//先确定好位置hashi;hashi % tables.size();}//再插入tables[hashi]._kv kv;tables[hashi]._sta EXIST;_n;return true;}HashDataK,V* find(const K key){Hash hf;size_t hashi hf(key % tables.size());while (tables[hashi]._sta!EMPTY ){if (tables[hashi]._staEXISTtables[hashi]._kv.first key){return tables[hashi];}hashi;hashi % tables.size();}return NULL;}//伪删除bool erase(const Kkey){HashDataK, V tmp find(key);if (tmp){tmp._sta DELETE;_n--;return true;}else{return false;}}void Printf(){for (int i 0; i tables.size(); i){if (tables[i]._sta EXIST){cout i tables[i]._sta - tables[i]._kv.first endl;}else if (tables[i]._sta DELETE){cout i DELETE tables[i]._kv.first endl;}else if (tables[i]._sta EMPTY){cout i EMPTY tables[i]._kv.first endl;}}}private:vectorHashDataK,V tables;size_t _n;//插入的关键字的个数
};
}
方法二闭散列哈希桶/拉链法
不同于上述的除留余数法在实际的应用当中而是引用哈希桶的方法所谓的哈希桶就是将哈希冲突的值放一起内部处理此时整体结构就是vecorlist型的结构。 每一个key对应有一个桶相同也没事放在一起内部解决。
我来们可以将上面的挂着的链表理解为桶里面存放着相同key的值但是当存放的值太多遍历桶里的值时间复杂度就是O(N)效率太低因此当长度达到某个界限时就会换成红黑树来存放提高查找效率。
在结构上vector中的list我们为了实现迭代器我们自己写单链表里面存放Node*再插入时我们采用头插的方式如下图假设111111他们的key值一样。 由于key类型不一定是整形也有可能是其他类型对于字符换类型我们选他们的ascll码之和再称31用仿函数转化为size_t,以此来表示位置。
namespace Hash_Bucket
{using namespace std;templateclass Kstruct HahFunc{size_t operator()(const K k){return size_t(k);}};templatestruct HahFuncstring{//如果是字符串,我们用所有字符的ascll的和表示key//但是字符串之和也是有很大可能重合很多人通过在数学方面的研究出了一些解决办法//这里最好的方式是采用的BKDR方法给每个字符乘以31131....这样的数 之后的和大概率不会重复size_t operator()(const string k){size_t sum 0;for (int i 0; i k.size(); i){sum sum * 31;sum sum k[i];}return sum;}};templateclass K, class V struct HashNode{pairK, V _kv;HashNode* next;HashNode(const pairK, V kv):_kv (kv),next(nullptr){}};templateclass K, class V,class Hash HahFuncKclass HashTable{public:typedef HashNodeK, V Node;HashTable(){_table.resize(10);}~HashTable(){//循环遍历释放桶的每一个节点for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-next;delete cur;cur next;}_table[i] nullptr;}}bool insert(const pairK, V kv){Hash hf;if (find(kv.first)){//不插入相同的值return false;}//对于哈希桶如果满了就要扩容也就是负载因子为1if (_n _table.size()){//第一种扩容方式我们延续上面的扩容方式//size_t newsize _table.size() * 2;//扩二倍//HashTableK, V newHaTa;//newHaTa.tables.resize(newsize);//新表//for (int i 0; i _table.size(); i)//{// Node* cur _table[i];// while (cur)// {//newHaTa.insert(cur-kv);//重新走一遍映射再插入其中// }// //}现在的需要的哈希表是新的交换过来//_table.swap(newHaTa.tables);//没必要用上述方式我们直接重新弄个表把节点挪动下来vectorNode* newtable;newtable.resize(2 * _table.size());for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* Next cur-next;//重新映射到新表当中size_t hashi hf(kv.first) % newtable.size();//头插cur-next newtable[i];//表中的新头newtable[i] cur;cur Next;//遍历下一个}//旧表置空_table[i] nullptr;}//交换旧表与新表_table.swap(newtable);}//还是先通过取模节省空间size_t hashi hf(kv.first) % _table.size();//头插Node* newnode new Node(kv);newnode-next _table[hashi];_table[hashi] newnode;_n;return true;}Node* find( const Kkey){Hash hf;size_t hashi hf( key) % _table.size();Node* cur _table[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-next;}return NULL;}bool erase(const K* key){Hash hf;size_t hashi hf(key )% _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){//找到并删除//头删if (prev nullptr){_table[hashi] cur-next;//如果头被断开为空cur的下一个就是新头节点}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 _table.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);}void Print(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){if (cur){cout cur-_kv.first cur-_kv.second endl;} cur cur-next;}}cout endl;}private:vectorNode* _table;//这里存放节点指针,目的是为了实现迭代器size_t _n;};
可能有些人觉得哈希桶可能太长效率可能太低 但实际上哈希桶并不会太长通过BKDR以及负载因子的控制不会有太多相同的key值。因此哈希桶实现的哈希表效率与上述基本不差。4. 4.哈希表的封装
对于哈希表的封装和封装红黑树一样我们可以封装出unordered_map与unordered_map。
首先就是统一哈希表的模板参数直接传pair哈希表中用T表示通过仿函数传T张key的类型 之后就是实现迭代器迭代器与哈希表两者相互依赖需要提前声明以及再哈希表中声明友元迭代器方便我们使用在之后为了实现const迭代器在传入参数Ref,Ptr作为T,T*.
对于迭代器的封装这里我们需要三个参数分别是哈希表也可用vector结点指针以及下标位置hashi通过遍历判断实现前置。
哈希表封装后
namespace Hash_Bucket
{using namespace std;templateclass Kstruct HahFunc{size_t operator()(const K k){return size_t(k);}};templatestruct HahFuncstring{//如果是字符串,我们用所有字符的ascll的和表示key//但是字符串之和也是有很大可能重合很多人通过在数学方面的研究出了一些解决办法//这里最好的方式是采用的BKDR方法给每个字符乘以31131....这样的数 之后的和大概率不会重复size_t operator()(const string k){size_t sum 0;for (int i 0; i k.size(); i){sum sum * 31;sum sum k[i];}return sum;}};templateclass T struct HashNode{T _data;HashNode* next;HashNode(const T data):_data (data),next(nullptr){}};//迭代器//由于迭代器与哈希表存在双向依赖//我们在这里给上前置声明templateclass K, class T, class keyofT, class Hashclass HashTable;templateclass K, class T, class Ref, class Ptr, class keyofT, class Hashstruct HTiterator{typedef HashNode T Node;HTiterator(Node*node, HashTable K, T, keyofT, Hash* _tab,size_t _hashi):_node(node), tab(_tab),hashi(_hashi){}//这里除了传一个指针还需要数组或整个表Node* _node;const HashTable K, T, keyofT, Hash* tab;size_t hashi;typedef HTiterator K, T, Ref,Ptr,keyofT, Hash self;//后置加加self operator(){if (_node-next){//继续走这个桶_node _node-next;}else{//下一个桶,找下一个桶hashi;//新的桶while (hashi tab-_table.size()){if (tab-_table[hashi]){//如果不为空我的节点就是这个新节点_node tab-_table[hashi];break;}else {hashi;}}if (hashi tab-_table.size()){_node nullptr;}}return *this;}Ptr operator-(){return (_node-data);}Ref operator*(){return (_node-_data);}bool operator!(const self tmp){return _node ! tmp._node;}};templateclass K,class T,class keyofT,class Hash HahFuncKclass HashTable{public://声明友元templateclass K, class T,class Ref,class Ptr, class keyofT, class Hash friend struct HTiterator;typedef HTiterator K, T,T,T*, keyofT, Hash iterator;typedef HTiterator K, T, const T, const T*, keyofT, Hash const_iterator;iterator begin(){for (int i 0; i _table.size(); i){if (_table[i]){return iterator(_table[i],this,i);}}return end();}iterator end(){return iterator(nullptr, this,-1);}const_iterator begin()const{for (int i 0; i _table.size(); i){if (_table[i]){return const_iterator(_table[i], this, i);}}return end();}const_iterator end()const{return const_iterator(nullptr, this, -1);}typedef HashNodeT Node;HashTable(){_table.resize(10);}~HashTable(){//循环遍历释放桶的每一个节点for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* next cur-next;delete cur;cur next;}_table[i] nullptr;}}Hash hf;keyofT kot;bool insert(const T data){if (find(kot(data))){return false;}//对于哈希桶如果满了就要扩容也就是负载因子为1if (_n _table.size()){vectorNode* newtable;newtable.resize(2 * _table.size());for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){Node* Next cur-next;//重新映射到新表当中size_t hashi hf(kot(data)) % newtable.size();//头插cur-next newtable[i];//表中的新头newtable[i] cur;cur Next;//遍历下一个}//旧表置空_table[i] nullptr;}//交换旧表与新表_table.swap(newtable);}//还是先通过取模节省空间size_t hashi hf(kot(data)) % _table.size();//头插Node* newnode new Node(data);newnode-next _table[hashi];_table[hashi] newnode;_n;return true;}Node* find( const Kkey){Hash hf;size_t hashi hf( key) % _table.size();Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return cur;}cur cur-next;}return NULL;}bool erase(const K* key){Hash hf;size_t hashi hf(key )% _table.size();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (kot(cur-data) key){//找到并删除//头删if (prev nullptr){_table[hashi] cur-next;//如果头被断开为空cur的下一个就是新头节点}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 _table.size(); i){Node* cur _table[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, _table.size());printf(bucketSize:%d\n, bucketSize);printf(maxBucketLen:%d\n, maxBucketLen);printf(averageBucketLen:%lf\n\n, averageBucketLen);}void Print(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];while (cur){if (cur){cout kot(cur-data) kot(cur-data) endl;} cur cur-next;}}cout endl;}private:vectorNode* _table;//这里存放节点指针,目的是为了实现迭代器size_t _n;};}; unordered_map简单封装
namespace myspace1
{using namespace std;templateclass K, class Vclass unordered_map{struct mapkeyofT{const K operator()(const pairK, V data){return data.first;}};public:typedef typename Hash_Bucket::HashTable K, pairK, V, mapkeyofT ::iterator iterator;iterator begin(){return table.begin();}iterator end(){return table.end();}bool insert(const pairK, V kv){return table.insert(kv);}private:Hash_Bucket::HashTableK, pairK, V, mapkeyofT table;};void test(){unordered_mapstd::string, std::string dictionary;dictionary.insert(std::make_pairstd::string, std::string(苹果, 两个));dictionary.insert(std::make_pairstd::string, std::string(梨子, 两个));dictionary.insert(std::make_pairstd::string, std::string(香蕉, 两个));unordered_mapstd::string, std::string::iterator it dictionary.begin();while (it ! dictionary.end()){cout (*it).first (*it).second ;it;}}
};
unordered_set简单封装
namespace myspace2
{templateclass Kclass unodered_set{struct setkeyofT{const K operator()(const K key){return key;}};public:typedef typename Hash_Bucket::HashTable K,K, setkeyofT ::iterator iterator;iterator begin(){return table.begin();}iterator end(){return table.end();}bool insert(const K key){return table.insert(key);}private:Hash_Bucket::HashTableK, K, setkeyofT table;};
};
