C++中unordered_set的find操作如何实现平均O(1)时间复杂度？

C++官方文档指出unordered_set的find操作平均时间复杂度为Θ(1)，最坏为O(n)。你疑惑的点在于直觉上认为线性查找期望是n/2，应该是Θ(n)，这其实是没抓住哈希表的核心逻辑：

unordered_set底层是哈希表结构，核心依赖哈希函数和桶数组：

• 哈希函数会把每个元素映射到一个桶的索引，理想的哈希函数能让元素均匀分散到各个桶中，加上容器会在负载因子（元素数/桶数）过高时自动扩容桶的数量，最终每个桶里的平均元素数会维持在常数级别（比如接近1）。
• 执行find时，第一步是用哈希函数计算目标元素对应的桶位置，这一步是O(1)操作；第二步是在对应桶内查找元素，因为桶内平均只有常数个元素，这一步的时间也是常数级。两者相加，整体平均时间复杂度就是Θ(1)。

你之前的错误直觉来自把find当成了全局线性遍历，但实际上哈希表先通过哈希值快速定位到极小的范围（单个桶），再在这个小范围内查找，而非遍历整个集合。只有当哈希函数失效（所有元素都被映射到同一个桶）时，才会退化成最坏情况的O(n)——也就是在单个桶里线性遍历所有元素。

内容的提问来源于stack exchange，提问作者Paul Talma