algorithm - 使用线性探测实现 Hashtable 时调整大小权衡

Question

我正在尝试使用线性探测来实现哈希表。

在将（键，值）对插入哈希表之前，我想检查它是否是半满的。如果是，我需要将底层数组的大小加倍。

显然，有两种方法可以做到这一点：

一种是创建另一个大小加倍的数组，重新散列旧数组中的所有条目并将它们添加到新数组中。然后，将旧数组重新绑定到新数组。这种方式很容易实现，但占用大量空间。

另一种是将数组加倍并就地进行重新散列。似乎这种方式可能会导致更长的运行时间，因为重新散列可能会导致与新散列的插槽和旧插槽发生冲突。

我应该使用哪种方式？

Answer 1

如果实际上有空间来就地扩展现有哈希表，则您的第二个解决方案仅在调整大小过程中节省空间-我认为大型哈希表这种情况的可能性很小，所以我会选择你的第一个解决方案。