哈希表通过哈希函数将键映射到桶中，实现 $O(1)$ 平均时间复杂度的插入、删除和查找。
本质：用空间换时间，将遍历查找的 $O(n)$ 降为 $O(1)$。
1
2
3
4
5
6
| // 经典：是否存在两数和为 target
unordered_set<int> seen;
for (int x : nums) {
if (seen.count(target - x)) return true;
seen.insert(x);
}
|
1
2
| unordered_map<int, int> freq;
for (int x : nums) freq[x]++;
|
1
2
3
4
5
6
7
| unordered_map<int, int> pos; // 值 → 最后一次出现的下标
for (int i = 0; i < n; i++) {
if (pos.count(nums[i])) {
// 之前出现过
}
pos[nums[i]] = i;
}
|
1
2
3
4
5
6
7
8
9
| // 双射：两个方向都要映射
unordered_map<char, char> s2t, t2s;
for (int i = 0; i < s.size(); i++) {
char a = s[i], b = t[i];
if ((s2t.count(a) && s2t[a] != b) || (t2s.count(b) && t2s[b] != a))
return false;
s2t[a] = b;
t2s[b] = a;
}
|
1
2
3
4
5
6
7
8
9
10
11
| // 拉链法替代方案，缓存友好
const int N = 20007; // 质数，开 2~3 倍
int h[N], nil = 0x3f3f3f3f;
int find(int x) {
int k = (x % N + N) % N;
while (h[k] != nil && h[k] != x) {
if (++k == N) k = 0;
}
return k;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| // 滚动哈希：用于字符串匹配 / 最长重复子串
typedef unsigned long long ull;
const ull P = 131; // 基数，131 或 13331
vector<ull> h(n + 1), p(n + 1);
p[0] = 1;
for (int i = 0; i < n; i++) {
h[i+1] = h[i] * P + s[i];
p[i+1] = p[i] * P;
}
// 子串 [l, r] 的哈希值
ull hash = h[r+1] - h[l] * p[r - l + 1];
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| // --- unordered_map ---
unordered_map<int, int> mp;
mp.count(key); // 是否存在（0 或 1）
mp[key] = val; // 插入/修改
mp.erase(key); // 删除
mp.find(key); // 返回迭代器，不存在返回 mp.end()
for (auto& [k, v] : mp) { } // 遍历
// --- unordered_set ---
unordered_set<int> st;
st.insert(x);
st.erase(x);
st.count(x);
// 自定义哈希（pair 等）
struct pair_hash {
template<class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
return hash<T1>{}(p.first) ^ (hash<T2>{}(p.second) << 1);
}
};
unordered_map<pair<int,int>, int, pair_hash> mp;
// 用数组替代哈希表（值域小时更快）
int cnt[100001] = {0}; // 省去哈希开销
|
- 哈希表 vs 数组：值域小（< 10^6）时优先用数组，常数小且无冲突
- unordered_map vs map：不需要有序时用
unordered_map，$O(1)$ vs $O(\log n)$ - key 不存在时
mp[key] 会插入默认值，判断存在用 count() 或 find() - 避免哈希退化：
unordered_map 最坏 $O(n)$，竞赛中可能被卡，可自定义哈希函数 - 两数之和类问题，先查再插，避免自己和自己配对
- 双射问题（同构、单词模式），必须同时维护两个方向的映射
