algorithm - 将 n 个元素插入空哈希表的运行时间

Question

人们说将 O(1) 分摊到哈希表中。因此，放n个元素一定是O(n)。然而，对于大 n 来说情况并非如此，因为正如一位回答者所说，“满足预期的分摊 O(1) 所需要做的就是扩展表并在发生冲突时使用新的随机散列函数重新散列所有内容。”

那么:将 n 个元素插入哈希表的平均运行时间是多少？我意识到这可能与实现有关，所以请提及您所谈论的实现类型。

例如，如果存在 (log n) 次等距碰撞，并且每次碰撞都需要 O(k) 来解决，其中 k 是哈希表的当前大小，那么您将具有以下递推关系:

T(n) = T(n/2) + n/2 + n/2

(也就是说，你花时间插入n/2个元素，然后你有一个碰撞，用n/2个来解决，然后你在没有碰撞的情况下进行剩余的n/2个插入)。这仍然是 O(n)，所以是的。但这合理吗？

Answer 1

这完全取决于您的重新散列效率有多低。具体来说，如果您第二次可以正确估计哈希表的预期大小，您的运行时间仍然接近 O(n)。实际上，在确定预期顺序之前，您必须指定重新哈希大小计算的效率有多低。