为什么这个哈希表查找探针像它一样？

Question

这段代码（从来历不明的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);
  }

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

Answer 1

计算新探测器的算法很简单，尽管它看起来很丑：

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

不太清楚为什么选择了这个函数，但它确实经历了所有可能的位置1。。5020以循环且看似随机的方式（0被发送回循环）。（不，它没有，请看oops！）应该注意的是，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, ...)。更奇怪的是有人选择使用这个算法。（或者我分析错了。）