哈希表中负载因子和时间复杂度之间的关系？
Relation between the load factor and time complexity in hash tables?
关于散列tables，我们使用负载因子来衡量散列table的性能。但是我需要了解负载因子和 hash table 的时间复杂度之间的关系。根据我的理解，这个关系是成正比的。这意味着，我们只需要 O(1) 来计算哈希函数来找到索引。如果加载因子很低，这意味着 table 中没有足够的元素，因此在正确索引处找到键值对的机会很高，因此搜索操作最少，但复杂度仍然很高是一个常数。另一方面，当负载因子很高时，找到键值对到其确切位置的机会很低，因此我们将需要进行一些搜索操作，因此复杂度将上升到 O(n) 。插入操作也是如此。这样对吗？
这是一个很好的问题，答案是 "it depends on what kind of hash table you're using."
A chained hash table 其中，要存储一个项目，您将其散列到一个存储桶中，然后将该项目存储在该存储桶中。如果多个项目最终出现在同一个桶中，您只需将最终出现在该桶中的所有项目的列表存储在桶本身中。 （这是散列的最常教授的版本 table。）在这种散列 table 中，假设一个好的散列函数，桶中元素的预期数量是 O(α) ，其中负载因子用 α 表示。这符合直觉，因为如果您将项目随机分布在桶中，您会期望大约 α 的项目最终出现在每个桶中。在这种情况下，随着负载因子的增加，您平均必须做越来越多的工作才能找到一个元素，因为每个桶中的元素都会越来越多。不过，查找的运行时间不一定会达到 O(n)，因为即使没有足够多的存储桶可供使用，您仍然会将项目分布在存储桶中。
A linear probing hash table 通过有一个插槽数组来工作。每当你对一个元素进行哈希处理时，你都会转到它的槽位，然后在 table 中向前走，直到你找到该元素或找到一个空闲槽位。在那种情况下，随着负载因子接近 1，越来越多的 table 槽将被填充，实际上你会发现自己处于这样一种情况，即在最坏的情况下搜索确实需要时间 O(n) 因为只有几个免费插槽可以停止您的搜索。 （Don Knuth 有一个漂亮而著名的分析表明，假设散列函数的行为类似于随机选择的函数，查找或插入散列不成功的成本 table 将花费时间 O(1 / (1 - α)2)。绘制此函数并查看运行时间如何随着 α 越来越接近 1 而增长是很有趣的。)
希望对您有所帮助！
关于散列tables，我们使用负载因子来衡量散列table的性能。但是我需要了解负载因子和 hash table 的时间复杂度之间的关系。根据我的理解，这个关系是成正比的。这意味着，我们只需要 O(1) 来计算哈希函数来找到索引。如果加载因子很低，这意味着 table 中没有足够的元素，因此在正确索引处找到键值对的机会很高，因此搜索操作最少，但复杂度仍然很高是一个常数。另一方面，当负载因子很高时，找到键值对到其确切位置的机会很低，因此我们将需要进行一些搜索操作，因此复杂度将上升到 O(n) 。插入操作也是如此。这样对吗？
这是一个很好的问题，答案是 "it depends on what kind of hash table you're using."
A chained hash table 其中，要存储一个项目，您将其散列到一个存储桶中，然后将该项目存储在该存储桶中。如果多个项目最终出现在同一个桶中，您只需将最终出现在该桶中的所有项目的列表存储在桶本身中。 （这是散列的最常教授的版本 table。）在这种散列 table 中，假设一个好的散列函数，桶中元素的预期数量是 O(α) ，其中负载因子用 α 表示。这符合直觉，因为如果您将项目随机分布在桶中，您会期望大约 α 的项目最终出现在每个桶中。在这种情况下，随着负载因子的增加，您平均必须做越来越多的工作才能找到一个元素，因为每个桶中的元素都会越来越多。不过，查找的运行时间不一定会达到 O(n)，因为即使没有足够多的存储桶可供使用，您仍然会将项目分布在存储桶中。
A linear probing hash table 通过有一个插槽数组来工作。每当你对一个元素进行哈希处理时，你都会转到它的槽位，然后在 table 中向前走，直到你找到该元素或找到一个空闲槽位。在那种情况下，随着负载因子接近 1，越来越多的 table 槽将被填充，实际上你会发现自己处于这样一种情况，即在最坏的情况下搜索确实需要时间 O(n) 因为只有几个免费插槽可以停止您的搜索。 （Don Knuth 有一个漂亮而著名的分析表明，假设散列函数的行为类似于随机选择的函数，查找或插入散列不成功的成本 table 将花费时间 O(1 / (1 - α)2)。绘制此函数并查看运行时间如何随着 α 越来越接近 1 而增长是很有趣的。)
希望对您有所帮助！