关于哈希表，我们使用负载因子来衡量哈希表的性能。但是我需要了解负载因子和哈希表的时间复杂度之间的关系。据我了解，该关系是成正比的。这意味着，我们只需要使用O（1）进行哈希函数的计算即可找到索引。如果负载系数很低，则意味着表中没有足够的元素，因此在其正确索引处找到键值对的机会很高，因此搜索操作最少，而且复杂度仍然是恒定的。另一方面，当负载系数高时，找到键值对到其精确位置的机会就很小，因此我们将需要执行一些搜索操作，因此复杂度将提高到O（n）。插入操作也可以这样说。这样对吗？
这是一个很好的问题，答案是“这取决于您使用的是哪种哈希表。”
A chained hash table，要在其中存储项目，请将其哈希到存储桶中，然后将项目存储在该存储桶中。如果多个项目最终出现在同一个存储桶中，则只需将所有最终存储在该存储桶中的所有项目的列表存储在存储桶本身内。 （这是哈希表最常用的版本。）在这种哈希表中，假设哈希函数良好，则存储桶中期望的元素数为O（α），其中负载因子表示为α。这具有直观的意义，因为如果您将商品随机分布在各个存储桶中，则可以预期其中的α最终会出现在每个存储桶中。在这种情况下，随着负载因子的增加，平均来说，要找到一个元素，您将不得不做越来越多的工作，因为每个存储桶中将有更多的元素。不过，查找的运行时间不一定会达到O（n），因为即使没有足够的存储桶来回移动，您仍然可以在存储桶中分配项目。
A linear probing hash table通过具有一组插槽来工作。每当对元素进行哈希处理时，都将转到其插槽，然后在表中向前走，直到找到该元素或找到一个空闲插槽。在这种情况下，随着负载系数接近一个，将填充越来越多的表插槽，并且实际上，您会发现自己在最坏的情况下确实确实要花费时间O（n）的情况，因为这样只会一些免费的插槽来停止您的搜索。 （Don Knuth进行了一项美丽而著名的分析，该研究表明，假设哈希函数的行为类似于随机选择的函数，不成功查找或将其插入哈希表的开销将花费时间O（1 / /（1--α）< [2）有趣的是绘制此函数并查看当α越来越近时运行时间如何增长。）]
希望这会有所帮助！