1

我有一段奇怪的代码困扰着我，

   // exbPtr points to 128-bit unsigned integer
   // lgID is a "short" with 0xFFFF being the max value

   int hash = (*exbPtr + (int)lgID * 9) & tlpLengthMask;

最初，这个实际上是一个数组的“哈希表”被初始化为 256 个元素，并且 tlpLengthMask 被设置为 255。

然后是这个神秘的代码.. 上面有一条评论说“如果我们到达这里.. 发生了碰撞”。然后它又开始循环回来，所以看起来这是一个哈希冲突，然后重新哈希？

   hash = (hash + (int)lgID * 2 + 1) & tlpLengthMask;

此外，还有大量的调试代码说这个数组的长度应该是 2 的幂，因为我们使用掩码作为模数。

有人可以解释作者的意图是什么吗？这背后的原因是什么？

编辑——我试图辨别的是为什么他乘以 9，然后为什么乘以 2 来重新散列。

4

1 回答 1

1

有三种可能：

1) 原作者只是或多或少地随机构造了散列函数，看到它们工作得很好，就放弃了。

2) 原作者拥有能很好地代表实际数据的测试数据，并且看到这些函数在他的确切应用中运行得非常好。

3) 这段代码执行得很差，他的哈希表根本没有有效地运行。

唯一真正的要求是对于他实际遇到的任何输入，输出看起来均匀分布在哈希表上，并且总是为相同的输入产生相同的输出。虽然这些类型的功能通常表现不佳，但对于这个特定的应用程序来说它们可能已经足够好了。

顺便说一句，这种类型的开放散列在删除时不起作用。例如，假设您向表中添加了一条记录。然后你去添加第二个，但它与第一​​个发生冲突，所以你向前跳来添加第二个。现在一切都很好——你可以找到第一条记录（直接）和第二条记录（当你在第二条记录的哈希位置找到它时跳过第一条记录）。

但是如果你删除第一条记录，你怎么找到第二条呢？当您查看第二条记录的哈希位置时，您什么也找不到。你尝试跳过吗？如果有，有多少次？

这些问题有一些解决方法，但它们往往很容易做错。

于 2012-05-29T08:49:14.400 回答