data-structures - 在哈希表中重新哈希

Question

我有一个关于重新散列的问题。据我所知，当负载因子(表中元素的数量/表的大小)达到 0.5 时，我们使用重新散列并通过重新散列，我们希望减少冲突。我很确定在进行二次探测时可以使用重新散列，我的问题是，重新散列应该与线性探测或单独链接一起使用吗？在进行单独链接或线性探测时是否有任何使用重新散列的逻辑？

谢谢

Answer 1

正如您所解释的那样，通常我们会在哈希表的填充量超过一定数量 - 负载因子时进行重新哈希处理。在进行重新哈希时，我们增加哈希表的大小并进行重新哈希。 Rehashin 不是关于使用替代哈希策略，而是关于重新哈希到新大小的 hashtale(使用旧/新策略)

使用哪种碰撞处理策略取决于您。通常人们会选择封闭哈希。我们也可以使用单独的链接，但它仅用于未知和已知大小，但开放寻址用于已知大小。因此，如果已知大小，我们更喜欢开放寻址以避免数据浪费。