C++基础（18）——使用哈希表封装unordered_map和unordered_set
·
目录
哈希表的源代码
我们这里的实现就是使用我们在数据结构初阶上面的代码来实现的，我们这里采用的开散列的方式来实现哈希表的，有兴趣的友友可以看看这一篇博客——哈希表。
#pragma once
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
template <class K, class V>
struct HashNode {
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
};
template <class K, class V>
class HashTable {
public:
HashTable() : _table(11), _n(0) {}
typedef HashTable<K, V> Node;
bool Insert(const pair<K, V>& kv) {
Node* pos = Find(kv.first);
if(pos) {
return false;
}
// 刚刚超过了负载因子
if(_n == _table.size()) {
vector<Node*> newTable(_table.size() * 2);
for(size_t i = 0; i < _table.size(); i++) {
Node* cur = _table[i];
while(cur) // 遍历原来哈希桶里面的节点
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr; // 置空
}
_table.swap(newTable); // 交换
}
// 开始插入键值对
size_t hashi = kv.first % _table.size();
// 也是头插
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
_n++;
return true;
}
HashNode<K, V>* Find(const K& key) {
size_t hashi = key % _table.size();
HashNode<K, V>* cur = _table[hashi];
while(cur) {
if(cur->_kv.first == key) {
return cur;
}
cur = cur->_next;
}
return nullptr;
}
bool Erase(const K& key) {
size_t hashi = key % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while(cur) {
if(cur->_kv.first == key) {
if(prev == nullptr) // 头节点
{
_table[hashi] = cur->_next;
}else // 在中间
{
prev->_next = cur->_next;
}
delete cur;
_n--;
return true;
}else {
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _table;
size_t _n;
};哈希表模板参数的控制
我们这里的模板控制逻辑其实是和我们在红黑树封装map和set是一样的，我们这里实现的unordered_map是KV模型，但是我们的unordered_set实现的K模型。
我们这里也是将我们的哈希表的第二个参数设置成了T，然后我们在实现我们的unordered_map的时候，我们就是传入key和value的键值对作为我们的T：
template<class K, class V>
class unordered_map {
public:
// ...
private:
HashTable<K, pair<K, V>> _ht
};当我们实现的unordered_set的时候，我们传入的就是key和key了：
template<class K>
class unordered_set {
public:
// ...
private:
HashTable<K, K> _ht;
};我们这里的T的取值完全就是取决于，我们的实现的需要：
于是我们的哈希表的节点也是有了相应的变化：
template<class T>
struct HashNode {
T _data;
HashNode<T>* _next;
HashNode(const T& data) : _data(data), _next(nullptr) {}
};我们的实现哈希表里面时常会需要获得我们的键值，但是我们这里统一使用了T类作为我们存储的值的类型，这个T可能是键值对，也可能是键值，但是我们的哈希表是不知道的，所以我们要在实现的结构里面提供一个仿函数给哈希表。
所以我们的unordered_map容器就要给哈希表提供一个仿函数，来返回我们的键值：
template<class K, class V>
class unordered_map {
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
}
private:
HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};虽然我们的unordered_set容器的传入的T就是我们要的键值，但是我们的底层哈希表是不知道的，我们统一使用我们的仿函数来获取key值，所以我们的unordered_set还是要实现一份，即使就是返回自身：
template<class K>
class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) {
return key;
}
}
private:
HashTable<K, K, SetKeyOfT> _ht;
};string类型不好取哈希值
我们上面也已经提到了，我们的哈希表的实现取出哈希值使用的函数是除留余数的方法，但是我们的string类型并不是整数，所以我们就要给string类提供一个哈希函数，但是我们的字符串不可能一一对应一个数字，因为字符串的组成是无穷无尽的，所以不管我们使用了，什么方法我们就会有发生哈希冲突的可能，只是我们的冲突概率不同而已。
我们的计算机大佬们在经过了实验之后，发明了BKDHash算法，这个算法在实际的使用中效果明显要好于其他的算法，所以一直被一些高级语言使用，比如我们的Java。
所以我们的哈希表的模版参数中还有增加一个仿函数，就是我们的哈希函数，由于我们使用
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable如果我们没有传入这个仿函数，我们就使用了默认的仿函数，也就是直接返回我们的key值，但是我们有的时候会使用到string类型，所以我们个string类设计了一个类模板的特化：
非string：
template<class K>
struct HashFunc {
size_t operator()(const K& key) {
return (size_t)key;
}
};string：
template<>
struct HashFunc<string> {
size_t operator()(const string& s) {
{
// BKDR
size_t hash = 0;
for(auto ch : s) {
hash += ch;
hash *= 131;
}
return hash;
}
};
哈希函数的默认成员函数
✍️构造函数
我们实现哈希表的时候，主要就是两个成员变量，一个就是我们存哈希节点的vector，一个就是我们哈希表里面的有效元素个数：
vector<Node*> _table;
size_t _n = 0;我们这里的构造函数默认是将我们的vector开到我们预处理的空间大小数组的第一个元素：
HashTable()
:_table(__stl_next_prime(0)
, _n(0){}✍️拷贝构造函数
我们这里的拷贝构造使用的是深拷贝，也就是拷贝节点重新插入。
实现的步骤如下：
1、将要拷贝给的对象的哈希表的大小调整为拷贝的对象的大小。
2、将节点一个一个的创建并添加进入要拷贝给的对象中。
3、更新我们的有效数据个数
代码如下：
HashTable(const HashTable& ht) {
_table.resize(ht._table.size());
for(size_t i = 0; i < ht._table.size(); i++) {
if(ht._table[i]) {
Node* cur = ht._table[i];
while(cur) {
Node* temp = new Node(cur->_data);
temp->_next = _table[i];
_table[i] temp;
cur = cur->_next;
}
}
}
_n = ht._n;
}✍️赋值运算符重载函数
我们一般地想要实现赋值运算符重载函数，一般的是间接地调用我们之前实现的拷贝构造函数来实现，也就是传值传参之后，交换临时变量和我们的被赋值对象的成员，然后函数调用结束之后我们的原来的值也就被自动地释放掉了。
实现代码如下：
HashTable& operator=(HashTable ht) {
_table.swap(ht._table);
swap(_n, ht._n);
return *this;
}✍️析构函数
我们这里的析构主要是将我们创建出来的节点一个一个的释放掉。
~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;
}
}相关迭代器的实现
我们这里封装的主要是正向的迭代器，由于我们这里要实现++运算符的重载，所以我们这里要存储哈希表的地址，方便我们找到下一个哈希桶。
迭代器：
template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIerator {
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, keyOfT, Hash> Self;
Node* _node;
const HT* _ht;
};
💡构造函数
HTIterator(Node* node, HT* pht)
:_node(node)
, _pht(pht){}
💡解引用操作
Ref operator*() {
return _node->data;
}💡->操作
我们只要返回我们的节点指针即可
Ptr operator->() {
return &_node->_data;
}💡判断是否相等的操作
bool operator!=(const Self& s) {
return _node != s._node;
}bool operator==(const Self& s) {
return _node==s._node;
}💡重载++元算符
我们这里实现的++运算符的逻辑如下：
1、如果我们的当前节点不是当前哈希桶的最后一个节点，就++到我们哈希桶的下一个节点即可。
2、如果是当前我们哈希桶的最后一个节点了，我们就++到下一个非空哈希桶的第一个节点的位置。
3、所有的哈希桶都遍历过了，我们就给当前的位置的迭代器的指针置空即可。
4、上面的操作完毕后，返回当前对象的引用。
代码如下：
Self& operator++() {
if(_node->_next) {
_node = _node->_next;
}else {
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_table.size();
hashi++;
while(hashi < _ht->_table.size())
{
_node = _ht->_table[hashi];
if(_node) // 找到了一个非空的桶了
break;
else // 没找到继续
hashi++;
}
if(hashi == _ht->_table.size()) // 所有的桶都找完了
{
_node = nullptr;
}
}
return *this;
}
实现完了上面这几个操作之后，我们就要来实现我们的哈希表的两个中要的迭代器相关函数了：
一个是begin，一个是end。
template<class K, class T, class KeyOfT, class Hash>
class HashTable {
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HTIterator; // 友员类
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
iterator begin() {
if(_n == 0) {
return end();
}
size_t i = 0;
while(i < _table.size()) {
if(_table[i]) {
return iterator(_table[i], this);
}
}
return end();
}
iterator end() {
return iterator(nullptr, this);
}
private:
vector<Node*> _table;
size_t _n = 0;
}unoredered_map的模拟实现
#include "HashTable.h"
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};unordered_set的模拟实现
#include "HashTable.h"
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};最终实现代码
🔖哈希表的实现代码
#include <iostream>
#include <vector>
using namespace std;
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131;
}
return hash;
}
};
inline unsigned long __stl_next_prime(unsigned long n)
{
// Note: assumes long is at least 32 bits.
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
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
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 友元声明
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HTIterator;
typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;
Iterator Begin()
{
if (_n == 0)
return End();
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);
}
ConstIterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
return End();
}
ConstIterator End() const
{
return ConstIterator(nullptr, this);
}
HashTable()
:_tables(__stl_next_prime(0))
, _n(0)
{}
// 拷贝构造和赋值重载也需要
~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;
}
}
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return { it, false};
Hash hash;
// 负载因子 == 1时扩容
if (_n == _tables.size())
{
/*HashTable<K, V> newht;
newht._tables.resize(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
newht.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newht._tables);*/
vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = hash(kot(cur->_data)) % newTable.size();
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTable);
}
size_t hashi = hash(kot(data)) % _tables.size();
// 头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return { Iterator(newnode, this), false };
}
Iterator Find(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return Iterator(cur, this);
}
cur = cur->_next;
}
return End();
}
bool Erase(const K& key)
{
KeyOfT kot;
size_t hashi = key % _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;
--_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 表中存储数据个数
};🔖迭代器的实现代码
// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
Node* _node;
const HT* _ht;
HTIterator(Node* node, const HT* ht)
:_node(node)
,_ht(ht)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
// 16:46
Self& operator++()
{
if (_node->_next)
{
// 当前桶还有数据，走到当前桶下一个节点
_node = _node->_next;
}
else
{
// 当前桶走完了，找下一个不为空的桶
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];
if (_node)
break;
else
++hashi;
}
// 所有桶都走完了，end()给的空标识的_node
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
};
🔖unordered_map的实现代码
#include "HashTable.h"
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};🔖unordered_set的实现代码
#include "HashTable.h"
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert({ key, V() });
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
iterator Find(const K& key)
{
return _ht.Find(key);
}
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};更多推荐
24
0- 0
已为社区贡献6条内容
所有评论(0)