哈希表是C++算法竞赛中最常用的数据结构之一，它能在平均 O(1) 时间内完成插入、删除和查找操作。但哈希表有一个绕不开的问题：哈希冲突——两个不同的键被映射到了同一个桶（槽位）。如果处理不当，哈希表可能退化成链表，时间复杂度骤降至 O(n)，让你在关键时刻 TLE（超时）。
那么，在 C++ 信奥实战中，我们该如何优雅地应对哈希冲突？本文将从冲突起因讲起，系统介绍拉链法、开放地址法、双哈希、完美哈希等经典策略，并给出可直接用于竞赛的 C++ 代码模板和性能对比。
一、哈希冲突从何而来？
哈希函数将无限的输入空间映射到有限的桶数组，根据鸽巢原理，冲突必然存在。例如，用一个大小为 10 的数组存储 1000 个整数，无论哈希函数多么均匀，平均每个桶要装 100 个元素。冲突的严重程度取决于三个因素：
竞赛中，我们通常希望 α 保持在 0.7 左右，并通过动态扩容来维持效率。
二、策略一：拉链法（Separate Chaining）—— 最直观的方案
拉链法的思想很简单：每个桶不再存储单个元素，而是指向一个链表的头指针（或动态数组）。冲突发生时，新元素直接追加到该桶对应的链表尾部。
C++ 实现（基于 vector 的邻接表）
template<typename K, typename V>
class HashMapChaining {
private:
struct Node {
K key;
V value;
Node(K k, V v) : key(k), value(v) {}
};
vector<vector<Node>> buckets;
int size;
float load_factor_limit = 0.75;
int hash(const K& key) const {
return std::hash<K>{}(key) % buckets.size();
}
void rehash() {
int new_capacity = buckets.size() * 2;
vector<vector<Node>> new_buckets(new_capacity);
for (auto& bucket : buckets) {
for (auto& node : bucket) {
int idx = std::hash<K>{}(node.key) % new_capacity;
new_buckets[idx].push_back(node);
}
}
buckets.swap(new_buckets);
}
public:
HashMapChaining(int init_cap = 16) : buckets(init_cap), size(0) {}
void put(const K& key, const V& val) {
if ((float)size / buckets.size() > load_factor_limit) rehash();
int idx = hash(key);
for (auto& node : buckets[idx]) {
if (node.key == key) {
node.value = val;
return;
}
}
buckets[idx].emplace_back(key, val);
size++;
}
bool get(const K& key, V& val) const {
int idx = hash(key);
for (const auto& node : buckets[idx]) {
if (node.key == key) {
val = node.value;
return true;
}
}
return false;
}
};
优点：实现简单，删除方便，最坏情况仅发生在单链表过长时（可通过扩容缓解）。
缺点：需要额外的指针/容器开销，对缓存不友好（链表节点在内存中可能不连续）。
在竞赛中，拉链法常被 std::unordered_map 采用。但如果你需要手写（例如自定义哈希或避免被卡），拉链法是首选。
三、策略二：开放地址法（Open Addressing）—— 紧凑的自救
开放地址法将所有元素直接存储在桶数组本身。当冲突发生时，通过探测序列（probing sequence）寻找下一个空闲桶。探测的几种常见方式：
1. 线性探测（Linear Probing）
冲突时依次检查下一个桶：h(k, i) = (hash(k) + i) mod m，i=0,1,2,…
template<typename K, typename V>
class HashMapLinear {
vector<pair<K, V>> table;
vector<bool> occupied;
int size;
int hash(const K& key) const {
return std::hash<K>{}(key) % table.size();
}
int probe(int start, int i, const K& key) const {
return (start + i) % table.size();
}
public:
HashMapLinear(int cap = 16) : table(cap), occupied(cap, false), size(0) {}
void put(const K& key, const V& val) {
if ((float)size / table.size() > 0.7) expand();
int start = hash(key);
int i = 0;
int first_deleted = -1;
while (occupied[probe(start, i, key)]) {
int idx = probe(start, i, key);
if (table[idx].first == key) {
table[idx].second = val;
return;
}
i++;
}
int idx = probe(start, i, key);
table[idx] = {key, val};
occupied[idx] = true;
size++;
}
};
优点：内存连续，缓存友好，无额外指针开销。
缺点：删除复杂（通常需要“墓碑”标记），容易产生主聚集（primary clustering），导致探测长度激增。
2. 二次探测（Quadratic Probing）
探测序列为 h(k, i) = (hash(k) + c1·i + c2·i²) mod m，常用 c1=0, c2=1。二次探测可以减少主聚集，但可能无法探测到所有桶（需要保证 m 是质数且形如 4k+3）。
3. 双哈希（Double Hashing）
使用两个独立的哈希函数 h1 和 h2，探测序列：h(k, i) = (h1(k) + i·h2(k)) mod m。双哈希是开放地址法中分布最均匀的方法，但计算开销稍大。
int h1(const K& key) { return std::hash<K>{}(key) % M; }
int h2(const K& key) { return 1 + (std::hash<K>{}(key) % (M-1)); }
int probe(int i, const K& key) { return (h1(key) + i * h2(key)) % M; }
竞赛评价：开放地址法在手写哈希表（尤其是整数键值对）时非常高效。比如在哈希集合中存储 1e6 个整数，良好的线性探测比 unordered_set 快 30% 以上，因为避免了链表指针跳跃。
四、策略三：双重哈希（Double Hashing）作为独立的冲突解决
严格来说，双哈希既可作为开放地址的一种，也可作为“再哈希法”的一种特例。在竞赛中，有时会结合两个不同的哈希函数 独立计算两个哈希值，只有当两个哈希值都匹配时才认为相同。这种方法极大概率消除了冲突（但对刻意构造的数据仍然可能碰撞）。
典型应用：字符串哈希。比如用 hash1 = (hash1 * base + s[i]) % mod1 和 hash2 = (hash2 * base + s[i]) % mod2 组成一个 pair，作为字符串的指纹。两个模数取 1e9+7 和 1e9+9，碰撞概率几乎为零。
using HashPair = pair<long long, long long>;
const long long MOD1 = 1000000007, MOD2 = 1000000009;
const long long BASE = 131;
HashPair get_hash(const string& s) {
long long h1 = 0, h2 = 0;
for (char c : s) {
h1 = (h1 * BASE + c) % MOD1;
h2 = (h2 * BASE + c) % MOD2;
}
return {h1, h2};
}
如果你需要将双哈希作为 key 存入 unordered_set，可以定义一个 struct 并特化 std::hash，或者直接用 map（但 map 是 O(log n)）。
五、策略四：完美哈希（Perfect Hashing）—— 静态数据的极致
对于静态（不会变化）的键集合，我们可以构造一个完美哈希函数 —— 最坏情况下无冲突，且空间复杂度 O(n)。经典方法是使用两层哈希：第一级将键分到桶中，第二级为每个桶单独构造一个无冲突的哈希表。
竞赛中很少需要手写完美哈希，但有一种简单变体：排序后二分查找。如果键集合静态且可排序，那么有序数组 + 二分查找 O(log n) 比哈希表更简洁且无冲突。当然，这不是哈希。
完美哈希的代表库是 gperf，在编写编译器词法分析器时常用，但在信奥中几乎用不到。
六、竞赛实战：如何避免被卡哈希？
在 Codeforces、洛谷等平台上，出题人常常会构造数据使某些哈希算法退化，特别是 std::unordered_map 的默认哈希。常见卡法：插入大量 x 和 x+65536 等具有相同低位哈希值的数，导致线性探测链过长。
防御手段有以下几种：
1. 自定义哈希函数（针对整数）
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<int, int, custom_hash> mp;
上述代码使用 splitmix64 和随机种子，使哈希值分布均匀，能有效抵抗针对性数据。
2. 改用开放地址法手写哈希表
很多选手会手写一个线性探测哈希表，避开 unordered_map 的过高常数和可能的退化。例如：
const int N = 2e6 + 7;
int key[N], val[N];
int find_pos(int k) {
int pos = k % N;
while (key[pos] != 0 && key[pos] != k) {
pos = (pos + 1) % N;
}
return pos;
}
这种写法极快，且能控制负载因子。缺点是需要事先知道大致数据量以确定 N。
3. 使用 gp_hash_table 或 cc_hash_table（GCC 扩展）
GCC 提供了两种基于探测法的哈希表：__gnu_pbds::gp_hash_table（基于二次探测）和 __gnu_pbds::cc_hash_table（基于拉链法）。它们比 std::unordered_map 更快且更抗卡。
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> mp;
在支持 PBDS 的 OJ（如洛谷、Codeforces 部分）上，这是非常实用的选择。
七、STR 字符串哈希与冲突处理
在大量字符串判重、子串匹配问题中，通常不直接用哈希表存储字符串本身，而是用滚动哈希将字符串映射成整数对（双哈希），然后将该整数对存入哈希集合。这里的冲突处理依然需要上述策略。但需要注意的是：双哈希已经将碰撞概率降到极低，实际中pair<long long,long long>作为unordered_set的键时，需要自定义哈希：
struct pair_hash {
template<class T1, class T2>
size_t operator() (const pair<T1,T2>& p) const {
auto h1 = custom_hash{}(p.first);
auto h2 = custom_hash{}(p.second);
return h1 ^ (h2 << 1);
}
};
unordered_set<pair<LL,LL>, pair_hash> seen;
八、策略选择总结
九、一个完整的手写开放地址哈希表示例
下面给出一个适合竞赛使用的、支持动态扩容的线性探测哈希表（整数键值对）：
class FastHashMap {
static const int INIT_CAP = 1 << 20;
vector<int> keys, vals;
vector<bool> used;
int size = 0;
int hash(int key) const {
return (key ^ (key >> 16)) & (keys.size() - 1);
}
void expand() {
int old_cap = keys.size();
vector<int> old_keys = move(keys);
vector<int> old_vals = move(vals);
vector<bool> old_used = move(used);
keys.assign(old_cap * 2, 0);
vals.assign(old_cap * 2, 0);
used.assign(old_cap * 2, false);
size = 0;
for (int i = 0; i < old_cap; ++i) {
if (old_used[i]) {
put(old_keys[i], old_vals[i]);
}
}
}
public:
FastHashMap(int cap = INIT_CAP) {
keys.assign(cap, 0);
vals.assign(cap, 0);
used.assign(cap, false);
}
void put(int key, int value) {
if (size * 2 > (int)keys.size()) expand();
int idx = hash(key);
while (used[idx] && keys[idx] != key) {
idx = (idx + 1) & (keys.size() - 1);
}
if (!used[idx]) size++;
keys[idx] = key;
vals[idx] = value;
used[idx] = true;
}
bool get(int key, int& value) const {
int idx = hash(key);
while (used[idx]) {
if (keys[idx] == key) {
value = vals[idx];
return true;
}
idx = (idx + 1) & (keys.size() - 1);
}
return false;
}
};
这个版本取容量为 2 的幂，用 & (size-1) 代替取模，速度极快。在洛谷 P3370 字符串哈希模板中，用它存储 1e5 个 64 位哈希值，时间不到 unordered_set 的一半。
十、结语
哈希冲突并不可怕，关键是根据数据规模、操作类型和时间限制选择合适的策略。信奥中，我们往往追求极致的速度和可靠性，因此需要掌握拉链法和开放地址法的手写实现，以及自定义哈希函数的技巧。
当你的程序因为哈希冲突而 TLE 时，不要立刻否定哈希表——尝试换一种冲突解决策略，很可能就会从超时变成 AC。希望本文介绍的多种策略和 C++ 代码能成为你竞赛路上的利器。 |
