深度剖析C++ STL无序关联式容器的底层构造

C++ STL无序关联式容器：unordered_map容器、unordered_multimap容器、unordered_set容器、unordered_multiset容器，其底层构造都是基于哈希表封装的。如果读者还不具备哈希基础的话可自行跳转《哈希算法实例详解》学习。简单来说，无序关联式容器可以看作指针数组+链表的奇妙组合。原理可理解为：我们向堆区开辟了一段连续空间（可理解为数组），空间大小为n，每个单位空间被称为“桶”且能够存储一个头指针，头指针“牵引"着一个单向链表(双向链表太费内存了）。当我们输入一个键值对时，键会被哈希函数转变成哈希值hash，随后由hash%n（充分利用模运算的周期性）分配到该空间中，键值对作为一个整体被封装在链表节点中。

通过哈希定位到对应的链表，在理想情况下提供O(1)的访问效率，但在哈希冲突严重时可能退化为O(n)的链表查找性能。

那什么是”哈希冲突“呢？在实际使用时，哈希函数作用于不同键或者键值对数量大于空间时，都可能会产生相同的哈希值，此时会出现多个键值对会被映射到“同一个位置上”，为了解决这个问题，通常使用链地址法，即采用链表思想，把键值对“串”起来。查询时先通过哈希快速定位到桶（模糊区分），再在链表中遍历比较键的具体值（绝对区分）。

无序关联式容器内都维护着一个重要的成员变量——load_factor()，它叫做负载因子，数据类型为float，其值=插入键值对总量/桶数量，功能是分析键值对的分布情况，当负载因子<0.5时，说明不管是空间利用率还是访问效率都比较高，反之。下面我们通过代码来分析插入键值对对负载因子的影响。

#include <iostream>
#include<unordered_map>//需要包含头文件 
#include<string>
using namespace std;
/*无序关联式容器内的负载因子——load_factor()*/ 
void test()
{
unordered_map<string,string> ump{
{"C语言教程","https://www.dotcpp.com/BbNkeAOzdW.php/cms/archives?ref=addtabs"},
{"计算机二级C语言","https://www.dotcpp.com/course/erjic/"},
};//初始化列表
cout << "插入两个键值对时的负载因子为【"  << ump.load_factor() << "】\n";
cout << "插入多个键值对后：\n";
ump["数据结构教程"]="https://www.dotcpp.com/course/ds/";
ump["ACM与蓝桥杯竞赛指南"]="https://www.dotcpp.com/course/acm/";
ump["算法竞赛教程"]="https://www.dotcpp.com/course/algorithm/";
ump["单片机教程"]="https://www.dotcpp.com/course/scm/";
ump["Python教程"]="https://www.dotcpp.com/course/python/";
ump["Java教程"]="https://www.dotcpp.com/course/java/";
cout << "插入多个键值对时的负载因子为【"  << ump.load_factor() << "】\n";
 
}
int main() {
    test();
    return 0;
}

编译结果如下：

我们可以清晰地看到，随着键值对的不断插入，负载因子的值不断提高，而负载因子的增加会影响容器的空间利用率和元素的操作效率，我们该如何避免哈希冲突提高容器的性能呢？

1. 我们需要设计好的哈希函数，将键尽量均匀地分配到空间中。

2. 我们可以通过reserve()实现提前预定空间，尽量避免使用空间<插入键值对数量。

3. 尽可能将负载因子控制在0.7一下，同时使用较为稳定的数据类型作为键。（比如int比float稳定性好）