可扩展哈希在目录加倍后重新指向指针

Question

3

我需要了解在目录翻倍后重新定向指针的规则。每个存储桶将有两倍于当前指针数的指针，但我的问题是如何确定要将哪个目录条目指向每个存储桶？注意：这不是关于重新定向指针的问题，在存储桶拆分后本地深度低于目录中当前使用的比特数的情况下，在这种情况下，位于本地深度+1的比特将决定这一点。

- Daniel Valland

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bunny · Answer 1

让我们考虑一个例子，每个桶的大小为4，并且在目录中使用了“最低有效位”。

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

- 目录的全局深度：用于确定一个条目属于哪个桶所需的最大位数。在我们的例子中，由于在目录中使用了最低有效位，全局深度等于用于标识桶的最低有效位的位数。 - 桶的局部深度：用于确定一个条目是否属于该桶的位数。

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

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

现在，让我们插入一个哈希值为20的条目。20的二进制值的最后两位是00，所以20*应该被插入到桶A中。然而，由于桶A已满，这是不可能的。

扩展目录

为了解决这个问题，我们必须将全局深度增加1。因此，新的全局深度变为3，这意味着我们现在必须考虑哈希值的最后3位来确定其位置。 32*和16*被放置在同一个桶中，因为它们的最后3位是相同的。（将4*、12*和20*放在同一个桶中的原因也是相同的。）

注意