电子商务网站设计小结,爱站工具包下载,宣传海报在什么网站做,wordpress 下载远程图片前言#xff1a; 前面我们学习了unordered_map和unordered_set容器#xff0c;比较了他们和map、set的查找效率#xff0c;我们发现他们的效率比map、set高#xff0c;进而我们研究他们的底层是由哈希实现。哈希是一种直接映射的方式#xff0c;所以查找的效率很快…前言 前面我们学习了unordered_map和unordered_set容器比较了他们和map、set的查找效率我们发现他们的效率比map、set高进而我们研究他们的底层是由哈希实现。哈希是一种直接映射的方式所以查找的效率很快。与学习红黑树和map、set的思路一样我们现在学完了unordered_map和unordered_set本章将模拟实现底层结构来封装该容器 作者建议在阅读本章前可以先去看一下前面的红黑树封装map和set——红黑树封装map和set
这两篇文章都重在强调泛型编程的思想上一篇由于是初认识作者讲解的会更详细一点~
目录
一如何复用一个哈希桶
1、结点的定义
2、两个容器各自的模板参数类型编辑
3、改造哈希桶
二哈希桶的迭代器的模拟实现
1、begin()和end()的模拟实现
2、operator*和operator-及operator!和operator的模拟实现
3、operator 的模拟实现
三迭代器和改造哈希桶的总代码
四封装unordered_map和unordered_set 一如何复用一个哈希桶
我们学习过知道unordered_map和unordered_set容器存放的结点并不一样为了让它得到复用我们就需要对哈希桶进行改造将哈希桶改造的更加泛型一点既符合Key模型也符合Key_Value模型。
1、结点的定义 所以我们这里还是和封装map和set时一样无论是Key还是Key_Value都用一个类型T来接收这里高维度的泛型哈希表中实现还是用的是Kye_Value模型K是不能省略的同样的查找和删除要用故我们可以引出两个容器各自模板参数类型。 2、两个容器各自的模板参数类型 如何取到想要的数据
我们给每个容器配一个仿函数各传不同的仿函数拿到想要的不同的数据
同时我们再给每个容器配一个哈希函数。
3、改造哈希桶
通过上面1和2我们可以把各自存放的数据泛化成data 这样我们哈希桶的模板参数算是完成了
哈希函数我们可以自由选择并传仿函数在各自容器的封装中实现用于比较时我们可以取出各自容器想要的数据
我们把上一篇文章封装的哈希桶拿来改造
//K -- 键值KeyT -- 数据
//unordered_map -HashTableK, pairK, V, MapKeyOfT _ht;
//unordered_set -HashTableK, K, SetKeyOfT _ht;
templateclass K, class T, class KeyOfT, class HashFunc
class HashTable
{templateclass K, class T, class KeyOfT, class HashFuncfriend class __HTIterator;typedef HashNodeT Node;
public:typedef __HTIteratorK, T, KeyOfT, HashFunc iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];if (cur){return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}~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;}}size_t GetNextPrime(size_t prime){const int PRIMECOUNT 28;static const size_t primeList[PRIMECOUNT] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};//获取比prime大那一个素数size_t i 0;for (i 0; i PRIMECOUNT; i){if (primeList[i] prime)return primeList[i];}return primeList[i];}pairiterator, bool Insert(const T data){HashFunc hf;KeyOfT kot;iterator pos Find(kot(data));if (pos ! end()){return make_pair(pos, false);}//负载因子 1 扩容 -- 平均每个桶挂一个结点if (_tables.size() _n){//size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;size_t newSize GetNextPrime(_tables.size());if (newSize ! _tables.size()){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(kot(cur-_data)) % newSize;//转移到新的表中cur-_next newTable[hashi];newTable[hashi] cur;cur next;}//将原表置空_tables[i] nullptr;}newTable.swap(_tables);}}size_t hashi hf(kot(data));hashi % _tables.size();//头插到对应的桶即可Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;//有效数据加一_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K key){if (_tables.size() 0){return iterator(nullptr, this);}KeyOfT kot;HashFunc hf;size_t hashi hf(key);//size_t hashi HashFunc()(key);hashi % _tables.size();Node* cur _tables[hashi];//找到指定的桶之后顺着单链表挨个找while (cur){if (kot(cur-_data) key){return iterator(cur, this);}cur cur-_next;}//没找到返回空return iterator(nullptr, this);}bool Erase(const K key){if (_tables.size() 0){return false;}HashFunc hf;KeyOfT kot;size_t hashi hf(key);hashi % _tables.size();//单链表删除结点Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) 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;
};主要改造的地方就是上述所注意的地方
比较时需要调用各自的仿函数调用外部传的哈希函数
还有对扩容的二次思考
研究表明除留余数法最好模一个素数
通过查STL官方库我们也发现其提供了一个取素数的函数所以我们也提供了一个直接拷贝过来 这样我们在扩容时就可以每次给素数个桶 在扩容时加了一条判断语句是为了防止素数值太大过分扩容容易直接把空间(堆)干崩了 二哈希桶的迭代器的模拟实现
1、begin()和end()的模拟实现 以第一个桶中第一个不为空的结点为整个哈希桶的开始结点以空结点为哈希桶的结束结点 2、operator*和operator-及operator!和operator的模拟实现 这两组和之前实现的一模一样大家自行理解。
3、operator 的模拟实现 注
这里要在哈希桶的类外面访问其私有成员我们要搞一个友元类迭代器类是哈希桶类的朋友这样就可以访问了 思路
判断一个桶中的数据是否遍历完如果所在的桶没有遍历完在该桶中返回下一个结点指针如果所在的桶遍历完了进入下一个桶判断下一个桶是否为空非空返回桶中第一个节点空的话就遍历一个桶后置和之前一眼老套路不赘述
注意
unordered_map和unordered_set是不支持反向迭代器的从底层结构我们也能很好的理解单链表找不了前驱所以不支持实现迭代器的operator- -
最后注意一点我们需要知道哈希桶大小所以不仅要传结点地址还要传一个哈希桶这样才能知道其大小除此由于哈希桶改造在后面所以我们要在前面声明一下 三迭代器和改造哈希桶的总代码
#includevector
#includestring
#includeiostream
using namespace std;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 Bucket
{templateclass Tstruct HashNode{T _data;HashNodeT* _next;HashNode(const T data):_data(data), _next(nullptr){}};templateclass K, class T, class KeyOfT, class HashFuncclass HashTable;//哈希桶的迭代器templateclass K, class T, class KeyOfT, class HashFuncclass __HTIterator{typedef HashNodeT Node;typedef __HTIteratorK, T, KeyOfT, HashFunc Self;public:Node* _node;__HTIterator() {};//编译器的原则是向上查找定义必须在前面否则必须先声明HashTableK, T, KeyOfT, HashFunc* _pht;__HTIterator(Node* node, HashTableK, T, KeyOfT, HashFunc* pht):_node(node), _pht(pht){}Self operator(){if (_node-_next){_node _node-_next;}else//当前桶已经走完了要走下一个桶{KeyOfT kot;HashFunc hf;size_t hashi hf(kot(_node-_data)) % _pht-_tables.size();hashi;//找下一个不为空的桶 -- 访问到了哈希表中私有的成员友元for (; hashi _pht-_tables.size(); hashi){if (_pht-_tables[hashi]){_node _pht-_tables[hashi];break;}}//没有找到不为空的桶用nullptr去做end标识if (hashi _pht-_tables.size()){_node nullptr;}}return *this;}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s) const{return _node ! s._node;}bool operator(const Self s) const{return _node s._node;}};//K -- 键值KeyT -- 数据//unordered_map -HashTableK, pairK, V, MapKeyOfT _ht;//unordered_set -HashTableK, K, SetKeyOfT _ht;templateclass K, class T, class KeyOfT, class HashFuncclass HashTable{templateclass K, class T, class KeyOfT, class HashFuncfriend class __HTIterator;typedef HashNodeT Node;public:typedef __HTIteratorK, T, KeyOfT, HashFunc iterator;iterator begin(){for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];if (cur){return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}~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;}}size_t GetNextPrime(size_t prime){const int PRIMECOUNT 28;static const size_t primeList[PRIMECOUNT] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};//获取比prime大那一个素数size_t i 0;for (i 0; i PRIMECOUNT; i){if (primeList[i] prime)return primeList[i];}return primeList[i];}pairiterator, bool Insert(const T data){HashFunc hf;KeyOfT kot;iterator pos Find(kot(data));if (pos ! end()){return make_pair(pos, false);}//负载因子 1 扩容 -- 平均每个桶挂一个结点if (_tables.size() _n){//size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;size_t newSize GetNextPrime(_tables.size());if (newSize ! _tables.size()){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(kot(cur-_data)) % newSize;//转移到新的表中cur-_next newTable[hashi];newTable[hashi] cur;cur next;}//将原表置空_tables[i] nullptr;}newTable.swap(_tables);}}size_t hashi hf(kot(data));hashi % _tables.size();//头插到对应的桶即可Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;//有效数据加一_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K key){if (_tables.size() 0){return iterator(nullptr, this);}KeyOfT kot;HashFunc hf;size_t hashi hf(key);//size_t hashi HashFunc()(key);hashi % _tables.size();Node* cur _tables[hashi];//找到指定的桶之后顺着单链表挨个找while (cur){if (kot(cur-_data) key){return iterator(cur, this);}cur cur-_next;}//没找到返回空return iterator(nullptr, this);}bool Erase(const K key){if (_tables.size() 0){return false;}HashFunc hf;KeyOfT kot;size_t hashi hf(key);hashi % _tables.size();//单链表删除结点Node* prev nullptr;Node* cur _tables[hashi];while (cur){if (kot(cur-_data) 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;};
}
四封装unordered_map和unordered_set
有了上面的哈希桶的改装我们这里的对map和set的封装就显得很得心应手了。
unordered_map的封装
#include HashTable.hnamespace zc
{templateclass K, class V, class HashFunc DefaultHashKclass unordered_map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename Bucket::HashTableK, pairK, V, MapKeyOfT, HashFunc::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const pairK, V kv){return _ht.Insert(kv);}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:Bucket::HashTableK, pairK, V, MapKeyOfT, HashFunc _ht;};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;}cout endl;for (auto e : dict){cout e.first e.second endl;}}}
这里unordered_map中的operator[ ]我们知道其原理之后模拟实现就非常方便直接调用插入函数控制好参数和返回值即可。
对unordered_set的封装
#include HashTable.h#include HashTable.hnamespace zc
{templateclass K, class HashFunc DefaultHashKclass unordered_set{struct SetKeyOfT{const K operator()(const K key){return key;}};public://2.48typedef typename Bucket::HashTableK, K, SetKeyOfT, HashFunc::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pairiterator, bool insert(const K key){return _ht.Insert(key);}iterator find(const K key){return _ht.Find(key);}bool erase(const K key){return _ht.Erase(key);}private:Bucket::HashTableK, K, SetKeyOfT, HashFunc _ht;};struct Date{Date(int year 1, int month 1, int day 1):_year(year), _month(month), _day(day){}bool operator(const Date d) const{return _year d._year _month d._month _day d._day;}int _year;int _month;int _day;};struct DateHash{size_t operator()(const Date d){//return d._year d._month d._day;size_t hash 0;hash d._year;hash * 131;hash d._month;hash * 1313;hash d._day;//cout hash endl;return hash;}};void test_set(){unordered_setint s;//setint s;s.insert(2);s.insert(3);s.insert(1);s.insert(2);s.insert(5);s.insert(12);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;unordered_setDate, DateHash sd;sd.insert(Date(2022, 3, 4));sd.insert(Date(2022, 4, 3));}
}最后大家可以利用代码中给的测试函数进行测试
感谢你的阅读
