set 和 unordered_set 的成员函数几乎逐个对得上:insert、erase、find、count、size、clear 名字一样,参数一样,返回值也一样。把源码里的类型名换掉,多数代码照样编译。差异藏在模板参数和底层结构里,落在下面这张表里:
map / set | unordered_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 / 桶数 Munordered_* 默认的 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 是折中值,不是最优值。
还没有评论 — 第一条由你来留。