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

Question

通常说，哈希表上搜索操作的平均成本为 O(1)，因为表上给定列表的长度与负载因子成正比。我没有得到的是负载因子显然取决于我们要存储的条目数，因此它不一定是常数。假设我们经常添加新条目，那么平均列表的长度不是也取决于条目的数量吗？O(1) 的操作如何？

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

Answer 1

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