当使用一个好的散列函数（任意两个元素碰撞的概率为 1 / m，其中 m 是桶的数量）实现散列表时，众所周知，查找元素是 Θ(1 + α)，其中 α 是负载因子。但是，如果所有元素最终都放入同一个桶中，最坏情况的运行时间是 O(n)。
我最近在阅读哈希表，发现这篇文章声称（第 3 页）如果 α = 1，则预期的最坏情况复杂度为 Θ(log n / log log n)。通过“预期的最坏情况复杂性”，我的意思是，根据预期，如果元素由统一的散列函数分布，您将不得不做的最大工作量。这与实际的最坏情况不同，因为最坏情况的行为（同一桶中的所有元素）极不可能实际发生。
我的问题如下——作者似乎暗示不同的 α 值可以改变查找的预期最坏情况复杂性。有谁知道某处的公式、表格或文章讨论了改变 α 如何改变预期的最坏情况运行时间？
对于固定α的，预期的最坏时间总是Θ(log n / log log n)。但是，如果您制作α的函数n，则预期的最坏时间可能会改变。例如，如果α = O(n)预期的最坏时间是O(n)（即您拥有固定数量的哈希桶的情况）。
一般来说，项目在桶中的分布近似为泊松分布，随机桶中包含i项目的几率为。最坏的情况只是接近独立观察的第一个最坏的情况。（不完全独立，但相当接近。）观察中最糟糕的往往是发生几率大约为几倍的事情。（更准确地说，分布由 Β 分布给出，但对我们的分析来说已经足够好了。）αi e-α / i!mmmm1/m1/m
当您进入泊松分布的尾部时，该i!术语的增长支配着其他所有事物，因此高于给定值的所有事物的累积概率i小于选择i自身的概率。因此，您可以通过求解以下问题得出一个很好的近似值：
α我e-α / 我！= 1/m = 1/(n/α) = α/n
取双方的日志，我们得到：
i log(α) - α - (i log(i) - i + O(log(i)) = log(α) - log(n) log(n) - α = i log(i) - i - i log(α) + O(log(i))
如果我们保持α不变，那么这是：
log(n) = i log(i) + O(i)
i如果有表格k log(n) / log(log(n))，这可以工作k = Θ(1)吗？让我们尝试一下：
log(n) = (k log(n) / log(log(n))) (log(k) + log(log(n)) - log(log(log(n)))) + O(log(日志（n）））
= k (log(n) + o(log(n)) + o(log(n))
然后我们得到更清晰的估计，对于任何固定负载平均值α，预期的最坏时间是(1 + o(1)) log(n) / log(log(n))