data-structures - 封闭哈希表的线性冲突空间不足

Question

所以我有一个 8 桶哈希表，h(i) = i mod 8 其中插入了这些数字：

7, 11, 18, 28, 20, 8, 15, 23

我刚开始学习哈希表，所以我对这些概念很困惑。

如果我有一个开放的哈希表，结果将是：

0 | 8
1 |
2 | 18
3 | 11
4 | 28 20
5 |
6 |
7 | 7 15 23

现在，如果我必须使用封闭哈希并实现线性冲突处理，我会

0 | 8
1 | 15 moved from 7
2 | 18
3 | 11
4 | 28 
5 | 20 moved from 4
6 | 23 moved from 7
7 | 7

我这样做对吗？

Answer 1

是的，这看起来是正确的。请注意，实际上哈希表具有阈值负载因子，在该阈值负载因子上它们将执行调整大小以保持较低的负载因子，因此通常您不会让线性探测表填充到您演示的水平。