单独链接中的负载因子？

Question

bounty到期在3天内。该问题的答案有资格获得+ 50声望赏金。Fabulous想要引起更多关注对此问题。

为什么在单独链接中建议负载系数为1？

[我已经看到很多人说这是推荐的，但没有对为什么给出清晰解释。

在开放式寻址中，我知道负载系数应该在0.5到0.7之间，因为在处理冲突时，这应该是查找未占用索引的快速操作。但是我看不到为什么单独链接中的负载因子应该更好。我的意思是，如果我有一个大小为100的表，那么是否还没有机会将所有100个元素散列到相同的索引并放入相同的列表中？天哪，我真的不明白为什么单独链接的此特定负载系数应为1。

Answer 1

tl]：通过not保留空闲的插槽来节省内存空间，通过减少列表遍历操作的次数来加快访问速度。 具有

load factor of 1

仅描述了使用单独链接冲突处理的，实现良好的哈希表的理想情况：没有插槽留空。 另一种经典方法，即“打开地址”，要求表在添加新项目时始终具有可用的空闲插槽。调整表的大小对于每个项目来说都太昂贵了，但是我们也受内存限制，并且不想有太多未使用的插槽。必须在速度（很少调整表大小，快速插入和查找）和内存（很少有空插槽）之间找到平衡（在编程中经常如此）。

理想负载因子

基于这种平衡思想，并且可以基于实际的哈希函数，值域和其他因素进行估算。 另一方面，我们通常希望从一开始就拥有比可用哈希表槽更多（更多）的项目。如果发生冲突，我们需要将该项目添加到存储在特定插槽中的链表中。由于在链接列表中进行搜索的成本很高，因此我们希望最大程度地减少列表遍历操作。为此，最好的情况是让

all

插槽填充理想长度相同的列表！填充所有插槽对应于1的负载系数。换句话说：负载因子<1意味着有空插槽，必须将项目添加到另一个插槽的链表中，这会增加列表遍历操作的数量并浪费一些内存。

关于您的大小为100的表的示例：是的，所有项目有可能发生冲突，并且仅占据一个插槽。在这种情况下，有效负载系数将为0.01，并且性能会受到严重影响。