data-structures - 哈希表中的重新散列

Question

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

谢谢

Answer 1

正如您所解释的，当哈希表填充超过某个数字负载因子时，通常我们会重新散列。在进行重新散列时，我们增加哈希表的大小并进行重新散列。Rehashin 不是关于使用替代散列策略，而是关于重新散列成新大小的散列故事（使用旧/新策略）

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