持续更新中: 现代C++高效编程实战手册:从项目痛点直通现代C++精髓
从论文到部署的 C++语音推理全栈实战
动手学习CUDA编程
3年C++开发还看不懂Workflow框架?这套教程让你逆袭
动手学习100个Qt项目
读懂OpenCV的每一行代码
![]()
"hash map 慢是因为 hash 函数不够好"——这句话被说了十年,但它是错的。你可以把 hash 函数从 std::hash 换成 wyhash、xxhash、甚至用密码学级的 SipHash, std::unordered_map 的 find 延迟不会有数量级变化。瓶颈不在 hash 的质量,在 hash 之后的事:每次查找至少追两个指针(桶数组→链表节点→key),每个指针都是一次几乎必然的 cache miss。
abseil 的 flat_hash_map 换了一种做法。它把每个槽的 hash 值拆出高 7 位,存进一个独立的、连续的控制字节数组(control bytes)。查找时,先用一条 SSE2 指令 _mm_cmpeq_epi8 把目标指纹广播到 128-bit 寄存器里,和 16 个控制字节同时比较——一次 SIMD 操作过滤 16 个槽,只有指纹匹配的槽(期望不到 0.11 个)才会去碰真正的 key。
Matt Kulukundis 在 CppCon 2017 公开这个设计后,Google 在整个代码库里把 unordered_map 替换成 flat_hash_map ,取得了可测量的全舰队 CPU 使用率下降。此后 Rust 标准库(hashbrown, 2019)、Boost.Unordered(2022)、Go 1.24(2025)先后采用同一设计。这篇文章拆开这个设计的每一层:从 unordered_map 的内存布局讲起,到控制字节的位编码、SIMD 探测循环、三角数步长的数论证明、tombstone 的代价,最后讲清楚为什么 C++ 标准库被引用稳定性焊死在链式实现上。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.