哈希表

深入学习 std::unordered_map 头文件：<unordered_map> 命名空间：std 编译器要求：C++11 起（C++17 新增 try_emplace / insert_or_assign / extract / merge） 一、为什么需要 unordered_map 1.1 有序 vs 无序：性能差异 操作 std::map（红黑树） std::unordered_map（哈希表） 查找 O(log n) 平均 O(1)，最坏 O(n) 插入 O(log n) 平均 O(1) 删除 O(log n) 平均 O(1) 有序遍历 天然有序 无序 内存布局 散列树节点 bucket 数组 + 链表 核心取舍： 如果不需要按 key 有序遍历，unordered_map 几乎总是更快。 1.2 典型应用场景 玩家 ID → 会话数据（海量玩家快速查找） 配置表 key → value（启动时加载，运行时只读查询） 字符串 → 枚举映射（协议解析） 缓存 / 去重（快速判断"是否存在"） 二、内部结构：Bucket + 链表 2.1 经典分离链接法（Separate Chaining） 标准要求 unordered_map 使用分离链接法（不是开放寻址）： ...