在 C++ 中使用 HashMap
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 <string>
#include <map>
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 | 标准::地图 | |
---|---|---|
搜索时间 | O(log n) | O(1) |
插入时间 | O(log n) + 再平衡时间 | O(1) |
删除时间 | O(log n) + 再平衡时间 | O(1) |
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
都有某些相似之处和不同之处,可以根据当时的需要进行操作。
Nimesha is a Full-stack Software Engineer for more than five years, he loves technology, as technology has the power to solve our many problems within just a minute. He have been contributing to various projects over the last 5+ years and working with almost all the so-called 03 tiers(DB, M-Tier, and Client). Recently, he has started working with DevOps technologies such as Azure administration, Kubernetes, Terraform automation, and Bash scripting as well.