链接中哈希 table 中成功搜索的平均成本

Question

我到处都找过这个，但我不明白为什么是 O(1+a/2) 其中 a 是负载因子。谁能一步一步解释一下。

Answer 1

让散列中的元素数 table 为 n。
这意味着散列中有 n/a 个单元格（/行）总数 table，每个单元格包含一个元素列表。这是负载因子的定义。

因此，与每个此类单元格关联的元素的预期数量为 n/(n/a) = a。
未排序列表中的线性搜索需要遍历一半的元素，直到平均找到正确的元素（我们假设它是一个成功的搜索），所以它需要遍历a/2个元素。

1 因素来自访问哈希 table 本身中的正确列表。