为什么哈希表的不成功搜索时间复杂度为 Θ(1+α)?

Question

我得到Θ(1(部分是用于计算哈希表的时间，但我不明白Θ(α(部分。

在我看来，时间复杂度是 Θ(n(。假设α是预期长度，并且表有 m 个插槽。为了确保密钥不在表中，我们需要搜索每个插槽，每个插槽都有α例外长度，所以总时间为 α 乘以 m，然后是 Θ(n(。

谁能告诉我哪一部分我没有正确理解？

Answer 1

测试给定的密钥是否在哈希表中不需要测试所有插槽。您只需计算给定键 (1( 的哈希值。此哈希值标识密钥必须位于哪个插槽(如果它在哈希表中(。因此，您只需将该插槽中的所有条目 (α( 与给定密钥进行比较，得到 Θ(1+α(。您无需查看其他插槽，因为密钥不能存储在任何其他插槽中。