我已经到处寻找这个，但我不明白为什么它是 O(1+a/2) 其中 a 是负载因子。有人可以一步一步解释一下吗？
最佳答案
令哈希表中的元素数量为n。
这意味着哈希表中有n/a个单元格(/行)，每个单元格包含一个元素列表。这就是负载因子的定义。
因此，与每个此类单元关联的元素的预期数量为 n/(n/a) = a。
未排序列表中的线性搜索需要遍历一半的元素，直到平均找到正确的元素(我们假设这是一次成功的搜索)，因此需要遍历 a/2 元素。
1 因子来自访问哈希表本身中的正确列表。
关于performance - 链式哈希表中成功搜索的平均成本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29458675/