为什么一个hash的不成功搜索时间table的时间复杂度为Θ(1+α)？
Why has an unsuccessful search time for a hash table a time complexity Θ(1+α)?
我知道 Θ(1) 部分是用来计算哈希的时间 table，但我不明白 Θ(α) 部分。
在我看来，时间复杂度是Θ(n)。假设 α 是预期长度并且 table 有 m 个槽。为保证key不在table中，我们需要搜索每个slot，每个slot有α个例外长度，所以总时间是α乘以m，则为Θ(n)。
谁能告诉我哪一部分我没有理解正确？
测试给定键是否在散列中 table 不需要测试所有槽。您只需计算给定键 (1) 的哈希值。如果密钥在哈希 table 中，则此哈希值标识密钥必须位于哪个插槽中。因此，您只需将该槽中的所有条目 (α) 与给定键进行比较，得到 Θ(1+α)。您不需要查看其他插槽，因为密钥不能存储在任何其他插槽中。
我知道 Θ(1) 部分是用来计算哈希的时间 table，但我不明白 Θ(α) 部分。
在我看来，时间复杂度是Θ(n)。假设 α 是预期长度并且 table 有 m 个槽。为保证key不在table中，我们需要搜索每个slot，每个slot有α个例外长度，所以总时间是α乘以m，则为Θ(n)。
谁能告诉我哪一部分我没有理解正确？
测试给定键是否在散列中 table 不需要测试所有槽。您只需计算给定键 (1) 的哈希值。如果密钥在哈希 table 中，则此哈希值标识密钥必须位于哪个插槽中。因此，您只需将该槽中的所有条目 (α) 与给定键进行比较，得到 Θ(1+α)。您不需要查看其他插槽，因为密钥不能存储在任何其他插槽中。