0

このコード (出所不明の LZW 圧縮プログラムから抜粋) は、0 から 5020 までのインデックスが付けられたサイズ 5021 のハッシュ テーブルで空のスロットを見つけます。

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を参照してください

おっと：これはLCGですが、2^1004 % 5021 == 1であるため、最適な期間を持つものではありません。次のメンバーを持つ5つの異なるサイクルがあります: (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 に答える