穿越数据迷宫：C++哈希表的奇幻旅程
穿越数据迷宫：C++哈希表的奇幻旅程
前言
在C++的世界中，哈希表是一种高效、独特的数据结构，被广泛应用于需要快速查找、插入、删除的场景。通过哈希函数将数据映射到表中，它不仅提高了操作效率，还在解决冲突时展现了精巧的设计。哈希表在算法的应用中尤为重要，无论是缓存、字典处理还是集合操作，都离不开它的身影。本篇博客将带你一步步深入理解哈希表的实现原理及其应用，让你在编码之路上更上一层楼。
📔一、unordered系列关联式容器
在 C++ 标准库中，unordered 系列容器（如 unordered_map 和 unordered_set）是一类基于哈希表实现的关联式容器。与传统的 map 和 set 容器不同，unordered 容器通过哈希函数实现了无序存储，能够在均摊
时间复杂度内完成插入、查找和删除操作。这使得 unordered 系列容器在处理需要快速查找的场景中非常高效。
📕1.1 unordered 容器概述
unordered 容器包含以下几种类型，主要用于不同类型的键值对或集合操作：
unordered_set：一个不包含重复元素的集合，存储的是唯一的键。unordered_multiset：与unordered_set相似，但允许包含重复元素。unordered_map：一个键值对的容器，每个键只能出现一次，键是唯一的。unordered_multimap：一个键值对的容器，允许键重复。
与传统的有序容器（如 map 和 set）不同，unordered 容器中的元素没有特定的顺序。因此，unordered_map 和 unordered_set 更加适用于不关心元素顺序、仅关注快速访问的场景。
📕1.2 哈希表在 unordered 容器中的实现原理
unordered 容器的核心数据结构是哈希表，它利用哈希函数将键映射到表中的位置。在哈希表中，unordered 容器采用了一种**桶（bucket）**的机制来存储数据：
- 哈希函数：将键值映射到特定的哈希值，这个哈希值会决定键值对存储的位置（即桶）。
- 桶：哈希表中的每个位置称为一个桶，键值对根据哈希值分布在不同的桶中。
- 冲突处理：当多个键映射到同一个桶时，使用链表（或其他方法）来解决冲突。这种冲突解决方法通常称为拉链法。
📕1.3 unordered 容器的特点
- 均摊时间复杂度：在理想的情况下，插入、查找和删除的平均时间复杂度为
。
- 无序性：
unordered容器不维护元素的顺序，元素顺序与插入顺序无关。 - 哈希函数与相等比较器：可以指定自定义的哈希函数和比较器，适用于自定义类型和不同的哈希策略。
📔二、unordered_set 和 unordered_map 的基本操作
📕2.1 unordered_set 的基本用法
unordered_set 是一个集合，用于存储唯一的元素，元素的顺序是无序的。主要用在需要快速查找元素的场景中。
📖1. 创建和初始化
#include <unordered_set>
#include <iostream>
int main() {
std::unordered_set<int> uset = {1, 2, 3, 4, 5}; // 初始化
// 遍历输出元素
for (const int& num : uset) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}📖2. 插入元素
使用 insert 方法插入元素。如果元素已存在，insert 不会插入重复元素。
uset.insert(6); // 插入元素6
uset.insert(3); // 3已存在，不插入📖3. 查找元素
使用 find 方法查找元素，若找到则返回元素的迭代器，否则返回 end()。
if (uset.find(3) != uset.end()) {
std::cout << "3 存在于集合中" << std::endl;
}📖4. 删除元素
使用 erase 方法删除指定元素，可以传入元素值或迭代器。
uset.erase(4); // 删除元素4📖5. 大小和清空
size()获取集合的大小。clear()清空集合中的所有元素。
std::cout << "集合大小: " << uset.size() << std::endl;
uset.clear();📕2.2 unordered_map 的基本用法
unordered_map 是一种键值对关联容器，使用哈希表实现。每个键是唯一的，可以通过键快速访问对应的值。
📖1. 创建和初始化
#include <unordered_map>
#include <iostream>
#include <string>
int main() {
std::unordered_map<std::string, int> umap = {{"apple", 3}, {"banana", 5}, {"orange", 2}}; // 初始化
// 遍历键值对
for (const auto& kv : umap) {
std::cout << kv.first << " -> " << kv.second << std::endl;
}
return 0;
}📖2. 插入元素
使用 insert 或 operator[] 插入键值对。operator[] 如果键不存在，会插入新键并初始化值为默认值。
umap["grape"] = 10; // 插入或更新键为 "grape" 的值
umap.insert({"melon", 8}); // 插入键值对 {"melon", 8}📖3. 查找元素
使用 find 方法查找元素，若找到则返回指向键值对的迭代器，否则返回 end()。
auto it = umap.find("banana");
if (it != umap.end()) {
std::cout << "香蕉数量: " << it->second << std::endl;
}📖4. 删除元素
使用 erase 方法删除指定键的元素。
umap.erase("orange"); // 删除键 "orange"📖5. 大小和清空
size()获取unordered_map的键值对数量。clear()清空所有元素。
std::cout << "键值对数量: " << umap.size() << std::endl;
umap.clear();📔三、哈希表
哈希表是一种基于哈希函数的数据结构，用于快速存储和查找数据。它的核心思想是将键（Key）通过哈希函数转换为数组索引，从而实现快速的数据访问。哈希表被广泛用于字典、缓存、集合等需要高效查找的场景，是以上所介绍容器的底层结构。
📕3.1 哈希表的基本原理
哈希表包含以下几个核心概念：
- 哈希函数：将任意类型的键映射到数组中的一个索引位置。
- 桶（Bucket）：哈希表的每个索引位置称为一个桶，存储一个或多个元素。
- 冲突（Collision）：当不同的键被映射到相同的索引时发生冲突。
- 负载因子（Load Factor）：表示哈希表的填充程度，用公式
负载因子 = 元素个数 / 桶的数量表示。负载因子过高会影响性能，通常哈希表会在负载因子达到一定值时扩容。
哈希表的操作，如插入、删除、查找，在理想情况下的时间复杂度为
。这是因为哈希表可以通过哈希函数将键快速映射到对应的存储位置。
📕3.2 哈希函数
哈希函数是哈希表性能的核心，其目的是将键均匀地分布在哈希表的桶中，减少冲突的发生。好的哈希函数具有以下特性：
- 均匀性：不同的键被分布在不同的桶中，避免过多的冲突。
- 快速计算：哈希函数的计算速度应尽可能快，以提高哈希表操作的整体效率。
在 C++ 中，标准库提供了许多内置类型的哈希函数，如 std::hash<int>、std::hash<std::string> 等。此外，用户也可以为自定义类型定义自己的哈希函数。
📕3.3 解决冲突的几种办法
📖1. 开放地址法（Open Addressing）
开放地址法是在哈希表中找一个新的空位来存储冲突元素。当发生冲突时，通过探测寻找下一个可用位置存放新元素。开放地址法常见的探测方式有：
📄a. 线性探测（Linear Probing）
在发生冲突时，线性探测通过固定步长（通常为 1）逐步查找下一个空位，直到找到可用位置。
- 公式：
hash(key) + i，其中i是冲突次数。 - 优点：实现简单。
- 缺点：容易出现“聚集”现象，即相邻的桶很容易连续被填满，降低查找效率。
int linearProbing(int hashValue, int i, int tableSize) {
return (hashValue + i) % tableSize;
}📄b. 二次探测（Quadratic Probing）
二次探测通过平方增长的步长来查找下一个位置，避免线性探测的“聚集”问题。
- 公式：
hash(key) + i^2。 - 优点：减少了聚集现象。
- 缺点：在高负载因子下，探测序列可能重复循环导致找不到空位。
int quadraticProbing(int hashValue, int i, int tableSize) {
return (hashValue + i * i) % tableSize;
}📄c. 双重哈希（Double Hashing）
双重哈希采用两个哈希函数，在发生冲突时，根据第二个哈希函数的值决定步长。
- 公式：
hash1(key) + i * hash2(key)。 - 优点：能有效降低聚集现象，冲突处理更加均匀。
- 缺点：需要设计两个独立的哈希函数，且对负载因子要求较高。
int doubleHashing(int hashValue, int i, int tableSize, int hash2) {
return (hashValue + i * hash2) % tableSize;
}📖2. 拉链法（Chaining）
拉链法将每个哈希表位置（桶）设计为一个链表，所有被哈希到同一位置的元素都存储在该链表中。插入新元素时，将其添加到链表中，查找时则遍历该链表。
- 优点：
- 实现简单，链表支持动态扩展，不受哈希表容量影响。
- 插入、删除操作简单，尤其适合不定长数据结构（如链表、树等）。
- 缺点：
- 冲突严重时，链表可能变长，影响查找效率，最坏情况为
O(n) 。
- 需要额外的链表存储空间。
📔四、哈希表的模拟实现
📕4.1 开放地址法（线性探测）
📖1. DefaultHashFunc 哈希函数类
DefaultHashFunc 是一个通用的哈希函数模板类，用于将键转换为哈希值。代码对整型和字符串类型分别进行了不同的哈希计算：
- 对于整型或其他非字符串类型，直接将键转换为
size_t类型。 - 对于
string类型，定义了一个专门的特化版本，使用一种常见的哈希算法，将字符串中的每个字符逐步加入到哈希值中，并乘以一个质数（131）来增加分布的均匀性。
template<class K>
class DefaultHashFunc {
public:
size_t operator()(const K& key) {
return (size_t)key;
}
};
template<>
class DefaultHashFunc<string> {
public:
size_t operator()(const string& str) {
size_t hash = 0;
for (auto ch : str) {
hash *= 131;
hash += ch;
}
return hash;
}
};📖2. HashData 类
HashData 类表示哈希表中的一个数据节点，包含一个键值对 _kv 和一个 STATE 状态 _state。STATE 枚举类定义了三个状态：
- EXIST：表示该位置有数据。
- EMPTY：表示该位置为空。
- DELETE：表示该位置的数据已被删除。
这种状态管理方便在开放地址法中处理删除操作。
enum STATE {
EXIST,
EMPTY,
DELETE
};
template<class K, class V>
class HashData {
public:
pair<K, V> _kv;
STATE _state = EMPTY;
};📖3. HashTable 类
HashTable 是哈希表的主体类，支持以下操作：
- 构造函数：初始化哈希表容量，默认大小为 10。
public:
HashTable() {
_table.resize(10);
}- 插入操作
Insert：向哈希表插入一个键值对kv。如果负载因子达到 0.7，进行扩容操作（即resize）。- 扩容操作：创建一个新的哈希表，将所有旧数据重新插入到新表中。这样可以重新计算哈希值，以确保数据均匀分布。
- 线性探测：若哈希值对应的桶已经存在数据，使用线性探测法查找下一个空闲位置，直到找到空位。
bool Insert(const pair<K, V>& kv) {
// 扩容,扩容之后映射关系变了，需要重新映射
if ((double)_n / _table.size() >= 0.7) {
size_t newSize = _table.size() * 2;
// 遍历旧表，重新映射到新表
HashTable<K, V, HashFunc> newHT;
newHT._table.resize(newSize);
for (size_t i = 0; i < _table.size(); ++i) {
newHT.Insert(_table[i]._kv);
}
_table.swap(newHT._table);
}
// 线性探测
// 起始位置，处理空间大小，是capacity还是size
HashFunc hf;
size_t hashi = hf(kv.first) % _table.size();
while (_table[hashi]._state == EXIST) {
++hashi;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}- 查找操作
Find：通过哈希函数定位键在哈希表中的位置，若发生冲突，则使用线性探测逐步查找直到找到匹配的键或遇到空位置。
HashData<const K, V>* Find(const K& key) {
// 线性探测
HashFunc hf;
size_t hashi = hf(key) % _table.size();
while (_table[hashi]._state != EMPTY) {
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key) {
return (HashData<const K, V>*) & _table[hashi];
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}- 删除操作
Erase：先通过Find方法查找键的位置，如果找到则将该位置的状态标记为DELETE，并减少元素计数_n。
bool Erase(const K& key) {
HashData<const K, V>* ret = Find(key);
if (ret) {
ret->_state = DELETE;
--_n;
return true;
}
return false;
}📖4. 私有成员
_table：存储HashData的向量，作为哈希表的实际存储容器。_n：存储有效数据的个数，用于计算负载因子并触发扩容操作。
private:
vector<HashData<K, V>> _table;
size_t _n = 0; // 存储有效数据的个数
};🏷️总结
- 哈希函数：代码定义了默认的
DefaultHashFunc，支持不同类型的键。 - 开放地址法（线性探测）：处理冲突的方式，当发生哈希冲突时，逐步向后探测下一个空位。
- 扩容机制：当负载因子达到一定值时，动态扩展哈希表大小并重新分配数据，减少冲突。
📕4.2 拉链法（哈希桶）
这里我们继续沿用以上的DefaultHashFunc 哈希函数类。
📖1. HashNode 类
HashNode 类表示哈希表中的一个节点，包含一个键值对 _kv 和一个指向下一个节点的指针 _next。该类用于构成链表，以解决哈希冲突。
template<class K, class V>
class HashNode {
public:
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv)
: _kv(kv), _next(nullptr) {}
};_kv：存储键值对。_next：指向链表中的下一个节点。
📖2. HashTable 类
HashTable 使用拉链法来处理哈希冲突。每个桶存储一个链表的头节点，当多个键映射到相同的哈希位置时，通过链表存储多个节点。
📄成员变量
_table：std::vector的每个位置存储一个链表头节点指针，表示一个桶。_n：存储哈希表中当前有效数据的数量。
private:
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少有效数据📄构造函数和析构函数
- 构造函数：初始化哈希表大小为 10 个桶。
- 析构函数：遍历每个桶的链表并释放所有节点的内存。
HashTable() {
_table.resize(10, nullptr);
}
~HashTable() {
for (size_t i = 0; i < _table.size(); ++i) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}📄插入操作 Insert
插入操作首先检查键是否已存在，若存在则返回 false，避免重复插入。若键不存在，执行以下步骤：
- 扩容：若负载因子达到 1，则将哈希表容量扩大一倍。
- 新建一个更大的表，并将旧表中的元素重新哈希并插入新表。
- 计算哈希值：根据哈希函数
HashFunc计算哈希值。 - 插入到链表：将新节点插入到对应桶的链表头部（头插法），方便且高效。
bool Insert(const pair<K, V>& kv) {
if (Find(kv.first)) {
return false;
}
HashFunc hf;
if (_n == _table.size()) {
size_t newSize = _table.size() * 2;
vector<Node*> newTable;
newTable.resize(newSize, nullptr);
for (size_t i = 0; i < _table.size(); ++i) {
Node* cur = _table[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hf(cur->_kv.first) % newSize;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
size_t hashi = hf(kv.first) % _table.size();
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}📄查找操作 Find
查找操作使用哈希函数计算键的位置，遍历该位置的链表，查找对应键的节点。如果找到则返回节点指针，否则返回 nullptr。
Node* Find(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) {
return cur;
}
cur = cur->_next;
}
return nullptr;
}📄删除操作 Erase
删除操作与查找类似，通过哈希值定位到对应的链表，找到目标节点后将其从链表中移除。
- 如果要删除的节点是链表头节点，直接更新桶头指针。
- 否则，将该节点从链表中删除。
bool Erase(const K& key) {
HashFunc hf;
size_t hashi = hf(key) % _table.size();
Node* prev = nullptr;
Node* cur = _table[hashi];
while (cur) {
if (cur->_kv.first == key) {
if (prev == nullptr) {
_table[hashi] = cur->_next;
} else {
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}📄打印操作 Print
打印哈希表中的内容，展示每个桶中的链表结构，用于观察哈希表的分布情况。
void Print() {
for (size_t i = 0; i < _table.size(); ++i) {
printf("[%d]->", i);
Node* cur = _table[i];
while (cur) {
cout << cur->_kv.first << ":" << cur->_kv.second << "->";
cur = cur->_next;
}
printf("NULL\n");
}
cout << endl;
}🏷️总结
- 哈希函数：使用默认的
HashFunc计算键的哈希值，映射到对应桶位置。 - 拉链法：每个桶使用链表来处理哈希冲突，链表结构灵活且易于扩展。
- 扩容：当负载因子达到 1 时，哈希表自动扩容以减少冲突。
结语
哈希表不仅仅是一个工具，更是一种思想。它带给我们的不仅是高效的算法，更是对数据结构和算法优化的深刻理解。掌握了哈希表的设计与实现，你将拥有在数据密集型任务中快速处理信息的能力。希望本篇博客能帮助你在C++的学习道路上更进一步，感受到编程的魅力。 今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！
腾讯云开发者
