「C++笔记」unordered_map：哈希化的无序映射函数（键值对）

unordered_map 是 C++ 中一个经过哈希函数（Hash）处理的映射（map）容器。

本文中的map和set是差不多的，unordered_map与unordered_set也是对应的。所以不再单独写一篇了。

这里的内容建议看完本文之后再回过头来看
二者虽然都有两个属性，但是程序员定义的时候数目不一样。
set是一种属性的容器，就像字典你定好“字”，页数是后面放的位置确定的。但是map是由两个属性确定的，所以也被称为键值对（key-value pairs）。
此外，unordered_set官方不建议修改元素值，因为修改之后，哈希值可能会发生变化，这样就出问题了。需要的话，删除再加就行了。但是unordered_map并没有这种提示。

为什么会有个无序的map

据《A Tour of C++ Third Edition》中描述，使用unordered_map而非map是因为在很多情况下，使用处理过的数据查询速度要比有序的快很多。其实这很容易理解，不过这里要先说明一下map是什么样的。

C++ 中的 map 其实就是某些语言里的字典（dictionary）、关联数组（associative array）。

map 实际上是一个平衡二叉树（通常会使用红黑树），如下：

二叉树的查询时间是 $O(\log (n))$，假设有 1000000 个元素，那么最多只要 20 步就能找到这个元素。

这导致了一个现象：在很多时候，经过哈希函数处理的元素排列要比顺序的元素排列快很多。

经过哈希函数处理的元素排列是乱序的，这也是函数名中的“unordered”的由来。
unordered_map其实就是个哈希表。

举个例子，一个 1000000 个元素序列是升序的，那么如果查询的内容大多是较大的数，实际查询次数基本上都会超过 10 次。而经过哈希函数处理的乱序序列可能有的不足 10 次，有的超过 10 次，会比较平均。

正因如此，C++ 搞了个unordered_map避免这种问题。unordered_map结构如下：

unordered_map是通过标准库<hash>实现的，这部分内容你可以看看书中的内容，Bjarne Stroustrup 进行了一些简单地说明。书中基本上在强调找到一个好的 hash 函数是核心，因为只有这个函数好（适合要应用的数据）， 乱序才能比顺序快。

举个🌰（使用方法）

下面是官方文档中的一个例子，个人感觉非常全面，就不再自己想了。那么就通过这个例子来说明一下如何使用unordered_map。

头文件如下：

#include <iostream>
#include <string>
#include <unordered_map>

在main()主函数中，首先创建一个unordered_map，两个属性都是字符串，拥有3个元素：

std::unordered_map<std::string, std::string> u =
{{"RED", "#FF0000"},{"GREEN", "#00FF00"},    {"BLUE", "#0000FF"}
};

接下来官方声明了一个lambda帮助函数（Helper lambda function）来打印键值对，这样可以大大减少后续输出时的代码量：

auto print_key_value = [](const auto& key, const auto& value)
{std::cout << "Key:[" << key << "] Value:[" << value << "]\n";
};

接下来有两种打印方式：第一种是普通的，第二种是 C++17 的结构化绑定（structured binding），个人推荐第二种：

for (const std::pair<const std::string, std::string>& n : u)print_key_value(n.first, n.second);for (const auto& [key, value] : u)print_key_value(key, value);

此时输出为：

Key:[BLUE] Value:[#0000FF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]

如果想给这个unordered_map添加两个新的键值对，那么直接使用下面的方法就行：

u["BLACK"] = "#000000";
u["WHITE"] = "#FFFFFF";

这样就已经添加了，你可以打印一下看看，输出如下：

Key:[BLACK] Value:[#000000]	<-----这个是新插入的
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]	<-----这个是新插入的
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]

这里你可以看到，BLACK和WHITE并不是按照顺序插入到最后的，这里体现了它的“unordered”，而这是它的哈希函数做的。

除此之外，如果你对一个不存在的键（key）使用运算符[]，那么会插入一个新的键值对：

print_key_value("new_key", u["new_key"]);

执行完这行代码之后，如果你想输出请使用auto类型，因为这里的键值对里的值并没有设置，如果使用前面的输出代码可能会报错（不过这个例子并没有出现错误），这里官方输出代码如下：

for (const auto& n : u)print_key_value(n.first, n.second);

此时输出如下：

Key:[new_key] Value:[]	<-----这个是新插入的
Key:[GREEN] Value:[#00FF00]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]
Key:[RED] Value:[#FF0000]

如果你想借此机会插入一个键值对，可以使用下面的代码：

print_key_value("new_key", u["new_key"]="#123456");for (const auto& n : u)print_key_value(n.first, n.second);

此时输出为：

Key:[new_key] Value:[#123456]	<-----这个是新插入的
Key:[GREEN] Value:[#00FF00]
Key:[BLACK] Value:[#000000]
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]
Key:[RED] Value:[#FF0000]

需要注意不能写成下面这样，因为是[]操作符实现新建键值对的，而这样没有使用[]：

print_key_value("new_key", u["#123456");for (const auto& n : u)print_key_value(n.first, n.second);

此时输出结果为：

Key:[BLACK] Value:[#000000]	<-----这个是新插入的
Key:[BLUE] Value:[#0000FF]
Key:[WHITE] Value:[#FFFFFF]
Key:[GREEN] Value:[#00FF00]
Key:[RED] Value:[#FF0000]

可以看到值并不是我们想要的#123456。

完整代码

#include <iostream>
#include <string>
#include <unordered_map>int main()
{// 创建一个unordered_map，两个属性都是字符串，拥有3个元素。std::unordered_map<std::string, std::string> u ={{"RED", "#FF0000"},{"GREEN", "#00FF00"},{"BLUE", "#0000FF"}};//print_key_value是一个lambda帮助函数（Helper lambda function）用来打印键值对//这样可以大大减少后续输出时的代码量auto print_key_value = [](const auto& key, const auto& value){std::cout << "Key:[" << key << "] Value:[" << value << "]\n";};std::cout << "迭代并打印unordered_map的键值对，并且显示其类型：\n";for (const std::pair<const std::string, std::string>& n : u)print_key_value(n.first, n.second);std::cout << "\n使用C++17结构化绑定（structured binding）迭代和打印键值对:\n";for (const auto& [key, value] : u)print_key_value(key, value);// 向unordered_map添加两个新条目u["BLACK"] = "#000000";u["WHITE"] = "#FFFFFF";for (const auto& [key, value] : u)print_key_value(key, value);std::cout << "\n通过键（key）输出值：\n""RED的HEX:[" << u["RED"] << "]\n""BLACK的HEX:[" << u["BLACK"] << "]\n\n";std::cout << "对不存在的键（key）使用运算符[]插入新的键值对:\n";print_key_value("new_key", u["new_key"]);std::cout << "\n使用`auto`类型迭代打印键值对；“new_key现在是映射中的键（key）:\n";for (const auto& n : u)print_key_value(n.first, n.second);
}

希望能帮到有需要的人～

参考资料

《A Tour of C++ Third Edition》：6.5.6 hash<>，12.6 unordered_map。

C++ unordered_set 和 unordered_map 的中文官方文档，很多本文没有提到的功能都可以自行查看这里：
std::unordered_set - cppreference.com
std::unordered_map- cppreference.com