链接不会减少哈希表中的主要冲突吗？

Question

我有一个关于作业的问题，询问对于哈希表，如果选择链式、线性探测或二次探测，主要冲突的数量是否会更低。

答案是没关系，但我认为通过链接，桌子上会有更多未占用的位置（因为你不会进行任何探测），因此这会导致更少的主要碰撞。

有人可以帮助解释为什么我的想法是错误的吗？谢谢。

Answer 1

要理解答案，您必须检查您是否理解主要冲突是什么，因为名称本身并不能明确传达含义。

主要冲突是指散列不同的键将您引导到同一个存储桶，而不考虑任何冲突后解决策略。因此，所有直接散列到同一个“主”存储桶的 N 个键之间可能会发生 N 向主要冲突，即使实际存储在该存储桶中的值是由于在其冲突后进行探测而最终到达那里的另一个键。自己的散列到（主）存储桶....

通过链接，桌子上会有更多未占用的位置（因为您不会进行任何探测），因此这会导致更少的主要碰撞。

这里的错误只是“会导致较少的主要碰撞”——它会导致较少的碰撞，但那些不同的碰撞都是次要碰撞（这也是一个有点令人困惑的术语——它只是意味着非主要的，而不是特别是第二个地方尝试了钥匙；没有“第三次”碰撞 - 我们不计算，只是分类为主要/直接/在家和次要/间接/不在家）。