一、哈希的核心概念
1. 哈希到底是什么？
先回忆两个基础数据结构的痛点：
C++算法
哈希（Hash）核心概念与 C++ 应用
深入解析哈希（Hash）的核心概念，包括哈希函数、哈希表及冲突处理机制。详细对比了拉链法与开放寻址法的优劣，重点介绍了 C++ 标准库中 unordered_map 和 unordered_set 的使用方法及性能调优技巧。内容涵盖自定义类型作为 Key 的实现方案、常见坑点规避以及经典应用场景，旨在帮助开发者高效掌握哈希数据结构。
深入解析哈希（Hash）的核心概念，包括哈希函数、哈希表及冲突处理机制。详细对比了拉链法与开放寻址法的优劣，重点介绍了 C++ 标准库中 unordered_map 和 unordered_set 的使用方法及性能调优技巧。内容涵盖自定义类型作为 Key 的实现方案、常见坑点规避以及经典应用场景，旨在帮助开发者高效掌握哈希数据结构。
先回忆两个基础数据结构的痛点：
哈希的核心解决思路：
定义一个「映射规则」（哈希函数），把 任意类型的原始数据 (key) 转换成一个 整型数字（哈希值），然后用这个哈希值作为「数组下标」存储数据。
最终效果：查找/插入/删除的平均时间复杂度都是 O(1)，和数据量无关，极致高效！
概念 1：哈希函数 (Hash Function)
定义：把任意输入值（key）映射成固定范围整型值（哈希值）的函数，记为 hash(key) = value。
核心要求
C++ 中常见的哈希函数
hash(key) = key % 数组长度（最基础，比如学号 1001，模 10 得到哈希值 1）；hash(key) = key（比如 key 是整型 ID，直接用 ID 当下标）；概念 2：哈希表 (Hash Table)
定义：哈希的底层存储结构，本质是「数组 + 冲突解决结构」。
我们把哈希函数计算出的哈希值，作为数组的「下标」，这个数组的每个位置称为「桶（bucket）」，数据就存在对应的桶里。
如果没有哈希冲突，哈希表就是一个简单的数组，所有操作都是 O(1)。
概念 3：哈希冲突 (Hash Collision)
1. 什么是哈希冲突？
白话解释：不同的原始 key，通过哈希函数计算后，得到了相同的哈希值，最终要存在哈希表的同一个桶里，这种情况就是哈希冲突。
比如：哈希函数是 hash(key) = key % 10，那么 key=1 和 key=11，计算出的哈希值都是 1，就会发生冲突。
哈希冲突是无法避免的，只能尽可能减少和解决。
原因：哈希函数是「将无限大的输入值域」映射到「有限小的哈希值范围」，就像把 1000 个苹果放进 100 个篮子，必然有篮子放多个苹果。
1. 拉链法的本质：给哈希表的每个桶挂个'链条'
拉链法是解决哈希冲突的最主流、最易实现的方案，没有之一。
它的核心思路是：
key 计算出相同的哈希值（发生冲突）时，不会争抢同一个桶的位置，而是像挂灯笼一样，把新数据挂载到对应桶的'链条'末尾。形象比喻：把哈希表的数组想象成一排挂钩，每个挂钩就是一个桶；冲突的数据就是一串钥匙，全挂在同一个挂钩上，互不干扰。
2. 拉链法的核心结构
哈希表数组（桶数组）
索引 0 → 桶 0 → 链表节点 (key:A, val:1) → 链表节点 (key:J, val:3) → null
索引 1 → 桶 1 → 链表节点 (key:B, val:2) → null
索引 2 → 桶 2 → null （空桶）
索引 3 → 桶 3 → 链表节点 (key:D, val:5) → 链表节点 (key:M, val:7) → 链表节点 (key:X, val:9) → null
key、value 和指向下一个节点的指针。3. 为什么 C++ 标准库选拉链法？
对比开放寻址法，拉链法的优势是工程上的'容错性'和'易用性'，这也是标准库选择它的核心原因：
| 特性 | 拉链法 | 开放寻址法 |
|---|---|---|
| 冲突处理难度 | 简单（挂链表即可） | 复杂（需找空位，处理删除） |
| 负载因子容忍度 | 高（>1 也能工作） | 低（>0.7 性能急剧下降） |
| 内存利用率 | 非连续内存，灵活分配 | 连续数组，易浪费空间 |
| 删除操作 | 直接删链表节点，无残留 | 需'标记删除'，易产生空洞 |
| 扩容成本 | 元素迁移时不影响原链条 | 需重新探测所有元素位置 |
结论：拉链法更适合作为通用哈希容器的冲突解决方案，开放寻址法仅适合内存极度紧张的嵌入式场景。
4. 拉链法的核心操作：插入、查找、删除
插入操作
输入：key 和 value
核心目标：将数据挂载到对应桶的链条上，且保证 key 唯一
步骤拆解：
hash(key) 得到哈希值 h；index = h % 桶数组长度（取模是最基础的映射方式）；index 对应的链表：
value，结束插入；key：执行下一步；元素总数 / 桶数组长度 > 负载因子阈值（默认 0.75），触发扩容（桶数组长度翻倍，所有元素重新哈希迁移）。头部插入 vs 尾部插入
查找操作（平均 O(1)，最坏 O(k)）
输入：要查找的 key
核心目标：找到对应桶的链条中 key 匹配的节点
步骤拆解：
h 和桶索引 index（同插入步骤 1-2）；index 对应的链表：
key 匹配的节点：返回 value，查找成功；性能瓶颈：当链条长度
k过大时，查找效率会从 O(1) 退化到 O(k)—— 这也是 C++ 标准库引入红黑树优化的原因。
删除操作（平均 O(1)，最坏 O(k)）
输入：要删除的 key
核心目标：从链条中移除 key 匹配的节点，保证链表结构不断裂
步骤拆解：
h 和桶索引 index（同插入步骤 1-2）；index 对应的链表，同时记录当前节点和前驱节点：
key 匹配的节点：
关键细节：必须记录前驱节点，否则删除中间节点后，链表会断裂，后续节点会'丢失'。
5. C++ 标准库的拉链法优化：链表→红黑树
C++11 中的 unordered_map/unordered_set，对拉链法做了一个革命性优化：当桶内的链表长度超过阈值（默认 8）时，自动将链表转换为红黑树；当长度低于阈值（默认 6）时，再转回链表。
为什么要做这个优化？
k=8 时，最坏查找时间是 O(8)；当 k=100 时，退化到 O(100)，性能极差；k=8 时，O(log 8)=O(3)，比链表快 2 倍多；当 k=100 时，O(log 100)≈O(7)，比链表快 14 倍。阈值选择的原因
结论：这个优化让 C++ 的哈希容器，在极端冲突场景下，依然能保持高效的查找性能。
6. 手写拉链法哈希表
#include <iostream>
#include <string>
using namespace std;
// 定义链表节点结构
template <typename K, typename V>
struct HashNode {
K key; // 键
V value; // 值
HashNode<K, V>* next; // 指向下一个节点的指针
// 构造函数
HashNode(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
};
// 简易拉链法哈希表
template <typename K, typename V>
class HashTable {
private:
using Node = HashNode<K, V>;
Node** buckets; // 桶数组：二级指针，指向指针数组
size_t bucketCount; // 桶的数量
size_t elementCount; // 元素总数
const float loadFactorThreshold = 0.75f; // 负载因子阈值
// 简易哈希函数：针对 string 类型（可扩展其他类型）
size_t hashFunc(const string& key) const {
size_t hash = 0;
for (char c : key) {
hash = hash * 31 + c; // 31 是质数，减少哈希冲突
}
return hash;
}
// 针对 int 类型的哈希函数
size_t hashFunc(int key) const {
return key;
}
// 计算桶索引
size_t getBucketIndex(const K& key) const {
return hashFunc(key) % bucketCount;
}
// 扩容：桶数量翻倍，所有元素重新哈希
void resize() {
size_t newBucketCount = bucketCount * 2;
Node** newBuckets = new Node*[newBucketCount](); // 初始化所有桶为 nullptr
// 遍历旧桶，将所有元素迁移到新桶
for (size_t i = 0; i < bucketCount; ++i) {
Node* curr = buckets[i];
while (curr != nullptr) {
Node* next = curr->next; // 保存下一个节点，避免迁移时丢失
// 计算新桶索引
size_t newIndex = hashFunc(curr->key) % newBucketCount;
// 头部插入新桶
curr->next = newBuckets[newIndex];
newBuckets[newIndex] = curr;
curr = next;
}
delete[] buckets[i]; // 释放旧桶的链表节点
}
// 替换桶数组
delete[] buckets;
buckets = newBuckets;
bucketCount = newBucketCount;
}
public:
// 构造函数：初始化桶数组
HashTable(size_t initBucketCount = 16) : bucketCount(initBucketCount), elementCount(0) {
// 初始化桶数组，每个桶初始为 nullptr
buckets = new Node*[bucketCount]();
}
// 析构函数：释放所有内存
~HashTable() {
for (size_t i = 0; i < bucketCount; ++i) {
Node* curr = buckets[i];
while (curr != nullptr) {
Node* next = curr->next;
delete curr;
curr = next;
}
}
delete[] buckets;
}
// 插入/更新元素
void put(const K& key, const V& value) {
// 检查负载因子，触发扩容
if (static_cast<float>(elementCount) / bucketCount > loadFactorThreshold) {
resize();
}
size_t index = getBucketIndex(key);
Node* curr = buckets[index];
// 遍历链表，检查 key 是否存在
while (curr != nullptr) {
if (curr->key == key) {
curr->value = value; // key 存在，更新 value
return;
}
curr = curr->next;
}
// key 不存在，头部插入新节点
Node* newNode = new Node(key, value);
newNode->next = buckets[index];
buckets[index] = newNode;
elementCount++;
}
// 查找元素
bool get(const K& key, V& value) {
size_t index = getBucketIndex(key);
Node* curr = buckets[index];
while (curr != nullptr) {
if (curr->key == key) {
value = curr->value; // 找到 key，返回 value
return true;
}
curr = curr->next;
}
return false; // key 不存在
}
// 删除元素
bool remove(const K& key) {
size_t index = getBucketIndex(key);
Node* curr = buckets[index];
Node* prev = nullptr; // 记录前驱节点
while (curr != nullptr) {
if (curr->key == key) {
// 处理删除逻辑
if (prev == nullptr) { // 删除头节点
buckets[index] = curr->next;
} else { // 删除中间/尾节点
prev->next = curr->next;
}
delete curr;
elementCount--;
return true;
}
prev = curr;
curr = curr->next;
}
return false; // key 不存在
}
// 获取元素总数
size_t size() const {
return elementCount;
}
};
// 测试代码
int main() {
HashTable<string, int> ht;
// 插入元素
ht.put("apple", 5);
ht.put("banana", 3);
ht.put("apple", 10); // 更新 apple 的值
// 查找元素
int value;
if (ht.get("apple", value)) {
cout << "apple: " << value << endl; // 输出 10
}
// 删除元素
ht.remove("banana");
cout << "size: " << ht.size() << endl; // 输出 1
return 0;
}
代码核心亮点
key/value 类型，通用性强；7. 拉链法的工程优化技巧
在实际项目中，使用拉链法哈希表（比如 unordered_map）时，掌握这些技巧能大幅提升性能：
reserve(n)，避免多次扩容（扩容的 rehash 操作是 O(n)，很耗时）；unordered_map<string, int> mp;
mp.reserve(10000); // 提前分配足够的桶，避免插入 10000 个元素时多次扩容
string 哈希函数在极端场景下冲突率较高，可以自定义哈希函数（比如结合 BKDRHash 等工业级哈希算法）；原理
当发生哈希冲突时，不额外开辟空间，而是在哈希表的「其他空桶」中寻找新的存储位置，核心是「找下一个空位」。常见的寻址策略：线性探测（冲突后往后找 1 个位置）、二次探测（往后找平方数位置）、再哈希（换一个哈希函数重新计算）。
简单理解：一个桶被占了，就去隔壁桶看看，直到找到空桶。
核心优缺点
优点：不需要额外内存，空间利用率高；缓存友好（数据存在连续的数组中）； 缺点：实现复杂，删除数据时不能直接清空（会导致后续查找失效），只能做「标记删除」；负载因子过高时，冲突概率急剧上升，性能退化严重；
适用场景：内存紧张的嵌入式开发、高性能缓存系统，C++ 中极少用标准库实现，一般是手写。
定义
负载因子 α = 哈希表中存储的元素个数 / 哈希表的桶的总数。比如：哈希表有 100 个桶，存了 75 个元素，负载因子就是 0.75。
核心作用
负载因子是衡量哈希表拥挤程度的核心指标，也是哈希表「扩容」的唯一触发条件！
为什么 C++ 的哈希容器默认负载因子是 0.75？
当 α ≤ 0.75 时，哈希冲突的概率极低，拉链法的链条长度基本都是 1，操作效率稳定在 O(1)；当 α > 0.75 时，冲突概率会指数级增长，链条长度快速变长，性能开始退化；
当哈希表的负载因子超过 0.75 时，C++ 会自动触发「扩容」：桶的数量翻倍，所有元素重新计算哈希值并迁移（rehash），这个过程的时间复杂度是 O(n)，但扩容是「摊还」的，整体平均复杂度还是 O(1)。
哈希表的 平均时间复杂度：查找、插入、删除都是 O(1)；
哈希表的 最坏时间复杂度：查找、插入、删除都是 O(n)；
最坏情况的触发原因：
unordered_* 容器和 set/map 的核心区别之一；unordered_set）中，同一个 key 只能存一次；哈希映射（unordered_map）中，key 是唯一的，value 可以重复；C++ 对哈希的支持是从 C++11 开始的，提供了两个核心的哈希容器，也是项目开发中最常用的容器，没有之一。
核心结论
C++ 的 unordered_set 和 unordered_map：
-std=c++11 编译。哈希容器 vs 有序容器（set/map）：怎么选？
| 特性 | unordered_set/unordered_map（哈希） | set/map（红黑树） |
|---|---|---|
| 底层实现 | 哈希表 + 拉链法 | 红黑树（平衡二叉树） |
| 元素顺序 | 无序 | 按键升序排列 |
| 平均时间复杂度 | O(1) 极致高效 | O(log n) 稳定高效 |
| 最坏时间复杂度 | O(n) | O(log n) 永远稳定 |
| 内存占用 | 较大（空间换时间） | 较小 |
| 适用场景 | 只需要查找/插入/删除，不需要有序 | 需要有序遍历、范围查询 |
能哈希，不树型；要有序，再树型。
简单说：只要业务不需要有序，优先用哈希容器，性能碾压红黑树容器！
语法极简，和 set/map 几乎一致，只是少了有序相关的接口，新手可以直接复制运行，快速上手。
unordered_set：哈希集合，核心功能「去重、查找、判存在」
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
unordered_set<int> s;
// 1. 插入元素 (平均 O(1))
s.insert(1);
s.insert(2);
s.insert(1); // 重复元素，插入失败，无报错
// 2. 查找元素 (平均 O(1))
if (s.find(1) != s.end()) {
cout << "找到元素 1" << endl;
}
// 3. 删除元素 (平均 O(1))
s.erase(2);
// 4. 判空/大小/清空
cout << "容器大小：" << s.size() << endl;
cout << "是否为空：" << s.empty() << endl;
// 5. 遍历（无序）
for (auto num : s) {
cout << num << " "; // 输出：1
}
return 0;
}
unordered_map：哈希映射，核心功能「键值对存储、通过 key 快速查 value」
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
int main() {
unordered_map<string, int> mp;
// 1. 插入键值对 (平均 O(1))
mp["张三"] = 20;
mp.insert({"李四", 22});
mp.insert({"张三", 25}); // 重复 key，插入失败
// 2. 查找 value (平均 O(1))
if (mp.count("张三")) { // count：判断 key 是否存在，返回 0/1
cout << "张三的年龄：" << mp["张三"] << endl; // 输出：20
}
// 3. 删除元素 (平均 O(1))
mp.erase("李四");
// 4. 遍历（无序）
for (auto& pair : mp) {
cout << pair.first << " : " << pair.second << endl;
}
return 0;
}
坑点 1：哈希容器是「无序的」，遍历顺序不固定
很多新手以为哈希容器的遍历顺序和插入顺序一致，实际完全无关！遍历顺序由哈希值决定，每次运行可能都不一样，绝对不要依赖哈希容器的遍历顺序做业务逻辑。
坑点 2：自定义类型不能直接作为哈希容器的 key
比如你定义了一个 Person 结构体，直接用 unordered_set<Person> 会编译报错！原因有两个：
== 运算符）。坑点 3：哈希容器的迭代器失效问题
哈希容器的迭代器失效规则和 vector/list 不同
结论：哈希容器的迭代器失效问题，比 vector/list 温和得多，开发中不用过度担心。
坑点 4：哈希容器的 key 必须是「不可变的」
比如用 unordered_map<string, int>，如果修改了 key 的内容（比如 pair.first = "王五"），会导致哈希值变化，这个元素就会「丢失」，后续无法通过 key 找到。
解决方案：如果需要修改 key，先删除旧的键值对，再插入新的。
坑点 5：哈希容器不是线程安全的
C++ 标准库的所有容器（包括哈希容器）都没有实现线程安全，在多线程环境下，同时读写哈希容器会导致程序崩溃/数据错乱。
解决方案：加锁（mutex）、用线程安全的哈希容器（如 folly::ConcurrentHashMap）。
需求场景：
定义一个结构体/类，比如 Student，包含学号、姓名，需要用 unordered_set<Student> 去重，或 unordered_map<Student, int> 存储成绩。
核心要求
== 运算符：让哈希容器能判断两个对象是否相等（解决冲突时需要）；完整实现代码
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;
// 自定义结构体：学生
struct Student {
int id; // 学号
string name; // 姓名
// 要求 1：必须重载 == 运算符，判断两个学生是否相等
bool operator==(const Student& other) const {
return this->id == other.id; // 学号唯一，作为相等判断依据
}
};
// 方案 1：特化 std::hash 模板（最推荐，C++ 标准做法，面试首选）
namespace std {
template<>
struct hash<Student> {
size_t operator()(const Student& s) const {
// 计算哈希值：复用标准库对 int 的哈希函数
return hash<int>()(s.id);
}
};
}
// 方案 2：自定义哈希函数，传入容器（灵活，适合临时使用）
struct StudentHash {
size_t operator()(const Student& s) const {
return hash<int>()(s.id);
}
};
int main() {
// 方案 1 使用：直接用 unordered_set
unordered_set<Student> s1;
s1.insert({1001, "张三"});
s1.insert({1002, "李四"});
// 方案 2 使用：传入自定义哈希函数
unordered_set<Student, StudentHash> s2;
s2.insert({1001, "张三"});
return 0;
}
如果结构体有多个成员（比如 id + 姓名），需要组合所有成员的哈希值，避免冲突：
size_t operator()(const Student& s) const {
// 组合哈希值：用异或/乘质数的方式，避免单一成员冲突
return hash<int>()(s.id) ^ (hash<string>()(s.name) << 1);
}
reserve(n)，避免多次扩容（扩容的 rehash 是 O(n) 操作）；比如要存 10000 个元素，直接 mp.reserve(10000)；unordered_set 一键实现；unordered_map 实现 O(1) 查找；unordered_map<key, int> 计数；
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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