如何在可扩展哈希中创建空桶

Question

我知道如何在纸张上执行可扩展哈希，但我不知道如何创建空桶。

什么会导致在可扩展哈希中创建空桶？你能举一个简单的例子吗？

Answer 1

假设散列函数h(x)是h(x) = x，并且每个存储桶可以容纳两件事。

我也将使用散列码的最低有效位作为哈希目录的索引，而不是最高有效位。

基本上，为了得到一个空的桶，我们希望通过尝试将某些东西放入没有空间的桶中，但我们希望这种加倍失败的情况来诱发散列表的加倍。

所以，让我们开始插入东西。

首先，插入0.这应该在第一个桶中，因为h(0) = 0和0 % 2 = 0。

然后，插入4.这也应该在第一个桶中，因为h(4) = 4和4 % 2 = 0。

现在，插入8失败，因为存储桶只能容纳两件事，所以表必须加倍大小。因此，全局散列级别从1增加到2。其他更改包括新的第三个存储桶和指向第二个存储桶的第四个散列索引。

不幸的是，由于重新哈希过程花费了h(x) % 4，而且我们所有的数字都是（有意）4的倍数，所以第一个桶仍然太满，第三个桶是空的。这解决了哈希表的又一倍。