为什么这个哈希表查找探查是这样的

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被发送回循环)。(不，它没有，看到哦!)应该注意的是，数字5021在这个上下文中有点神奇。

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

OOPS:它是LCG，但不是最优周期的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，…)。更奇怪的是有人选择使用这个算法。(或者我分析错了)