一、std::unordered_map 是什么？

#include <unordered_map>

std::unordered_map 是 C++11 引入的哈希表容器，以键值对形式存储数据，支持：

• O(1) 平均时间复杂度的插入、查找、删除
• 键（key）唯一
• 基于哈希函数组织数据

对比如下：

类型	底层结构	是否排序	查找时间复杂度
std::map	红黑树（平衡二叉树）	✅ 排序	O(logN)
std::unordered_map	哈希表	❌ 无序	O(1) 平均，O(N) 最坏

---

二、核心接口和常用函数

std::unordered_map<KeyType, ValueType> umap;

方法	功能
umap[key] = value	插入或更新键值对
umap.at(key)	访问某键值（越界抛异常）
umap.find(key)	查找 key 是否存在
umap.count(key)	返回 key 出现次数（0 或 1）
umap.erase(key)	删除 key
umap.clear()	清空整个 map
umap.size()	获取元素数量

---

三、常用代码示例

示例 1：基本使用

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ageMap;

    // 插入数据
    ageMap["Alice"] = 25;
    ageMap["Bob"] = 30;

    // 访问数据
    std::cout << "Alice: " << ageMap["Alice"] << std::endl;

    // 查找 key 是否存在
    if (ageMap.find("Charlie") == ageMap.end()) {
        std::cout << "Charlie not found." << std::endl;
    }

    // 遍历 map
    for (const auto& pair : ageMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

---

示例 2：自定义类型作为 key（必须提供哈希函数）

#include <iostream>
#include <unordered_map>

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 哈希函数需要重载 std::hash
namespace std {
    template <>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_map<Point, std::string> pointMap;

    pointMap[{1, 2}] = "A";
    pointMap[{3, 4}] = "B";

    std::cout << pointMap[{1, 2}] << std::endl;

    return 0;
}

---

四、使用注意事项

问题	建议
哈希冲突	提供好的 hash() 函数，避免大量 key 映射到同一 bucket
不能重复 key	新插入相同 key 会覆盖旧值
operator[] 会插入默认值	使用 find() 判断 key 是否存在更安全
遍历是无序的	若需有序遍历，请使用 std::map

---

五、进阶技巧

1. 预分配空间（减少 rehash）

umap.reserve(1000); // 提前分配桶数量，提升性能

2. 使用引用访问值（避免拷贝）

auto& val = umap[key]; // 获取引用，直接修改
val += 10;

3. 用 emplace 插入避免构造拷贝

umap.emplace("Tom", 23); // 更高效，避免中间构造

---

六、应用场景举例

• 视觉 SLAM 中的 Feature -> Frame 映射
• 点云数据索引（如 KD-tree + Hash 区块）
• 数据库缓存系统（Key -> Object）
• ID 查询表、图节点邻接表（如 Graph Optimization 中使用）

---

总结表

特性	std::unordered_map
底层	哈希表
查找	O(1) 平均，O(N) 最坏
是否排序	❌ 无序
Key 唯一性	✅ 唯一
适合场景	高速查找 / 快速插入 / ID 映射
Key 类型限制	若是自定义类型，需重载 == 和 std::hash

---