データ構造におけるLCFSハッシング（後着優先方式）の仕組みと探索時間の評価式

LCFSハッシングとは

この記事では、LCFSハッシング（Last Come First Serve Hashing：後着優先ハッシング）について詳しく解説します。LCFSはオープンアドレス法（開番地法）の一種であり、従来の衝突解消の戦略を変更した興味深い手法です。

従来のオープンアドレス法との違い（FCFS方式）

オープンアドレス法によるハッシングのアルゴリズムを確認すると、2つの要素が衝突した場合、先に到着した要素がテーブルに保持され、後から来た要素は次の空き場所へ移動しなければなりません。つまり、通常のオープンアドレス法は「先着順（FCFS：First Come First Serve）」の基準で動作していると言えます。

LCFS方式の動作原理

LCFS（Last Come First Serve：後着優先）方式では、まったく逆の方法で処理が行われます。新しい要素を挿入する際、まず位置x₀への配置を試みます。その場所がすでに要素yによって占有されている場合（y_j = x₀ のとき）、既存の要素yを次の位置y_j+1へ移動させます。さらにその場所にも要素zが存在すれば、同様に押し出していく、という手順を繰り返します。つまり、最後に到着した要素が常に優先的に配置されるのがLCFS方式の特徴です。

期待探索時間の評価式

PobleteとMunroの研究によれば、空のテーブルにn個の要素を挿入した後の期待探索時間は、以下の式によって上界付けられることが示されています。

$$E[W]=1+\Gamma^{-1}(\alpha n)\lgroup 1+\frac{\ln\:\ln\:\frac{1}{1+\alpha}}{\ln\:\Gamma^{-1}(\alpha n)}+O(\frac{1}{\ln^{2}\:\Gamma^{2}(\alpha n)})\rgroup$$

ここで、Γはガンマ関数を表し、Γ^-1(αn)は次のように近似できます。

$$\Gamma^{-1}(\alpha n)=\frac{\ln\:n}{\ln\:\ln\:n}\lgroup 1+\frac{\ln\:\ln\:\ln\:n}{\ln\:\ln\:n}+O(\frac{1}{\ln\:\ln\:n})\rgroup$$

この結果から、LCFSハッシングは単純な後着優先という規則を採用するだけで、衝突連鎖の解析において理論的に優れた性質を持つことが分かります。