首先需要我们了解的是unordered_map 与 unordered_set 是关联式容器的一种是基于哈希表实现的哈希表作者会在后面简单介绍。两者的核心优势是平均 O (1) 级高效查询、插入与删除无序性它们被广泛应用于 Linux C 开发中的高频查找、大量数据去重、缓存设计等场景。一.哈希表1.哈希概念哈希(hash)又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立一个映射关系查找时通过这个哈希函数计算出Key存储的位置进行快速查找。2. 哈希函数STL 默认提供哈希函数 std::hashKey支持 int、float、string 等基础类型自定义类型需手动提供哈希函数或重载哈希函数核心要求相同 Key 的哈希值必须相同一致性。不同 Key 的哈希值尽量不同均匀性减少冲突。哈希函数计算高效避免耗时操作影响容器性能。同时Key 必须支持 “相等比较” 运算符用于在桶内遍历查找时判断是否为目标 Key。前面我们说哈希函数把关键字Key跟存储位置建立一个映射关系并且也提到了哈希是一种存储数据的方式哈希函数就是具体实现这种方式的一个函数我们通过哈希函数和已经给定的key值来算出这个数据应该存放的位置然后来存放。这也造成了哈希表的无序性但是这种无序性反而方便我们使用我们在查找或者插入时只需要按照哈希函数来进行对应位置的计算不需要进行遍历等操作这也是 O (1)的原因。哈希函数一般使用以下几个函数除法散列法/除留余数法乘法散列法全域散列法这里正在只详细介绍第一个方法其他两个读者可以自行查找还有一些其他的哈希函数作者在这里不做过多赘述。除法散列法可以简单理解为取余数作为存放位置这个方法需要我们设置一个M通常是哈希表的大小然后用key%M得出来的数就一定是小于M的同时这个数就是插入的位置下标。举个具体的例子M为13然后我插入一个key为5的数据5%135那么这个数据存放在下标为5的地方再插入一个key为40的数据40%131那么就放在下标为1的位置。当使用除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是2的x次 那么key%2的x次 本质相当于保留key的后x位那么后x位相同的值计算出的哈希值都是⼀样的就冲突了。如 {6331}看起来没有关联的值如果M是16也就是2的4次 那么计算出的哈希值都是15因为63的二进制后8位是0011111131的⼆进制后8位是00011111。如果是10的x次就更明显了保留的都是10进值的后x位如{11212312}如果M是100也就是10的平方那么计算出的哈希值都是12。因此当使用除法散列法时建议M取不太接近2的整数次幂的⼀个质数(素数)。3.哈希冲突当不同 Key 的哈希值相同时会触发哈希冲突因为第二个插入的数据的位置已经被占领这种情况下就需要我们处理哈希冲突。主要有两种方法开放定址法和链地址法。3.1开放定址法开放定址法具体也有三种方式线性探测、二次探测、双重探测。这里作者还是主要讲线性探测后面两种可以自行查阅。线性探测是从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置继续一直往后找。这里我们也需要负载因子来判断插入前是否有空余空间避免插入时哈希表已经满了的情况负载因子会在后面提到。对线性探测举个例子我们先对M为13的哈希表用除留余数法插入key为5620这三个数3.2链地址法链地址法就是每个数组都作为一个链表一直把数据串联起来当遇到哈希冲突时在当前元素下面“挂”起来找的时候顺着往下找就行。3. 负载因子与扩容机制假设哈希表中已经映射存储了N个值哈希表的大小为M那么负载因子N/M 负载因子有些地方也翻译为载荷因子/装载因子等他的英文为load factor。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低当元素插入后负载因子超过阈值就会触发扩容新建一个容量为原数的 2 倍或 1.5 倍因编译器而异的数组重新计算所有元素的哈希值映射到新哈希表中重哈希Rehashing也可以理解为把原来所有的数据重新插入到新表里面只不过函数的计算方式不变函数的数值可能改变。可通过 reserve (n) 提前预留桶数避免频繁扩容。二.unorder_map与unorder_set1. 概念undered_set的声明如上第一个参数是key第二个参数为哈希函数第三个参数是支持相等比较的函数用以比较两个 Key 值一般是比较哈希函数处理 Key 后得到的哈希值是否相等第四个参数就又是空间配置器了后面三个参数一般不需要我们自己进行传参。undered_map的声明如上与undered_set相差无几只是多出来一个Value。两者均属于 STL 无序关联容器底层依赖哈希表Hash Table实现使用包含的头文件#include unordered_map、#include unordered_set。核心特点是 “以空间换时间”—— 通过哈希函数将 Key 映射到指定存储位置实现高效访问区别于 map/set 的红黑树有序特性unordered_set无序集合和set一样仅存储单一 KeyKey 唯一且不可重复容器无序存储顺序与插入顺序无关核心作用是 “高效去重 快速判断元素是否存在”。unordered_map无序映射表和map一样存储键值对Key-ValueKey 唯一且不可修改Value 可修改容器无序核心作用是通过 Key 快速定位 Value。2.unordered_multiset 与 unordered_multimap为满足 “允许重复 Key” 的场景STL 提供对应变体核心差异仅在于 “Key 是否唯一”底层哈希表实现逻辑完全复用unordered_multiset是 C 标准模板库STL中的一种无序关联容器。它unordered_set类似但允许存储多个相同的元素。unordered_multiset使用哈希表作为底层数据结构因此不对元素进行排序。unordered_multimap是 C 标准库中的一种无序关联容器与unordered_map类似但允许存储多个键相等的键值对。底层实现是哈希表因此可以在常数时间内进行插入、删除和查找操作。3. unordered_multiset/map与unordered_set/map对比容器类型核心特性时间复杂度平均 / 最坏适用场景unordered_setKey 唯一、不可修改无序仅存 Key插入 / 查找 / 删除O (1)/O (n)海量数据去重、快速判断元素存在性、高频查询场景unordered_mapKey 唯一、不可修改Value 可修改无序存键值对插入 / 查找 / 删除O (1)/O (n)高频键值查询、缓存设计、字典映射、配置存储unordered_multisetKey 可重复无序仅存 Key插入 / 查找 / 删除O (1)/O (n)重复数据统计、允许重复元素的快速查询unordered_multimapKey 可重复无序存键值对插入 / 查找 / 删除O (1)/O (n)一对多映射、多值关联查询如用户 - 订单列表补充最坏时间复杂度 O (n) 出现在 “哈希冲突严重” 时所有 Key 映射到同一存储位置此时哈希表退化为链表实际开发中通过合理设计哈希函数、调整负载因子可规避该问题。4. 与 map/set红黑树的差异对比维度unordered_map/unordered_set哈希表map/set红黑树有序性无序存储顺序与插入顺序无关不支持范围查询有序默认升序支持范围查询如区间遍历时间复杂度平均 O (1)最坏 O (n)冲突严重需要一直往后推稳定 O (logn)无波动内存占用较高数组预留空间节点含哈希值与指针较低红黑树节点仅含数据与指针无预留空间插入 / 删除迭代器特性扩容时所有迭代器失效插入 / 删除仅影响对应迭代器仅被删除元素迭代器失效其他迭代器仍有效适用场景无需有序、追求极致查询效率、高频读写场景需有序性、范围查询、稳定效率场景