【数据结构】`unordered_map` 和 `unordered_set` 的底层原理

unordered_map 和 unordered_set 是 C++ 标准库中的两个容器，它们被广泛应用于需要快速查找的场景中。它们的查找、插入和删除的平均时间复杂度都是 O(1)，这也是它们的一个重要特性。本文将详细介绍 unordered_map 和 unordered_set 的底层原理，帮助计算机专业的小白理解什么是哈希、桶以及为什么它们的查找效率如此之高。

本篇文章需要有unordered_map、unordered_set、vector等的基础，若不清楚，建议先去了解后再来阅读【编程语言】在C++中使用map与unordered_map【编程语言】C++ 新手指南：如何使用 set 和 unordered_set【编程语言】C++ 中 vector 的常用操作方法【数据结构】链表详解：数据节点的链接原理【数据结构】时间复杂度和空间复杂度是什么？

全文共计2600字，耗时5天缝缝补补写完

若本文对你有帮助的话，可以给我点点关注和赞👍，感谢。

一、什么是 unordered_map 和 unordered_set？

在 C++ 中，unordered_map 和 unordered_set 是两个基于 哈希表 实现的容器。

• unordered_map：是一个关联容器，用于存储键值对（key-value pairs）。每个键（key）是唯一的，并且与一个值（value）相关联。
• unordered_set：是一个无序的集合，用于存储唯一的键值（key）。它不存储重复元素。

简单代码示例

#include<iostream>#include<unordered_map>#include<unordered_set>intmain(){ // 使用 unordered_map std::unordered_map<int, std::string> map; map[1]="One"; map[2]="Two";// 使用 unordered_set std::unordered_set<int> set; set.insert(1); set.insert(2);// 输出 map 和 set 内容 std::cout <<"Map:"<< std::endl;for(constauto& pair : map){  std::cout << pair.first <<": "<< pair.second