在 C++ 中使用 HashMap

1. 在 C++ 中使用带有 std::map 的 HashMap
2. 在 C++ 中使用带有 std::unordered_map 的 HashMap
3. C++ 中的关键差异以及何时使用每个映射

HashMap 是一种重要的数据结构，包含键值对，其中可以使用相关键检索值。每个键都映射到 HashMap 中的一个特定值。

在迭代期间使用键，我们可以更快地访问相应的值。因此，在检索值时，HashMap 被认为是一种有效且必不可少的数据结构，具有任何类型的键和值。

在 C++ 11 之前，标准定义的哈希表不存在于 C++ 的标准库中，但有些不同的实现者有哈希表的非标准变体，通常称为 HashMap。与 C++ 11 一起，哈希表的标准实现被添加到标准库中。

尽管如此，由于哈希表的各种变体是来自不同库的 HashMap，因此决定使用单独的名称来调用新实现以避免混淆。

因此，在 C++ 中，std::unordered_map 是 HashMap 的替代名称，但另一个映射使用键值对概念，std::map。

std::unordered_map 和 std::map 之间存在关键区别。顾名思义，std::unordered_map 中的元素是无序的，而 std::map 中的元素是有序的。

在 C++ 中使用带有 std::map 的 HashMap

std::map 属于关联容器的类别，其中元素存储在映射的键值对中。在 std::map 和 std::unordered_map 中，键应该始终是唯一的，但可以有多个映射值相似的唯一键。

std::map 是使用自平衡二叉搜索树（AVL 树/红黑树）实现的。BST（Self-Balancing Binary Search Tree）的主要特点是当插入和删除元素时高度总是自动保持在最小值。

在 std::map 中，平均时间复杂度以对数方式取决于存储的元素数量；因此，一个操作发生平均需要 O(log n) 时间。在 O(log n) 中，O 是指 Big O 表示法，n 是指存储的元素数。

因此，BST 在创建和维护有序列表时很有帮助。

例子：

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

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

输出：

Number of Players 2
1: Chen Long
2: Lin Dan

在 C++ 中使用带有 std::unordered_map 的 HashMap

std::unordered_map 是使用 C++ 中的哈希表实现的。哈希表也属于关联容器。映射的值存储在桶或槽数组中的哈希表中，可以从中检索必要的值。

这个索引是使用散列函数，散列码完成的。std::unordered_map 的搜索、插入和删除的平均时间复杂度是 O(1)，其中 O 是 Big O 表示法，这就是 std::unordered_map 非常有效。

例子：

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> info;

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

输出：

Number of Players 15
Year 2022
Age 18

C++ 中的关键差异以及何时使用每个映射

当比较 std::unordered_map 和 std::map 时，两者之间的效率差距是巨大的。

std::unordered_map 显然比 std::map 有相当大的性能优势。这主要是因为 std::unordered_map 可以直接寻址值，因为它们被放置在插槽中，因此没有需要保留的顺序。

另一方面，std::map 有一个需要保留的顺序；因此，它会消耗更多时间。对于小型数据集，这种效率可能不可见，但对于大型数据集，这种差异是巨大的。

std::unordered_map 可用于从数据集中访问单个元素或在不需要顺序时保持元素计数。

std::map 也确实比 std::unordered_map 有一些优势。通常，BST 可以比哈希表更快地实现，我们可以用我们喜欢的方式来实现，但是对于哈希，我们需要严重依赖库。

因此，与 std::unordered_map 相比，std::map 可以轻松实现。此外，在排序方面，在 std::map 中对键进行排序比在 std::unordered_map 中排序要容易得多，因为 inorder traversing 不是哈希表的自然操作，而是适用于 BST。

std::map 可用于按排序顺序打印数据等情况，其中需要对数据进行排序以进行搜索查询、排序统计等。

std::map 和 std::unordered_map 都有某些相似之处和不同之处，可以根据当时的需要进行操作。