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(log⁡N)O(\log N) O(1)O(1)
最坏查找 O(log⁡N)O(\log N) O(N)O(N)

因此,只要业务依赖键的顺序,通常就应优先考虑有序容器。不能为了平均 O(1)O(1) 查找而牺牲真正需要的范围查询能力。

性能和内存不能只看大 O

标准有序关联容器通常以平衡搜索树实现,每个节点除了数据,还需要保存树结构相关的信息。查找、插入和删除具有 O(log⁡N)O(\log N) 的复杂度保证,性能特征比较稳定。

哈希容器除元素节点外,还需要维护桶数组,并受哈希函数、负载因子和扩容影响。键分布合理时,查找、插入和删除的平均复杂度是 O(1)O(1);大量键发生哈希冲突时,最坏情况可能退化到 O(N)O(N)。

内存方面也不能简单认为哈希容器一定更省。桶数组本身需要空间,扩容时通常还会保留一定空桶,因此 unordered 容器在不少实现和负载下反而可能占用更多内存。实际差异应使用目标平台和真实数据测量,而不是仅凭容器名称判断。

用代码观察两类查询

下面的 C++17 示例同时保存一组整数。有序集合完成边界和区间查询,哈希集合完成精确存在性判断,这正是两类容器最典型的分工。

cpp
#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';
}

预期输出:

text
lower_bound(10): 12
hashed contains 12: true
count in [8, 20]: 3

这里没有遍历 unordered_set 来展示元素顺序,因为标准并不保证其迭代结果按照键排序,也不应让程序依赖某次运行恰好观察到的排列。

用需求做最终选择

如果需要排序遍历、范围查询、前驱后继或稳定的对数复杂度保证,选择 set、map、multiset 或 multimap。如果主要工作是大量精确键查询,不关心顺序,并且键具有质量良好的哈希函数,可以考虑对应的 unordered 容器。

还要区分 set 与 map:只保存键时使用集合;需要由键关联一个值时使用映射。multi 版本允许重复键,而普通版本要求键唯一。先确定数据语义,再在有序与哈希两类实现之间选择,通常比单纯追求理论上的平均 O(1)O(1) 更可靠。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

有序容器和哈希容器怎么选

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通