在 C++ 中使用 HashMap

在 C++ 中，哈希映射由 std::unordered_map 提供；std::map 是相关的键值容器，会按顺序保存键。两者都是关联容器：每个键都唯一，并对应一个映射值。不同的键可以对应相同的值。如果需要按键查找，可以使用其中任意一种；具体选择取决于是否需要按顺序遍历。

C++ 标准没有规定 std::map 必须采用哪种内部实现。它对外呈现的顺序由键的比较规则决定；使用默认比较器时，键按升序排列。相比之下，std::unordered_map 使用哈希函数和桶，其迭代顺序未作规定。不要依赖某次运行中恰好看到的顺序。

C++ 中哈希映射的工作方式

包含 <map> 或 <unordered_map>，并声明键和值的类型，例如 std::map<int, std::string>。insert 仅在键不存在时添加键值对；通过 operator[] 赋值时，如果键尚不存在，容器会先插入一个经过值初始化的映射值，然后再赋值。对于 int 这样的标量映射类型，值初始化会先得到零，再执行赋值。给已有键赋值会更新其值，不会创建重复键。如果要先检查键是否存在再使用其值，可以调用 find。at 也会查找键，但键不存在时会报告 std::out_of_range。

提供的运行记录显示，原始的两个示例都成功运行。下面 std::map 的输出是记录中的实际输出；后面的无序容器示例新增了遍历循环，因此不对修改后示例的输出顺序作任何保证。

使用 std::map 保存有序键

如果需要按比较器确定的顺序遍历键，或需要查找大于等于某个值的首个键等有序操作，请使用 std::map。它的查找、插入和删除操作耗时为对数级，即 O(log n)，其中 n 是元素数量。这种可预测的开销和有序遍历适用于生成报告、处理范围以及列出排序后的内容。标准保证的是排序行为，而不是某种特定的树实现。

运行以下示例：

本节中的代码以及显示的标签或输出仍为英文。

#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> players;
  players.emplace(2, "Lin Dan");
  players.emplace(1, "Chen Long");

  const auto found = players.find(1);
  if (found != players.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : players) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
}

1: Chen Long
1: Chen Long
2: Lin Dan

查找操作会打印键 1；循环按比较器顺序遍历键，因此无论插入顺序如何，1 都排在 2 前面。

使用 std::unordered_map 进行基于哈希的查找

如果按键查找是首要需求，而且不需要排序遍历，可以选择 std::unordered_map。查找、插入和删除操作的平均复杂度为 O(1)，但最坏情况下可能达到 O(n)，例如大量键发生冲突时。重新哈希也可能改变迭代顺序，并使迭代器失效。该容器有自己的哈希和相等性要求：相等的键必须产生相同的哈希值。

运行以下示例：

本节中的代码以及显示的标签或输出仍为英文。

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

int main() {
  std::unordered_map<std::string, int> scores;
  scores["Ada"] = 8;
  scores["Lin"] = 11;

  const auto found = scores.find("Ada");
  if (found != scores.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : scores) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
  std::cout << "Players: " << scores.size() << '\n';
}

基于范围的循环会遍历 scores 中的每一项。条目可能以任意顺序出现，C++ 标准和此示例都不保证特定的遍历顺序。如果需要按顺序展示，请将键收集到另一个列表中并排序。

如何在 std::map 与 std::unordered_map 之间选择

对于词频统计或不关心顺序的缓存，std::unordered_map 通常是自然的选择。需要排序输出或按键进行范围查询时，请使用 std::map。如果无序容器适合查找需求，但展示结果时需要排序，就先收集并排序键，再进行打印，不要假定容器的迭代顺序。选择容器时，除了平均速度，还要考虑所需行为；如果性能对应用很重要，请使用有代表性的数据进行基准测试。

两种容器都支持键值访问，但迭代行为和性能保证不同。遍历时若必须按键排序，请使用 std::map；如果需要基于哈希的查找且不关心顺序，请使用 std::unordered_map。有关有序遍历的另一个示例，请参阅 C++ 中的中序遍历。