C++ unordered_map 用法：哈希表快速查找详解

当顺序不重要时

你刚刚学过 std::map，它用平衡树让键保持有序，提供 O(log n) 的操作。但排序是有代价的，而很多时候你并不在乎键以什么顺序出现，只想尽快知道“这个键在不在，它的值是什么？”

这正是 std::unordered_map 的用途。它是一个哈希表：每个键都会经过哈希函数，以决定存放在哪里，这让插入、查找和删除的复杂度变成平均 O(1)，而不是 O(log n)。代价是遍历顺序是未指定的：键会按照桶里恰好存放的顺序出现。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

它的接口有意设计得和 map 几乎一样，很多时候只要改一下类型就能互相替换。要包含的是 <unordered_map>（而不是 <map>），而且键出来时是无序的。

插入与更新

放入元素有好几种方式，它们的行为并不完全一样。最常用的两种是 operator[] 和 insert：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // create or overwrite
    votes["alice"] = 5;              // overwrites -> 5
    votes.insert({"bob", 2});        // inserts only if "bob" is absent
    votes.insert({"bob", 99});       // ignored, "bob" already exists

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, not 99
}

关键区别在于：operator[] 会覆盖已有的值，而 insert 不会动已经存在的键。如果你用的是 C++17，insert_or_assign(key, value) 提供“无论如何都设置”的语义，而 try_emplace(key, args...) 只在键是新的时候才原地构造值，适合构造成本高的值。

operator[] 的陷阱：读取时也会插入

这是 unordered_map 最常见的 bug，所以单独用一节来讲。m[key] 不是单纯的读取。如果键不存在，它会默认构造并插入这个键（int 变成 0，string 变成 ""），然后返回一个引用。所以看起来像是查找的代码，会悄悄让 map 变大：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // We only meant to CHECK for "y", but [] inserted it:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, not 1!
}

仅仅是提到了 seen["y"]，就创建了一个 "y" -> 0 条目。要在不修改 map 的情况下检查键是否存在，请使用 count（返回 0 或 1）或 find：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() reads cleaner than count()
    if (seen.contains("x")) cout << "x is here\n";
}

经验法则：只有在你打算“创建或更新”时才用 []。单纯读取时，用 count、contains（C++20）或 find。

find 与 at：安全的查找

find 返回指向该条目的迭代器，键不存在时返回 end()。它从不插入，而且一次查找就能通过 it->first 和 it->second 拿到键和值：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

当你确定键应该存在、并且希望它不存在时直接报错，就用 at。和 [] 不同，at 不会插入：键不存在时它会抛出 std::out_of_range：

int p = prices.at("pen");   // fine
int q = prices.at("hat");   // throws std::out_of_range - key absent

所以你有三种查找方式：[]（会插入）、at（会抛出异常）、find/count（报告是否存在，不改动 map）。选择失败方式与你的意图相符的那一种。

遍历与删除

用带结构化绑定的基于范围的 for 循环，是遍历每个条目的简洁方式。记住顺序是任意的，永远不要依赖它：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // order is unspecified
    }
}

要删除一个条目，erase 可以直接接收一个键，并返回删除的个数（0 或 1）。有一个重要的陷阱：在 unordered_map 中边遍历边删除，只会让被删除元素的迭代器失效，所以要用 erase(it) 的返回值来安全地前进：

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Drop every team with a score below 3
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase returns the next valid iterator
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

写成 wins.erase(it++) 的风格，或者在普通的 erase(it) 之后再 ++it，是经典的悬空迭代器陷阱：被删除的迭代器已经失效，所以一定要使用 erase 返回的迭代器。

选 map 还是 unordered_map？

两者都存储键值对，接口也相似，所以选择取决于你需要什么：

// std::map            -> sorted keys, O(log n), range queries (lower_bound)
// std::unordered_map  -> no order,    O(1) avg, fastest plain lookup

只需要按键快速查找、顺序无关紧要时（统计词频、缓存、去重），用 unordered_map。需要键保持有序、按顺序遍历或做范围查询时，选 map。unordered_map 有两点要注意：它的 O(1) 是平均值，糟糕的哈希会让它退化；自定义的键类型需要特化哈希或提供哈希函数对象，而 map 只需要 operator<。

下一步：set

现在你已经见过两种键值容器了。不过有时你根本不需要值，只关心某样东西是否存在，比如一组不重复的标签或已访问过的 ID。接下来我们看看 std::set（以及它基于哈希的兄弟 unordered_set），它们只存储键，并自动保持键的唯一性。