目录加倍后可扩展散列重新指向指针

Question

我需要了解目录加倍后重新指向指针的规则。每个存储桶将有两倍于其当前指针，但我的问题是如何确定哪个目录条目指向每个存储桶？注意：这不是在存储桶分割后重新指向指针的问题，其中局部深度低于目录中当前使用的位数，其中局部深度+1 处的位将确定这一点。

Answer 1

让我们考虑一个示例，其中每个存储桶的大小为 4，并且最低有效位用于目录。

但在此之前，你必须了解以下术语：

插入一些值后，假设目录和桶的状态如下：

哈希值（用星号表示）显示在桶内（而不是数据）以方便理解。实际上，数据而不是哈希值被放置在桶中。

现在我们插入一个哈希值为 20 的条目。20 的二进制值的最后两位是

，所以

20*

应该插入到 Bucket A 中。但是，由于 Bucket A 已满，这是不可能的。

双重目录

为了解决这个问题，我们必须将全局深度增加 1。因此新的全局深度变为 3，这意味着我们现在必须考虑哈希值的最后 3 位来确定其位置。

32*

和

16*

保存在同一个桶中，因为它们的最后 3 位是相同的。（将

4*

、

12*

和

20*

放入同一个桶中的原因相同。）