【C++复习】Map Set HashMap HashSet的模拟实现{代码分享}

1.Map && Set

RBTree.h

#pragma once
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <assert.h>
using namespace std;// 颜色枚举
enum Colour
{RED,BLACK,
};// 结点类
template <class T>
struct RBTreeNode
{RBTreeNode<T> *_left;RBTreeNode<T> *_right;RBTreeNode<T> *_parent;T _data;Colour _col;RBTreeNode(const T &data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};// 迭代器类
template <class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node *_node;// 结点构造函数RBTreeIterator(Node *node): _node(node){}RBTreeIterator(const RBTreeIterator<T, T &, T *> &it): _node(it._node){}// 重载解引用运算符Ref operator*(){return _node->_data;}// 重载成员访问运算符Ptr operator->(){return &_node->_data;}// 关系运算符bool operator!=(const Self &s){return _node != s._node;}// 自增 ++a// 一棵树 最小的[begin]在左下角 最大的在右下角// [end指向最大的后一个即null]// 自增自减运算符遍历从小到大Self &operator++(){//_node指向当前结点// 右不空if (_node->_right){// next为右子树最左节点// 右子树根节点Node *subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}// 更改指向 ++成功_node = subLeft;}// 右空: 遍历时 一个结点右空 当前结点所在子树遍历结束else{// 向上回溯--next特征:右为空的结点所在子树的上一代Node *cur = _node;Node *dad = cur->_parent;// 如果cur是父右 向上回溯// 不是父右 定是父左 循环结束// 特殊: 当遍历到最后一个结点[右下角]  一直回溯直到dad指向根时// 此时再回溯一次 dad为空 循环结束 _node指向空while (dad && cur == dad->_right){cur = dad;dad = dad->_parent;}// 更改指向 ++a成功_node = dad;}return *this;}// a++Self operator++(int){Self it(_node);++*this;return it;}// 自减//++从小到大 --从大到小 ++找次小 --找次大Self &operator--(){// 假定_node指向最后一个结点[右一定为空]if (_node->_left){// 左不空 次大为左子树最右节点Node *subRight = _node->_left;while (subRight->_right){subRight = subRight->_right;}// 更改指向 ++成功_node = subRight;}else{// 左为空 遍历时 一个结点左空 当前结点所在子树遍历结束// 向上回溯--prev特征:左为空的结点所在子树的上一代Node *cur = _node;Node *dad = cur->_parent;// 如果cp是父左 向上回溯// 不是父右 定是父左 循环结束// 特殊:当遍历到最后一个结点[左下角]  一直回溯直到dad指向根时// 此时再回溯一次 dad为空 循环结束 _node指向空while (dad && cur == dad->_left){cur = dad;dad = dad->_parent;}// 更改指向 ++成功_node = dad;}return *this;}Self operator--(int){Self it(_node);--*this;return it;}
};// 红黑树类
template <class K, class T, class GetKey>
class RBTree
{typedef RBTreeNode<T> Node;private:Node *_root = nullptr;public:typedef RBTreeIterator<T, T &, T *> itertaor;typedef RBTreeIterator<T, const T &, const T *> const_itertaor;///  迭代器  // begin迭代器[左路最后一个结点]itertaor begin(){Node *cp = _root;// 防止传入空树while (cp && cp->_left){cp = cp->_left;}return itertaor(cp);}// end迭代器[最后一个数据的下一个位置]itertaor end(){return itertaor(nullptr);}// const_begin迭代器const_itertaor begin() const{Node *cp = _root;while (cp && cp->_left){cp = cp->_left;}return const_itertaor(cp);}// const_end迭代器const_itertaor end() const{return const_itertaor(nullptr);}///  迭代器  // 查找函数Node *Find(const K &key){Node *cp = _root;GetKey get;while (cp){if (get(cp->_data) < key){cp = cp->_right;}else if (get(cp->_data) > key){cp = cp->_left;}else{return cp;}}return nullptr;}// 插入函数pair<itertaor, bool> Insert(const T &data){// 根节点为空if (_root == nullptr){_root = new Node(data);_root->_col = BLACK; // 根节点颜色为黑return make_pair(itertaor(_root), true);}// 不为空 定位至合适位置GetKey get;Node *dad = nullptr;Node *cur = _root;while (cur){if (get(cur->_data) < get(data)){dad = cur;cur = cur->_right;}else if (get(cur->_data) > get(data)){dad = cur;cur = cur->_left;}else{return make_pair(itertaor(cur), false);}}cur = new Node(data);Node *tmp = cur;if (get(dad->_data) > get(data)){dad->_left = cur;}else{dad->_right = cur;}cur->_parent = dad;// 2.构建红黑树// cur[红]此时定位新插入位置 若父存在且为红进入whilewhile (dad && dad->_col == RED){// 之后的循环来到此处 判断dad && dad->_col == RED// 父为空 则cur为根 [最后控制cur变黑] 循环结束; 父为黑 无需操作Node *grandpa = dad->_parent;// 若父为红 祖父定存在且为黑assert(grandpa && grandpa->_col == BLACK);// 2.1 判断uncle位置 分类一：父为左子树if (dad == grandpa->_left){// uncle为右子树Node *uncle = grandpa->_right;// 情况一、uncle存在为红 变色+回溯// dad-uncle变黑 grandpa变红if (uncle && uncle->_col == RED){// 变色dad->_col = uncle->_col = BLACK;grandpa->_col = RED;// 回溯cur = grandpa;dad = cur->_parent;}// 情况二-三：uncle不存在 或 存在且为黑else{if (cur == dad->_left){// 情况二：右单旋+变色RotateR(grandpa);dad->_col = BLACK;grandpa->_col = RED;}else{// 情况三：左右双旋+变色RotateL(dad);RotateR(grandpa);cur->_col = BLACK;grandpa->_col = RED;}break;}}// 2.2 判断uncle位置 父为右子树else{// uncle为左子树Node *uncle = grandpa->_left;// 情况一if (uncle && uncle->_col == RED){// 变色dad->_col = uncle->_col = BLACK;grandpa->_col = RED;// 回溯cur = grandpa;dad = cur->_parent;}else{if (cur == dad->_right){// 情况二：左单旋+变色RotateL(grandpa);dad->_col = BLACK;grandpa->_col = RED;}else{// 情况三：右左单旋+变色RotateR(dad);RotateL(grandpa);cur->_col = BLACK;grandpa->_col = RED;}break;}}}// 父不存在的情况：即该树是空树 插入的结点就是根 在该函数调用初就判断了直接把该节点变为黑即可// cur的父为黑 则不用操作_root->_col = BLACK;return make_pair(itertaor(tmp), true);}// 判断是否是红黑树bool IsRBTree(){if (_root && _root->_col == RED){cout << "根节点颜色错误!" << endl;return false;}// 事先计算出某一条路径黑色结点数量// 后续每一条路径都应和certain相等 不想等报错int certain = 0;Node *cur = _root;while (cur){if (cur->_col == BLACK)++certain;cur = cur->_left;}return PrevJudge(_root, 0, certain);}// 高度接口int Height(){return _Height(_root);}// 析构函数~RBTree(){_Destroy(_root);_root = nullptr;}private:// 后序遍历销毁红黑树void _Destroy(Node *root){if (root == nullptr){return;}_Destroy(root->_left);_Destroy(root->_right);delete root;}// 高度接口int _Height(Node *root){if (root == NULL)return 0;int leftH = _Height(root->_left);int rightH = _Height(root->_right);return leftH > rightH ? leftH + 1 : rightH + 1;}// 前序遍历判断bool PrevJudge(Node *root, int BNcount, int &certain){// 某一条路径结束if (root == nullptr){if (BNcount != certain){cout << "性质4违例: 存在某一路径黑色节点的数量不等!" << endl;return false;}return true;}// 遇黑--值++if (root->_col == BLACK){++BNcount;}// 遇红--连坐判断if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "性质3违例: 存在连续红节点!" << endl;return false;}return PrevJudge(root->_left, BNcount, certain) && PrevJudge(root->_right, BNcount, certain);}// 左旋void RotateL(Node *dad){Node *subR = dad->_right;Node *subRL = subR->_left;dad->_right = subRL;if (subRL)subRL->_parent = dad;Node *grandpa = dad->_parent;subR->_left = dad;dad->_parent = subR;if (grandpa == nullptr){_root = subR;_root->_parent = nullptr;}else{if (grandpa->_left == dad){grandpa->_left = subR;}else{grandpa->_right = subR;}subR->_parent = grandpa;}}// 右旋void RotateR(Node *dad){Node *subL = dad->_left;Node *subLR = subL->_right;dad->_left = subLR;if (subLR)subLR->_parent = dad;Node *grandpa = dad->_parent;subL->_right = dad;dad->_parent = subL;if (dad == _root){_root = subL;_root->_parent = nullptr;}else{if (grandpa->_left == dad){grandpa->_left = subL;}else{grandpa->_right = subL;}subL->_parent = grandpa;}}
};

Map.h

#pragma once
#include "RBTree.h"namespace ape
{// map类template <class K, class V>class map{// 仿函数operator() 获得keystruct GetKeyMap{const K &operator()(const pair<const K, V> &pair){return pair.first;}};private:RBTree<K, pair<const K, V>, GetKeyMap> _rbtree;public:// 迭代器均用普通迭代器// 但是传参RBTree<K, pair<const K, V>, GetKeyMap> _rbtree; 认定K为const 即只能修改Vtypedef typename RBTree<K, pair<const K, V>, GetKeyMap>::itertaor iterator;// begin迭代器iterator begin(){return _rbtree.begin();}// end迭代器iterator end(){return _rbtree.end();}// 重载下标运算符[]V &operator[](const K &key){pair<iterator, bool> pair = _rbtree.Insert(make_pair(key, V()));return pair.first->second;}// 插入函数pair<iterator, bool> insert(const pair<const K, V> &pair){return _rbtree.Insert(pair);}// 查找函数iterator find(const K &key){return _rbtree.Find(key);}// 编译器自动生成默认构造函数map() = default;// 迭代器区间构造template <class InputIterator>map(InputIterator first, InputIterator last){while (first != last){_rbtree.Insert(*first);++first;}}};/// 测试 void test_map1(){// 插入map<string, string> m;string a = "Eddie", b = "彭于晏";m.insert(make_pair(a, b));m.insert(make_pair("Tom", "汤姆"));m.insert(make_pair("Jerry", "杰瑞"));// 迭代器遍历map<string, string>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;/*it->first = "Ape";it->second = "阿猿";*/++it;}cout << endl;// for循环遍历for (auto &e : m){cout << e.first << ":" << e.second << endl;}cout << endl;}void test_map2(){string s[] = {"陀螺", "陀螺", "洋娃娃", "陀螺", "洋娃娃", "洋娃娃", "陀螺","洋娃娃", "悠悠球", "洋娃娃", "悠悠球", "乐高"};// 记录次数map<string, int> m;for (auto &e : s){m[e]++;}// for循环遍历for (auto &e : m){cout << e.first << ":" << e.second << endl;}}
}

Set.h

#pragma once
#include "RBTree.h"
namespace ape
{// set类template <class K>class set{// 仿函数operator() 获得keystruct GetKeySet{const K &operator()(const K &key){return key;}};private:RBTree<K, K, GetKeySet> _rbtree;public:/// ///  迭代器  /typedef typename RBTree<K, K, GetKeySet>::const_itertaor iterator; // 普通迭代器也定义为const迭代器typedef typename RBTree<K, K, GetKeySet>::const_itertaor const_iterator;// begin迭代器iterator begin(){return _rbtree.begin();}// end迭代器iterator end(){return _rbtree.end();}// 插入pair<iterator, bool> insert(const K &key){return _rbtree.Insert(key);}// 编译器自动生成默认构造函数set() = default;// 迭代器区间构造template <class InputIterator>set(InputIterator first, InputIterator last){while (first != last){_rbtree.Insert(*first);++first;}}iterator find(const K &k){return _rbtree.Find(k);}};/// 测试 void test_set(){// 插入int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};set<int> s;for (auto e : a){s.insert(e);}// 迭代器遍历set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;// for循环遍历for (auto e : s){cout << e << " ";}cout << endl;}
}

main.cc

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <functional>
using namespace std;#include "RBTree.h"
#include "Map.h"
#include "Set.h"/* pair
//类模板: pair
template <class T1, class T2>
struct pair
{T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){}
};//函数模板: make_pair
template <class T1, class T2> 
pair<T1, T2> make_pair(const T1& x, const T2& y)
{pair<T1, T2> pair(x, y);return pair;
}
*/int main()
{ape::test_set();ape::test_map2();return 0;
}

2.HashMap && HashSet

HashTable_Test.h

#include <iostream>
#include <vector>
#include <functional>
#include <utility>
#include <cassert>
using namespace std;// 闭散列/开放地址法
namespace OpenAddressing
{// 状态枚举enum State{EMPTY,EXIST,DELETE};// 哈希数据元素template <class K, class V>struct HashData{pair<K, V> _pair;State _state = EMPTY;};// 哈希表template <class K, class V>class HashTable{private:vector<HashData<K, V>> _tables;size_t _n = 0; // 存储的数据个数public:// 插入函数bool Insert(const pair<K, V> &pair){// 值已存在 插入错误if (Find(pair.first))return false;// 负载因子/荷载系数 -- Load_Factor = _n / _tables.size();//(double)_n / (double)_tables.size() >= 0.7//_n * 10 / _tables.size() >= 7// 使得扩容发生的条件: size为0 负载因子达到阈值if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7){/ 低级代码 //*//先更新size 由size作为参数扩容 解决只改容量 不更新访问范围的问题size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//调用vector的有参构造[有参构造里调用reserve] 创建一个新表vector<HashData<K,V>> newtables(newsize);//遍历旧表  由哈希函数更新数据位置for (auto& e :  _tables){if (e._state == EXIST){//哈希函数计算出的下标size_t hashi = pair.first % newtables.size();//重新线性探测size_t index = hashi;//index代替hashi进行操作 保留原始hashi的值不变for (size_t i = 1; newtables[index]._state == EXIST; ++i){index = hashi + i;        //从原始下标不断 +1 +2 +3 ...index %= newtables.size();//防止越界 只在表内定位index}//将数据放入合适位置newtables[index]._pair = e._pair;newtables[index]._state = EXIST;}}//新表的数据才是我们想要的数据 交换后 newtables中存放的变为旧数据//newtables是个局部变量 让其"自生自灭"_tables.swap(newtables);*///  高级代码 //size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> other;other._tables.resize(newsize);for (auto &e : _tables){if (e._state == EXIST)other.Insert(e._pair);}_tables.swap(other._tables);/// 以上高级代码实际是对下面的线性探测进行了复用}// 哈希函数计算出的下标size_t hashi = pair.first % _tables.size();// 线性探测size_t index = hashi; // index代替hashi进行操作 保留原始hashi的值不变for (size_t i = 1; _tables[index]._state == EXIST; ++i){index = hashi + i;       // 从原始下标不断 +1 +2 +3 ...index %= _tables.size(); // 防止越界 只在表内定位index}// 将数据放入合适位置_tables[index]._pair = pair;_tables[index]._state = EXIST;_n++; // 数据个数++return true;}// 查找函数HashData<K, V> *Find(const K &key){// 哈希表为空 返回nullptrif (_tables.size() == 0)return nullptr;// 哈希函数计算出的下标size_t hashi = key % _tables.size();// 线性探测size_t index = hashi;for (size_t i = 1; _tables[index]._state != EMPTY; ++i){// obj是key的前提是obj存在if (_tables[index]._state == EXIST && _tables[index]._pair.first == key){return &_tables[index];}index = hashi + i;index %= _tables.size();// 当表中元素状态非exist即delete时// for循环判断条件一直为真 死循环// 解决: 当找了一圈还未找到// 表中无此key 返回falseif (index == hashi)break;}return nullptr;}// 删除函数bool Erase(const K &key){HashData<K, V> *pos = Find(key);if (pos){pos->_state = DELETE;--_n; // 虽然已标记删除 仍然要使数据个数减减 防止有用数据未达到阈值就执行扩容return true;}elsereturn false;}};//  测试函数  ///void TestHashTable(){int a[] = {3, 33, 2, 13, 5, 12, 1002};HashTable<int, int> ht;// 插入for (auto &e : a)ht.Insert(make_pair(e, e));// 插入第8个数据 达到阈值  测试扩容ht.Insert(make_pair(15, 15));// 查找 + 删除int tmp = 12;if (ht.Find(tmp))cout << tmp << "在" << endl;elsecout << tmp << "不在" << endl;ht.Erase(tmp);if (ht.Find(tmp))cout << tmp << "在" << endl;elsecout << tmp << "不在" << endl;}
}// 开散列/链地址法
namespace ChainAddressing
{// 结点类template <class K, class V>struct HashNode{HashNode<K, V> *_next;pair<K, V> _pair;HashNode(const pair<K, V> &pair): _next(nullptr), _pair(pair){}};// 哈希函数类template <class K>struct hash{size_t operator()(const K &key){return key;}};template <>struct hash<string>{size_t operator()(const string &s){size_t value = 0;for (auto ch : s){value = value * 131 + ch;}return value;}};struct StringToInt{size_t operator()(const string& s){//问题代码://return s[0];//1.如果传空串 违背使用者意愿//2.不同单词相同首字母均会哈希冲突 不太合适 //代码改进size_t value = 0;for (auto& ch : s){value = value * 131 + ch;}return value;}};// 哈希表类template <class K, class V, class Hash = hash<K>>class HashTable{typedef HashNode<K, V> Node;private:vector<Node *> _tables; // 指针数组size_t _n = 0;          // 存储有效数据个数public:// 析构函数~HashTable(){for (auto &ptr : _tables){while (ptr){// 记录下一个结点Node *next = ptr->_next;// 释放当前结点delete ptr;// 更新ptrptr = next;}ptr = nullptr;}}// 查找函数Node *Find(const K &key){// 为空不查找 返回nullptrif (_tables.size() == 0)return nullptr;// 哈希函数计算的下标size_t hashi = key % _tables.size();// 首先得到表里的指针 即相当于每一个桶的头指针//[实际上 每一个桶就是一个链表 表中的ptr是每一个链表的哨兵指针]Node *ptr = _tables[hashi];while (ptr){if (ptr->_pair.first == key)return ptr;ptr = ptr->_next;}return nullptr;}// 删除函数bool Erase(const K &key){// 哈希函数计算的下标size_t hashi = key % _tables.size();// 首先得到表里的指针 即相当于每一个桶的头指针//[实际上 每一个桶就是一个链表 表中的ptr是每一个链表的哨兵指针]Node *ptr = _tables[hashi];Node *prv = nullptr;while (ptr){// 当前值为目标值 执行删除操作if (ptr->_pair.first == key){if (prv == nullptr)_tables[hashi] = ptr->_next;elseprv->_next = ptr->_next;delete ptr;return true;}// 当前值不为目标值 继续向下遍历else{prv = ptr;ptr = ptr->_next;}}return false;}// 插入函数bool Insert(const pair<K, V> &pair){// 表中已有 返回falseif (Find(pair.first))return false;Hash hash;// 负载因子/荷载系数 -- Load_Factor = _n / _tables.size();// 负载因子 == 1时 扩容+更新数据if (_n == _tables.size()){///  高级代码1.0  //*size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht.resize(newsize);for (auto& ptr : _tables){while (ptr){newht.Insert(ptr->_pair);ptr = ptr->_next;}}_tables.swap(newht._tables);*/// 引进stl库素数思想// size_t newsize = GetNextPrime(_tables.size());size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node *> newtables(newsize, nullptr);// 遍历旧表 取出旧表里每一个指针for (auto &ptr : _tables){// ptr是旧表里存储的每一个指针// 它指向当前哈希桶的首结点 即他存储的是首结点的地址while (ptr){// 算出 当前结点根据新哈希函数计算的新下标size_t hashi = hash(ptr->_pair.first) % newtables.size();// ptr是首结点的地址 ptr->_next为第二个结点的地址Node *next = ptr->_next;// 头插到新表ptr->_next = newtables[hashi];newtables[hashi] = ptr;// 更新ptr 即向下遍历ptr = next;}}_tables.swap(newtables);}// 哈希函数计算出的下标size_t hashi = hash(pair.first) % _tables.size();// 链表头插Node *newnode = new Node(pair);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}// 最大桶数据个数size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto ptr = _tables[i];size_t size = 0;while (ptr){++size;ptr = ptr->_next;}// 每个桶数据个数// printf("[%d] -> %d\n", i, size);if (size > max)max = size;}return max;}size_t GetNextPrime(size_t index){static const int num = 28;static const unsigned long prime[num] = {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};size_t i = 0;for (i = 0; i < num; ++i){if (prime[i] > index)return prime[i];}return prime[i];}};// 测试函数void TestHashTable1(){int a[] = {3, 33, 2, 13, 5, 12, 1002};HashTable<int, int> ht;for (auto &e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(15, 15));ht.Insert(make_pair(25, 25));ht.Insert(make_pair(35, 35));ht.Insert(make_pair(45, 45));}void TestHashTable2(){int a[] = {3, 33, 2, 13, 5, 12, 1002};HashTable<int, int> ht;for (auto &e : a){ht.Insert(make_pair(e, e));}ht.Erase(12);ht.Erase(3);ht.Erase(33);}// 字符串问题void TestHashTable3(){// 不实现类模板特化 显示传StringToInt// HashTable<string, string, StringToInt> ht;// 使用类模板特化 不需要显示传 更符合大佬设计的底层哈希HashTable<string, string> ht;ht.Insert(make_pair("Kevin", "凯文"));ht.Insert(make_pair("Eddie", "彭于晏"));ht.Insert(make_pair("Tom", "汤姆"));ht.Insert(make_pair("Jerry", "杰瑞"));ht.Insert(make_pair("", "null_string"));}// 性能测试void TestHashTable4(){size_t N = 900000;HashTable<int, int> ht;srand(time(0));for (size_t i = 0; i < N; ++i){size_t x = rand() + i;ht.Insert(make_pair(x, x));}cout << "最大桶数据个数" << ht.MaxBucketSize() << endl;}
}

HashTable.h

#pragma once#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <assert.h>
using namespace std;// 转换函数
template <class K>
struct HashFunc
{size_t operator()(const K &key){return key;}
};
template <>
struct HashFunc<string>
{size_t operator()(const string &s){size_t value = 0;for (auto ch : s){value = value * 131 + ch;}return value;}
};// 开散列/链地址法
namespace ChainAddressing
{// STL库中unordered_map/unordered_set的定义/* template<class Key,class T,class Hash = hash<Key>,class Pred = equal_to<Key>,class Alloc = allocator< pair<const Key,T> >>class unordered_map;class unordered_set;*/// 结点类template <class T>struct HashNode{T _data;HashNode<T> *_next;HashNode(const T &data): _next(nullptr), _data(data){}};///  迭代器// 哈希表前置声明template <class K, class T, class GetKey, class Hash>class HashTable;// 迭代器类template <class K, class T, class Ref, class Ptr, class GetKey, class Hash>struct HashIterator{typedef HashNode<T> Node;typedef HashTable<K, T, GetKey, Hash> HT;typedef HashIterator<K, T, Ref, Ptr, GetKey, Hash> Self;typedef HashIterator<K, T, T &, T *, GetKey, Hash> Iterator;// 成员属性Node *_node;const HT *_ht;// 构造函数HashIterator(Node *node, const HT *ht): _node(node), _ht(ht){}// 特殊构造函数HashIterator(const Iterator &it): _node(it._node), _ht(it._ht){}// 解引用运算符Ref operator*(){return _node->_data;}// 成员访问运算符Ptr operator->(){return &_node->_data;}// 关系运算符bool operator!=(const Self &s){return _node != s._node;}// 前置 ++aSelf &operator++(){// 下个结点不空 向下++即可if (_node->_next != nullptr){_node = _node->_next;}// 下个结点为空else{GetKey get;Hash hash;// 当前数据的哈希下标size_t hashi = hash(get(_node->_data)) % _ht->_tables.size();// 下个结点为空 说明当前桶已空 找下一个非空桶++hashi;// 找非空桶时 肯定不能越过哈希表while (hashi < _ht->_tables.size()){//_ht->_tables[hashi] :// 取出的是表中的ptr 指向桶中首结点指针[如果存在的话]if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else++hashi;}// while循环结束情况:// 1.不满足循环条件 hashi == _ht->_tables.size()//  即找完整个表 都没有找到非空桶 即当前桶之后的桶全为空// 2._ht->_tables[hashi]不为空 找到了 break出来了// 面对上述情况 只需对第一种情况操作 即桶均空 ++失败 表中已无数据 返回空指针if (hashi == _ht->_tables.size())_node = nullptr;}return *this;}};///// 哈希表类template <class K, class T, class GetKey, class Hash>class HashTable{typedef HashNode<T> Node;template <class U, class V, class Ref, class Ptr, class GetKEY, class HASH>friend struct HashIterator;private:vector<Node *> _tables; // 指针数组size_t _n = 0;			// 存储有效数据个数public:typedef HashIterator<K, T, T &, T *, GetKey, Hash> iterator;typedef HashIterator<K, T, const T &, const T *, GetKey, Hash> const_iterator;// 迭代器iterator begin(){Node *ptr = nullptr;for (size_t i = 0; i < _tables.size(); ++i){ptr = _tables[i];if (ptr)break;}return iterator(ptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin() const{Node *ptr = nullptr;for (size_t i = 0; i < _tables.size(); ++i){ptr = _tables[i];if (ptr)break;}return const_iterator(ptr, this);}const_iterator end() const{return const_iterator(nullptr, this);}// 析构函数~HashTable(){for (auto &ptr : _tables){while (ptr){// 记录下一个结点Node *next = ptr->_next;// 释放当前结点delete ptr;// 更新ptrptr = next;}ptr = nullptr;}}// 查找函数iterator Find(const K &key){if (_tables.size() == 0)return end();GetKey get;Hash hash;size_t hashi = hash(key) % _tables.size();Node *ptr = _tables[hashi];while (ptr){if (get(ptr->_data) == key)return iterator(ptr, this);ptr = ptr->_next;}return end();}// 删除函数bool Erase(const K &key){Hash hash;GetKey get;size_t hashi = hash(key) % _tables.size();Node *prv = nullptr;Node *ptr = _tables[hashi];while (ptr){if (get(ptr->_data) == key){if (prv == nullptr)_tables[hashi] = ptr->_next;elseprv->_next = ptr->_next;delete ptr;return true;}else{prv = ptr;ptr = ptr->_next;}}return false;}size_t GetNextPrime(size_t index){static const int num = 28;static const unsigned long prime[num] ={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};size_t i = 0;for (i = 0; i < num; ++i){if (prime[i] > index)return prime[i];}return prime[i];}// 插入函数pair<iterator, bool> Insert(const T &data){GetKey get;iterator it = Find(get(data));if (it != end())return make_pair(it, false);Hash hash;// 负载因子/荷载系数 -- Load_Factor = _n / _tables.size();// 负载因子 == 1时扩容if (_n == _tables.size()){///  高级代码1.0  //*size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V> newht;newht.resize(newsize);for (auto& ptr : _tables){while (ptr){newht.Insert(ptr->_pair);ptr = ptr->_next;}}_tables.swap(newht._tables);*/// 初代扩容size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;// 引进stl库素数思想// size_t newsize = GetNextPrime(_tables.size());vector<Node *> newtables(newsize, nullptr);// 遍历旧表 取出旧表里每一个指针for (auto &ptr : _tables){// ptr是旧表里存储的每一个指针// 它指向当前哈希桶的首结点 即他存储的是首结点的地址while (ptr){// 算出 当前结点根据新哈希函数计算的新下标size_t hashi = hash(get(ptr->_data)) % newtables.size();// ptr是首结点的地址 ptr->_next为第二个结点的地址Node *next = ptr->_next;// 头插到新表ptr->_next = newtables[hashi];newtables[hashi] = ptr;// 更新ptr 即向下遍历ptr = next;}}_tables.swap(newtables);}// 哈希函数计算出的下标size_t hashi = hash(get(data)) % _tables.size();// 链表头插Node *newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), false);}// 最大桶数据个数size_t MaxBucketSize(){size_t max = 0;for (size_t i = 0; i < _tables.size(); ++i){auto ptr = _tables[i];size_t size = 0;while (ptr){++size;ptr = ptr->_next;}// 每个桶数据个数printf("[%ld] -> %ld\n", i, size);if (size > max)max = size;}return max;}};
}

Unordered_Map.h

#pragma once
#include "HashTable.h"namespace ape
{template <class K, class V, class Hash = HashFunc<K>>class unordered_map{public:// 获得keystruct MapGetKey{const K &operator()(const pair<K, V> &pair){return pair.first;}};private:public:ChainAddressing::HashTable<K, pair<const K, V>, MapGetKey, Hash> _ht;public:typedef typename ChainAddressing::HashTable<K, pair<const K, V>, MapGetKey, Hash>::iterator iterator;typedef typename ChainAddressing::HashTable<K, pair<const K, V>, MapGetKey, Hash>::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> &pair){return _ht.Insert(pair);}// 下标运算符V &operator[](const K &key){pair<iterator, bool> pair = insert(make_pair(key, V()));return pair.first->second;}// 查找iterator find(const K &key){return _ht.Find(key);}// 删除bool erase(const K &key){return _ht.Erase(key);}};void test_unordered_map1(){unordered_map<int, int> m;m.insert(make_pair(1, 1));m.insert(make_pair(3, 3));m.insert(make_pair(2, 2));unordered_map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void test_unordered_map2(){string s[] = {"西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨"};unordered_map<string, int> um;for (auto &e : s){um[e]++;}for (auto &pair : um){cout << pair.first << ":" << pair.second << endl;}}class Date{friend struct HashDate;friend ostream &operator<<(ostream &_cout, const Date &d);public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date &d) const{return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date &d) const{return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day);}bool operator==(const Date &d) const{return _year == d._year && _month == d._month && _day == d._day;}private:int _year;int _month;int _day;};ostream &operator<<(ostream &_cout, const Date &d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}struct HashDate{size_t operator()(const Date &d){size_t value = 0;value += d._year;value *= 131;value += d._month;value *= 131;value += d._day;value *= 131;return value;}};void test_unordered_map4(){Date d1(2023, 10, 1);Date d2(2023, 10, 5);Date d3(2023, 10, 2);Date d4(2023, 10, 2);Date d5(2023, 10, 2);Date d6(2023, 10, 1);Date a[] = {d1, d2, d3, d4, d5, d6};unordered_map<Date, int, HashDate> um;for (auto e : a){um[e]++;}for (auto &pair : um){cout << pair.first << ":" << pair.second << endl;}}// 测试unordered_map性能 哈希桶最大个数void test_unordered_map5(){unordered_map<int, int> m;// 插入100万随机数srand(time(NULL));for (int i = 0; i < 1000000; ++i){m.insert(make_pair(rand(), rand()));}size_t max =  m._ht.MaxBucketSize();cout << max << endl;}
}

Unordered_Set.h

#pragma once
#include "HashTable.h"namespace ape
{template <class K, class Hash = HashFunc<K>>class unordered_set{public:// 获得keystruct SetGetKey{const K &operator()(const K &key){return key;}};private:ChainAddressing::HashTable<K, K, SetGetKey, Hash> _ht;public:typedef typename ChainAddressing::HashTable<K, K, SetGetKey, Hash>::const_iterator iterator;typedef typename ChainAddressing::HashTable<K, K, SetGetKey, Hash>::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 K &key){return _ht.Insert(key);}// 查找iterator find(const K &key){return _ht.Find(key);}// 删除bool erase(const K &key){return _ht.Erase(key);}};// 打印函数void print(const unordered_set<int> &s){unordered_set<int>::const_iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;}// 测试函数void test_unordered_set(){int a[] = {3, 33, 2, 13, 5, 12, 1002};unordered_set<int> s;for (auto e : a)s.insert(e);s.insert(54);s.insert(107);unordered_set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s)cout << e << " ";cout << endl;print(s);}
}

main.cc

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#include <array>
#include <time.h>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <assert.h>
using namespace std;#include "HashTable.h"
#include "Unordered_Map.h"
#include "Unordered_Set.h"int main()
{//ape::test_unordered_set();ape::test_unordered_map5();return 0;
}