为什么C++ STL unordered_set的find()方法平均时间复杂度为O(1)？

1. 底层核心不是线性结构，是哈希表 #

你直觉上认为它是线性结构是误区，unordered_set的底层实现是哈希表（散列表），这是它能实现平均O(1)查找的核心基础。
哈希表的核心逻辑非常好理解：

• 定义一个哈希函数，将你要存储的元素映射为一个整数，这个整数会直接作为底层数组的下标
• 存储元素时，先通过哈希函数算出下标，把元素存在数组对应下标位置
• 查找元素时，对目标元素再做一次哈希计算，直接去对应下标的位置取元素即可，这一步不需要遍历，时间复杂度天然是O(1)

2. 哈希冲突的解决逻辑 #

你担心的最坏O(n)复杂度是客观存在的，它来自「哈希冲突」场景：不同的元素通过哈希函数计算出来的下标完全相同，这时候不可能把多个元素塞到同一个数组位置里。
STL的unordered_set采用**链地址法（开链法）**解决冲突：

• 底层数组的每个位置（STL里称为「桶/bucket」）不直接存元素，而是存一个链表的头指针（新版本STL会在链表长度超过阈值时替换为红黑树优化长链表查找效率）
• 所有哈希值相同的元素，都会被挂到对应下标的链表上
• 查找时，先算哈希值找到对应链表，再遍历链表匹配目标元素即可

如果哈希函数设计合理，元素会均匀分布在各个桶的链表上，平均每个链表的长度就是1或者非常小的常数，所以平均查找次数就是常数级，也就是大家常说的平均O(1)复杂度。

3. STL unordered_set的专属实现细节 #

STL对哈希表做了很多工程优化，保证实际使用的效率：

• 你可以直接调用unordered_set的内置方法查看底层状态：bucket_count()返回当前桶的总数量，bucket_size(n)返回第n个桶里存储的元素总数
• 为了避免链表过长拉低效率，unordered_set设置了负载因子（默认值为1）：当元素总数量 / 桶总数量 > 负载因子时，会自动触发扩容：申请一个更大的桶数组，把所有元素重新计算哈希值放到新桶里，这个过程叫重哈希（rehash），单次重哈希的时间是O(n)，但均摊到所有插入操作中，平均时间复杂度还是常数级
• 最坏O(n)的场景只有在所有元素哈希值都相同、全部挂在同一个桶的链表上时才会触发，只要哈希函数设计合理，这种场景几乎不会出现，刷题时除非碰到刻意构造卡哈希的测试用例，否则不需要担心。

4. 实际使用注意事项 #

• 平时刷LeetCode时，unordered_set的find()、count()、插入、删除操作平均效率都远高于底层是红黑树的set，优先用它做存在性判断、去重即可，碰到卡哈希的题再换set
• 游戏开发中如果要存大量唯一ID、做状态判重，unordered_set是非常合适的选择，只有当你需要给自定义类型做哈希函数时，才需要注意设计哈希规则避免大量冲突。

内容的提问来源于stack exchange，提问作者Apekshik Panigrahi