一、unordered系列容器的底层结构 - 哈希

1. 哈希概念

• 引入：
  顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。

  尽管平衡二叉搜索树的查找方式已经很快了，但我们仍然认为该方法不够极致，理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构，通过某种函数(HashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

• 插入元素
  根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素
  对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希方法（或散列法），哈希方法中使用的转换函数称为哈希函数（或散列函数），构造出来的结构称为哈希表(Hash Table)（或散列表）

[!Example] 例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity
（capacity为存储元素底层空间总的大小)

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？发现该位置已经有元素，这就是哈希冲突。

2. 哈希冲突

对于两个数据元素的关键字$k_i$和$k_j$ (i != j)，有$k_i$ != $k_j$
但有：Hash($k_i$) == Hash($k_j$)
即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

哈希冲突指的是：不同的输入数据经过哈希函数计算后，产生了相同的哈希值。当两个或多个不同的输入数据生成相同的哈希值时，就发生了哈希冲突。

由于哈希函数将无限的输入域映射到有限的输出域，所以在理论上，哈希冲突是不可避免的。好的哈希函数应该尽量减少哈希冲突的概率，使其发生的概率非常低。如果哈希冲突的概率过高，将会降低哈希函数的效率和可靠性，因为哈希冲突可能会导致数据的错误匹配或冲突。

二、解决哈希冲突

引起哈希冲突的一个原因可能是：哈希函数设计不够合理

方法一：合理设计哈希函数

🚩哈希函数设计原则

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

🚩常见哈希函数

1. 直接定址法 (常用)
   取关键字的某个线性函数为散列地址：$Hash（Key）=A\ast Key+B$
   优点：简单、均匀
   缺点：需要事先知道关键字的分布情况
   使用场景：适合查找比较小且连续的情况

   下面这道题是哈希直接定址法的典型例子：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution
{
public:int firstUniqChar(string s){int countA[26]={0};for(auto ch:s){countA[ch-'a']++;}for(int i=0;i<s.size();i++){if(countA[s[i]-'a']==1){return i;}}return -1;}
};

2. 除留余数法 (常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：$Hash(key)=key(mod)p$，(其中 mod 是取余操作)，将关键码转换成哈希地址

3. 平方取中法 (了解)
   哈希函数：$Hash(key)=(ke{y}^2>>r)$ 按位与 (m−1)
   （其中 >> 是右移操作，r 是一个常数，通常选取为关键字位数的一半）
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
   再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
   平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

4. 折叠法 (了解)
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
   折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

5. 随机数法 (了解)
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
   通常应用于关键字长度不等时采用此法

6. 数学分析法 (了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：
   假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。
   数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

方法二：开闭散列

🚩闭散列

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “下一个” 空位置中去；那如何寻找下一个空位置呢？有两种方法 – 线性探测法和二次探测法。

线性探测法（实现）

线性探测是从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

1. 基本骨架

#pragma once
#include <vector>template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 闭散列
namespace chen
{enum Status{EMPTY,EXIST,DELETE};template<class K,class V>struct HashData{pair<K, V> _kv;Status _s;       //状态};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(){_tables.resize(10);}// 插入bool Insert(const std::pair<K, V>& kv) { ... }// 查找HashData<K,V>* Find(const K& key) { ... }// 删除bool Erase(const K& key) { ... }void Print(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;}else if (_tables[i]._s == EMPTY){printf("[%ud]->\n", i);}else{printf("[%ud]->D\n", i);}}cout << endl;}private:std::vector<HashData<K,V>> _tables;size_t _n = 0;    // 存储的关键字个数};void TestHT1(){chen::HashTable<int, int> ht;int a[] = { 42,45,345,4,37,45,23 };for (auto e : a){ht.Insert(std::make_pair(e, e));}ht.Print();ht.Insert(std::make_pair(42, 42));ht.Print();ht.Erase(42);ht.Erase(45);ht.Print();}void TestHT2(){string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };//HashTable<string, int, HashFuncString> ht;HashTable<string, int, HashFunc<string>> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashData<string, int>* ret = ht.Find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair("apple", 1));ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("abc", 1));ht.Insert(make_pair("acb", 1));ht.Insert(make_pair("aad", 1));ht.Print();}
}

2. 插入和扩容

bool Insert(const std::pair<K, V>& kv)
{if (Find(kv.first)){return false; // 如果关键字已存在，则返回false}// 负载因子_n/size == 0.7 就扩容if (_n * 10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);// 遍历旧表，将数据插入新表for (size_t i = 0;i < _tables.size();i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables); // 交换旧表和新表}Hash hf;// 线性探测，找到合适的位置插入数据size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv; // 插入数据_tables[hashi]._s = EXIST; // 设置状态为存在++_n; // 更新关键字个数return true; // 插入成功，返回true
}

3. 查找

HashData<K,V>* Find(const K& key)
{Hash hf;size_t hashi = hf(key) % _tables.size();while (_tables[hashi]._s != EMPTY){if (_tables[hashi]._s==EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return NULL;
}

4. 删除

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_s = DELETE;--_n;return true;}else{return false;}
}

5. 仿函数HashFunc

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 原始写法
struct HashFuncString
{size_t operator()(const string& key){// BKDR方法size_t hash = 0;for (auto ch : key){hash *= 31;hash += ch;}return hash;}
};// 模板特化写法
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDR方法size_t hash = 0;for (auto ch : key){hash *= 31;hash += ch;}return hash;}
};

二次探测法（介绍）

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i =1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

🚩开散列

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中，如图：

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

实现

namespace HashBucket
{template<class K, class V>struct HashNode{HashNode<K, V>* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_next(nullptr), _kv(kv){}};template<class K>struct HashFunc{size_t operator()(const K& key){return key;}};// 特化template<>struct HashFunc<string>{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}Node* Find(const K& key){if (_tables.size() == 0)return nullptr;Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}size_t GetNextPrime(size_t prime){// SGIstatic 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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hash;// 负载因因子==1时扩容if (_n == _tables.size()){size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newtables.size();// 头插到新表cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);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 cur = _tables[i];size_t size = 0;while (cur){++size;cur = cur->_next;}//printf("[%d]->%d\n", i, size);if (size > max){max = size;}}return max;}private:vector<Node*> _tables; // 指针数组size_t _n = 0;         // 存储有效数据个数};void TestHT2(){string arr[] = { "香蕉", "甜瓜","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };HashTable<string, int, HashFunc<string>> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashNode<string, int>* ret = ht.Find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}}
}

三、std::unordered_set和std::unordered_map

STL中的unordered_map介绍

1. unordered_map 是存储 <key, value> 键值对的关联式容器，其允许通过 key 快速的索引到与其对应的value – 计算出余数找到下标位置。

2. 在 unordered_map 中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。

3. 在内部, unordered_map 没有对 <kye, value> 按照任何特定的顺序排序, 为了能在常数范围内找到 key 所对应的 value， unordered_map 将相同哈希值的键值对放在相同的桶中 – 开散列解决哈希冲突。

4. unordered_map 容器通过 key 访问单个元素要比 map 快，但它在遍历元素子集的范围迭代方面效率较低。

5. unordered_map 也重载了直接访问操作符 (operator[])，它允许使用 key 作为参数直接访问 value。

6. unordered_map 的迭代器是一个单向迭代器 – 哈希桶的结构是单链表。

测试：

#include <iostream>
#include <unordered_map>int main() 
{// (constructor) 构造函数std::unordered_map<int, std::string> myMap;// (insert) 插入元素myMap.insert({1, "One"});myMap.insert({2, "Two"});myMap.insert({3, "Three"});// (constructor) 通过范围构造函数std::unordered_map<int, std::string> rangeMap(myMap.begin(), myMap.end());// (constructor) 通过初始化列表构造函数std::unordered_map<int, std::string> initListMap = {{4, "Four"}, {5, "Five"}, {6, "Six"}};// (empty) 测试容器是否为空std::cout << "Is map empty? " << (myMap.empty() ? "Yes" : "No") << std::endl;// (size) 返回容器大小std::cout << "Size of map: " << myMap.size() << std::endl;// (find) 查找元素auto it = myMap.find(2);if (it != myMap.end()) {std::cout << "Element with key 2 found in map: " << it->second << std::endl;}// (count) 计算特定键的元素数量int count = myMap.count(3);std::cout << "Number of elements with key 3: " << count << std::endl;// (emplace) 构造并插入元素myMap.emplace(7, "Seven");// (erase) 删除元素myMap.erase(1);// (clear) 清空容器myMap.clear();// (hash_function) 获取哈希函数std::hash<int> hashFunction = myMap.hash_function();// (key_eq) 获取键的等价比较谓词auto keyEqual = myMap.key_eq();// (get_allocator) 获取分配器auto allocator = myMap.get_allocator();// (constructor) 拷贝构造函数std::unordered_map<int, std::string> copyMap(rangeMap);// (operator=) 赋值运算符std::unordered_map<int, std::string> assignedMap = initListMap;// (emplace_hint) 构造并插入元素带有提示位置auto hint = assignedMap.begin();assignedMap.emplace_hint(hint, 10, "Ten");// (swap) 交换内容myMap.swap(assignedMap);// (begin) 返回迭代器指向开头for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {std::cout << "Key: " << iter->first << ", Value: " << iter->second << std::endl;}// (cbegin) 返回 const 迭代器指向开头for (auto iter = myMap.cbegin(); iter != myMap.cend(); ++iter) {std::cout << "Key: " << iter->first << ", Value: " << iter->second << std::endl;}// (bucket_count) 返回桶的数量std::cout << "Bucket count: " << myMap.bucket_count() << std::endl;// (max_bucket_count) 返回最大桶的数量std::cout << "Max bucket count: " << myMap.max_bucket_count() << std::endl;// (bucket) 返回元素的桶号std::cout << "Bucket for key 2: " << myMap.bucket(2) << std::endl;// (bucket_size) 返回桶中元素的数量std::cout << "Bucket size for key 2: " << myMap.bucket_size(myMap.bucket(2)) << std::endl;// (load_factor) 返回当前负载因子std::cout << "Load factor: " << myMap.load_factor() << std::endl;// (max_load_factor) 获取或设置最大负载因子std::cout << "Max load factor: " << myMap.max_load_factor() << std::endl;myMap.max_load_factor(0.7);// (rehash) 设置桶的数量myMap.rehash(10);// (reserve) 请求容器容量变化myMap.reserve(20);return 0;
}

STL中的unordered_set介绍

unordered_set 和 unordered_map 的区别再于 unordered_set 是 K模型 的容器，而 unordered_map 是 KV模型 的容器，虽然二者底层都是开散列的哈希表，但是哈希表中每个节点的 data 的类型是不同的 – unordered_set 是单纯的 key，而 unordered_map 是 KV 构成的键值对，只是 哈希表 通过 KeyOfT 仿函数使得自己能够兼容 K模型 的 unordered_set 和 KV模型 的 unordered_map 而已。

unordered_set 和 unordered_map 的功能与要求基本一样：

1. unordered_set 的查询效率为 O(1)；
2. unordered_set 遍历得到序列的元素顺序是不确定的；
3. unordered_set 的底层结构为开散列的哈希表；
4. unordered_set 对 key 的要求是能够转换为整形。

与 unordered_map 为数不多的不同的地方在于，unordered_set 不需要修改 value，所以也就不支持 operator[] 函数；

测试：

int main() 
{// (constructor) 构造函数std::unordered_set<int> mySet;// (insert) 插入元素mySet.insert(1);mySet.insert(2);mySet.insert(3);// (constructor) 通过范围构造函数int arr[] = { 4, 5, 6 };std::unordered_set<int> rangeSet(arr, arr + 3);// (constructor) 通过初始化列表构造函数std::unordered_set<int> initListSet = { 7, 8, 9 };// (empty) 测试容器是否为空std::cout << "Is set empty? " << (mySet.empty() ? "Yes" : "No") << std::endl;// (size) 返回容器大小std::cout << "Size of set: " << mySet.size() << std::endl;// (find) 查找元素auto it = mySet.find(2);if (it != mySet.end()) {std::cout << "Element 2 found in set." << std::endl;}// (count) 计算特定键的元素数量int count = mySet.count(3);std::cout << "Number of elements with key 3: " << count << std::endl;// (emplace) 构造并插入元素mySet.emplace(4);// (erase) 删除元素mySet.erase(1);// (clear) 清空容器mySet.clear();// (hash_function) 获取哈希函数std::hash<int> hashFunction = mySet.hash_function();// (key_eq) 获取键的等价比较谓词auto keyEqual = mySet.key_eq();// (get_allocator) 获取分配器auto allocator = mySet.get_allocator();// (constructor) 拷贝构造函数std::unordered_set<int> copySet(rangeSet);// (operator=) 赋值运算符std::unordered_set<int> assignedSet = initListSet;// (emplace_hint) 构造并插入元素带有提示位置auto hint = assignedSet.begin();assignedSet.emplace_hint(hint, 10);// (swap) 交换内容mySet.swap(assignedSet);// (begin) 返回迭代器指向开头for (auto iter = mySet.begin(); iter != mySet.end(); ++iter) {std::cout << *iter << " ";}std::cout << std::endl;// (cbegin) 返回 const 迭代器指向开头for (auto iter = mySet.cbegin(); iter != mySet.cend(); ++iter) {std::cout << *iter << " ";}std::cout << std::endl;// (bucket_count) 返回桶的数量std::cout << "Bucket count: " << mySet.bucket_count() << std::endl;// (max_bucket_count) 返回最大桶的数量std::cout << "Max bucket count: " << mySet.max_bucket_count() << std::endl;// (bucket) 返回元素的桶号std::cout << "Bucket for key 2: " << mySet.bucket(2) << std::endl;// (bucket_size) 返回桶中元素的数量std::cout << "Bucket size for key 2: " << mySet.bucket_size(mySet.bucket(2)) << std::endl;// (load_factor) 返回当前负载因子std::cout << "Load factor: " << mySet.load_factor() << std::endl;// (max_load_factor) 获取或设置最大负载因子std::cout << "Max load factor: " << mySet.max_load_factor() << std::endl;mySet.max_load_factor(0.7);// (rehash) 设置桶的数量mySet.rehash(10);// (reserve) 请求容器容量变化mySet.reserve(20);return 0;
}

unordered_multimap

和 multimap 和 map 的区别一样，unordered_multimap 和 unordered_map 的区别在于 unordered_multimap 中允许出现重复元素，所以 unordered_multimap 中 count 用来计算 哈希表 中同一 key 值的元素的数量比较方便，但 unordered_multimap 也因此不再支持 operator[] 运算符重载，其他的地方都差不多，对细节有疑惑的建议查阅官方文档 unordered_multimap - C++ Reference (cplusplus.com)

unordered_multiset

unordered_multiset 也一样，与 unordered_set 不同的地方在于其允许出现重复元素：unordered_set - C++ Reference (cplusplus.com)

四、用hashtable模拟实现unordered_set和unordered_map

hashtable实现

为了使哈希表能够同时封装 KV模型的 unordered_map 和 K模型的 unordered_set，哈希表不能将节点的数据类型直接定义为 pair<K, V>，而是需要通过参数 T 来确定

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// HashFunc的模板特化
// 原因：不存在string类到size_t的显示类型转换
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};namespace hash_bucket
{// 哈希表节点template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_data(data), _next(nullptr){}};// 这里前置声明HashTable是因为在下面迭代器的定义里要用到HashTable这个类名（相互引用）template<class K, class T, class KeyOfT, class Hash>class HashTable;// K     ：Key的类型// T     ：T的类型（set就放key的类型，map就放std::pair(key,value)）迭代器封装的就是T类型的对象// Ref   ：T的引用类型// Ptr   ：T的指针类型// KeyOfT：用来取出T中的key的仿函数类型，因为T不一定是纯key，如果存放pair，要从中取出key// Hash  ：用来把key转换成size_t的仿函数类，就是算key的哈希值template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;public:Node* _node;                               // 哈希表节点指针size_t _hashi;                             // 哈希桶编号const HashTable<K, T, KeyOfT, Hash>* _pht; // 哈希表指针 为什么是const？？？public:__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi){}__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi):_node(node), _pht(pht), _hashi(hashi){}Self& operator++(){if (_node->_next != nullptr){// 当前桶还有节点，走到下一个节点_node = _node->_next;}else{// 当前桶已经走完了，从下一个桶开始找++_hashi;while (_hashi < _pht->_tables.size()){if (_pht->_tables[_hashi]){_node = _pht->_tables[_hashi];break;}++_hashi;}if (_hashi == _pht->_tables.size()){_node = nullptr;}}return *this;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node; // 迭代器不等，就是节点指针不等}};// unordered_set -> Hashtable<K, K>// unordered_map -> Hashtable<K, pair<K, V>>template<class K, class T, class KeyOfT, class Hash>class HashTable{public:typedef HashNode<T> Node;typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;// 友元类声明template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>friend struct __HTIterator;public:iterator begin(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return iterator(_tables[i], this, i);}}return end(); // 遍历完发现没有元素，返回一个尾后迭代器}iterator end(){// 尾后迭代器，是一个无效迭代器return iterator(nullptr, this, -1);}const_iterator begin() const{for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return const_iterator(_tables[i], this, i);}}return end();}const_iterator end() const{// this的类型：const HashTable<K, T, KeyOfT, Hash>*return const_iterator(nullptr, this, -1);}HashTable(){_tables.resize(10);}~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;}}// bool用来标记是否开辟新节点// 待插入数据已存在：false// 待插入数据不存在：turestd::pair<iterator, bool> Insert(const T& data){Hash hf;KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return std::make_pair(it, false);}// 负载因子最大到1 ,到1扩容if (_n == _tables.size()){vector<Node*> newTables;newTables.resize(_tables.size() * 2, nullptr);// 遍历旧表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next; // 旧的哈希桶（链表）的头节点的下一个先存着// 把旧的节点映射到新表size_t hashi = hf(kot(cur->_data)) % newTables.size();cur->_next = newTables[i];newTables[hashi] = cur;cur = next; // 迭代}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hf(kot(data)) % _tables.size();Node* newnode = new Node(data);// 头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return std::make_pair(iterator(newnode, this, hashi), true);}iterator Find(const K& key){Hash hf;KeyOfT kot;size_t hashi = hf(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this, hashi);}cur = cur->_next;}return end();}bool Erase(const K& key){Hash hf;KeyOfT kot;size_t hashi = hf(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;return true;}prev = cur;cur = cur->_next;}return false;}void Some(){size_t bucketCount = 0;      // 哈希桶数量size_t maxBucketLen = 0;     // 最大哈希桶（链表）长度size_t sum = 0;              // 总节点数double averageBucketLen = 0; // 平均桶长度for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){++bucketCount;}size_t bucketLen = 0;while (cur){++bucketLen;cur = cur->_next;}sum += bucketLen;if (bucketLen > maxBucketLen){maxBucketLen = bucketLen;}}averageBucketLen = (double)sum / (double)bucketCount;printf("all bucketSize:%d\n", _tables.size());printf("bucketSize:%d\n", bucketCount);printf("maxBucketLen:%d\n", maxBucketLen);printf("averageBucketLen:%lf\n\n", averageBucketLen);}private:std::vector<Node*> _tables;size_t _n = 0;};

my_unordered_map实现

namespace chen
{// 外层是<key,value>template<class K, class V, class Hash = HashFunc<K>>class unordered_map{// 提取T中的key的仿函数类struct MapKeyOfT{const K& operator()(const std::pair<K, V>& kv){return kv.first;}};public:// 去HashTable里面拿HashTable的迭代器 作unordered_map的迭代器// 这里迭代器里封装的是pair<const K, V>typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;typedef typename hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}std::pair<iterator, bool> insert(const std::pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));return ret.first->second;}const V& operator[](const K& key) const{std::pair<iterator, bool> ret = _ht.Insert(std::make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, std::pair<const K, V>, MapKeyOfT, Hash> _ht;};
}

my_unordered_set实现

namespace chen
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;const_iterator begin() const{return _ht.begin();}const_iterator end() const{return _ht.end();}std::pair<const_iterator, bool> insert(const K& key){auto ret = _ht.Insert(key);return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};
}

其他STL模拟实现（持续更新）

https://gitee.com/chenzhuowen4384/My_STL