负载因子才0.5，unordered_map就有30%的桶在碰撞——读libstdc++源码看懂Google为什么要造absl::flat_hash_map

往std::unordered_map里插100万个随机整数，负载因子控制在0.5——每两个桶才分到一个元素。

听起来很宽裕。但如果你遍历每个桶，数一下有多少桶里挂了超过一个节点，你会得到一个不太直觉的数字：大约30%的桶已经在拉链了。

不是负载因子0.9，不是0.8，是0.5。桶的数量是元素的两倍，平均下来每个桶不到一个元素，但将近三分之一的桶里有两个或两个以上的节点排队等候。每多一个节点，就多一次指针跳转，多一次cache miss。

这个数字不是bug，是数学。跟哈希函数好不好没关系。任何足够均匀的哈希函数在这个负载因子下都会产生这个碰撞比例，因为元素到桶的分配本质上是一个独立随机过程，碰撞概率由Poisson分布精确描述。

Google内部的工程师做了同样的算术，但他们多算了一步：不仅算了碰撞比例，还算了每次碰撞在现代CPU上的真实代价。结论是，std::unordered_map的拉链法设计，在Google的服务规模下，仅哈希表这一个数据结构就贡献了可观的CPU cache miss。于是他们造了absl::flat_hash_map——一个用open addressing替代拉链法、用flat layout替代node-based存储、用SIMD指令并行探测元数据的哈希表。2017年CppCon上，Google工程师Matt Kulukundis在演讲Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step中首次公开了这套设计，后来被称为Swiss Table。

这篇从libstdc++的_H