2.9、什么时候用map，什么时候用hash_map？

数据结构与底层实现差异

std::map

• • 底层结构：基于**红黑树（自平衡二叉搜索树）**实现
• • 元素顺序：按键的严格弱排序规则自动排序，支持顺序遍历
• • 时间复杂度：插入/查找/删除均为 O(log N)
• • 键类型要求：必须支持 operator< 比较操作

std::unordered_map（hash_map标准替代）

• • 底层结构：基于**哈希表（Hash Table）**实现
• • 元素顺序：无序存储，遍历顺序无定义
• • 时间复杂度：平均 O(1)（最坏情况因哈希冲突退化为 O(N)）
• • 键类型要求：必须支持 operator== 及哈希函数（标准类型有默认实现）

何时选择std::map？

1. 需要有序数据访问

• • 场景：范围查询（如查找键在[a, b]之间的元素）、按顺序遍历、区间统计
• • 优势：红黑树天然支持有序性，无需额外排序逻辑

2. 键类型哈希困难

• • 情况：自定义复杂类型（如结构体）缺乏高效哈希函数
• • 方案：直接使用operator<实现排序比实现哈希函数更简单

3. 稳定性能需求

• • 场景：对操作耗时敏感（如实时系统）
• • 优势：红黑树时间复杂度严格可预测（O(log N)），无哈希冲突风险

4. 内存优化场景

• • 特点：红黑树节点结构紧凑（仅存储键值对+指针），内存占用可控

何时选择std::unordered_map？

1. 极致访问性能需求

• • 场景：高频查找、缓存系统、计数器（如单词频率统计）
• • 优势：平均常数时间操作，大数据量下性能显著优于红黑树

2. 键类型哈希友好

• • 情况：使用标准类型（int、string等）或可快速实现高效哈希函数
• • 优势：标准库提供默认哈希实现，冲突概率低，性能稳定

3. 无序数据场景

• • 场景：元素顺序无关紧要（如用户ID到用户信息的映射）
• • 劣势：若需排序需额外处理（如收集键后手动排序）

4. 大数据量操作

• • 场景：百万级元素插入/删除
• • 优势：哈希表平均操作效率远高于树结构

面试核心考察点

1. 底层原理深度

• • 必答点：
  • • map是红黑树，保证有序性，时间复杂度O(log N)
  • • unordered_map是哈希表，无序，平均O(1)

2. 关键差异辨析

3. 实践场景举例

• • 用map：实现按时间顺序存储的日志系统，需按时间范围查询
• • 用unordered_map：实现LRU缓存，需快速判断键是否存在

对比表

代码示例

// std::map：有序字典（自动按键排序）
#include <map>
#include <string>
std::map<std::string, int> word_count;
word_count["apple"] = 10;    // 插入时自动按字符串顺序排序
word_count["banana"] = 5;

// std::unordered_map：快速查找（无序）
#include <unordered_map>
std::unordered_map<int, User> user_cache;
user_cache[123] = User("Alice"); // 哈希表存储，访问O(1)

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）