Joz*_*ers 3 hash hash-function hashtable load-factor
为什么建议在单独链接中将负载因子设为 1？
我看到很多人说它是推荐的，但没有给出明确的解释原因。
在开放寻址中，我知道负载因子应该在 0.5 到 0.7 之间，因为在处理冲突时找到未占用的索引应该是一个快速的操作。但我不明白为什么在单独链接中负载因子为 1 应该更好。我的意思是，如果我有一个大小为 100 的表，是否还有机会将所有 100 个元素散列到相同的索引并放在同一个列表中？天啊，我真的无法理解为什么这个单独链接的特定负载因子应该是 1。
tl; dr：通过不占用插槽来节省内存空间并通过最小化列表遍历操作的数量来加快访问速度。
如果您将负载系数理解为n_used_slots / n_total_slots：
有一个1客座率只是介绍了使用分离链冲突处理一个良好实现的哈希表中的理想状况：没有插槽处于空。
另一种经典方法，开放寻址，要求表在添加新项目时始终有可用的空闲槽。为每个项目调整表格大小的成本太高了，但我们也受到内存限制，不希望周围有太多未使用的插槽。必须在速度（很少调整表大小、快速插入和查找）和内存（很少有空槽）之间找到平衡点（在编程中如此频繁）。在理想的负载因子是基于这样的想法平衡，并且可以根据实际的散列函数，该值域和其他因素来估计。
另一方面，使用分离链，我们通常从一开始就期望拥有（方式）比可用哈希表槽更多的项目。如果发生冲突，我们需要将项目添加到存储在特定插槽中的链表中。由于在链表中搜索成本很高，因此我们希望最小化列表遍历操作。为此，最好的情况是让所有插槽都充满理想情况下相同长度的列表！填充所有插槽对应的负载因子为 1。
换句话说：负载因子 < 1 意味着有空槽并且项目必须添加到另一个槽中的链表中，增加了列表遍历操作的次数并浪费了一些内存。
关于大小为 100 的表格示例：是的，所有项目都有可能发生碰撞并仅占用一个插槽。在这种情况下，有效负载因子将为 0.01，性能将受到严重影响。
如果您将负载系数理解为n_items / n_total_slots：
在这种情况下，加载因子可以大于 1。因子 < 1 表示您有空槽，而因子 > 1 表示有多个槽包含多个项目，因此需要遍历列表。在第一种情况下，您正在浪费空间，而在第二种情况下，列表遍历会导致（小）性能下降，具体取决于列表的大小。
示例：负载因子为 10 意味着平均每个插槽可容纳 10 个项目。因此，搜索一个项目意味着平均遍历 5 个列表节点。
负载因子为 1 意味着您不浪费空间并拥有最快的查找，如果您使用体面的哈希函数来确保插槽的定期和均衡使用。