可扩展散列:为什么有人使用最重要的位？

Question

在对可扩展散列进行编码时,可以选择使用散列值的最高有效位或最低有效位来确定要散列到哪个桶.使用最低有效位具有许多优点:

• 当您将目录加倍时,您可以只复制所有指针,而不必创建一个交错它们的新目录.
• 您可以简化对算法的讨论,甚至根本不讨论比特,只需使用模拟算法,就像使用散列一样.使用3个最低有效位来选择桶与h(x)= x mod 2 ^ 3相同.
• 您不需要事先指定二进制数的宽度; 如果您使用的是最重要的位,则需要考虑特定的位长.

我无法理解的是为什么在参考之后参考后的参考显示了使用最高有效位完成的可扩展散列.据我所知,最重要的比特产生的唯一优势是纸上(或屏幕上)没有交叉线的图表.是否有任何充分的理由可以解释为什么这么多来源如此最重要而非最少？

Answer 1

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

“我们注意到，如果我们使用伪键的后缀而不是前缀，那么将目录加倍的算法将特别简单：它本质上包括在第一个副本之后立即制作目录非标头部分的第二个副本。然而，为了直观简单起见，我们选择使用前缀（因此，通过使用前缀，可以轻松地按伪键顺序访问键，而不是按反向伪键顺序访问）。”

我不明白为什么他们认为这种方法更直观，因为你可以放弃整个位的想法并使用模块化算术，但看来这至少是他们的基本原理。