太原网站建设公司排名,WordPress来必力,网页制作教程百度网盘,网页版梦幻西游礼包码本文旨在讲解哈希表的封装#xff0c;我们以哈希桶的结构来进行封装unorderedmap/set。要想实现封装哈希表#xff0c;我们首先得先将哈希表的结构给搭建出来#xff0c;然后再根据哈希桶的结构进一步封装unorderedmap/set#xff01; 下面我们先来实现哈希桶的结构#x…本文旨在讲解哈希表的封装我们以哈希桶的结构来进行封装unorderedmap/set。要想实现封装哈希表我们首先得先将哈希表的结构给搭建出来然后再根据哈希桶的结构进一步封装unorderedmap/set 下面我们先来实现哈希桶的结构哈希桶的结构其实就是相同映射值的在一个桶内然后把相同的桶内的元素通过指针链接起来即可所以我们要先实现哈希表中的结点的结构体因为其节点类似于链表的结构所以里面存放的是节点的指针以及该节点存储的值
因为我们是用自己的方式来实现哈希表并进一步封装unorderedmap/set所以我们得用自己的命名空间来包装下面来看一下该哈希表结点的结构实现步骤分为两大步1.实现哈希表。
2.利用已有的哈希表来进行封装 一、实现哈希表
对于哈希表么我们首先也得实现哈希表中的结构的结构体上面已经讲过该结构体类型类似于一种链表所以我们现在就开始实现一下哈希表结点的结构体
1.哈希表结点的结构 构造函数也是同样的直接进行值的构造即可
采用模版首先一开始都将存储的元素即为pair类型最后进行封装的时候再进行修改即可 当哈希表的结点的结构体搭建出来的时候我们就可以搭建我们得哈希表整体的结构了对于哈希表而言我们需要的成员是以哈希结点指针为元素的向量vector以及有效元素的个数
下面来看一下哈希表中的成员
2.哈希表中的成员变量 都是基于模版给出的可以适用于多种类型
当表中的成员写完之后我们首先要都该类进行构造函数和析构函数的编写 3.构造函数
构造函数就是完成初始化的动作我们只需要对我们的vector向量开辟一段空间即可完成构造函数 4.析构函数
因为成员变量中自定义的指针类型所以系统默认的析构函数不能完成析构需要我们手动释放自己来实现析构函数实现析构函数只需要将表中存在的结点释放然后置空即可
对于析构函数我们只需要遍历表然后将表中存在的元素进行delete掉即可然后一个桶内的元素清空之后然后将表进行赋空即可!下面来看一下析构函数的实现 构造函数以及析构函数实现之后那么我们就开始实现一些相关操作的函数
增删查这几个常见的函数
5.Insert函数
对与Insert函数我们首先需要关注的是是否需要扩容当需要扩容的话我们无需在新建节点了只需要将结点的指针进行修改即可我们需要定义一个新的vector,然后用于存储旧表中的元素我们可以采用头插法来进行对新表的插入最后将旧表中所有的元素插入完成之后将旧表置空然后交换新旧表即可因为新表的创建是在局部内且在栈上进行创建的所以不用担心有内存泄漏的问题
下面来看一下Insert函数的实现 实现了Insert函数之后我们可以继续实现Find函数如果找到Find的值时返回该节点的指针即可否则返回nullptr我们要做的是首先要求出对应的映射值然后在桶内进行遍历若桶内存在与key值相同的元素返回该节点的指针即可下面我们来实现一下Find函数
6.Find函数 实现了Find函数之后我们再来实现Erase函数需要注意的是我们实现Erase函数的时候不能复用Find函数来找到该节点因为要删除一个节点的时候我们需要其前驱节点以及后继节点才能正确删除断开联系需要注意的是如果找到了要删除的节点我们需要判断一下是否为头删头删与中间节点的删除是不一样的下面来看一下Erase函数的实现
7.Erase函数 HashFun的引进及实现用于将一个类型转化为整形
实现了上述函数之后我们的哈希表基本大致实现但是当我们插入字符类型的时候我们就会发现问题所在因为字符类型无法自动转化为整形这时就引进了仿函数HashFun此时我们可以利用HashFun来将各种类型转化为整形下面我们就来介绍一下如何实现HashFun对于整形/浮点型等等我们直接进行强转成size_t即可因为平常我们使用string的类型较多所以我们对于string类型直接进行模版的特化专门针对string类型写一个HashFun;HashFun的实现也是基于模版下面来看一下HashFun的实现 因为我们后期要一直使用这个仿函数我们直接将其定义成全局即可当引进了仿函数时我们就需要对我们之前的代码进行修改凡是设计到求余的操作都要用到这个函数将key转化为size_t类型
所以我们直接在Hashtable该类中再加一个模版参数Hash 给他一个缺省参数修改如下 再给一个缺省参数即可完成下面我们还要声明一个这样的函数hf下面代码凡是设计到求余的操作都要用到这个函数那么我们就对Insert来进行改造 其他函数凡是涉及取余都是同样的这里不再修改其他了就是将取余套一层hf函数即可 二、unorderedmap/set封装
至此我们的哈希桶结构已经完成那么下一步就开始封装我们自己unorderdmap/set对于我们自己的unorderedmap/set而言我们只需要添加自己的命名空间然后就可以与库中的unorderedmap/set进行区分
因为基于泛型编程我们对unorderedmap/set的封装总不能写两份代码的所以我们要实现一种格式让二者都能使用我们得哈希桶这个结构来进行对unorderedmap/set的封装。所以我们首先要进行修改的就是我们桶中的数据类型我们只需要桶中的数据类型进行一种改变即可使unorderedmap/set都能调用代码同红黑树的封装一样我们只需要将红黑树中的第二个模版参数当成数据节点的类型即可下面是哈希桶中数据节点的类型的改变以及哈希桶的模版参数的变化 当我们使用map时T就是一个pair的类型当我们使用set的时候T就是一个K的类型那么我们应该如何求出我们T的类型就再次引进了一个仿函数KeyofT。下面来看一下MapkofT/SetkofT的实现 KeyofT的仿函数实现之后我们的unorderedmap/set就可以使用一份代码来进行封装了只不过我们需要在取K的时候套一层KeyofT函数即可至此我们再将哈希表中的Insert...等函数封装到我们的unorderedmap/set即可完成这些函数的调用
下面看一下我们的unorderd_map/set的实现。
1.Unorderd_Map 2.Unorderd_Set 至此我们封装的UnorderedMap/Set也能正常使用
三、迭代器的封装
下面我们再继续封装我们的迭代器!对于迭代器我们还是像以前那样用节点的指针来构造迭代器但是当我们重载operator的时候我们发现仅仅有节点的指针是不行的还需要有哈希表中的table向量以及当前位置的映射值这里我使用哈希表来给大家讲解一些关于类之间相互依赖的问题所以我们的迭代器的构造就有节点的指针哈希表以及哈希映射值这三者组成
下面来看一下迭代器实现
1.迭代器内的成员变量 2.迭代器的构造函数
需要注意的是当我们对迭代器进行构造时我们需要用到哈希表而哈希表也需要用到我们的迭代器这就造成了相互依赖的过程这时我们只需要加一个前置声明即可解决我们的问题即在迭代器的前面加上对类模版哈希类的声明需要注意的是对类模版的前置声明时也需要加上模版参数代码如下 3.重载operator
迭代器既然已经实现了那么我们就可以来重载operator操作在哈希表中的操作首先判断当前桶内是否还有下一节点如果当前桶内没有节点继续向下找其他桶直到找到最后返回空即可代码如下 4.重载operator-
重载operator-即返回_node当前节点指向的值的地址代码如下 5.重载operator*
重载operator*即返回_node当前节点指向的值 6.重载operator! 下面我们再对表内进行迭代器的封装
四、哈希表内对迭代器的封装
我们只需要将迭代器在表内进行重定义即可!然后实现begin()和end()函数即可代码如下 需要注意的是对内嵌类型进行typedef时需要加上typename用于表示是一中类型 1.begin()函数的实现 2.end()函数的实现 注意因为迭代器中要访问到我们表中的私有成员变量所以我们要进行友元类的声明对于模版友元的声明我们需要将模版参数也加上去才能正确进行声明 此时普通迭代器已经大致完成要想实现在我们的unorderedmap/set内实现迭代器只要再次进行封装即可
3.Unordered_set对迭代器的封装 再加上begin,end函数的实现就可以完成范围for的使用了 4.Unordered_Map对迭代器的封装 Unordered_Map中的begin和end与上面Unordered_Set的同理 至此我们的迭代器也实现完成那么我们发现当我们对值进行修改的时候我们的值还能进行修改但库中的却不能进行修改所以我们应该再添加一个const迭代器来进一步对我们的迭代器进行完善 五、const迭代器的实现
下面我们来实现一下const迭代器
对于const迭代器我们需要再次引进两个变量Ref,Ptr才能完成const迭代器的实现
下面来看一下const迭代器的声明
然后将begin函数和const函数都添加一个const版本 1.Unordered_Set中的const迭代器
然后再对set/map中进行封装即可对于set而言我们只需将set中的普通迭代器和const迭代器都声明为const迭代器即可! 但是对于set而言当我们仅仅将迭代器全部声明为const时并不能解决问题因为我们的this类型是const的类型而在迭代器的构造中表是普通类型当const变量给非const变量赋值时就会导致权限的放大那么我们只需要将迭代器的构造再写一个const版本试试 此时构成了重载但是当再次对旧表进行构造时因为旧表也是普通对象此时我们的表是const对象所以也会导致权限的放大那么我们再将表进行const声明即可 这样就解决了set中key值能修改的问题
2. Unordered_Map中的const迭代器
对于Map类型我们只需要对pair中的first不能修改而second依旧不能修改我们只需要对pair的first加上const修饰即可 至此我们的const迭代器也实现完成 下面我们就来实现一下operator[]函数
六、operator[]函数的实现
对于实现operator函数我们的Insert/Find函数的返回值类型也要进行修改
我们将Insert的返回值类型设置为pairiterator,bool类型这时当我们在UnorderedSet中进行封装时就会发现问题迭代器转化的问题对于红黑树那里我们只需要将迭代器转化为Node*即可但是对我们的哈希表中迭代器有三部分组成所以不能进行转化那么我们只好用一个ret类型进行调用Insert的值然后将ret对迭代器进行构造即可解决问题 这里是因为我们知道迭代器的底层是什么所以我们可以进行对pair的构造 下面就可以实现operato[]然后就可以实现统计次数 至此UnorderedMap/Set已经实现在进行封装的时候一定要一步一步的来不要想着一口气将所有的代码实现否则很难完美的封装
下面我把源代码发到下面供大家参考看完本文希望各位佬留下免费的关注和小心心 七、源码
1.Hashtable的实现
#pragma once
//哈希表的实现
//首先将结点的类型用结构体表示出来
//然后哈希表主要是有这些结点的类型的向量vector/以及有效元素的个数组成
#includestring
#includevector
#includeiostream
using namespace std;//区别于库中的哈希用自己的命名空间来进行实现1templateclass K
struct HashFun
{//仿函数的实现本质上就是对operator的重载 size_t operator()(const K key){return size_t(key);}
};//专门针对于string的一个模版特化
template
struct HashFunstring
{size_t operator()(const string str){size_t ret 0;for (auto ch:str){ret * 31; //这时基于一种算法来实现的×什么数都可以就是为了减少冲突ret ch;}return ret;}
};
namespace Hashbucket
{//类似于链表结构 节点内存储值以及下一个节点的指针1//泛型编程将节点的类型设置为一个T即可templateclass Tstruct Hashdata{T _data;Hashdata* _next;//构造函数Hashdata(const T data):_data(data),_next(nullptr){}};templateclass K, class T, class KeyofT, class Hash HashFunK class Hashtable;//迭代器的构造因为要使用到节点所以放在节点的结构体下面进行声明templateclass K, class T,class Ref,class Ptr, class KeyofT, class HashHashFunKstruct __Iterator{typedef HashdataT Node;typedef __IteratorK, T, Ref,Ptr,KeyofT Self;//迭代器的实现需要节点的指针哈希表以及哈希映射值所以要声明这三个成员size_t _hashi;Node* _node;const HashtableK, T, KeyofT* _pht;//构造函数__Iterator(Node* node, HashtableK, T, KeyofT* pht, size_t hashi):_hashi(hashi),_pht(pht),_node(node){}__Iterator(Node* node, const HashtableK, T, KeyofT* pht, size_t hashi):_hashi(hashi), _pht(pht), _node(node){}Self operator(){//当前桶存在下一个节点if (_node-_next){_node _node-_next;return *this;}//当前桶后面没有节点了else{//寻找其他桶找到不为空的桶返回即可_hashi;while (_hashi _pht-_table.size()){Node* cur _pht-_table[_hashi];if (cur){_node cur;break;}_hashi;}//最后判断_hashi的值如果与表的大小一样说明结束了if (_hashi _pht-_table.size()){_node nullptr;}}return *this;}Ptr operator-()//返回当前节点对应的值的地址{return _node-_data;}//重载operator!bool operator!(const Selfs){return _node ! s._node;}Ref operator*()//返回当前节点对应的值{return _node-_data;}};//搭建哈希表的框架templateclass K,class T,class KeyofT,class Hashclass Hashtable{public:templateclass K, class T,class Ref,class Ptr, class KeyofT, class Hash friend struct __Iterator;typedef HashdataT Node;typedef typename __IteratorK, T,T,T* ,KeyofT iterator;typedef typename __IteratorK, T,const T,const T*, KeyofT const_iterator;iterator begin(){//从头遍历表一旦发现有元素返回迭代器for (size_t i 0; i _table.size(); i){Node* cur _table[i];if (cur){return iterator(cur, this, i);}}return end();}iterator end(){//迭代器的最后 用空指针哈希值用-1表示return iterator(nullptr, this, -1); }const_iterator begin()const{//从头遍历表一旦发现有元素返回迭代器for (size_t i 0; i _table.size(); i){Node* cur _table[i];if (cur){return const_iterator(cur, this, i);}}return end();}const_iterator end()const {//迭代器的最后 用空指针哈希值用-1表示return const_iterator(nullptr, this, -1);}Hash hf;KeyofT kot;//构造函数Hashtable(){//对向量进行开辟一定的空间即可_table.resize(10);}//析构函数~Hashtable(){for (size_t i 0; i _table.size(); i){Node* cur _table[i];{while (cur){Node* next cur-_next;delete cur;cur next;}}_table[i] nullptr;}}pairiterator,bool Insert(const T data){iterator it Find(kot(data));if (it ! end()){return make_pair(it, false);}if (_n _table.size()){//需要进行扩容vectorNode* newtable;size_t newsize _table.size() * 2; //默认每次扩容2倍//开始遍历旧表当旧表中存在元素的时候对新表进行头插即可//这里的头插只需要改变指针的指向无需真正新建节点for (size_t i 0; i _table.size(); i){Node* cur _table[i];size_t hashi hf(kot(data)) % _table.size(); //求出哈希映射值while (cur){Node* next cur-_next; //提前记录下一个节点因为下面需要修改cur-_next!//对新表进行头插cur-_next newtable[hashi];newtable[hashi] cur;cur next;}//将旧表中的桶置为空_table[hashi] nullptr;}//最后交换两个向量即可_table.swap(newtable);}else{//无需扩容 直接进行头插即可//先求出hashi即该节点的映射的位置Node* newnode new Node(data); //堆中创建一个节点以kv进行构造size_t hashi hf(kot(data)) % _table.size();//对当前位置进行头插即可newnode-_next _table[hashi];_table[hashi] newnode;//有效元素_n;return make_pair(iterator(newnode,this,hashi),true);}}iterator Find(const K key){size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (key kot(cur-_data)){//找到相等的值直接返回cur即可return iterator(cur,this,hashi);}cur cur-_next;}return iterator(nullptr,this,-1);}bool Erase(const K key){size_t hashi hf(key) % _table.size();Node* pre nullptr;Node* cur _table[hashi];while (cur){if (cur-_kv.first key){//找到要删除的节点了//分两种情况 头删 正常删除1if (pre nullptr){//头删_table[hashi] cur-_next;}else{pre-_next cur-_next;}delete cur;return true;}pre cur;cur cur-_next;}return false;}private:vectorNode* _table; //存储结点指针的向量size_t _n0; //有效元素的个数默认给0};//void test1()//{// Hashtableint, int ht;// ht.Insert(make_pair(4, 4));// ht.Insert(make_pair(5, 5));// ht.Insert(make_pair(7, 7));// bool ret ht.Erase(4);// if (ret true)// {// cout 删除成功;// }// std::cout ret;// int c 0;//}//void test2()//{// Hashtablestring, string ht;// ht.Insert(make_pair(string, 字符));// ht.Insert(make_pair(left, 左边));// // int c 0;//}
}2.UnorderedMap
#pragma once#includeHash.h
namespace Zhj
{templateclass K, class V, class Hash HashFunKclass Unordered_Map{//创建仿函数struct MapkeyofT{//对于Map而言,K就是返回pair的first即可const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename Hashbucket::HashtableK, pair const K, V, MapkeyofT::iterator iterator;pairiterator,bool insert(const pairK,Vkv){return ht1.Insert(kv);}bool Erase(const K key){return ht1.Erase(key);}iterator begin(){return ht1.begin();}iterator end(){return ht1.end();}/* const_iterator begin(){return ht1.begin();}const_iterator end(){return ht1.end();}*/V operator[](const K key){pairiterator, bool ret ht1.Insert(make_pair(key, V()));return ret.first-second;}const V operator[](const K key)const{pairiterator, bool ret ht1.Insert(make_pair(key, V()));return ret.first-second;}Hashbucket::HashtableK, pairconst K,V, MapkeyofT ht1;};//void test2()//{// Unordered_Mapstring, string m1;// m1.insert(make_pair(string, 字符串));// m1.insert(make_pair(left, 左边));// for (auto ch : m1)// {// ch.first x;// ch.second x;// cout ch.first : ch.second endl;// }// int c 0;// //}void test2(){string arr[] { 西瓜, 西瓜,香蕉, 苹果, 苹果, 梨, 梨 };Unordered_Mapstring, int count_map;for (auto e : arr){count_map[e];}for (auto kv:count_map){cout kv.first : kv.second endl;}cout endl;}}
3.UnorderedSet
#pragma once
#includeHash.hnamespace Zhj
{templateclass K,class HashHashFunKclass Unordered_Set{//创建仿函数struct SetkeyofT{//对于Set而言,K就是返回K即可const K operator()(const K k){return k;}};public:Hashbucket::HashtableK, K, SetkeyofT ht1;typedef typename Hashbucket::HashtableK, K, SetkeyofT::const_iterator iterator;typedef typename Hashbucket::HashtableK, K, SetkeyofT::const_iterator const_iterator;pairconst_iterator, bool insert(const K key){auto ret ht1.Insert(key);return pairconst_iterator,bool(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi),ret.second);}//iterator begin()//{// return ht1.begin();//}//iterator end()//{// return ht1.end();//}const_iterator begin()const{return ht1.begin();}const_iterator end()const {return ht1.end();}};void test(){Unordered_Setint s;s.insert(9);s.insert(7);s.insert(6);s.insert(4);for (auto ch : s){//ch 50;cout ch ;}int c 0;cout endl;}
}
