libstdc++.so.6.0.28中的unordered_map的代码非常多，设计也很复杂，看上去就让人头大。这里我先从全局视角出发，然后到局部细节结合源码来梳理一下unordered_map的源码。
宏观结构
在Linux下打开/usr/include/c++/9/可以看到一个一个unodered_map文件，这就是我们写代码时包含的，打开unordered_map文件可以看到包含了很多头文件，和unordered_map直接相的就是我标出红色这几个：
bits/function_hash.h:包含了哈希算法相关内容。
bits/hashtable:包含了哈希表的实现。
bits/unordered_map.h:就是提供给我们的接口类。
打开bits/unordered_map.h文件可以看到，unordered_map模板类里面定义了一个模板成员变量_M_h这就是hashtable类的实例化对象，后续的所有接口方法都是通过访问_M_h的方法实现的，二者是组合关系。
看一下__umap_hashtable到底是什么：是对_Hashtable模板类起的别名。
模板参数_Key：代表key值。_Tp：代表value值。_Hash是H1仿函数可以用于将key转换为hash_code的函数。_Pred：判断两个key是否相等。_Alloc：空间分配器。_Tr：这个很重要，后续通过此参数来区分是unordered_map还是unordered_multimap，是否进行缓存hash_code，是否使用常迭代器。
__detail::_Mod_range_hashing：是H2仿函数，搭配H1仿函数使用，将hash_code%bucket_len。
__detail::_Default_range_hash：上述的H1和H2仿函数两者搭配实现了将插入的node分配到指定的桶内，而_Default_range_hash可以实现直接将node分配到桶内，默认是空实现。
其他实现：使用掩码
直接将key进行模运算：
注意第一行的__umap_traits，__hash_cached代表是否使用hash_code缓存，也就是是否在hash_node中保留hash_code，保留会提高运行速度，但是要损失空间为代价。
__constant_iterators表示是否使用常迭代器
__unique_keys表示是否key是唯一，unordered_map的key是唯一的，unordered_multimap的key是不唯一。通过上面传入的参数可以看到_Cache,false,true，这里的_Cache是模板参数，是由__cache_default<_Key, _Hash>::value>控制的，这是一个编译器布尔值，通过模板元编程来判断是否缓存hash_code,如果hash函数是一个快速的hash函数(默认的hash函数都是fast_hash)并且不抛出hash函数不会抛出异常就不会缓存hash_code，也就是说正常情况下是会节省内存不会缓存hash_code的。
接着来查看bits/hashtable.h的内容：hashtable类通过继承6个类，分别代表6个模块来实现了unordered_map的全部内容。接下来让我们依次查看。
具体实现
Hash_node
在_Hashtable类中有: using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;就代表Hash_node
Hash_node有两种:一种是不缓存hash_code,另一种缓存hash_code。通过类模板的局部特化来创建适合的节点。
UML类图如下：
hash_table
hash_table本质就是vector + list，因为unordered_map是存储一个pair，包含key和value，将传入的key通过hash算法获取hash_code,在通过除留余法找到要存储到哪个桶中(数组中)，libstdc++解决哈希冲突的办法是通过链地址法，将同一个桶中的元素以链表的形式组织起来。我们以hash_table中的几个重要函数来更加深刻的理解。
首先以find函数：
1.首先，通过调用_M_hash_code方法计算出键的hash_code。hash_code用于确定键在哈希表中的存储位置。
_M_hash_code是_Hash_code_base中的一个方法：
可以看到调用了_M_h1()函数，返回了H1仿函数，_H1(k)获取到了hash_code
2.然后调用_M_bucket_index方法根据hash_code算出hash_code对应的桶的索引__n。可以看到也是通过调用_M_h2()函数获得一个_H2的仿函数，然后_H2(__c,__n)来确定桶的索引。
3.通过_M_find_node(桶号，key,hash_code)在指定桶中查找节点，该方法会遍历桶中的节点，并根据节点的键和hash_code与目标键进行对比，找到匹配的节点。
可以看到这里再次调用_M_find_before_node函数，也就是先获取到了前一个节点，也能理解毕竟是单链表。
在_M_find_before_node中，首先获取了__n号桶中记录的地址，然后通过for循环遍历单链表，通过
比较当前节点和需求是否相符并且判断是否超出了当前桶的链表范围。(为什么是__prev_p->_M_nxt？为什么要进行_M_bucket_index(__p->_M_next())!=__n的判断？这都和hash_table的结构有关，后面会讲解！！！)
_M_equals函数最终会调用:有hash_code缓存调用上面的判等函数，没有hash_code缓存就调用下面的判等函数。这里盘不判断hash_code是否相等都无所谓的，因为后面的_M_bucket_index(__p->_M_next())!=__n会进行判断的。
让我们看一下_M_bucket_index函数发生了什么，最终会从两个版本中进行选择，如果缓存了hash_code那么执行，可以看到只是进行了_H2仿函数的调用，起始就是一个除留余法的调用，性能消耗并不大。
但是如果没有缓存hash_code会发生什么呢？ 没错，会先调用_H1获取计算hash_code然后调用_H2,这里的_H1进行hash算法应该是挺耗性能的，也就是在使用find函数的情况下，没有缓存hash_code，每次我们遍历链表上的一个节点之后都要进行一次_H1计算一次_H2计算，这样效率肯定低的离谱，其实源码里完全可以不进行_M_bucket_index(__p- >_M_next())!=__n的判断，但是需要遍历完所有链表元素，但是我感觉也比每次都做一次hash运算速度快把，但也不一定因为链表不连续访存是缓存无法利用效率肯定也不高。 最优解肯定是进行缓存hash_code了如果内存空间不是很紧张的情况下。 我们最后可以做个测试，通过不同数据量来进行find查找看一下缓存hash_code和不缓存hash_code的查找速率的影响，以及hash_code所增加的内存！
4.最后就是返回数据，如果找到了匹配的节点，就创建一个迭代器指向该节点，如果没有找到就返回尾迭代器，表示未匹配的节点。
如何确定桶？
这其实在上面的find函数的过程中已经体现过了，就是看你是否缓存了hash_code。
无论上层接口如何调用最终都是要通过hash_table中的这两个函数：
如果缓存了hash_code就会根据以上二者函数进行调用下面对应的函数:
如果没有缓存hash_code：
如何确定在元素在桶中的位置呢？
其实就是这个函数:
__node_type* _M_find_node(size_type __bkt, const key_type& __key,
__hash_code __c) const
{
// 查找目标节点之前的节点
__node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
// 如果找到了目标节点之前的节点，返回目标节点
if (__before_n)
return static_cast<__node_type*>(__before_n->_M_nxt);
// 否则返回 nullptr，表示未找到目标节点
return nullptr;
}
__node_base* _M_find_before_node(size_type __n, const key_type& __k,
__hash_code __code) const
{
// 获取桶中的首节点
__node_base* __prev_p = _M_buckets[__n];
// 如果桶中没有节点，返回 nullptr
if (!__prev_p)
return nullptr;
// 遍历桶中的节点，查找目标节点之前的节点
for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);; __p = __p->_M_next())
{
// 判断当前节点是否与目标节点匹配
if (this->_M_equals(__k, __code, __p))
return __prev_p;
// 如果当前节点没有下一个节点，或者下一个节点所在桶的索引不等于当前桶索引，结束遍历
if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
// 更新目标节点之前的节点为当前节点
__prev_p = __p;
}
// 返回 nullptr，表示未找到目标节点之前的节点
return nullptr;
}Rehash
还是我们从一个点入手然后全局展开这样即方便理解也可以理清楚整个rehash的过程。我们以insert为例。
当我们如此调用insert函数.
int main()
{
unordered_map<int, int> mp = { {1,2},{2,3} };
auto it = mp.insert({1,2});
return 0;
}1.首先会调用到bits/unordered_map中的这两个重载函数之一。
2.会调用到bits/hashtable_policy.h中__detail::_Insert_base中insert函数
3.调用__h._M_insert(__v,__node_gen,__unique_keys)函数。
这里先提取出来key_type类型的key，然后获取hash_code，接着查询到bucket_index，如果发现找到则会返回一个pair<iterator(__n),false>代表插入失败。
否则创建一个hash_node然后通过_M_insert_unique_node进行插入。
1.首先获取_M_state其实就是获取当前桶中的元素个数。
2.进行_M_need_rehash判断是否需要进行rehash。
判断的方法就是将现在的元素 + 要插入的元素个数 然后和阈值进行比较，如果没达到阈值就返回即可，如果达到了阈值需要通过元素个数和负载因子(libstlc++默认是1.0)来获取min_bkts，如果此时满足元素要求所需要的min_bkts<__n_bkt此时拥有的桶数量，那也无需rehash直接返回即可，但是如果确实需要扩容了，那么需要将__min_bkts和)_M_growth_factor*__n_bkt进行比较取较大值，_M_growth_factor是增长因子默认是2.0，此时并不是真正扩容的同数，需要传入_M_next_bkt来确定最终扩容的桶数量。
查找素数表，找到第一个大于等于所需桶的数量最为最终的桶的扩容数量，可见网上大片大片说直接二倍扩容的言论完全是不正确的，这里可以思考一下，为什么桶要按照素数进行扩容呢？(最后会解答)。
确定桶的数量之后就要进行_M_rehash操作，这里调用了一个辅助函数aux，第二个参数是一个编译时bool值，判断key是否允许重复来调用不同的模板函数。
这里是真正的桶重新分配的逻辑：
先分配新桶n个，然后获取之前的桶中的虚头结点用p指针指向来遍历所有元素，获取p指向的当前元素因该在新桶中的index，判断当前index桶号中是否有元素了，如果有直接头插法插入元素，如果没有将元素插入到_M_before_begin这个虚头节点后面，然后将_M_before_begin挂载到index号桶中。这样既可以将元素以链表的形式存入到桶中，又可以以_M_before_begin为整个链表的虚头结点，方便遍历链表。就像这个图:
这也就解释了为什么上面要进行__prev_p->_M_nxt，因为第一个节点是虚拟头节点，为什么要进行_M_bucket_index(__p->_M_next)!=n判断，因为每个桶中的节点又连接成了一个单向链表，我们必须通过hash运算看当前桶中元素是否还在__n号桶中才知道有没有继续遍历的必要。
最后销毁原来的桶，记录当前的桶的数量和首地址。最后只需要将元素插入新桶即可。
迭代器
迭代器本质就是一个内嵌类的对象，封装了指针的对象，重载运算符操作使其看起来像指针。在unordered_map中实现了两种迭代器，一种是_Local_iterator，这种迭代器访问元素桶时，只会访问当前桶的元素，超出当前桶之后就返回无效迭代器，当然如果是常对象就会调用const__Local_iterator。另外一种是_Node_iterator迭代器，逐个元素进行遍历，常对象调用const__Node_iterator,无论哪种迭代器都无法进行–操作，也就是说这是单向迭代器，原因很简单，每个节点只有一个指向下一个节点的指针，并非双向链表。并且因为unordered_map存储的都是一对pair元素，对迭代器进行*操作返回的也是pair只不过是 typedef typename std::conditional<__constant_iterators, const _Value&, _Value&>::type reference;根据编译时bool来确定引用类型，如果是true则为const_Value&不可修改，如果是false则为_Value&非常量引用，当我们插入{1,2}时，会根据1所对应的桶将{1,2}作为一个整体放到链表元素中，迭代器会返回pair整个对象，无论是否为常引用{1,2}中的first都是不可被修改的。因为传入时的类型就是const修饰。
测试
#include <iostream>
#include <string>
#include <unordered_map>
#include <chrono>
// 带缓存哈希的键类型
struct CachedStringKey {
std::string key; // 原始键值
size_t hash_value; // 缓存的哈希值
// 构造函数中计算并缓存哈希
CachedStringKey(const std::string& s)
: key(s), hash_value(std::hash<std::string>{}(s)) {}
// 必须定义相等运算符
bool operator==(const CachedStringKey& other) const {
return key == other.key;
}
};
// 自定义哈希函数（直接返回缓存值）
struct CachedStringHash {
size_t operator()(const CachedStringKey& k) const {
return k.hash_value;
}
};
// 定义优化后的map类型
using OptimizedMap = std::unordered_map<
CachedStringKey,
int,
CachedStringHash,
std::equal_to<CachedStringKey>
>;
// 模拟慢速哈希函数
struct SlowHash {
size_t operator()(const std::string& s) const {
return std::hash<std::string>{}(s);
}
};
// 普通map使用慢速哈希
using NormalMap = std::unordered_map<
std::string,
int
>;
int main() {
const int N = 100000;
// 测试普通map
auto t1 = std::chrono::high_resolution_clock::now();
NormalMap normal_map;
for(int i=0; i<N; ++i){
normal_map[std::to_string(i)] = i;
}
auto t2 = std::chrono::high_resolution_clock::now();
// 测试优化map
OptimizedMap optimized_map;
for(int i=0; i<N; ++i){
optimized_map.emplace(CachedStringKey(std::to_string(i)), i);
}
auto t3 = std::chrono::high_resolution_clock::now();
// 输出耗时对比
auto dur1 = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1);
auto dur2 = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2);
std::cout << "普通map插入耗时: " << dur1.count() << "ms\n";
std::cout << "优化map插入耗时: " << dur2.count() << "ms\n";
return 0;
}这是自己定义的缓存hash_code的unordered_map和没缓存的进行了对比，居然发现速度几乎相等，后面又查看了源码才发现原来当key为string时默认不是fast_hash因此源码实现上就会hash_code无需我们操作，果然AI有时候还是不可信，还得自己看源码。
而对于int类型作为key时更加无需缓存hash_code因为默认的hash_code十分简单，如下：直接返回了key…
这也有优化的空间，毕竟这样的hash函数均匀性应该不太行把，我们可以自己实现均匀性比较好的hash函数，然后缓存hash_code来提高效率。
这里有个很有意思的问题。上面我们提到过哈希桶的个数去素数表里找，也就是哈希桶都是素数个，为什么呢？
其本质也就是为了减少模运算的冲突概率。index = hash(key)%bucket_count;当bucket_count为素数时，模运算的结果分布会更加均匀，特别是当键值存在特定模式时。
如果哈希函数可以将键值完美均匀分布到整个值域，那么桶是否为素数个无关紧要，但是在现实中：大多数哈希函数本身存在一定规律。而素数具有抗规律性，这与数论中的因数分解特性和模运算周期性规律有关。
假设N是合数，那么N = a✖b(a,b>1)，则当键值以a或者b为步长时，就会大大增加冲突概率。
比如：桶数 N=8(因数：2，4，8)，键值序列 key = 0，4，8，12，16，20…(步长4)
模运算结果：0 mode 8 =0，4 mode 8 =4，8 mode 8 =0，12 mode 8 =4，16%8 =0
可见冲突率为 50%
如果N是素数7，那么当且仅当键的步长为7时，模运算才会周期性重复。
贝祖定理指出，若两个整数a和b互质(即gcd(a,b) = 1)，存在整数x,y使得 ax + by =1，应用到哈希表中就是，若键增量s与桶数N互质。则键值序列会通过模运算均匀覆盖所有桶。
尽管桶数为素数个可以大大降低冲突率，但是在一些场景下也可以为2的幂次方桶数(如1024)，当桐树为2的幂次方时，可以用&操作来获取桶号，index = hash(key) &(N-1)。因为当桶数为2的幂次时，位运算和模运算具有等效性质，hash(key)&(N-1) = hash(key) mod N.比如Java中就是这么实现的，因为&操作比%效率高十倍。如果使用这种方式要求哈希函数映射的哈希值低位具有随机性，否则会产生大量冲突。
解决哈希冲突办法
拉链法
这就是在libstlc++中使用的方法，每个桶中不是单独的元素，而是记录了一条链表的首地址，当放生hash冲突时，新的元素会被插入到对应桶的链表中。
优点：有效避免了聚集效应，并且删除简单，但是如果存在大量hash冲突，链表会变得很长，O(1)时间复杂度变为O(c).c为链表平均长度，并且由于链表非连续存储地址不连续，无法命中缓存，查询效率因此受制。对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销） ②由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费。
开放寻址法
在开放寻址法中，当发生Hash冲突时，我们会顺序查找下一个可用的桶位置，知道找到一个空闲位置为止。探测方式如下：
- 线形探测：顺序查找下一个单元，知道找到一个空单元或遍历全表，如当hash值为3冲突时(假设此时hash表长度为11)，线性探测的过程：H1 = (3+1)%11 =4.此时4依然冲突，再hash，即H2 = (3+2)%11 =5，通过这种线性增长，知道找到空位置为止。
- 二次探测。当哈希冲突时，在表的左右进行跳远探测，比较灵活一定程度解决了聚集效应。此时di = 1²,(-1)²,2²,(-2)²….假设当hash值为3(hash表为11)，利用二次探测过程为：H1 = (3+(-1)²)%11 = 2.直到找到空位置。如果直接如此操作就会出现，平方探测无法探测到整个列表空间，造成列表浪费，解决办法就是：有定理现实如果散列表的长度是4k+3(k是正整数)形式的素数，那么平方探测就可以探测整个列表。
- 伪随机探测：这种方法是产生一系列随机值，并给定随机数作为起点。假设当前hash值为3冲突（hash表长度为11），利用伪随机探测的过程：假设产生的随机值为2，5，9…则H1 = (3+2)%11 = 5,H2 = (3+5)%11 = 8.直到找到空位置为止。
优点：不会引入额外的数据结构，节省了空间，并且数组的连续性特点可以命中缓存提高查找效率。
缺点：可能会产生聚集效应，当key经过hash发现当前index被占用了，那么就会通过某种步长寻找下一个位置，因此相邻位置会被频繁占用，导致查询效率大幅度降低。其次，删除操作也相对复杂，需要特殊标记来记录，直接删除元素会导致探测链断裂。存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷。
想象一下：在开放寻址法中，假设键A，B，C均哈希到索引0，通过线性探测一次存储到索引0，1，2.当我们查找键B时，判断键B不存在的依据是，如果从索引0开始依次往后递增的位置发现桶为空还没有找到键B则认为键B不存在，但是当我们直接删除索引0的键A时，然后查找键B，键C，探测链会在索引0处断裂，误认为B,C并不存在。
对应这一问题，开放寻址法采用伪删除技术，哈希槽中保留一个状态位，有三种状态，Unused(未使用):槽未被占用，Active(活跃)：槽存储有效数据，Dummy(伪删除)：槽曾经被占用但已删除。
删除流程：
1.寻找目标键：沿探测序列(线性探测，二次探测)找到目标键的位置。
2.标记为Dummy:将该槽标记改为Dummy，而非清空数据或重置为Unused。
3.保留数据结构：键值对的存储位置不变，但是逻辑上标记为无效。
插入操作：
遇到Dummy标记：可以复用该槽位，但是需要先完成当前探测链遍历，确保没有冲附件。
覆盖逻辑：插入时遇到Dummy标记，优先复用该槽位，但需要检测后续槽位是否有相同的键。
性能方面：Dummy会占用额外的状态位，并且过多的Dummy会严重降低探测效率，需要定期进行Rehash来清除无效标记位。
再哈希法
再哈希法又叫双哈希探测法顾名思义，就是使用两个不同的Hash函数，fi = (f(key) + i*g(key))%m(i = 1,2,….,m-1)其中,f(key)和g(key)两个不同的哈斯函数，m为哈希表长度。
先用第一个函数f(key)对关键码计算哈希地址，如果地址冲突，再使用第二个函数g(key)确定易懂的步长因子，最后通过步长因子序列由探测函数寻找空的哈希地址。
比如，f(key)=a 时产生地址冲突，就计算g(key)=b，则探测的地址序列为 f1=(a+b) mod m，f2=(a+2b) mod m，……，fm-1=(a+(m-1)b) % m。
缺点：由于冲突时需要再次hash增加了计算时间。
公共溢出区
设立两个表：基础表和溢出表，将所有关键字通过哈希函数计算出相应的地址，然后将未发生冲突的关键字放入基础表中，一旦发生了冲突，将其放入溢出表中即可。
查找时，先给定值通过哈希函数计算出相应的散列地址后，首先查找基础表的相应位置进行比较，如果不相等，再到溢出表中顺序查找。
