C / C++ / 系统课时
有序容器和哈希容器怎么选
有序容器和哈希容器怎么选
当程序需要按键保存和查找数据时,set、map 与对应的 unordered 容器都能完成基本任务,但它们擅长的问题不同。选择时不要只看平均查找复杂度,还要同时考虑顺序、范围查询、最坏情况和内存开销。
学习目标
- 根据顺序和范围查询需求选择有序容器或哈希容器
- 理解两类容器在查找复杂度和内存结构上的差异
- 能为常见查找场景选择合适的
set、map或unordered容器
先按查询能力分流
std::set 和 std::map 会按照键的比较规则维护有序关系,因此除了精确查找,还能高效完成 lower_bound、upper_bound、最小值、最大值以及某个键区间内的遍历。
std::unordered_set 和 std::unordered_map 按哈希值把元素分配到桶中,不维护键的大小顺序。它们适合回答“这个键在不在”“这个键对应什么值”,却不能直接回答“第一个不小于某值的键是什么”。
| 需求 | 有序容器 | 哈希容器 |
|---|---|---|
| 精确按键查找 | 支持 | 支持 |
| 按键从小到大遍历 | 支持 | 不保证顺序 |
lower_bound、范围查询 |
支持 | 不支持按键范围定位 |
| 平均精确查找 | ||
| 最坏查找 |
因此,只要业务依赖键的顺序,通常就应优先考虑有序容器。不能为了平均 查找而牺牲真正需要的范围查询能力。
性能和内存不能只看大 O
标准有序关联容器通常以平衡搜索树实现,每个节点除了数据,还需要保存树结构相关的信息。查找、插入和删除具有 的复杂度保证,性能特征比较稳定。
哈希容器除元素节点外,还需要维护桶数组,并受哈希函数、负载因子和扩容影响。键分布合理时,查找、插入和删除的平均复杂度是 ;大量键发生哈希冲突时,最坏情况可能退化到 。
内存方面也不能简单认为哈希容器一定更省。桶数组本身需要空间,扩容时通常还会保留一定空桶,因此 unordered 容器在不少实现和负载下反而可能占用更多内存。实际差异应使用目标平台和真实数据测量,而不是仅凭容器名称判断。
用代码观察两类查询
下面的 C++17 示例同时保存一组整数。有序集合完成边界和区间查询,哈希集合完成精确存在性判断,这正是两类容器最典型的分工。
#include <iostream>
#include <iterator>
#include <set>
#include <unordered_set>
int main() {
std::set<int> ordered{20, 5, 12, 8, 30};
std::unordered_set<int> hashed{20, 5, 12, 8, 30};
// 有序容器可以直接定位第一个不小于目标值的元素。
auto first = ordered.lower_bound(10);
std::cout << "lower_bound(10): " << *first << '\n';
// 哈希容器适合做精确存在性查询,不依赖遍历顺序。
std::cout << std::boolalpha
<< "hashed contains 12: "
<< (hashed.find(12) != hashed.end()) << '\n';
auto begin = ordered.lower_bound(8);
auto end = ordered.upper_bound(20);
std::cout << "count in [8, 20]: "
<< std::distance(begin, end) << '\n';
}预期输出:
lower_bound(10): 12
hashed contains 12: true
count in [8, 20]: 3这里没有遍历 unordered_set 来展示元素顺序,因为标准并不保证其迭代结果按照键排序,也不应让程序依赖某次运行恰好观察到的排列。
用需求做最终选择
如果需要排序遍历、范围查询、前驱后继或稳定的对数复杂度保证,选择 set、map、multiset 或 multimap。如果主要工作是大量精确键查询,不关心顺序,并且键具有质量良好的哈希函数,可以考虑对应的 unordered 容器。
还要区分 set 与 map:只保存键时使用集合;需要由键关联一个值时使用映射。multi 版本允许重复键,而普通版本要求键唯一。先确定数据语义,再在有序与哈希两类实现之间选择,通常比单纯追求理论上的平均 更可靠。