当前位置：首页 > news >正文

C/C++ 哈希

news 2026/6/13 15:25:31

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 {}; }