c++ - 哈希表中搜索函数的平均案例复杂度

Question

通过单独的链接解决冲突的哈希表中搜索函数的平均情况是什么？最好的情况是 Θ(1)，最坏的情况是 Θ(n)，但平均情况呢？我如何证明普通案例的复杂性？

Answer 1

它仍然是 O(1)，假设哈希表实现为 size() / buckets 提供了一些阈值，超过它调整大小（根据 std::unordered map）。您可以很容易地看到这一点 - 如果您搜索哈希表中的每个元素，那么平均值将是 O(1) 的线性倍数，其中线性因子是上面的加载因子......线性因子在大期间被删除-O 分析。