線形ハッシュ

線形ハッシュ( LH ) は、ハッシュ テーブルを実装し、一度に 1 つのバケットを拡大または縮小する動的データ構造です。1980 年に Witold Litwin によって発明されました^{。[1] [2]} Baeza-Yates と Soza-Pollman によって分析されました。^[3]これは、Larson の部分拡張による線形ハッシュ、[ ^5]優先度分割による線形ハッシュ、 [ ^6]部分拡張と優先度分割による線形ハッシュ、^{[7]または再帰線形ハッシュなど、動的ハッシュ[3] [4]}として知られるいくつかの方式の最初のもの^です。

動的ハッシュデータ構造のファイル構造は、ファイルサイズの変化に適応するため、コストのかかる定期的なファイル再編成は避けられます。^[4]リニアハッシュファイルは、所定のバケットを 2 つに分割することで拡張し、所定の 2 つのバケットを 1 つにマージすることで縮小します。再構築のトリガーはスキームの種類によって異なります。バケットのオーバーフローや、所定の範囲外への負荷係数(レコード数をバケット数で割った値) がトリガーとなる場合があります。^[1]リニアハッシュには、分割されるバケットとすでに分割されているバケットの 2 種類があります。拡張可能ハッシュはオーバーフローしたバケットのみを分割しますが、スパイラルハッシュ(別名スパイラルストレージ) は、挿入、削除、または取得のコストが高いバケットが最初に分割されるように、レコードをバケットに不均等に分散します。^[5]

線形ハッシュは、スケーラブルな分散データ構造であるLH*にも組み込まれています。LH*では、各バケットは異なるサーバーに存在します。^[9] LH*自体は、バケットに障害が発生した場合でもデータの可用性を提供できるように拡張されています。^[10] LHとLH*でのキーベースの操作（挿入、削除、更新、読み取り）は、バケットの数、つまりレコードの数に関係なく、最大で一定の時間がかかります。^{[1] [10]}

LH または LH* のレコードはキーとコンテンツで構成され、後者は基本的にレコードの他のすべての属性です。^{[1] [10]} これらはバケットに格納されます。たとえば、Ellis の実装では、バケットはレコードのリンク リストです。^[2]ファイルでは、キー ベースの CRUD 操作 (作成または挿入、読み取り、更新、削除) と、すべてのレコードをスキャンするスキャン操作 (たとえば、キー以外の属性に対するデータベース選択操作) が可能です。^[10]レコードは、番号が 0 から始まるバケットに格納されます。^[10]

フェイギンの拡張可能ハッシュなどの方式との主な違いは、挿入によりファイルが拡張されても、一度に1つのバケットのみが分割され、バケットが分割される順序がすでに決定されていることです。^[11]

ハッシュ関数は、キー を持つレコードを含むバケットの 0 ベースのインデックスを返します。ハッシュ関数を使用するバケットが2 つの新しいバケットに分割されると、ハッシュ関数は両方の新しいバケットで に置き換えられます。常に、最大 2 つのハッシュ関数と が使用されます。つまり、 は現在のレベルに対応します。ハッシュ関数のファミリは、動的ハッシュ関数とも呼ばれます。 ${\displaystyle h_{i}(c)}$${\displaystyle c}$${\displaystyle h_{i}}$${\displaystyle h_{i}}$${\displaystyle h_{i+1}}$${\displaystyle h_{l}}$${\displaystyle h_{l+1}}$${\displaystyle l}$${\displaystyle h_{i}(c)}$

通常、のの値は、バケットを分離するために使用されるキーの右端の 2 進桁の数に対応します。この動的ハッシュ関数は、算術的に と表すことができます。バケットの合計数が 1 に等しい場合、 であることに注意してください。 ${\displaystyle i}$${\displaystyle h_{i}}$${\displaystyle c}$${\textstyle h_{i}(c)\mapsto (c{\bmod {2}}^{i})}$${\displaystyle i=0}$

以下の計算を実行して、与えられたハッシュキーの正しいハッシュ関数を決定します。^[10]${\displaystyle c}$

# l は現在のレベルを表します
# s は分割ポインタのインデックスを表します
a  =  h_l ( c ) 
if  ( a  <  s ):  a  =  h_ { l + 1 }( c )

線形ハッシュ アルゴリズムでは、制御された分割のみを使用することも、制御された分割と制御されていない分割の両方を使用することもできます。

制御された分割は、ファイルによって監視される負荷係数が所定のしきい値を超えるたびに分割が実行される場合に発生します。 ^[10]ハッシュインデックスが制御された分割を使用する場合、リンクされたオーバーフローブロックを使用してバケットをオーバーフローできます。負荷係数が設定されたしきい値を超えると、分割ポインターの指定されたバケットが分割されます。負荷係数を使用する代わりに、このしきい値は占有率として表現することもできます。その場合、ハッシュインデックスの最大レコード数は、(占有率)*(オーバーフローしないバケットあたりの最大レコード数)*(バケット数)に等しくなります。^[12]

制御されていない分割は、バケットがオーバーフローするたびに分割が実行され、そのバケットが 2 つの別々のバケットに分割されるときに発生します。

一部のLHアルゴリズム実装では、制御された分割によって負荷係数がしきい値を下回った場合にファイル縮小が発生します。この場合、マージ操作がトリガーされ、最後の分割が元に戻され、ファイル状態がリセットされます。^[10]

次に分割されるバケットのインデックスはファイル状態の一部であり、分割ポインタ と呼ばれます。分割ポインタは、の代わりにハッシュ関数を使用する最初のバケットに対応します。^[10]${\displaystyle s}$${\displaystyle h_{l}}$${\displaystyle h_{l+1}}$

たとえば、数値レコードがハッシュインデックスに右端の2進数に従って挿入されると、追加されたバケットに対応するバケットが分割されます。したがって、バケットに000、001、10、11、100、101というラベルが付いている場合、次の連続バケット110を追加して作成するため、バケット10を分割します。これにより、バケット000、001、010、11、100、101、110が得られます。^[12]

バケットが分割されると、分割ポインタとレベルが次のように更新され、線形ハッシュインデックスにバケットが1つしかない場合はレベルが0になります。^[10]

# l は現在のレベルを表します
# s は分割ポインターのインデックスを表します
s  =  s  +  1 
if  ( s  >=  2 ^ l ):  
    l  =  l  +  1 
    s  =  0

LH* の主な貢献は、LH* ファイルのクライアントが、ファイルの状態を知らない場合でも、レコードが存在するバケットを見つけられるようにすることです。クライアントは実際には、ファイル状態の自分のバージョンを保存します。これは、最初は最初のバケット、つまりバケット 0 の知識にすぎません。クライアントは、ファイル状態に基づいてキーのアドレスを計算し、そのバケットに要求を送信します。バケットで要求がチェックされ、レコードがバケットにない場合は転送されます。適度に安定したシステム、つまり、要求の処理中に 1 つの分割または結合のみが行われているシステムでは、最大 2 回の転送があることがわかります。転送後、最後のバケットは、分散ファイルの状態に近づいた状態になったクライアントにイメージ調整メッセージを送信します。^[10] アクティブなクライアントでは転送がかなりまれですが、サーバーとクライアント間の追加情報交換によって、その数をさらに減らすことができます^[13]

ファイル状態は分割ポインタとレベルから構成される。元のファイルがバケットで始まっていた場合、バケットの数とファイル状態は ^{[13]によって関連付けられる。}${\displaystyle s}$${\displaystyle l}$${\displaystyle N=1}$${\displaystyle n}$

${\displaystyle n=2^{l}+s}$。

GriswoldとTownsend ^[14]はIcon言語における線形ハッシュの採用について議論した。彼らは線形ハッシュで使用される動的配列アルゴリズムの実装の代替案について議論し、Iconベンチマークアプリケーションのリストを使用してパフォーマンス比較を提示した。

線形ハッシュはBerkeley データベース システム (BDB)で使用されており、 CACM の記事から派生し、1988 年に Esmond Pitt によって Usenet で初めて公開された C 実装を使用して、多くのソフトウェア システムで使用されています。

• TommyDS、線形ハッシュテーブルの C 実装
• 説明付きのメモリ内 Go 実装
• ファイルシステムとメモリ内ストレージの両方をサポートする線形ハッシュテーブルの C++ 実装

• 拡張可能なハッシュ
• 一貫性のあるハッシュ
• スパイラルハッシュ