为什么建议在分离链接中使用 1 的负载因子？
我看到很多人说它是推荐的，但没有给出明确的解释为什么。
在开放寻址中，我知道负载因子应该在 0.5 和 0.7 之间，因为在处理冲突时它应该是一种快速查找未占用索引的操作。但我不明白为什么在分离链接中负载因子为 1 应该更好。我的意思是，如果我有一个大小为 100 的表，是否还有机会将所有 100 个元素散列到同一个索引并放在同一个列表中？上帝，我真的无法理解为什么分离链接的这个特定负载因子应该是 1。
问问题
3373 次
1 回答
6
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 意味着您不会浪费任何空间并具有最快的查找速度，前提是您使用合适的散列函数来确保插槽的定期和均匀平衡使用。
于 2020-05-07T01:05:52.447 回答