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

news/2024/11/19 12:52:04/

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>int main() {// 使用 unordered_mapstd::unordered_map<int, std::string> map;map[1] = "One";map[2] = "Two";// 使用 unordered_setstd::unordered_set<int> set;set.insert(1);set.insert(2);// 输出 map 和 set 内容std::cout << "Map:" << std::endl;for (const auto& pair : map) {std::cout << pair.first << ": " << pair.second << std::endl;}std::cout << "Set:" << std::endl;for (const auto& item : set) {std::cout << item << std::endl;}return 0;
}

二、哈希表的工作原理

哈希表的关键概念包括桶（bucket）、哈希函数（hash function）、链表等。我们将通过一些符号表示出其内部结构。

在标准库的实现中，哈希表的桶通常是一个 std::vector，但其具体实现可能因标准库（如 libstdc++ 或 libc++）的不同而有所差异。下面是对桶的具体结构的详细分析：

1. 桶的结构

桶 是一个容器，用于存储所有映射到该桶的元素。其底层实现通常是以下两种方式之一：

(1) 指针形式

每个桶存储一个指向链表（或其他结构）的指针。例如：

[ 桶0 ] -> nullptr
[ 桶1 ] -> head -> [key2] -> [key1] -> nullptr
[ 桶2 ] -> nullptr
[ 桶3 ] -> head -> [key3] -> nullptr

这种实现中，桶本身存储指向链表的指针，而链表存储具体的键值。

(2) 动态数组形式（std::vector 或类似结构）

每个桶本身是一个动态数组（如 std::vector），用于直接存储冲突的元素：

[ 桶0 ] -> 空
[ 桶1 ] -> [key1, key2]
[ 桶2 ] -> 空
[ 桶3 ] -> [key3]

2. 实际实现中的常见选择

大多数标准库实现中，unordered_map 和 unordered_set 的桶是用 std::vector 作为底层数据结构，并且每个桶存储一个 指向链表头部的指针，而链表用来存储具体元素。原因如下：

(1) 使用 std::vector 管理桶
  • std::vector 是常见的选择，因为它提供高效的随机访问（通过下标快速定位桶）。
  • 动态扩展的特性允许哈希表在需要时进行 rehashing（增加桶数量）。
(2) 使用链表存储冲突元素
  • 链表 允许高效插入和删除元素，尤其在发生哈希冲突时。
  • 每个链表节点可能存储键值对（对于 unordered_map）或单独的键（对于 unordered_set），并且包含指向下一个节点的指针。

3. 哈希表中桶的管理

哈希表维护一个桶数组，这个数组的大小会根据装载因子（load factor）动态调整：

  • 装载因子 是表中元素总数与桶数量的比值。例如：
    • 如果有 10 个桶和 30 个元素，装载因子为 3。
  • rehashing 发生时，桶的数量通常会增大到一个质数（比如 2 倍+1），以减少冲突概率。

rehashing 过程中：

  • 将旧桶中的元素重新分配到新桶中。
  • 由于每个桶的元素重新映射到新桶，链表也会被重新构造。

4. 小结

  • 桶本身通常是一个 std::vector，它存储指向链表的指针。
  • 链表 是冲突处理的主要数据结构，用于存储同一桶中的多个元素。
  • 这种设计兼顾了随机访问的效率（通过 std::vector）和动态操作的灵活性（通过链表）。

三、 哈希表的基本结构

哈希表中的每一个桶都是一个存放数据的单元，用于存放一个或多个元素。当我们向哈希表中插入一个键（key）时，哈希表会先通过 哈希函数 将该键映射到一个特定的桶。如下图所示：

假设有一个简单的哈希表结构，包含 5 个桶：

哈希表结构:
[ 桶0 ]    [ 桶1 ]    [ 桶2 ]    [ 桶3 ]    [ 桶4 ]

1. 哈希函数的作用

哈希函数将键值转化为整数值（索引），表示对应桶的位置。例如，对于键 key1，如果哈希函数将其映射到索引 1，那么 key1 就会存储在 桶 1 中。

设 hash(key1) = 1，即 key1 存在 桶 1 中。

2. 哈希冲突的处理：链地址法

由于不同的键可能会映射到同一个桶中，这种现象称为 哈希冲突。在 unordered_map 和 unordered_set 中，通常使用 链地址法 来处理冲突。链地址法是指，每个桶中有一个链表，用于存储发生冲突的元素。每当冲突发生时，新元素会被追加到链表的末尾。

例如，假设 key1 和 key2 都映射到 桶 1，哈希表的结构如下所示：

[ 桶0 ]      [ 桶1 ]               [ 桶2 ]       [ 桶3 ]       [ 桶4 ]head -> key1 -> key2

这里，桶 1 存储一个链表，其中 key1 是链表头节点，key2 是链表的下一个节点。

3. 链表结构的插入和查找

在链表结构中：

  • 插入：新元素被追加到链表末尾。
  • 查找：通过遍历链表，依次检查节点是否与目标键匹配。

具体过程如下：

插入过程：

假设我们要插入 key3，且 hash(key3) = 1（与 key1 和 key2 冲突）。哈希表插入后的结构如下：

[ 桶0 ]      [ 桶1 ]                       [ 桶2 ]       [ 桶3 ]       [ 桶4 ]head -> key1 -> key2 -> key3
查找过程：

假设要查找 key2，查找步骤如下：

  1. 通过哈希函数找到桶索引：hash(key2) = 1。
  2. 在桶 1 中找到对应链表，遍历链表并依次检查各节点：
    • head 是 key1，不匹配，继续向后找；
    • 第二个节点是 key2，匹配成功，返回结果。

四、为什么查找是 O(1)

在理想情况下，哈希表能够将数据分布在不同的桶中，每个桶中只有少量元素，查找和插入的时间复杂度接近 O(1)。我们可以通过以下符号化结构了解平均 O(1) 时间复杂度的实现条件。

1. 理想情况

假设哈希表结构如下，其中每个桶中只有一个节点：

[ 桶0 ]    [ 桶1 ]    [ 桶2 ]    [ 桶3 ]    [ 桶4 ]key0      key1      key2      key3      key4

这种情况下，哈希表中没有冲突，查找过程只需要哈希函数定位到特定桶即可完成，查找时间为 O(1)。

2. 发生冲突时的情况

当哈希表元素数量增加或哈希函数无法避免冲突时，多个键会映射到同一个桶。例如：

[ 桶0 ]         [ 桶1 ]                  [ 桶2 ]       [ 桶3 ]       [ 桶4 ]head -> key1 -> key2

此时，在桶 1 中查找 key2，需要遍历链表，这样的查找复杂度接近 O(n)。不过，在实际使用中，C++ unordered_map 会自动 扩容，将桶数量增多，从而降低冲突发生的几率，使查找平均复杂度保持在 O(1)。

五、代码示例

1. unordered_map 查找示例

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<std::string, int> map;map["apple"] = 1;map["banana"] = 2;map["cherry"] = 3;std::string key = "banana";if (map.find(key) != map.end()) {std::cout << "Found: " << key << " => " << map[key] << std::endl;} else {std::cout << key << " not found." << std::endl;}return 0;
}

2. unordered_set 查找示例

#include <iostream>
#include <unordered_set>int main() {std::unordered_set<int> set = {1, 2, 3, 4, 5};int key = 3;if (set.find(key) != set.end()) {std::cout << "Found: " << key << std::endl;} else {std::cout << key << " not found." << std::endl;}return 0;
}

六、扩展内容：使用哈希表时的注意事项

1. 负载因子

负载因子定义了哈希表的装填情况。过高的负载因子会导致更多冲突，进而影响性能。在 C++ 中，可以通过 max_load_factor 和 rehash 函数管理负载因子。

2. 自定义哈希函数

C++ 提供了 std::hash 作为默认的哈希函数，但在某些情况下我们可以自定义哈希函数。

示例：自定义哈希函数

#include <iostream>
#include <unordered_map>
#include <functional>struct Key {int x, y;bool operator==(const Key& other) const {return x == other.x && y == other.y;}
};struct KeyHash {std::size_t operator()(const Key& k) const {return std::hash<int>()(k.x) ^ (std::hash<int>()(k.y) << 1);}
};int main() {std::unordered_map<Key, int, KeyHash> map;map[{1, 2}] = 3;Key key = {1, 2};if (map.find(key) != map.end()) {std::cout << "Found key (1, 2) with value: " << map[key] << std::endl;} else {std::cout << "Key (1, 2) not found." << std::endl;}return 0;
}

六、总结

unordered_map 和 unordered_set 是 C++ 中重要的容器类型，它们基于哈希表实现，能够在平均 O(1) 的时间内完成查找、插入和删除操作。这种特性在需要高效查找的应用场景中非常有用。理解其底层的哈希表原理及冲突处理方法，是编写高性能代码的基础。


http://www.ppmy.cn/news/1548235.html

相关文章

QT QLabel双击事件

QT QLabel双击事件

新建类&#xff1a; DoubleClickLabel .h #pragma once#include <QLabel>class DoubleClickLabel : public QLabel {Q_OBJECTpublic:DoubleClickLabel(QWidget *parent);~DoubleClickLabel(); signals:void doubleClicked();protected: //这里重写双击事件virtual v…
阅读更多...
学习rust语言宏之macro_rules!

学习rust语言宏之macro_rules!

学习rust语言&#xff0c;必然不可避免要了解和熟悉宏。rust语言的宏功能非常强大&#xff0c;通过合理的编写利用宏&#xff0c;可以简化程序代码&#xff0c;也少写很多代码。今天我们先从宏的基本编写方法macro_rules开始&#xff1a; 1&#xff0c;格式 macro_rules! $na…
阅读更多...
[C++]：C++11(一)

[C++]：C++11(一)

1. 统一列表初始化 1.1 C11 之前的初始化方式 在 C11 标准中&#xff0c;引入了一个非常实用且强大的特性——统一列表初始化&#xff08;Uniform Initialization&#xff09;&#xff0c;它为我们在初始化各种类型的对象时提供了一种统一且方便的语法形式&#xff0c;极大地…
阅读更多...
基于 AI 智能名片 2 + 1 链动模式商城小程序的立体连接营销策略研究

基于 AI 智能名片 2 + 1 链动模式商城小程序的立体连接营销策略研究

摘要&#xff1a;本文围绕立体连接中线下连通社群这一环节展开&#xff0c;阐述其具体做法及意义&#xff0c;并深入探讨如何将 AI 智能名片 2 1 链动模式商城小程序融入其中&#xff0c;以优化立体连接营销策略&#xff0c;提升营销效果。 一、引言 在当今复杂多变的市场环境…
阅读更多...
WebRTC实现双端音视频聊天（Vue3 + SpringBoot）

WebRTC实现双端音视频聊天（Vue3 + SpringBoot）

目录 概述 相关概念 双端连接整体实现步骤概述 文章代码实现注意点 STUN和TURN服务器的搭建 开发过程描述 后端开发流程 前端开发流程 效果演示 Gitee源码地址 概述 文章描述使用WebRTC技术实现一对一音视频通话。 由于设备摄像头限制&#xff08;一台电脑作测试无法…
阅读更多...
商城小程序（源码+文档+部署+讲解）

商城小程序（源码+文档+部署+讲解）

本文将深入解析“商城小程序”的项目&#xff0c;探究其架构、功能以及技术栈&#xff0c;并分享获取完整源码的途径。 系统概述 商城小程序是一款专为商城小程序设计的管理平台&#xff0c;旨在通过集成各种商城管理功能来提高商城的运营效率和用户体验。该系统提供了从登录…
阅读更多...
Leetcode打卡：最少翻转次数使二进制矩阵回文II

Leetcode打卡：最少翻转次数使二进制矩阵回文II

执行结果&#xff1a;通过 题目&#xff1a;3240 最少翻转次数使二进制矩阵回文II 给你一个 m x n 的二进制矩阵 grid 。 如果矩阵中一行或者一列从前往后与从后往前读是一样的&#xff0c;那么我们称这一行或者这一列是 回文 的。 你可以将 grid 中任意格子的值 翻转 &…
阅读更多...
[AI] 人工智能会导致大规模失业吗？——技术发展与就业关系的深度解析

[AI] 人工智能会导致大规模失业吗？——技术发展与就业关系的深度解析

近年来，人工智能（AI）的快速发展引发了社会对其潜在影响的深刻思考，其中一个核心问题就是：人工智能是否会导致大规模失业？事实上，人工智能在提高生产效率、优化工作流程、取代部分重复性工作的同时，也在为社会带来新的职业机会。然而，关于技术和就业的关系仍然存在诸多…
阅读更多...
最新文章

Copyright @ 2022~2023