可扩展哈希：为什么要使用最高有效位？

Question

在编写可扩展哈希时，我们可以使用哈希值的最高位或最低位来确定哈希到哪个桶中。使用最低位有很多优点：

• 当你将目录加倍时，你只需复制所有指针，而不是创建一个交错它们的新目录。
• 你可以通过不谈论位，而只使用模算术（就像一般哈希一样）来简化算法的讨论。使用3个最低位选择一个桶与 h(x) = x mod 2^3 相同。
• 您无需预先指定二进制数的宽度；如果使用最高有效位，则需要考虑特定的位长度。

但我不理解的是，为什么在参考之后，使用最高有效位完成了可扩展哈希，如此处 、此处 和 此处 等多个参考文献。据我所知，最高有效位仅提供在纸上（或屏幕上）没有交叉线的图表。是否有任何充分理由使这么多来源使用最高有效位而不是最低位呢？

- Vultan

---

可能的原因就是你提到的那个：图表更整洁，因为所有这些引用都是为了解释目的。例如，你第一个参考中提供的实际实现使用了LSB。 - rici

Answer 1

我最终回到了Fagin等人的原始论文。他们解决了这个问题：

“我们注意到，如果我们使用伪码字的后缀而不是前缀，那么加倍目录的算法将变得特别容易：它基本上将在第一份副本之后立即创建目录的非头部分的第二份副本。然而，出于直观上的简单性考虑（因此，通过使用前缀，可以轻松地按伪关键字顺序访问关键字，而不是倒置的伪关键字顺序），我们选择使用前缀。”

我不理解他们为什么认为这种方法更直观，因为你可以摆脱整个比特概念，改用模算术，但至少他们有这样的理由。

- Vultan