スパイラルハッシュ

スパイラルハッシュは、スパイラルストレージとも呼ばれ、拡張可能なハッシュアルゴリズムです。^{[1] [2] [3] [4] [5]}すべてのハッシュスキームと同様に、スパイラルハッシュは、アドレス指定にレコードキーを使用して、さまざまな数のバケットにレコードを格納します。拡張リニアハッシュファイルでは、バケットは定義済みの順序で分割されます。これにより、ファイルの末尾に新しいバケットが追加されます。これにより、ファイルの段階的な再編成が可能になりますが、新しく作成されたバケットと分割されたバケットのレコードの予想数は、以前の数の半分に減少します。このスペース使用率の急激な低下を軽減するために、いくつかの試みがなされました。マーティンのスパイラルストレージは、異なるアプローチを使用します。ファイルは、連続した番号のバケットで構成されています。番号の小さい（左側の）バケットには、予想されるレコード数がより多くなります。ファイルが拡張されると、左端のバケットが右側の 2 つのバケットに置き換えられます。このアイデアにはいくつかのバリエーションがあります。^{[6] [7] [8]}

スパイラル ハッシュでは、レコードのキーを単位間隔 に均一ハッシュ関数で処理する必要があります。ハッシュ ファイルがバケット で始まる場合、キーは実数 にマッピングされます。最終アドレスは次のように計算されます。ここでは「拡張係数」です。が増加すると、右側に約 個の新しいバケットが作成されます。Larson ^{[9] は、}線形ハッシュが依然としてスパイラル ハッシュよりも優れたパフォーマンスを発揮することを示す実験を行いました。 ${\displaystyle [0,1]}$${\displaystyle S}$${\displaystyle k}$${\displaystyle x=S+h(k)\in [S,S+1]}$${\displaystyle \lfloor d^{x}\rfloor }$${\displaystyle d}$${\displaystyle S}$${\displaystyle d}$

• 拡張可能なハッシュ
• 線形ハッシュ