【C++】unordered_map与set的模拟实现

unordered系列map和set，与普通区别

用法几乎相同，键值唯一，区别unordered系列迭代器是单向的并且遍历出来不是有序的。unordered系列在数据规模大且无序的情况下性能更优

底层实现：

map 和 set ：基于平衡二叉树（通常是红黑树）实现，元素在树中按有序的方式存储。
unordered_map 和 unordered_set ：基于哈希表实现，元素存储在哈希桶中，存储顺序与插入顺序无关。是通过哈希函数将键（或元素）映射到哈希表的桶索引

有序性：

map和set:有序，可按自定义排序规则
unordered：无序，存储顺序取决于哈希函数和哈希桶的分配。

适用场景

map 和 set ：适用于需要元素有序的场景，如排序、范围查询等unordered_map 和 unordered_set ：适用于需要快速插入和查找的场景，对元素的顺序没有要求。

1.哈希表改造

按照以下思路进行模拟实现
1、改装哈希表(哈希桶)
2、封装map和set
3、实现普通迭代器
4、实现const迭代器
5、解决insert返回值问题 实现operator[]
6、解决key不能修改的问题

节点定义

用一个模板参数T来表示数据，unordered_set为key，map为pair<K,V>，实现了泛型。

1.2增加迭代器

基本模板

总共有6个模板参数，K代表键值，T代表value值类型能实现map和set的泛型，Ptr是指针类型，Ref是引用类型，KeyOfT是用于从值中获取键值的函数，HashFunc是哈希函数将键值映射到地址上去
1.重定义一个self通用迭代器，模板参数为Ptr和Ref可以灵活地定义指针和引用类型，通常用于类的内部实现，引用或返回值。
2.重定义一个具体的迭代器iterator，其中指针类型和引用类型都被写死与T相同，是用于读写访问的迭代器，可以对容器中的元素进行修改。
3.需定义一个哈希表指针，因为自增操作时可以通过该指针方便遍历找到下一个哈希桶的位置。有如下作用：

a：提供对哈希表资源的访问。如哈希桶数组 _table、哈希函数 hf 和键提取函数 kot
b： 封装哈希表的实现细节。使哈希表的内部实现可以在不改变迭代器代码的情况下进行修改。

构造函数

1.将哈希表指针定义成const，因为在const迭代器begin和end函数中返回的this指针是const的，普通指针传进来也没问题，因为权限可以缩小不能放大，所以直接定义成const省略掉普通哈希表指针的迭代器构造
2.与set和map模拟实现中类似，一举两得，解决了返回值中非const的迭代器转化成const迭代器的过程。因为iterator的指针和引用参数写死了，就是常量。

自增++操作

self& operator++()
{if (_node->_next){//当前桶还没完，继续往下遍历_node = _node->_next;}else{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();//从下一个位置寻找hashi++;while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){_node = _pht->_table[hashi];return *this;}else{hashi++;}}//找完了没找到哈希桶_node = nullptr;}return *this;
}

1.返回对当前迭代器对象的引用（self&），以便支持连续的自增操作
2.分当前桶中继续往下遍历和查找下一个哈希桶中两种情况
3.查找下一个哈希桶时先用获取键kot函数拿到键值然后用哈希函数hf计算该键的映射哈希值。从下一个哈希桶的位置开始找不为空的哈希桶，循环条件为哈希值索引小于当前已存储桶的大小，若找到不为空哈希桶返回this指针，没找到对当前_node置空再返回this指针

前置声明

由于上图中存在相互包含问题，需要前置声明。
注意：编译器需要完整的类型定义来确定内存布局、调用成员函数和生成正确的机器码。前向声明只能用于指针和引用类型，因为这些类型不需要完整的类型信息。在需要直接实例化对象或调用成员函数时，必须包含完整的类型定义。
所以选择前向声明哈希表指针

• 完整代码

//前置声明
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{typedef HashNode<T> Node;typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc> self;typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;Node* _node;const HashTable<K, T, KeyOfT, HashFunc>* _pht;HTIterator(Node* node,const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){ }// 普通迭代器时，他是拷贝构造// const迭代器时，他是构造HTIterator(const iterator& it):_node(it._node), _pht(it._pht){ }Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){if (_node->_next){//当前桶还没完，继续往下遍历_node = _node->_next;}else{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();//从下一个位置寻找hashi++;while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){_node = _pht->_table[hashi];return *this;}else{hashi++;}}//找完了没找到哈希桶_node = nullptr;}return *this;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}
};

1.3哈希表基本模板

模板参数与模板重定义和迭代器的相同，注意要加上迭代器的友元声明，在迭代器中会访问哈希表中的私有变量

获取迭代器

iterator begin()
{//找第一个桶for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur){return iterator(cur, this);}}return iterator(nullptr, this);
}iterator end()
{return iterator(nullptr, this);
}const_iterator begin()const
{//找第一个桶for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur){return const_iterator(cur, this);}}return const_iterator(nullptr, this);
}const_iterator end()const
{return const_iterator(nullptr, this);
}

注意迭代器是由当前节点和哈希表指针构成，末尾迭代器返回空指针和this指针。

构造与析构函数

HashTable()
{_table.resize(10, nullptr);
}~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;}
}

resize开辟和初始化空间为空，由于vector数组中每个位置都存储着链表头指针，自定义类型需要手动释放空间

插入

pair<iterator,bool> Insert(const T&data)
{KeyOfT kot;iterator it=Find(kot(data));if(it!=end()){return make_pair(it,false);}HashFunc hf;//检查扩容，载荷因子到1就扩容if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);//遍历旧表，将节点转移挂到新表for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];//在数组中向下遍历处理每一个哈希桶while (cur){size_t hashi = hf(kot(data)) % newsize;Node* next = cur->_next;//头插cur->_next = newtable[hashi];newtable[hashi] = cur;//更新节点cur = next;}_table[i] = nullptr;}//交换新旧表_table.swap(newtable);}//插入新节点size_t hashi = hf(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);
}

1.创建一个提取键对象，可以像函数一样调用
2.检查待插入元素是否已存在
3.定义一个哈希函数对象，重载了()也可以像函数一样被调用
4.检查扩容，与原哈希表逻辑相同
5.重新计算哈希值再创建新节点并插入，更新有效值元素，返回一个由迭代器和bool值构成的键值对

由于unordered_map的[]重载需要通过insert实现，需要提供对指定键的值的访问，如果键不存在，则需要插入一个默认构造的值。所以insert的返回值要变成键值对

查找

iterator Find(const K& key)
{KeyOfT kot;HashFunc hf;size_t hashi = hf(key) % _table.size();//在该哈希桶中遍历寻找Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur,this);}cur = cur->_next;}return end();
}

与原哈希表区别在于返回值变成迭代器

删除

bool Erase(const K& key)
{HashFunc hf;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){//判断要删除节点为头节点情况if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}--_n;delete cur;return true;}//更新节点继续遍历prev = cur;cur = cur->_next;}return false;
}

与原哈希表相同

哈希函数

template<class K>
struct DefaultHashFunc
{size_t operator()(const K& key){//强转成返回值类型return (size_t)key;}
};
//模板特化
template<>
struct DefaultHashFunc<string>
{size_t operator()(const string& str){// BKDR,string的哈希算法size_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}
};

与原哈希表相同

• 代码

template<class K>
struct DefaultHashFunc
{size_t operator()(const K& key){//强转成返回值类型return (size_t)key;}
};
//模板特化
template<>
struct DefaultHashFunc<string>
{size_t operator()(const string& str){// BKDR,string的哈希算法size_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}
};namespace hash_bucket
{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 HashFunc>class HashTable;template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>struct HTIterator{typedef HashNode<T> Node;typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashFunc> self;typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;Node* _node;const HashTable<K, T, KeyOfT, HashFunc>* _pht;HTIterator(Node* node,const HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){ }// 普通迭代器时，他是拷贝构造// const迭代器时，他是构造HTIterator(const iterator& it):_node(it._node), _pht(it._pht){ }Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}self& operator++(){if (_node->_next){//当前桶还没完，继续往下遍历_node = _node->_next;}else{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();//从下一个位置寻找hashi++;while (hashi < _pht->_table.size()){if (_pht->_table[hashi]){_node = _pht->_table[hashi];return *this;}else{hashi++;}}//找完了没找到哈希桶_node = nullptr;}return *this;}bool operator!=(const self& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};// set -> hash_bucket::HashTable<K, K> _ht;// map -> hash_bucket::HashTable<K, pair<K, V>> _ht;template<class K, class T,class KeyOfT, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<T> Node;//友元声明template<class K, class T,class Ptr,class Ref, class KeyOfT, class HashFunc>friend struct HTIterator;public:typedef HTIterator<K, T,T*,T&, KeyOfT, HashFunc> iterator;typedef HTIterator<K, T,const T*,const T&, KeyOfT, HashFunc> const_iterator;iterator begin(){//找第一个桶for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur){return iterator(cur, this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{//找第一个桶for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];if (cur){return const_iterator(cur, this);}}return const_iterator(nullptr, this);}const_iterator end()const{return const_iterator(nullptr, this);}HashTable(){_table.resize(10, nullptr);}~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){KeyOfT kot;iterator it=Find(kot(data));if(it!=end()){return make_pair(it,false);}HashFunc hf;//检查扩容，载荷因子到1就扩容if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable;newtable.resize(newsize, nullptr);//遍历旧表，将节点转移挂到新表for (size_t i = 0; i < _table.size(); i++){Node* cur = _table[i];//在数组中向下遍历处理每一个哈希桶while (cur){size_t hashi = hf(kot(data)) % newsize;Node* next = cur->_next;//头插cur->_next = newtable[hashi];newtable[hashi] = cur;//更新节点cur = next;}_table[i] = nullptr;}//交换新旧表_table.swap(newtable);}//插入新节点size_t hashi = hf(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);}iterator Find(const K& key){KeyOfT kot;HashFunc hf;size_t hashi = hf(key) % _table.size();//在该哈希桶中遍历寻找Node* cur = _table[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur,this);}cur = cur->_next;}return end();}bool Erase(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){//判断要删除节点为头节点情况if (prev == nullptr){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}--_n;delete cur;return true;}//更新节点继续遍历prev = cur;cur = cur->_next;}return false;}void Print(){for (size_t i = 0; i < _table.size(); i++){printf("[%d]->", i);Node* cur = _table[i];while (cur){cout << cur->_kv.first << ":" << cur->_kv.second << "->";cur = cur->_next;}printf("NULL\n");}cout << endl;}private:vector<Node*> _table;//指针数组size_t _n = 0;};
}

• 测试代码

#include<iostream>
using namespace std;
#include"HashTable.h"#include"UnOrderedSet.h"
#include"UnOrderedMap.h"int main(){ee::unordered_set<int> us;us.insert(3);us.insert(1);us.insert(3);us.insert(4);us.insert(5);us.insert(0);ee::unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 10;不能修改keycout << *it << " ";++it;}cout << endl;ee::unordered_map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("insert", "插入"));dict.insert(make_pair("sort", "xxx"));ee::unordered_map<string, string>::iterator dit = dict.begin();while (dit != dict.end()){//不能修改key//dit->first += 'e';dit->second += 'e';cout << dit->first << ":" << dit->second << endl;++dit;}dict["sort"] = "排序";dict["insert"] = "插入";dict["string"] = "字符串";dict["left"];for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}return 0;}

2.封装unordered_set

#pragma once
namespace ee
{template<class K>struct unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;//迭代器底层都是const，直接定义成const即可const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}pair<const_iterator,bool> insert(const K& key){//return _ht.Insert(key);编译器严格检查下可能报错pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);return pair<const_iterator, bool>(ret.first, ret.second);}private:hash_bucket::HashTable<K, K, SetKeyOfT> _ht;};
}

迭代器底层都是const_iterator(确保键值不能修改)，会造成返回值类型不匹配，与map和set的模拟实现一样，这里解决办法相同，先用哈希表中迭代器接收插入后的返回值普通迭代器，利用在哈希表中写的支持非const转化为const迭代器的函数来构造出const迭代器并返回。

3.封装unordered_map

#pragma once
namespace ee
{template<class K,class V>struct unordered_map{struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT>::iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}const_iterator begin()const{return _ht.begin();}const_iterator end()const{return _ht.end();}pair<iterator,bool> insert(const pair<K,V>& kv){return _ht.Insert(kv);}V& operator[](const K&key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:hash_bucket::HashTable<K, pair<const K,V>, MapKeyOfT> _ht;};
}

这里插入就不会有set的迭代器返回值类型不匹配的问题，常量迭代器和普通迭代器底层就是其本身。
[]重载：
返回值 ：返回类型为 V&，即键对应的值的引用。如果键不存在，则插入一个默认构造的值并返回其引用。
Insert 方法 ：尝试将键值对插入哈希表。如果键已存在，Insert 返回一个 pair，其中迭代器指向已存在的键值对，bool 值为 false；如果键不存在，Insert 插入键值对并返回一个 pair，其中迭代器指向新插入的键值对,bool 值为 true。
返回值引用 ：ret.first->second 返回键值对中值的引用。无论键是否已存在，都能通过这个引用访问或修改值。