C++进阶—哈希/unordered系列关联式容器/底层结构（一篇文章学习哈希）

**C++进阶—哈希/unordered系列关联式容器/底层结构**

在 C++ 中，`std::hash_map` 和 `std::unordered_map` 是两种常用的关联式容器，它们都是基于哈希表的。然而，在 C++11 之后，`std::unordered_map` 成为了更推荐的选择，而 `std::hash_map` 已经被标记为过时。

在本文中，我们将深入探讨哈希表的基本概念、底层结构以及 `std::unordered_map` 的实现细节。我们还会提供一些示例代码来帮助理解这些概念。

**哈希表的基本概念**

哈希表是一种基于数组的数据结构，它通过计算一个键值（key）得到一个索引（index），然后将对应的值存储在该索引位置。这种方式可以实现快速查找和插入元素。

哈希表的主要特点是：

* 快速查找：通过计算键值，可以直接找到相应的值。
* 快速插入：新元素可以直接插入到对应的索引位置。

然而，哈希表也有一些缺点，如：

* 冲突：当两个不同的键值计算得到相同的索引时，就会发生冲突。这种情况下，需要进行处理，比如链式存储或开放寻址。
* 空间浪费：如果哈希表过大，可能会导致空间浪费。

**哈希表的底层结构**

哈希表通常由以下几个部分组成：

* **桶数组**（Bucket Array）：这是哈希表的主要存储区域，每个桶对应一个索引。
* **链式存储**（Linked List）：用于解决冲突问题，新元素会被插入到链式存储中。

在 C++ 中，`std::unordered_map` 使用桶数组作为底层结构。每个桶是一个 `std::unordered_bucket` 对象，它包含一个哈希表和一个链式存储。

**示例代码**

下面是使用 `std::unordered_map` 的示例代码：

cpp#include <iostream>
#include <unordered_map>

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

 // 插入元素 map[1] =10;
 map[2] =20;
 map[3] =30;

 // 查找元素 auto it = map.find(2);
 if (it != map.end()) {
 std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
 }

 return0;
}