C++朝花夕拾
从一道 groupAnagrams 题谈 STL 容器、哈希与字符串优化
起点：一段"看起来聪明但其实买椟还珠"的代码
// 用 map<int,int> 统计字符频次，再把这个 map 作为外层 map 的 key
map<map<int,int>, int> cache;
直觉上"用频次代替排序"是好思路（O(n) vs O(n log n)），但容器选择把这个优势全部抹掉。
一、map 的 key 不走哈希
第一个常见误解：std::map<K, V> 是红黑树 + operator<，不是哈希表。
std::map查找：O(log N) 次 key 之间的字典序比较std::unordered_map查找：平均 O(1)，需要std::hash<K>
把 map<int,int> 当 key，每次 find 是 O(log N) 次树遍历比较，每次比较还要遍历内层 map 的所有 pair——常数极差。
二、复杂度分析要分清"渐近"和"常数"
渐近最优（asymptotically optimal）= 在大 O 意义上达到问题下界，再优化只能改善常数。
groupAnagrams 在 σ=26（小写字母）假设下：
| 方案 | key 构造 | key 比较 |
|---|---|---|
map<map<int,int>, int> | O(k) | O(σ)=O(1) |
| 排序 string | O(k log k) | O(k) |
array<int,26> | O(k) | O(σ)=O(1) |
关键认知：
- σ 视为常数时，方案一和方案三渐近同阶，差距全在常数（堆分配 vs 栈数组）
- σ 视为变量时，三者才有渐近差距
- "渐近最优"和"工程最优"不是一回事——常数因子在实际系统里可能差几十倍
三、k 的规模决定方案选型
| k 范围 | 推荐 | 理由 |
|---|---|---|
| k ≤ ~20 | 排序 string | 落在 SSO 内，零堆分配，代码最短 |
| 20 < k ≤ 100 | 统计到 string(26,0) | key 固定 26 字节，hash/compare 快 |
| k > 100 | array<int,26> + 自定义 hash | 完全栈上，无分配 |
不要为了小规模 k 过早优化——sort 和 count 的差距小到要 profile 才能感知。
四、std::array 没有默认 hash
unordered_map<array<int,26>, vector<string>> m; // 编译失败
C++ 标准库没有为 std::array 提供 std::hash 特化（标委会认为"组合方式没有唯一正确答案"）。三种解法：
string(26, 0)当桶：复用std::hash<string>，但 26 > SSO 阈值，每次堆分配- 自定义 hash（推荐）：array 在栈上，零分配
- 二进制布局编码成 string：质量好但不必要——还是堆分配
五、boost::hash_combine 深入
不是标准库（提案 P0814 至 C++26 仍未通过），五行可以自己抄：
template<class T>
void hash_combine(size_t& seed, const T& v) {
seed ^= std::hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
逐项拆解：
0x9e3779b9= 黄金比例 φ × 2³² 取整。Knuth 在 TAOCP Vol.3 证明这个常数作为乘法哈希因子能让任意输入分布最均匀，避免簇聚(seed << 6) + (seed >> 2)：让 seed 高低位都参与扰动（雪崩效应）^=而非=：使 hash 顺序敏感（hash(a,b) ≠ hash(b,a)）- 单独一项不够强：纯异或会让 hash(a,a)=0，纯加法满足交换律——必须组合扰动
六、SSO（Small String Optimization）
std::string 对象本身约 24 字节，复用这块内存存短字符串，避免 malloc：
| 实现 | SSO 容量（不含 \0） |
|---|---|
| libstdc++ (GCC) | 15 |
| libc++ (Clang) | 22 |
| MSVC | 15 |
实际影响：
string a = "hello"; // 5 字符，SSO，零分配
string b(26, 0); // 26 字节，超出阈值，堆分配
避免一次堆分配（malloc 约 100 ns）往往比避免一次循环更值钱，尤其在 hot path。
判断技巧：
cout << (void*)s.data() << " vs " << (void*)&s;
// 地址相近 → SSO；地址区间不同 → 堆分配
七、最终参考实现
// k ≤ 100，简洁优先
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (auto& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[move(key)].push_back(s);
}
vector<vector<string>> rst;
rst.reserve(groups.size());
for (auto& [_, v] : groups) rst.push_back(move(v));
return rst;
}
// k 较大，性能优先
struct ArrayHash {
size_t operator()(const array<int,26>& a) const noexcept {
size_t seed = 0;
for (int x : a) seed ^= hash<int>{}(x) + 0x9e3779b9 + (seed<<6) + (seed>>2);
return seed;
}
};
unordered_map<array<int,26>, vector<string>, ArrayHash> groups;
核心收获
- 看 STL 容器的复杂度，先看底层数据结构：
map是树不是哈希 - 渐近最优 ≠ 工程最优：常数因子在真实系统里能差一两个数量级
- 避免堆分配 > 避免循环：SSO 是 string 性能的隐形分水岭
- 标准库没有给 array hash：必要时手写五行
hash_combine 0x9e3779b9不是魔法：是黄金比例的整数化，专治哈希簇聚
评论
发表评论