C/C++ 哈希

1.哈希（Hash）核心概念

1.哈希函数：任意 key→数组下标，定位存储位置。
2.哈希表：数组（桶）+ 链表，存储数据。
3.哈希冲突：不同 key 算出同一下标；STL 用链地址法（同桶挂链表）解决。
4.负载因子 = 元素数 / 桶容量，阈值 0.7，超限rehash扩容重排数据。
5.效率：平均增删查 O (1)，无序；map 红黑树 O (logn)、有序。

 2.C++ unordered 哈希容器

1.unordered_set（唯一值、无序、只存 key）

场景：去重、判断元素是否存在：

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
// 1. 创建哈希集合
unordered_set<int> s;

// 2. 插入元素（自动去重）
s.insert(1);
s.insert(3);
s.insert(2);
s.insert(3); // 重复插入，无效

// 3. 遍历（无序！）
cout << "unordered_set元素：";
for (auto x : s) cout << x << " ";
// 运行结果：无序，比如 2 1 3（和插入顺序无关）
cout << endl;

// 4. 查找元素
if (s.find(3) != s.end()) {
cout << "元素3存在" << endl;
}

// 5. 删除元素
s.erase(1);
cout << "删除1后大小：" << s.size() << endl; // 2

return 0;
}

2. unordered_map（键值对、key 唯一、无序）

场景：统计次数、映射关系（最常用！）：

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
// 键：字符串（名字），值：int（年龄）
unordered_map<string, int> mp;

// 插入方式1
mp["张三"] = 18;
mp["李四"] = 20;
// 插入方式2
mp.insert({"王五", 22});

// 遍历键值对
cout << "unordered_map内容：" << endl;
for (auto& p : mp) {
cout << p.first << "：" << p.second << endl;
}

// 查找+修改
if (mp.count("张三")) { // count=1存在，0不存在
mp["张三"] = 19;
}

cout << "张三年龄：" << mp["张三"] << endl; // 19

return 0;
}

3. unordered_multiset /unordered_multimap（允许重复 key）

// 允许重复元素
unordered_multiset<int> ms;
ms.insert(2);
ms.insert(2);
cout << ms.count(2); // 2（两个2）

// 允许重复键值对
unordered_multimap<string, int> mmp;
mmp.insert({"苹果", 5});
mmp.insert({"苹果", 3});

3.哈希底层核心概念 

1. 哈希函数（把数据转成数组下标）

举例：对整数 key = 15，桶数组大小 = 10 哈希函数：key % 桶大小 → 15%10=5 → 放在下标为 5 的桶里

字符串举例：key = "abc" 库函数会把字符串转成数字，再取模 → 得到桶下标

2. 哈希冲突（不同数据算到同一个下标）

举例：桶大小 = 10

• key=5 → 5%10=5

• key=15 →15%10=5 两个数据冲突了！

STL 解决方案：链地址法 把冲突的元素串成链表，挂在同一个桶下：

桶5 → 5 → 15 → 链表

3. 负载因子 & 扩容（自动优化效率）

公式：负载因子 = 元素个数 / 桶数量
默认阈值：0.7
举例：桶数量 = 10，最多放 7 个元素
插入第 8 个 → 触发扩容（桶数量变成 20）

所有元素重新计算下标 → 效率回归 O (1)

4.哈希 实际应用 经典代码举例

1. 数组去重（unordered_set）：

vector<int> nums = {1,2,2,3,3,3};
unordered_set<int> s(nums.begin(), nums.end());
// 去重后：1,2,3

2.统计字符出现次数（unordered_map）

string str = "hello world";
unordered_map<char, int> cnt;
for (char c : str) cnt[c]++;
cout << "l出现次数：" << cnt['l'] << endl; // 3

3.LeetCode 两数之和（哈希经典题）

vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i=0; i<nums.size(); i++) {
if (mp.count(target – nums[i])) {
return {mp[target-nums[i]], i};
}
mp[nums[i]] = i;
}
return {};
}

谢谢