为什么数组不够用了
上一篇讲了单调栈和单调队列，它们擅长处理有顺序关系的元素。但很多时候我们需要的是"快速查找"和"统计次数"。
如果想知道一个元素出现了几次，或者想快速判断某个值是否存在，用数组行不行？
如果元素范围不大，比如只有 0 到 1000，数组很完美。但如果元素是字符串、大数或者稀疏分布的整数，数组就无能为力了。比如：
- 统计字符串数组中每个单词出现的次数
- 判断一个很大的数（如 10^9）是否在某个集合中
- 记录用户 ID 和对应的信息
哈希表的核心思想
哈希表的核心就是把任意类型的 key，通过哈希函数映射到一个整数索引，然后用数组存储。这样就能做到平均 O(1) 的插入、查找和删除。
想象一下，你有一个很大的书架，但你给每本书编了一个独特的号码，然后根据这个号码就能直接找到书的位置，而不用一本一本找。哈希函数就是那个编号码的规则。
C++ STL 中的哈希容器
C++ STL 提供了两个常用的哈希容器：
unordered_map<K, V>：键值对的哈希表，像字典一样用；unordered_set<K>：哈希集合，只存键不存值，用于去重和存在性判断。
它们的名字里都有 unordered，因为遍历顺序是不确定的。如果需要有序，可以用 map 和 set（基于红黑树实现），但复杂度会变成 O(log n)。
计数：最常用的操作
统计元素出现次数是哈希表最基础的用法。比如统计数组中每个数出现几次：
vector a = {1, 2, 3, 2, 1, 3, 3, 3};
unordered_map cnt;
for (int x : a) {
cnt[x]++; // 自动初始化为0，然后加1
}
for (auto& [k, v] : cnt) {
cout << k << " 出现了 " << v << " 次\n";
}
// 输出：1 出现了 2 次，2 出现了 2 次，3 出现了 4 次
这里有个小技巧：unordered_map 访问不存在的 key 时，会自动创建并初始化为默认值（数值类型为 0）。所以 cnt[x]++ 能直接工作。
查找：判断是否存在
用 unordered_set 判断元素是否存在非常方便：
unordered_set s = {"apple", "banana", "cherry"};
if (s.count("apple")) {
cout << "存在 apple\n";
}
if (!s.count("orange")) {
cout << "不存在 orange\n";
}
count() 方法返回 0 或 1，因为集合里不会有重复元素。
典型题：两数之和
给定数组和目标值，找两个数的下标使它们的和等于目标值。这是 LeetCode 第一题，也是哈希表的经典应用：
vector twoSum(vector& nums, int target) {
unordered_map mp;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (mp.count(complement)) {
return {mp[complement], i};
}
mp[nums[i]] = i;
}
return {};
}
思路：遍历数组时，用哈希表记录已遍历元素及其下标。对当前元素 nums[i]，检查 target - nums[i] 是否在哈希表中。如果在，就找到了答案；如果不在，就把当前元素加入哈希表。
这个解法的复杂度是 O(n)，比暴力的 O(n^2) 快很多。
去重与统计频率
哈希表还能方便地去重。比如找出数组中只出现一次的元素：
int singleNumber(vector& nums) {
unordered_map cnt;
for (int x : nums) cnt[x]++;
for (auto& [k, v] : cnt) {
if (v == 1) return k;
}
return -1;
}
类似地，还可以找出出现次数最多的元素、找出重复元素等等。
哈希表还能做什么
哈希表的应用非常广泛，常见题型包括：
- 两数之和、三数之和等组合问题；
- 字符串异位词分组；
- 最长无重复子串；
- LRU 缓存（需要有序的哈希表）；
- 判断链表是否有环（记录访问过的节点）。
看到“统计频率”“快速查找”“键值映射”这类需求，就可以考虑哈希表。
哈希表的性能与注意事项
哈希表虽然平均是 O(1)，但有几个坑需要注意：
- 哈希冲突：不同的 key 可能映射到同一个位置，导致退化成链表，最坏 O(n)。现代实现通常用链表+红黑树来优化。
- 自定义类型：如果用自定义结构体当 key，需要提供哈希函数和相等比较函数。
- 遍历顺序：
unordered_map的遍历顺序是不确定的，不依赖插入顺序。 - 数组 vs 哈希表：如果 key 是小范围整数，数组比哈希表更快，因为没有哈希计算的开销。
在 C++17 中，可以用结构化绑定让代码更简洁：
for (auto& [key, value] : my_map) {
// 直接访问 key 和 value
}
什么时候用哈希表
看到这些场景，就可以考虑哈希表：
- 需要快速统计频率、计数；
- 需要快速判断元素是否存在；
- 需要建立键值映射关系；
- 需要 O(1) 时间的查找和插入。
这一篇先记住什么
unordered_map用于键值映射和计数；unordered_set用于去重和存在性判断；- 哈希表平均 O(1)，但要注意哈希冲突的影响；
- 小范围整数优先用数组，其他情况用哈希表；
- 两数之和是哈希表的经典应用，记住这个思路。
下一篇继续数据结构：并查集。它是处理连通性问题的利器，能高效解决动态连通性、分组等问题。