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_setint 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_mapstring, 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(张三)) { // count1存在0不存在 mp[张三] 19; } cout 张三年龄 mp[张三] endl; // 19 return 0; }3. unordered_multiset /unordered_multimap允许重复 key// 允许重复元素 unordered_multisetint ms; ms.insert(2); ms.insert(2); cout ms.count(2); // 2两个2 // 允许重复键值对 unordered_multimapstring, int mmp; mmp.insert({苹果, 5}); mmp.insert({苹果, 3});3.哈希底层核心概念1. 哈希函数把数据转成数组下标举例对整数key 15桶数组大小 10 哈希函数key % 桶大小→15%105→ 放在下标为 5 的桶里字符串举例key abc库函数会把字符串转成数字再取模 → 得到桶下标2. 哈希冲突不同数据算到同一个下标举例桶大小 10key5→ 5%105key15→15%105 两个数据冲突了STL 解决方案链地址法把冲突的元素串成链表挂在同一个桶下桶5 → 5 → 15 → 链表3. 负载因子 扩容自动优化效率公式负载因子 元素个数 / 桶数量默认阈值0.7举例桶数量 10最多放 7 个元素插入第 8 个 → 触发扩容桶数量变成 20所有元素重新计算下标 → 效率回归 O (1)4.哈希 实际应用 经典代码举例1. 数组去重unordered_setvectorint nums {1,2,2,3,3,3}; unordered_setint s(nums.begin(), nums.end()); // 去重后1,2,32.统计字符出现次数unordered_mapstring str hello world; unordered_mapchar, int cnt; for (char c : str) cnt[c]; cout l出现次数 cnt[l] endl; // 33.LeetCode 两数之和哈希经典题vectorint twoSum(vectorint nums, int target) { unordered_mapint, int mp; for (int i0; inums.size(); i) { if (mp.count(target - nums[i])) { return {mp[target-nums[i]], i}; } mp[nums[i]] i; } return {}; }谢谢