目录
编辑
一，实现一个可封装的哈希表
1，哈希表的节点
2，哈希表的成员
3，哈希表成员方法的实现
4，迭代器的实现
5，在哈希表中加入迭代器
二，封装哈希表
1，unorder_map封装
2，unordered_set的封装
一，实现一个可封装的哈希表
1，哈希表的节点
在哈希表的封装中，分为两类：unordered_map,unordered_set。其中map的元素类型为pair<K,V>类型，set的类型为K类型。
Node实现如下：
template<class T>
struct Node
{
Node<T>* _next;
T val;
};2，哈希表的成员
哈希表的成员有两个，一个是记录哈希表节点个数的成员_n，一个是成员为Node*类型的vector<Node*>数组。
HashTable实现如下：
template<class T>
class HashTables
{
typedef Node<T> Node;
public:
private:
vector<Node*>_tables;
size_t _n;
};3，哈希表成员方法的实现
（1），Find(V&key)方法
Find方法实现的是在一个哈希表中寻找某个值存不存在。步骤如下：1，找到这个值对应的hashi（在哈希表中的下标）。2，遍历这个下标上挂载的链表上是否有该值。3，有则返回true,没有就返回false.
要找到hashi: 先实现两个方法Getkey()与GetHashi()
Getkey()：
template <class K,class V>
struct Getkey
{
K operator()(const V& val)//一般的成员直接返回val,遇到特殊pair类型的则返回val.first(先不实现)
{
return val;
}
};GetHashi()：
template <class T>//一般情况下
struct GetHashi
{
size_t operator(T& val)
{
return (size_t)val;
}
};
template<>//模板特化，当这个成员的类型为string类型时
struct GetHashi<string>
{
size_t operator()(string& val)
{
size_t ret = 0;
for (int i = 0;i < val.size();i++)
{
ret += ret * 31 + val[i];
}
return ret;
}
};Find():
bool Find(V& val)
{
size_t hashi = GetHashi(Getkey(val)) % _tables.size();//计算hashi
Node* cur = _tables[hashi];//找到对应的位置上的链表
while (cur)//开始寻找
{
if (cur->val == _val) return true;
}
return false;
}（2），Insert（T&key）
实现插入函数：(1)，满载时要扩容，扩容逻辑是创建一个新的vector<Node*>temp并且把这个表的大小扩为旧表的二倍。 (2)，将旧表中的元素拆下来头插到新表中。（3），将就表中的值全部变为nullptr,防止二次析构。（4），将新表交换给旧表
Insert函数代码：
bool Insert(const V& val)
{
if (Find(val)) return false;//存在过则直接返回插入失败
if (_n == _tables.size())//检查是否需要扩容
{
int newsize = 2*(_n == 0? 1 : _n);//新的大小
vector<Node*>temp;//开一个临时数组
temp.resize(newsize);//扩大为原来哈希表的二倍
for (int i = 0;i < _tables.size();i++)
{
Node* cur = _tables[i];
Node* next = nullptr;
if (cur)
{
while (cur)
{
size_t hashi = GetHashi(Getkey(cur->_val))%_tables.size();//计算新的哈希值
//保存下一个值，并更新就哈希表上的值
next = cur->_next;
_tables[i] = next;
//头插到新的哈希表中
cur->_next = temp[hashi];
temp[hashi] = cur;
cur = next;
}
}
}
//扩容好后便夺回来
for (int i = 0;i < _tables.size();i++)
{
_tables[i] = nullptr;
}
_tables.swap(temp);
}
int hashi = GetHashi(Getkey(val))%_tables.size();
Node* newNode = new Node(val);
//头插
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
_n++;
return true;
}（3）Erase(V&val)
实现：先找到这个值，再删除。
Erase（V&val）代码：
bool Erase(const V& val)
{
int hashi = GetHashi(Getkey(val)) % _tables.size();//计算hashi
Node* pre = nullptr;//记录hashi前面的指针
Node* cur = _tables[hashi];//当前指针
while (cur)
{
if (cur->_val == val)//有相同的便开始执行删除逻辑
{
if(pre)pre->_next = cur->_next;//加上条件防止头删出错
delete cur;
cur = nullptr;
_n--;
return true;
}
pre = cur;
cur = cur->_next;
}
return false;
}4，迭代器的实现
（1），迭代器的成员
迭代器的成员：1，一个Node*类型的成员_node（因为迭代器就是一种模拟指针的行为所以要有哈希表元素的指针）。2，哈希表的指针和当前的_node对应的位置（主要是为了方便实现++）。
代码如下：
typedef HTiterator<K, V, ref, ptr, Getkey, GetHashi> self;//迭代器类型
typedef Node<V> Node;
Node* _node;//哈希表成员的指针
typedef HashTables<K, V, Getkey, GetHashi>* pht;
pht _pht;//哈希表的指针
size_t _hashi;//迭代器在哈希表中的位置（2）迭代器++的实现
1，找到下一个不为nullptr的点（这里要用到哈希表的指针和当前指针的位置） 。 2，返回一个迭代器。3，在实现++之前得实现一个迭代器的构造函数。
构造函数代码：
HTiterator(Node* node,pht Hp,size_t hashi)//构造函数
:_node(node)
,_pht(Hp)
,_hashi(hashi)
{}
实现迭代器operator++()代码：
//实现++
self operator ++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
_hashi++;
while (_hashi < _pht->_tables.size())
{
if (_pht->_tables[_hashi])
{
_node = _pht->_tables[_hashi];
return HTiterator(_node, _pht, _hashi);//找到了直接返回构造的iterator
}
_hashi++;
}
_node = nullptr;//找不到就将_node置为nullptr在构造
}
return HTiterator(_node, _pht, _hashi);
}（3）实现operator*()，operator->(),operator!=()
*:返回值是_node里面的val。->:返回值是_node->val的地址。！=：比较的是_node
代码：
ref operator*()
{
return _node->_val;
}
ptr operator->()
{
return& _node->_val;
}
bool operator!=(const self& s)
{
return _node != s._node;
}5，在哈希表中加入迭代器
typedef HTiterator<K, V, V&, V*> iterator;//定义一个迭代器类型
iterator begin()//实现begin()
{
for (int hashi = 0;hashi < _tables.size();hashi++)
{
if (_tables[hashi]) return iterator(_tables[hashi], this, hashi);
}
return end();
}
iterator end()//实现end()
{
return iterator(nullptr, this, -1);
}二，封装哈希表
1，unorder_map封装
(1)unordered_map的成员
unordered_map的底层便是一个哈希表，所以unordered_map的成员便是一个哈希表。
代码：
cq::HashTables<K,pair<K, V>, Getkey<K,V>> HT;（2）unordered_map的方法
在实现这些方法之前，先得把哈希表里的Insert()和Find()方法的返回值改一下，改成如下形式：pair<iterator,bool>，方便后面的operator[]的实现。
代码：
pair<iterator,bool> Insert(const V& val)//改成pair<iterator,bool>类型
{
iterator it = Find(val);
if (it != end()) return make_pair(it, false);
if (_n == _tables.size())//检查是否需要扩容
{
int newsize = 2*(_n == 0? 1 : _n);//新的大小
vector<Node*>temp;//开一个临时数组
temp.resize(newsize);
for (int i = 0;i < _tables.size();i++)
{
Node* cur = _tables[i];
Node* next = nullptr;
if (cur)
{
while (cur)
{
size_t hashi = GetHashi(Getkey(cur->_val))%_tables.size();//计算新的哈希值
//保存下一个值，并更新就哈希表上的值
next = cur->_next;
_tables[i] = next;
//头插到新的哈希表中
cur->_next = temp[hashi];
temp[hashi] = cur;
cur = next;
}
}
}
//扩容好后便夺回来
for (int i = 0;i < _tables.size();i++)
{
_tables[i] = nullptr;
}
_tables.swap(temp);
}
size_t hashi = GetHashi(Getkey(val))%_tables.size();
Node* newNode = new Node(val);
//头插
newNode->_next = _tables[hashi];
_tables[hashi] = newNode;
_n++;
return make_pair(iterator(newNode, this, hashi),true);
}（2） 实现V& operator[](K&key)
operator[]的作用是让我们能够通过key值来访问val值。
代码：
V& operator[](const K& key)
{
pair<iterator,bool> ret = HT.Insert(make_pair(key,V()));
return ret.first->second;//返回的是一个pair<iterator,bool>,first代表iterator，然后再调用iterator的->找到val值
}（3）unordered_map里其它的成员方法
其它的成员方法都是通过调用哈希表里面实现的方法实现的。
iterator begin()
{
return HT.begin();
}
iterator end()
{
return HT.end();
}
pair<iterator, bool> insert(const pair<K,V>& val)
{
return HT.Insert(val);
}
bool erase(const V& val)
{
return HT.Erase(val);
}
pair<iterator,bool> Find(const V& val)
{
return HT.Find(val);
}unordered_map封装代码：
template < class K,class V>
struct Getkey
{
K operator()(const pair<K,V>& val)
{
return val.first;
}
};
template <class K, class V>
class my_unordered_map
{
typedef typename cq::HashTables<K, pair<K,V>, Getkey<K,V>>::iterator iterator;
public:
iterator begin()
{
return HT.begin();
}
iterator end()
{
return HT.end();
}
pair<iterator, bool> insert(const pair<K,V>& val)
{
return HT.Insert(val);
}
bool erase(const V& val)
{
return HT.Erase(val);
}
pair<iterator,bool> Find(const V& val)
{
return HT.Find(val);
}
V& operator[](const K& key)
{
pair<iterator,bool> ret = HT.Insert(make_pair(key,V()));
return ret.first->second;
}
private:
cq::HashTables<K,pair<K, V>, Getkey<K,V>> HT;
};
2，unordered_set的封装
unordered_set的封装与unordered_map的封装类似。但是不用实现operator[]。
代码如下：
template < class K>//set的模板参数只要一个
struct Getkey
{
K operator()(const K& val)
{
return val;
}
};
template <class K>
class my_unordered_set
{
typedef typename cq::HashTables<K, K, Getkey<K>>::iterator iterator;
public:
iterator begin()
{
return HT.begin();
}
iterator end()
{
return HT.end();
}
pair<iterator, bool> insert(const K& val)
{
return HT.Insert(val);
}
bool erase(const K& val)
{
return HT.Erase(val);
}
pair<iterator, bool> Find(const K& val)
{
return HT.Find(val);
}
private:
cq::HashTables<K, K, Getkey<K>> HT;//内部成员哈希表
};
![[NOIP2011 普及组] 数字反转](https://img-blog.csdnimg.cn/direct/29abc83666914b5f8579b24fc746fbc9.png)
