set 和 unordered_set 的成员函数几乎逐个对得上:insert、erase、find、count、size、clear 名字一样,参数一样,返回值也一样。把源码里的类型名换掉,多数代码照样编译。差异藏在模板参数和底层结构里,落在下面这张表里:

map / setunordered_map / unordered_set
底层红黑树哈希桶(桶数组加链表)
对键的要求支持小于比较(<)支持哈希(Hash)和相等比较(==)
迭代器双向迭代器前向迭代器,只能 ++
遍历顺序中序遍历,按 Key 有序由哈希值和桶数决定,不保证顺序
增删查平均O(logN)O(1)
最坏O(logN)O(N)

四个模板参数,后三个平时不写

unordered_set 的声明是这样:

template<
    class Key,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key>
> class unordered_set;

unordered_map 的声明在 Key 后面多一个 T:

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, T>>
> class unordered_map;

unordered_set 是四个参数,unordered_map 是五个。后三个在两种容器里的含义相同:哈希仿函数、判等仿函数、分配器。

课件说“unordered_set 默认要求 Key 支持转换为整形”,这句话把默认哈希的行为当成了容器的要求。标准给的默认实参是 std::hash<Key>,容器需要的是“这个仿函数接受一个 Key,返回 size_t”。整数类型的 std::hash 恰好是恒等映射,看上去像“转成整形”;std::hash<std::string> 是一套真正的字符串哈希,逐字符计算,不是把整个 string 强转成整数。因此判断一个类型能不能不带第二个模板参数直接当键,看的是有没有可用的 std::hash 特化;没有就自己传一个哈希仿函数。

第二个仿函数 std::equal_to<Key> 要求 operator==。哈希表先用哈希值定位桶,再在桶内逐个比较键,两步缺一不可。自定义类型要自己补两个仿函数:

#include <cstddef>
#include <functional>
#include <unordered_set>
 
struct Point
{
    int x;
    int y;
};
 
struct PointHash
{
    std::size_t operator()(const Point& p) const
    {
        return std::hash<int>{}(p.x) * 31u + std::hash<int>{}(p.y);
    }
};
 
struct PointEqual
{
    bool operator()(const Point& a, const Point& b) const
    {
        return a.x == b.x && a.y == b.y;
    }
};
 
int main()
{
    std::unordered_set<Point, PointHash, PointEqual> pts;
    pts.insert({1, 2});
    return 0;
}

两条约束必须自洽:相等的两个对象,哈希值必须相同;哈希值相同的对象可以不等,桶里再比一次。== 比了 x 和 y,哈希却只算 x,程序不会报错,只是所有同 x 的点挤进一个桶,查找退化成链表遍历。

接口一样,迭代器只能朝前走

增删查的签名与 set 完全一致,只有两处要留意:

std::pair<iterator, bool> insert(const value_type& val);   // second 表示是否真的插入
std::size_type erase(const key_type& k);                   // 返回删掉的个数,0 或 1
iterator find(const key_type& k);

map 版本多一个 mapped_type& operator[](const key_type& k),语义是“键不存在就插入一个值初始化的映射值,再返回引用”。只查不改时用 find、count 或 at,at 找不到会抛 std::out_of_range。

迭代器类别写在前向迭代器(LegacyForwardIterator)这一档:++it 可以,it++ 可以,--it 和 it + n 不行。它遍历的是桶数组加桶内链表,所以顺序由哈希值和桶数决定。无序不等于随机:同一个程序、同一批数据、同一次运行,顺序是确定的;换编译器、换标准库版本,或者中间插入几个元素触发 rehash,顺序就可能变。不要把遍历顺序写进测试的期望值。

失效规则要分开记:

  • rehash(插入导致扩容,或调用 reserve / rehash 时确实重排了桶)可能让所有迭代器失效;
  • 指向元素的引用和指针只在对应元素被删除时失效,即使迭代器已经因 rehash 失效,引用仍然有效;
  • 遍历过程中插入或删除都可能让当前迭代器作废,批量删除先把键记下来,遍历结束再动手。

引用和指针的稳定性与 vector 相反。vector 扩容会搬走元素,引用一起废;哈希表扩容只换桶数组,结点不搬家,引用和指针得以保留。这也是标准库能给出上面那条承诺的原因。

平均 O(1) 的前提

哈希表的查找代价是“算一次哈希 + 走一条桶链”。平均复杂度 O(1) 里的 average,摊在合理哈希和受控负载因子(load factor)上:

负载因子 = 元素个数 N / 桶数 M

unordered_* 默认的 max_load_factor() 是 1,插入后超过这个值就自动 rehash,桶数扩大、所有元素重新挂链。bucket_count() 是当前桶数,load_factor() 是当前比值,reserve(n) 一次性把桶数准备到能装 n 个元素而不触发 rehash,rehash(n) 直接要求至少 n 个桶。桶数由实现挑选,reserve(100) 之后 bucket_count() 常见结果是 103 这类质数,不是 100。

想让两组数据可比,两边都要在计时前准备好容量。下面这段把 reserve 放在计时区间之外:

#include <chrono>
#include <cstddef>
#include <iostream>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>
 
int main()
{
    const std::size_t N = 1000000;
    std::mt19937 gen(20250101);
    std::vector<int> v;
    v.reserve(N);
    for (std::size_t i = 0; i < N; ++i)
        v.push_back(static_cast<int>(gen()));
 
    std::set<int> s;
    std::unordered_set<int> us;
    us.reserve(N);                     // 扩容发生在计时之前
 
    auto t0 = std::chrono::steady_clock::now();
    for (int e : v) s.insert(e);
    auto t1 = std::chrono::steady_clock::now();
    for (int e : v) us.insert(e);
    auto t2 = std::chrono::steady_clock::now();
 
    std::cout << "set: "
              << std::chrono::duration<double, std::milli>(t1 - t0).count() << " ms\n";
    std::cout << "unordered_set: "
              << std::chrono::duration<double, std::milli>(t2 - t1).count() << " ms\n";
    std::cout << "bucket_count=" << us.bucket_count()
              << " load_factor=" << us.load_factor() << '\n';
    return 0;
}

课件里的对比程序把 us.reserve(N) 放在了 begin2 之后,等于把一次重哈希算进 unordered_set 的插入耗时,而 set 那组没有对应动作。另外它只包含了 <unordered_set>、<unordered_map>、<set>、<iostream>,却用了 vector、srand、time;标准不保证这些头文件会顺带引入 <vector>、<cstdlib>、<ctime>,换一个实现可能编不过。比较性能时,两边的时间区间要包含同样的工作。

最坏情况也得知道。哈希函数被对手掌握时,可以刻意构造一批同桶的键,把 O(1) 拖成 O(N),这类攻击叫哈希洪泛(hash flooding)。多数标准库实现会对字符串哈希加随机种子,但这只是提高攻击成本;对外部输入做键、又要求稳定响应时间时,红黑树的 O(logN) 更可控。

什么时候仍然用 map 和 set

哈希表不是默认答案。下面几种情况换回红黑树更合适:

  • 需要按顺序遍历,比如输出排行榜、按时间区间扫数据。map 的中序遍历天然有序,unordered_map 得自己排序,多付一次 O(N logN)。
  • 需要范围查询。lower_bound、upper_bound 是树的强项,哈希表只能全表扫描。
  • 需要最坏情况有保证。对外网输入做键,或者服务对尾延迟敏感,树是稳定 O(logN)。
  • 数据量很小。几十个元素时,树的缓存局部性更好,哈希表要先算哈希再跳桶,未必更快。
  • 需要“插入不影响已有迭代器”。树插入不会让其他迭代器失效;哈希表一次 rehash 就让全部迭代器作废。

unordered_multimap 和 unordered_multiset 与 multimap / multiset 的关系相同:允许重复键,equal_range 返回一对迭代器覆盖所有同键元素。三方面差异照旧:键要能哈希、迭代器单向、平均 O(1)。用之前先确认真的需要重复键,很多“可能需要”最后都变成了 map 加一个 vector 值。

桶相关接口平时不用,排查性能时很有价值:

#include <iostream>
#include <string>
#include <unordered_set>
 
int main()
{
    std::unordered_set<std::string> us;
    us.max_load_factor(0.7f);
    us.reserve(1000);
 
    std::cout << us.bucket_count() << '\n';
    std::cout << us.bucket_size(us.bucket("hello")) << '\n';
    std::cout << us.load_factor() << '\n';
    return 0;
}

bucket(key) 返回键落在哪个桶,bucket_size(n) 返回第 n 个桶挂了几个元素。某个桶里长期挂着上百条,基本可以判定哈希函数写坏了,或者数据分布正好撞在这个模数上。把 max_load_factor 调到 0.7,用一点内存换更短的链;调到 2.0,省内存但桶里更挤。默认的 1 是折中值,不是最优值。