C++ unordered_map 和 unordered_set 基于哈希表实现，提供平均 O(1) 的查找、插入和删除效率。底层通过桶数组存储指向链表头部的指针，利用链地址法处理哈希冲突。哈希函数将键映射到桶索引，装载因子控制扩容时机。支持自定义哈希函数以适应复杂类型。理解其原理有助于编写高性能代码并优化内存使用。
unordered_map 和 unordered_set？在 C++ 中， 和 是两个基于 实现的容器。
unordered_mapunordered_set#include <iostream>
#include <unordered_map>
#include <unordered_set>
int main() {
// 使用 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 (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++）的不同而有所差异。下面是对桶的具体结构的详细分析：
桶 是一个容器，用于存储所有映射到该桶的元素。其底层实现通常是以下两种方式之一：
每个桶存储一个指向链表（或其他结构）的指针。例如：
[ 桶 0 ] -> nullptr
[ 桶 1 ] -> head -> [key2] -> [key1] -> nullptr
[ 桶 2 ] -> nullptr
[ 桶 3 ] -> head -> [key3] -> nullptr
这种实现中，桶本身存储指向链表的指针，而链表存储具体的键值。
std::vector 或类似结构）每个桶本身是一个动态数组（如 std::vector），用于直接存储冲突的元素：
[ 桶 0 ] -> 空
[ 桶 1 ] -> [key1, key2]
[ 桶 2 ] -> 空
[ 桶 3 ] -> [key3]
大多数标准库实现中，unordered_map 和 unordered_set 的桶是用 std::vector 作为底层数据结构，并且每个桶存储一个 指向链表头部的指针，而链表用来存储具体元素。原因如下：
std::vector 管理桶std::vector 是常见的选择，因为它提供高效的随机访问（通过下标快速定位桶）。unordered_map）或单独的键（对于 unordered_set），并且包含指向下一个节点的指针。哈希表维护一个桶数组，这个数组的大小会根据装载因子（load factor）动态调整：
rehashing 过程中：
std::vector，它存储指向链表的指针。std::vector）和动态操作的灵活性（通过链表）。哈希表中的每一个桶都是一个存放数据的单元，用于存放一个或多个元素。当我们向哈希表中插入一个键（key）时，哈希表会先通过 哈希函数 将该键映射到一个特定的桶。
假设有一个简单的哈希表结构，包含 5 个桶：
哈希表结构：[ 桶 0 ] [ 桶 1 ] [ 桶 2 ] [ 桶 3 ] [ 桶 4 ]
哈希函数将键值转化为整数值（索引），表示对应桶的位置。例如，对于键 key1，如果哈希函数将其映射到索引 1，那么 key1 就会存储在 桶 1 中。
设 hash(key1) = 1，即 key1 存在 桶 1 中。
由于不同的键可能会映射到同一个桶中，这种现象称为 哈希冲突。在 unordered_map 和 unordered_set 中，通常使用 链地址法 来处理冲突。链地址法是指，每个桶中有一个链表，用于存储发生冲突的元素。每当冲突发生时，新元素会被追加到链表的末尾。
例如，假设 key1 和 key2 都映射到 桶 1，哈希表的结构如下所示：
[ 桶 0 ] [ 桶 1 ] [ 桶 2 ] [ 桶 3 ] [ 桶 4 ]
head -> key1 -> key2
这里，桶 1 存储一个链表，其中 key1 是链表头节点，key2 是链表的下一个节点。
在链表结构中：
具体过程如下：
假设我们要插入 key3，且 hash(key3) = 1（与 key1 和 key2 冲突）。哈希表插入后的结构如下：
[ 桶 0 ] [ 桶 1 ] [ 桶 2 ] [ 桶 3 ] [ 桶 4 ]
head -> key1 -> key2 -> key3
假设要查找 key2，查找步骤如下：
hash(key2) = 1。head 是 key1，不匹配，继续向后找；key2，匹配成功，返回结果。在理想情况下，哈希表能够将数据分布在不同的桶中，每个桶中只有少量元素，查找和插入的时间复杂度接近 O(1)。我们可以通过以下符号化结构了解平均 O(1) 时间复杂度的实现条件。
假设哈希表结构如下，其中每个桶中只有一个节点：
[ 桶 0 ] [ 桶 1 ] [ 桶 2 ] [ 桶 3 ] [ 桶 4 ]
key0 key1 key2 key3 key4
这种情况下，哈希表中没有冲突，查找过程只需要哈希函数定位到特定桶即可完成，查找时间为 O(1)。
当哈希表元素数量增加或哈希函数无法避免冲突时，多个键会映射到同一个桶。例如：
[ 桶 0 ] [ 桶 1 ] [ 桶 2 ] [ 桶 3 ] [ 桶 4 ]
head -> key1 -> key2
此时，在桶 1 中查找 key2，需要遍历链表，这样的查找复杂度接近 O(n)。不过，在实际使用中，C++ unordered_map 会自动 扩容，将桶数量增多，从而降低冲突发生的几率，使查找平均复杂度保持在 O(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;
}
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;
}
负载因子定义了哈希表的装填情况。过高的负载因子会导致更多冲突，进而影响性能。在 C++ 中，可以通过 max_load_factor 和 rehash 函数管理负载因子。
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) 的时间内完成查找、插入和删除操作。这种特性在需要高效查找的应用场景中非常有用。理解其底层的哈希表原理及冲突处理方法，是编写高性能代码的基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online