0

此代码（从未知来源的 LZW 压缩程序中提取）在大小为 5021 的哈希表中找到一个空槽，索引从 0 到 5020：

probe := <random 12-bit hash key>
// probe is initially 0 to 4095
repeat
  {
  if table[probe] is empty then return(probe);
  if probe == 0 then probe := -1 else dec(probe, 5021-probe);
  if probe < 0 then inc(probe, 5021);
  }

这不是典型的线性或二次探测。为什么要这样探？这是一种已知的探测算法吗？我在哪里可以找到更多关于它的信息？

4

1 回答 1

0

尽管看起来很丑，但计算新探针的算法很简单：

if probe == 0
    probe <= 5020
else
    probe <= (2*probe) % 5021

目前还不太清楚为什么选择了这个函数，但它确实以一种循环且看似随机的方式遍历了所有可能的位置 1..5020（并且 0 被发送回循环）。（不，它没有，看到哎呀！）应该注意的是，数字 5021 在这种情况下有点神奇。

该算法实际上是一个线性同余生成器（LCG）。见http://en.wikipedia.org/wiki/Linear_congruential_generator

OOPS：它是 LCG，但不是具有最佳周期的，因为 2^1004 % 5021 == 1。有以下成员的五个不同周期：（1、2、4、8，...），（ 3, 6, 12, 24, ...), (7, 14, 28, 56, ...), (9, 18, 36, 72, ...), 和 (11, 22, 44, 88 , ...)。更奇怪的是有人选择使用这种算法。（或者然后我分析错了。）

于 2014-06-18T21:38:32.623 回答