本文旨在讲解哈希表的封装，我们以哈希桶的结构来进行封装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的返回值类型设置为pair<iterator,bool>类型，这时当我们在UnorderedSet中进行封装时，就会发现问题，迭代器转化的问题！对于红黑树那里，我们只需要将迭代器转化为Node*即可！但是对我们的哈希表中，迭代器有三部分组成，所以不能进行转化！那么我们只好用一个ret类型进行调用Insert的值，然后将ret对迭代器进行构造即可解决问题！
这里是因为我们知道迭代器的底层是什么，所以我们可以进行对pair的构造！！
下面就可以实现operato[]，然后就可以实现统计次数！
至此UnorderedMap/Set已经实现！在进行封装的时候，一定要一步一步的来，不要想着一口气将所有的代码实现！否则很难完美的封装！
下面我把源代码发到下面，供大家参考！看完本文希望各位佬留下免费的关注和小心心！
七、源码
1.Hashtable的实现！
#pragma once
//哈希表的实现！
//首先将结点的类型用结构体表示出来！
//然后哈希表主要是有这些结点的类型的向量vector/以及有效元素的个数组成！
#include<string>
#include<vector>
#include<iostream>
using namespace std;
//区别于库中的哈希用自己的命名空间来进行实现1
template<class K>
struct HashFun
{
//仿函数的实现本质上就是对operator的重载 ！
size_t operator()(const K& key)
{
return size_t(key);
}
};
//专门针对于string的一个模版特化！
template<>
struct HashFun<string>
{
size_t operator()(const string& str)
{
size_t ret = 0;
for (auto &ch:str)
{
ret *= 31; //这时基于一种算法来实现的！×什么数都可以，就是为了减少冲突！
ret += ch;
}
return ret;
}
};
namespace Hashbucket
{
//类似于链表结构 节点内存储值以及下一个节点的指针1
//泛型编程，将节点的类型设置为一个T即可！
template<class T>
struct Hashdata
{
T _data;
Hashdata* _next;
//构造函数！
Hashdata(const T& data)
:_data(data)
,_next(nullptr)
{
}
};
template<class K, class T, class KeyofT, class Hash = HashFun<K> >
class Hashtable;
//迭代器的构造！因为要使用到节点，所以放在节点的结构体下面进行声明！
template<class K, class T,class Ref,class Ptr, class KeyofT, class Hash=HashFun<K>>
struct __Iterator
{
typedef Hashdata<T> Node;
typedef __Iterator<K, T, Ref,Ptr,KeyofT> Self;
//迭代器的实现需要节点的指针，哈希表，以及哈希映射值，所以要声明这三个成员！
size_t _hashi;
Node* _node;
const Hashtable<K, T, KeyofT>* _pht;
//构造函数
__Iterator(Node* node, Hashtable<K, T, KeyofT>* pht, size_t hashi)
:_hashi(hashi)
,_pht(pht)
,_node(node)
{
}
__Iterator(Node* node, const Hashtable<K, 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 Self&s)
{
return _node != s._node;
}
Ref operator*()
//返回当前节点对应的值
{
return _node->_data;
}
};
//搭建哈希表的框架！
template<class K,class T,class KeyofT,class Hash>
class Hashtable
{
public:
template<class K, class T,class Ref,class Ptr, class KeyofT, class Hash >
friend struct __Iterator;
typedef Hashdata<T> Node;
typedef typename __Iterator<K, T,T&,T* ,KeyofT> iterator;
typedef typename __Iterator<K, 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;
}
}
pair<iterator,bool > Insert(const T& data)
{
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it, false);
}
if (_n == _table.size())
{
//需要进行扩容！
vector<Node*> 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)
{
//找到要删除的节点了！
//分两种情况 头删 正常删除1
if (pre == nullptr)
{
//头删！
_table[hashi] = cur->_next;
}
else
{
pre->_next = cur->_next;
}
delete cur;
return true;
}
pre = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _table; //存储结点指针的向量！
size_t _n=0; //有效元素的个数！默认给0！
};
//void test1()
//{
// Hashtable<int, 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()
//{
// Hashtable<string, string> ht;
// ht.Insert(make_pair("string", "字符"));
// ht.Insert(make_pair("left", "左边"));
//
// int c = 0;
//}
}
2.UnorderedMap
#pragma once
#include"Hash.h"
namespace Zhj
{
template<class K, class V, class Hash = HashFun<K>>
class Unordered_Map
{
//创建仿函数
struct MapkeyofT
{
//对于Map而言,K就是返回pair的first即可！
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Hashbucket::Hashtable<K, pair< const K, V>, MapkeyofT>::iterator iterator;
pair<iterator,bool > insert(const pair<K,V>&kv)
{
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)
{
pair<iterator, bool> ret = ht1.Insert(make_pair(key, V()));
return ret.first->second;
}
const V& operator[](const K& key)const
{
pair<iterator, bool> ret = ht1.Insert(make_pair(key, V()));
return ret.first->second;
}
Hashbucket::Hashtable<K, pair<const K,V>, MapkeyofT> ht1;
};
//void test2()
//{
// Unordered_Map<string, 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_Map<string, 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
#include"Hash.h"
namespace Zhj
{
template<class K,class Hash=HashFun<K>>
class Unordered_Set
{
//创建仿函数
struct SetkeyofT
{
//对于Set而言,K就是返回K即可！
const K& operator()(const K& k)
{
return k;
}
};
public:
Hashbucket::Hashtable<K, K, SetkeyofT> ht1;
typedef typename Hashbucket::Hashtable<K, K, SetkeyofT>::const_iterator iterator;
typedef typename Hashbucket::Hashtable<K, K, SetkeyofT>::const_iterator const_iterator;
pair<const_iterator, bool> insert(const K& key)
{
auto ret = ht1.Insert(key);
return pair<const_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_Set<int> 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;
}
}
