麦地

Back

1. 核心概念:哈希映射#

1.1 基本定义#

#include <unordered_map>
std::unordered_map<int, int> mp;
cpp

竞赛常用写法:

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> mp;
cpp

表示 key 到 value 的映射:

mp[10] = 100;
mp[20] = 200;
cout << mp[10]; // 100
cpp

1.2 三个关键词#

  1. 哈希:根据 key 的哈希值快速定位存储位置。
  2. 无序:遍历顺序不是升序,也不保证等于插入顺序。
  3. key 唯一:同一 key 只能对应一个 value。

1.3 与 map 的本质区别#

  • map:有序树形结构,操作通常稳定 O(log n)。
  • unordered_map:哈希表,操作平均 O(1),最坏可退化为 O(n),遍历顺序未指定。

1.4 哈希冲突#

两个不同 key 可能得到相同或落入同一位置的哈希结果,称为冲突。哈希表通过桶内比较等方式区分它们。不同实现的桶组织、冲突处理和扩容策略可以不同,不要依赖具体内部布局。


2. 创建与初始化#

unordered_map<int, int> a;
unordered_map<string, int> b;
unordered_map<int, int> c = {{1, 10}, {2, 20}};
vector<pair<int,int>> v = {{3, 30}, {4, 40}};
unordered_map<int,int> d(v.begin(), v.end());
cpp

键类型要求:

  1. 可以被默认哈希,或提供自定义 Hash。
  2. 可以进行相等比较,默认使用 operator== 或提供的 KeyEqual。

标准库已经为 int、long long、string 等常见类型提供 std::hash。pair、tuple 和自定义 struct 默认不能直接作为 unordered_map 的 key。


3. 查询:operator[]、at、find、count#

3.1 operator[]:会隐式插入#

mp[10] = 100; // 存在则赋值,不存在则先插入再赋值
cpp

读取也可能插入:

int x = mp[999]; // 若 999 不存在,会插入 {999, 0}
cpp

对 int,默认 value 为 0;对 string 为空串;对 vector 为空 vector。规则是值初始化。

这是频率统计很方便的原因:

for (int x : a) ++cnt[x];
cpp

但它是高频陷阱:只想查询时,operator[] 可能污染 map,增加不必要 key。

3.2 at:不插入,越界抛异常#

int x = mp.at(10);
cpp

key 不存在时抛出 std::out_of_range。调试阶段可用,竞赛热路径通常使用 find。

3.3 find:推荐的安全查询#

auto it = mp.find(key);
if (it != mp.end()) {
    cout << it->second;
}
cpp

不会隐式插入元素。

3.4 count 与 contains#

if (mp.count(key)) {} // unordered_map 中只会是 0 或 1
cpp

C++20:

if (mp.contains(key)) {}
cpp

3.5 const map 不能 operator[]#

void f(const unordered_map<int,int> &mp) {
    // mp[1]; // 错误:operator[] 可能插入,故没有 const 版本
    auto it = mp.find(1); // 正确
}
cpp

4. 插入、更新与删除#

4.1 insert:不覆盖旧值#

auto [it, inserted] = mp.insert({key, value});
cpp
  • key 不存在:插入新元素,inserted 为 true。
  • key 已存在:保留旧 value,inserted 为 false,it 指向旧元素。
mp.insert({1, 100});
mp.insert({1, 200}); // 不覆盖,value 仍是 100
cpp

4.2 赋值:会覆盖或插入#

mp[key] = value;
cpp

4.3 emplace#

mp.emplace(key, value);
cpp

与 insert 类似,如果 key 已存在,不会覆盖旧值。

4.4 try_emplace:C++17,存在时不修改#

auto [it, inserted] = mp.try_emplace(key, value);
cpp
  • key 不存在:构造并插入 value。
  • key 已存在:不构造/不修改 mapped value。

适合避免不必要构造或只想初始化一次的逻辑。

4.5 insert_or_assign:C++17,存在则覆盖#

auto [it, inserted] = mp.insert_or_assign(key, value);
cpp
  • key 不存在:插入。
  • key 已存在:把 mapped value 更新为新值。

4.6 erase#

按 key 删除:

size_t removed = mp.erase(key); // 返回 0 或 1
cpp

按迭代器删除:

auto it = mp.find(key);
if (it != mp.end()) {
    it = mp.erase(it); // 返回后继迭代器
}
cpp

删除区间:

mp.erase(first, last); // 删除 [first,last)
cpp

4.7 clear#

mp.clear(); // 删除所有键值对
cpp

5. 遍历与迭代器#

5.1 结构化绑定遍历#

for (const auto &[key, value] : mp) {
    cout << key << " -> " << value << '\n';
}
cpp

修改 value:

for (auto &[key, value] : mp) {
    ++value;
}
cpp

key 类型是 const,不能通过遍历修改:

for (auto &kv : mp) {
    // kv.first = 100; // 错误
    kv.second = 100;   // 可以
}
cpp

5.2 遍历顺序未指定#

for (auto &[k, v] : mp) {}
cpp

不要假设输出是升序、降序或插入顺序。扩容、重新哈希后顺序也可能变化。需要有序结果时:

  • 把 key 收集到 vector 后排序。
  • 直接使用 map。

5.3 迭代器类型#

unordered_map 提供至少前向迭代器,不提供随机访问,也不提供 rbegin()。不能:

// mp[0];       // 这不是数组下标
// mp.begin() + 3;
// --mp.end(); // 不能当作稳定的有序尾元素操作
cpp

5.4 遍历时删除#

for (auto it = mp.begin(); it != mp.end();) {
    if (it->second == 0) it = mp.erase(it);
    else ++it;
}
cpp

不要在范围 for 中随意插入元素:插入可能触发 rehash,使遍历使用的迭代器失效。


6. 复杂度、桶与扩容#

6.1 常用复杂度#

设元素数为 n:

操作 平均复杂度 最坏复杂度
operator[] 查询/插入 O(1) O(n)
find / count O(1) O(n)
insert / emplace O(1) O(n)
按 key erase O(1) O(n)
按迭代器 erase O(1) 通常 O(1)
遍历 O(n) O(n)
clear O(n) O(n)
rehash O(n) O(n)

对于 string key,还要加上计算哈希和比较字符串的线性成本;所谓平均 O(1) 指哈希定位的期望复杂度,不是让长字符串免费处理。

6.2 桶与负载因子#

mp.bucket_count();  // 当前桶数
mp.load_factor();   // size / bucket_count
mp.max_load_factor(); // 当前最大负载因子
cpp

修改最大负载因子:

mp.max_load_factor(0.7f);
cpp

较小负载因子通常减少冲突,但增加内存;较大负载因子节省内存,但可能降低查询性能。竞赛中一般不随意调整,除非有明确性能需求。

6.3 reserve 与 rehash#

mp.reserve(n); // 为至少 n 个元素预留,减少扩容
mp.rehash(n);  // 桶数至少为 n
cpp

区别:

  • reserve(n) 按当前 max_load_factor 计算,目标通常是容纳 n 个元素。
  • rehash(n) 直接指定至少 n 个桶。

已知大规模插入数量时,提前 reserve 可减少多次扩容和搬移:

mp.reserve(n * 2); // 也可留更多余量
cpp

6.4 迭代器与引用失效#

  • rehash 会使迭代器失效,并改变遍历顺序。
  • rehash 后元素引用和指针通常仍有效,但不要依赖具体实现保存这些指针作为长期逻辑。
  • 删除元素只会使指向被删元素的迭代器、指针和引用失效。
  • clear 使全部相关迭代器、引用失效。

竞赛建议:结构性修改后重新调用 find() 或 begin(),不要持有旧迭代器继续使用。


7. 应用一:频率统计#

unordered_map<long long, int> cnt;
cnt.reserve(n * 2);

for (long long x : a) {
    ++cnt[x];
}
cpp

查询:

int c = cnt[x]; // 若确定允许缺失时插入,可这样写
cpp

若只是查询且不希望插入:

int c = 0;
auto it = cnt.find(x);
if (it != cnt.end()) c = it->second;
cpp

如果需要按 key 升序输出频率:

vector<long long> keys;
keys.reserve(cnt.size());
for (auto &[k, v] : cnt) keys.push_back(k);
sort(keys.begin(), keys.end());
cpp

不要直接从 unordered_map 得到有序结果。


8. 应用二:两数之和#

vector<int> twoSum(const vector<int> &a, int target) {
    unordered_map<int,int> pos; // value -> index
    pos.reserve(a.size() * 2);

    for (int i = 0; i < (int)a.size(); ++i) {
        int need = target - a[i];
        auto it = pos.find(need);
        if (it != pos.end()) {
            return {it->second, i};
        }
        pos[a[i]] = i;
    }
    return {-1, -1};
}
cpp

关键点:

  1. 先查询再插入,避免同一元素与自身配对。
  2. map 存值到下标。
  3. 若下标从 1 开始,应存入 i+1。
  4. target - a[i] 涉及极端整数时需考虑溢出,可改用 long long。

平均时间 O(n),空间 O(n)。


9. 应用三:前缀和计数#

统计和为 k 的连续子数组个数:

long long countSubarraySumK(const vector<long long> &a, long long k) {
    unordered_map<long long,long long> cnt;
    cnt.reserve(a.size() * 2);

    long long prefix = 0, ans = 0;
    cnt[0] = 1; // 空前缀

    for (long long x : a) {
        prefix += x;
        auto it = cnt.find(prefix - k);
        if (it != cnt.end()) ans += it->second;
        ++cnt[prefix];
    }
    return ans;
}
cpp

原理:

  • 子数组 [l+1,r] 的和为 prefix[r] - prefix[l]。
  • 对当前 prefix,查找历史中出现过的 prefix-k 次数。

不要先插入当前前缀再查询,否则 k=0 时可能把当前位置错误匹配到自身。


10. 应用四:映射、分组与状态记录#

10.1 值到下标映射#

unordered_map<long long,int> pos;
for (int i = 0; i < n; ++i) pos[a[i]] = i; // 若重复,保留最后一次
cpp

如果需要保留第一次或记录所有下标,应明确设计:

unordered_map<long long, vector<int>> positions;
positions[x].push_back(i);
cpp

10.2 分组#

unordered_map<string, vector<int>> groups;
groups[key].push_back(i);
cpp

operator[] 会自动创建空 vector,适合流式追加。

10.3 稀疏状态记录#

当状态值很大但出现次数有限时,用 unordered_map 替代巨大数组:

unordered_map<long long, int> dp;
dp[state] = value;
cpp

如果状态空间连续且规模适中,vector 通常比哈希表更快、更省额外开销;不要盲目把所有数组都改成 unordered_map。


11. 自定义 key 与哈希函数#

11.1 pair 默认不能直接作为 key#

// unordered_map<pair<int,int>, int> mp; // 默认没有 std::hash<pair<int,int>>
cpp

11.2 防碰撞基础 hash:splitmix64#

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        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);
    }
};
cpp

使用:

unordered_map<long long, int, custom_hash> mp;
unordered_set<int, custom_hash> st;
cpp

加入随机种子能降低固定哈希被针对性构造最坏输入的风险,适合存在哈希攻击风险的竞赛环境。

11.3 pair 哈希#

struct PairHash {
    size_t operator()(pair<int,int> p) const noexcept {
        uint64_t a = static_cast<uint32_t>(p.first);
        uint64_t b = static_cast<uint32_t>(p.second);
        uint64_t mixed = a ^ (b + 0x9e3779b97f4a7c15ULL + (a << 6) + (a >> 2));
        return custom_hash{}(mixed);
    }
};

unordered_map<pair<int,int>, int, PairHash> mp;
mp[{1, 2}] = 10;
cpp

负数会先转换为固定的 32 位无符号表示,能作为稳定位模式参与哈希。

11.4 自定义结构体#

11.5 哈希与相等比较必须一致#

若 a == b,它们的哈希必须相同;否则即使逻辑上相等,也可能在查找时找不到。不能把随机值直接包含在每个对象的相等性之外又不正确处理哈希一致性。

11.6 浮点 key 要谨慎#

浮点舍入误差可能让逻辑上相同的 key 产生不同二进制值。竞赛中若坐标或状态来自整数输入,优先保留整数;需要浮点 key 时应考虑精度离散化,而不是直接信任 ==。


12. unordered_map 没有哪些功能#

// mp.lower_bound(x); // 错误:无序,没有边界查询
// mp.upper_bound(x);
// mp.rbegin();       // 没有反向有序迭代
// *mp.begin();       // 不表示最小值,只是某个桶顺序位置
cpp

如果需要:

  • 有序遍历:map。
  • 前驱/后继:map。
  • 第 k 小:map 也不够,需要专门结构。
  • 保持插入顺序:额外 vector 记录插入序列,unordered_map 只负责快速查询。

13. 与其他容器的选择#

需求 推荐容器
key-value 快速查询,不要求顺序 unordered_map
key-value 且要求 key 有序、前驱后继 map
只需要存在集合,不需要 value unordered_set 或 set
key 允许重复 unordered_multimap / multimap
key 是连续小整数 vector 通常更快更省
只需要当前最大/最小 priority_queue
需要稳定最坏复杂度 有序树结构通常更可靠

13.1 与 map 的复杂度取舍#

  • unordered_map:平均 O(1),最坏 O(n)。
  • map:通常稳定 O(log n),同时提供有序边界。

如果 n 很大且只需要快速存在或计数,unordered_map 往往更快;如果在线查询边界或要求确定性的对数复杂度,map 更合适。

13.2 与 vector 的取舍#

若 key 在 [0,N] 且 N 可接受:

vector<int> cnt(N + 1, 0);
cpp

通常比 unordered_map 更快、遍历稳定、内存布局更好。key 稀疏或范围巨大时才优先考虑哈希表。


14. 高频错误与避坑清单#

14.1 用 operator[] 查询导致隐式插入#

// if (mp[x] > 0) {} // x 不存在时也会插入 {x,0}
auto it = mp.find(x);
if (it != mp.end() && it->second > 0) {}
cpp

14.2 误以为遍历有序#

unordered_map 的 begin 不是最小 key。需要排序必须显式排序或使用 map。

14.3 pair/tuple 直接作 key 编译失败#

默认标准库没有它们的 hash,必须提供自定义哈希,或改用以单个整数编码 key。

14.4 遍历时插入触发 rehash#

范围 for 中插入可能导致迭代器失效。应收集待插入项,循环后统一插入,或使用不引发结构变化的算法。

14.5 忘记最坏复杂度#

平均 O(1) 不保证每次 O(1)。大量冲突、恶意输入或错误哈希函数可能显著退化。

14.6 不等价 key 的哈希不一致#

相等 key 必须有相同 hash,否则查找会失败。

14.7 前缀计数顺序错误#

统计当前前缀贡献时,应先查询历史计数,再插入当前前缀。

14.8 对巨大连续值域滥用哈希#

小整数下标直接使用 vector,通常比 unordered_map 更快。


15. 一页速记#

最终必须牢牢记住:

  1. unordered_map 是哈希表,平均 O(1),最坏 O(n)。
  2. 遍历顺序未指定,begin 不是最小 key。
  3. operator[] 在 key 不存在时会自动插入默认值。
  4. 安全查询使用 find;需要异常检查使用 at。
  5. pair、tuple、自定义 struct 需要自定义 Hash 和相等比较。
  6. 大量插入前可 reserve(n),减少 rehash。
  7. 插入、删除、扩容后不要继续使用可能失效的迭代器。
  8. 需要有序边界查询时用 map,不需要顺序时才优先 unordered_map。
Comment seems to stuck. Try to refresh?✨