使用单独链接对哈希表进行搜索操作的时间复杂度

Question

通常说在散列 table 上搜索操作的平均成本是 O(1)，因为 table 上给定列表的长度与负载因子成正比.我不明白的是，加载因子显然取决于我们要存储的条目数，因此它不一定是常数。假设我们经常添加新条目，这是否会使平均列表的长度也取决于条目数？ O(1) 的操作如何？

对不起我的英语。这不是我的主要语言。

Answer 1

许多实现调整 table 的大小，以便负载因子保持在常数范围内。调整大小花费的时间与存储的项目数量成正比，但如果不经常这样做，它会平衡，以便插入需要 amortized 常数时间。