完全ハッシュ関数

コンピュータサイエンスにおいて、集合 $Sの$ 完全ハッシュ関数 $hは、$ 衝突なしに $S$ 内の異なる要素を $m$ 個の整数の集合にマッピングするハッシュ関数です。数学的には、これは単射関数です。

完全ハッシュ関数は、最悪の場合のアクセス時間が一定であるルックアップテーブルを実装するために使用できます。完全ハッシュ関数は、他のハッシュ関数と同様にハッシュテーブルを実装するために使用でき、衝突解決を実装する必要がないという利点があります。さらに、キーがデータ内に存在せず、照会されたキーが有効であることがわかっている場合は、キーをルックアップテーブルに格納する必要がないため、スペースを節約できます。

$完全ハッシュ関数の欠点は、完全ハッシュ関数の構築にはS$ を知る必要があることです。非動的完全ハッシュ関数は、 $S$ が変更された場合に再構築する必要があります。頻繁に変更される $Sの場合、追加のスペースを犠牲にして$ 動的完全ハッシュ関数を使用できます。^[1]完全ハッシュ関数を格納するために必要なスペースは $O (n)$ です。ここで、 $n$ は構造内のキーの数です。

完全なハッシュ関数の重要なパフォーマンスパラメータは、一定であるべき評価時間、構築時間、および表現サイズです。

応用

限定された範囲の値を持つ完全ハッシュ関数は、関数の出力によってインデックス付けされたルックアップテーブルに $S$ のキー（または他の関連値）を配置することで、効率的なルックアップ操作に使用できます。次に、キーが $S$ に存在するかどうかをテストするか、テーブルのセルでそのキーに関連付けられた値を検索します。このような各ルックアップには、最悪の場合でも一定の時間がかかります。^[2]完全ハッシュでは、テーブルへの1回のアクセスで関連データを読み書きできます。^[3]

完全ハッシュ関数の性能

完全ハッシュの重要な性能パラメータは、表現サイズ、評価時間、構築時間、および範囲要件（ハッシュテーブル内のキーあたりのバケットの平均数）である。^{[4]評価時間は} $O$ $($ $1$ $)$ ほど速く、これが最適である。^[2]^[4] $S$ の各要素を考慮する必要があり、 $Sには$ $n$ 個の要素が含まれるため、構築時間は少なくとも $O$ $($ $n$ $)$ である必要がある。この下限は実際には達成可能である。^[4] ${\frac {m}{n}}$

表現サイズの下限は $m$ と $nに依存する$ $。m = (1+ε) n$ とし、 $hを$ 完全ハッシュ関数とする。下限の近似値は要素あたりのビット数である。最小完全ハッシュの場合、 $ε = 0$ 、下限は要素あたり $log e \approx 1.44$ ビットである。^[4] $\log e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}$

工事

特定の集合 $S$ に対して定数時間で評価でき、値が狭い範囲にある完全なハッシュ関数は、S のサイズに比例する操作回数のランダム化アルゴリズムによって見つけることができます。 Fredman、Komlós、Szemerédi (1984) の元の構築では、2 レベルのスキームを使用して、 $n 個$ の要素の集合 $Sを$ $O$ $($ $n$ $)$ 個のインデックスの範囲にマッピングし、各インデックスをハッシュ値の範囲にマッピングします。構築の最初のレベルでは、大きな素数 $p ($ $S$ が抽出される宇宙のサイズよりも大きい) とパラメーター $k を$ 選択し、 $S$ の各要素 $x を$ インデックスにマッピングします。

g(x)=(kx{\bmod {p}}){\bmod {n}}.

$k$ がランダムに選択される場合、このステップでは衝突が発生する可能性がありますが、同じインデックス $iに同時にマッピングされる要素$ $n i$ の数は少なくなる可能性があります。構築の2番目のレベルでは、各インデックス $i$ に $O$ $($ $n$ $i$ $2$ $)個の整数の互いに素な範囲を割り当てます。これは、各インデックス$ $i$ に1つずつ、2番目の線形モジュラー関数セットを使用して、 $S$ の各メンバー $x を$ $g$ $($ $x$ $)$ に関連付けられた範囲にマッピングします。^[2]

Fredman、Komlós、Szemerédi (1984) が示すように、パラメータ $kの選択が存在し、$ $g$ $($ $x$ $)の$ $n$ 個の異なる値の範囲の長さの合計が $O$ $($ $n$ $)$ になります。さらに、 $g$ $($ $x$ $)の各値に対して、$ $S$ の対応するサブセットをその値に関連付けられた範囲にマッピングする線形モジュラー関数が存在します。 $kと$ $g$ $($ $x$ $)$ の各値に対する第 2 レベル関数は、有効な値が見つかるまでランダムに値を選択することにより、多項式時間で見つけることができます。 ^[2]

ハッシュ関数自体は、 $k$ 、 $p$ 、および第2レベルの線形モジュラー関数のすべてを格納するために $O (n)のストレージスペースを必要とします。与えられたキー$ $xのハッシュ値の計算は、$ $g$ $($ $x$ $)を計算し、$ $g$ $($ $x$ $)$ に関連付けられた第2レベルの関数を検索し、この関数を $x$ に適用することで、定数時間で実行できます。この2レベルスキームの修正版を使用して、トップレベルの値の数を増やすと、 $Sをより小さな長さ$ $n$ $+$ $o$ $($ $n$ $)$ の範囲にマッピングする完全なハッシュ関数を構築できます。^[2]

より最近の完全なハッシュ関数を構築する方法は、Belazzougui、Botelho、Dietzfelbinger (2009) によって「ハッシュ、置換、圧縮」として説明されています。ここでは、第 1 レベルのハッシュ関数 $gも使用して、要素を$ $r$ 個の整数の範囲にマッピングします。要素 $x \in S$ は、バケット $B g(x)$ に格納されます。^[4]

次に、サイズの降順で、各バケットの要素は、 $Φ$ $1$ から始まる一連の独立した完全ランダムハッシュ関数 $(Φ 1 、Φ 2 、Φ 3 、...)$ のハッシュ関数によってハッシュされます。ハッシュ関数がバケットに対して衝突を生成せず、結果の値が他のバケットの他の要素によってまだ占有されていない場合、その関数はそのバケットに対して選択されます。そうでない場合は、シーケンス内の次のハッシュ関数がテストされます。^[4]

完全なハッシュ関数 $h (x)$ を評価するには、バケットインデックス $g (x)$ のマッピングσをシーケンス内の正しいハッシュ関数に保存するだけでよく、結果は $h(x) = Φσ (g(x))$ となる。^[4]

最後に、表現サイズを縮小するために、 $σ(i) 0\leqi<rは$ $O (1)$ で評価できる形式に圧縮される。^[4]

$このアプローチでは、構築にn$ の線形時間と、一定の評価時間が必要です。表現サイズは $O (n)$ で、達成される範囲によって異なります。たとえば、 $m = 1.23 n$ の場合、Belazzougui、Botelho、Dietzfelbinger (2009) は、1000 万エントリの例セットに対して 3.03 ビット/キーから 1.40 ビット/キーの表現サイズを達成しました。値が小さいほど、計算時間が長くなります。このシナリオでのスペースの下限は 0.88 ビット/キーです。^[4]

擬似コード

 ハッシュ、ディスプレイス、圧縮 アルゴリズムは、 
(1) S をバケット $B i := g -1 ({i})\capS,0 \leq i < r に$ 分割し、 
(2) バケット B _{iをサイズ |B}_i |の降順でソートする。
（３）配列T[0...m-1]を0で初期化する
(4)すべてのi∈ [r]に対して 、(2)の順序で、l ← 1,2,...に対して
(5)     を実行する。  
（６）          K _i ← {  $Φ$ _l (x)|x ∈ B _i }の形成を繰り返す    
(6)          |K _i |=|B _i |かつK _i ∩{j|T[j]=1}= ∅となるまで 
（７）      σ（ｉ）を成功lとする
（８）     すべてのj∈K iに対してT[j]:= 1と_する     $(9) O$  $($  $1$  $)$ アクセスを維持しながら、 
(σi ₎ 0≤i _<rを圧縮形式に変換する。

スペース下限

$Fredman、Komlós、Szemerédi（1984）の関数を格納するためにO （ n ）$ ワードの情報を使用することはほぼ最適である。定数時間で計算できる完全なハッシュ関数は、少なくとも $S$ のサイズに比例するビット数を必要とする。^[5]

最小完全ハッシュ関数の情報理論的空間の下限は

\log _{2}e\approx 1.44

ビット/キー。^[4]

$完全ハッシュ関数の場合、まずhの範囲は$ $m$ $= (1+ε)$ $n$ で $n$ に制限されると仮定します。Belazzougui、Botelho、Dietzfelbinger (2009)によって与えられた式と、サイズ $|$ $U$ $| =$ $u$ が無限大に近づく宇宙の場合、空間の下限は $U\supseteq S$

\log _{2}e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}

ビット/キー、全体では $log(n)$ ビットを引いたもの。^[4]

拡張機能

メモリアドレスの識別

完全ハッシュの些細だが一般的な例は、コンピュータの（仮想）メモリアドレス空間に暗黙的に存在します。仮想メモリの各バイトは、別個で一意であり、直接アドレス指定可能なストレージ位置であるため、メモリ内の任意のオブジェクトが格納されている開始アドレスの値は、そのオブジェクトのメモリアドレス範囲全体への事実上の完全ハッシュと見なすことができます。^[6]

動的完全ハッシュ

$完全ハッシュ関数を使用するのは、頻繁にクエリされるがめったに更新されない大きなセットS$ がある場合に最適です。これは、セット $S$ を変更すると、ハッシュ関数が変更されたセットに対して完全ではなくなる可能性があるためです。セットが変更されるたびにハッシュ関数を更新するソリューションは、動的完全ハッシュと呼ばれますが、^[1]これらの方法は実装が比較的複雑です。

最小完全ハッシュ関数

最小完全ハッシュ関数は、 $n$ 個のキーを $n 個の連続する整数 (通常は$ $0$ から $n - 1$ または $1から$ $n$ までの数値)にマッピングする完全ハッシュ関数です。これをより正式に表現するには、次のようにします。 $j$ と $k を$ 有限集合 $S$ の要素とします。このとき、 $h$ $($ $j$ $) =$ $h$ $($ $k$ $)が$ $j$ $=$ $k$ (単射)を意味し、かつ $h$ の範囲が $a$ $..$ $a$ $+ |$ $S$ $| - 1$ となる整数 $a が$ 存在する場合のみ、 h は最小完全ハッシュ関数 $です$ 。汎用の最小完全ハッシュ方式では、少なくともビット/キーが必要であることが証明されています。^{[4] が}範囲の整数を含むサイズの集合であると仮定すると、空間ビットを使用し、定数評価時間をサポートする、からまでの明示的な最小完全ハッシュ関数を効率的に構築する方法が知られています。^[7]実際には、十分な時間が与えられれば、およそ 1.56 ビット/キーを使用する最小完全ハッシュ方式があります。^[8] $\log _{2}e\approx 1.44$ $S$ $n$ $[1,2^{o(n)}]$ $S$ $\{1,2,\ldots ,n\}$ $n\log_{2}e+o(n)$

k-完全ハッシュ

ハッシュ関数は、 $S$ の最大 $k$ 個の要素が範囲内の同じ値にマッピングされる場合、 $k完全です。「ハッシュ、置換、圧縮」アルゴリズムを使用すると、最大$ $k回の衝突を許可することで、$ $k$ 完全ハッシュ関数を構築できます。これを実現するために必要な変更は最小限で、以下の修正された擬似コードで下線が引かれています。

(4)すべてのi∈ [r]に対して 、(2)の順序で、l ← 1,2,...に対して
(5)     を実行する。  
（６）          K _i ← {  $Φ$ _l (x)|x ∈ B _i }の形成を繰り返す    
(6)          |K _i |=|B _i |かつK _i ∩{j| T[j]=k }= ∅となるまで 
（７）      σ（ｉ）を成功lとする
（８）     すべてのj∈K iに対してT[j]←T[j] +1_とする

秩序の維持

最小完全ハッシュ関数 $F$ は、キーが何らかの順序 $a 1 、 a 2 、 ...、 a n$ で与えられ、任意のキー $a j$ および $a k$ に対して、 $j < k$ であれば $F (a j) < F(a k)$ が成り立つ場合、順序保存型である。^[9]この場合、関数値は、すべてのキーのソート順序における各キーの位置である。アクセス時間が一定の順序保存型最小完全ハッシュ関数の簡単な実装は、（通常の）完全ハッシュ関数を使用して各キーの位置の参照テーブルを格納することである。このソリューションはビットを使用するため、キーの比較関数が任意である可能性がある設定では最適である。^[10]ただし、キー $a$ $1$ $、$ $a$ $2$ $、 ...、$ $a$ $n$ がユニバースから抽出された整数である場合、ビットのスペースのみを使用して順序保存型ハッシュ関数を構築することができる。^[11]さらに、この境界は最適であることが知られている。^[12] $O(n\log n)$ $\{1,2,\ldots ,U\}$ $O(n\log \log \log U)$

参考文献

^ ab ディーツフェルビンガー、マーティン;アンナ・カーリン;クルト州;マイヤー・アウフ・デア・ハイデ、フリードヘルム。ローナート、ハンス。Tarjan、Robert E. (1994)、「動的完全ハッシュ: 上限と下限」、SIAM Journal on Computing、23 (4): 738–761、doi :10.1137/S0097539791194094、MR 1283572。
^ abcde フレッドマン、マイケル L. ;コムロス, ヤーノス島; Szemerédi、Endre (1984)、「Storing a Sparse Table with $O$ $(1)$ Worst Case Access Time」、Journal of the ACM、31 (3): 538、doi : 10.1145/828.1884、MR 0819156、S2CID 5399743
^ Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006)、「ネットワークアプリケーションのための完全ハッシュ」、2006 IEEE 国際情報理論シンポジウム、pp. 2774–2778、doi :10.1109/ISIT.2006.261567、ISBN 1-4244-0505-X、S2CID 1494710
^ abcdefghijkl ベラゾウギ、ジャマル;ボテーリョ、ファビアーノ C. Dietzfelbinger、Martin (2009)、「Hash、displace、compress」(PDF)、Algorithms - ESA 2009 (PDF)、Lecture Notes in Computer Science、vol. 5757、ベルリン: Springer、682–693 ページ、CiteSeerX 10.1.1.568.130、doi :10.1007/978-3-642-04128-0_61、ISBN 978-3-642-04127-3、MR 2557794。
^ Fredman, Michael L. ; Komlós, János (1984)、「分離システムのサイズと完全ハッシュ関数のファミリについて」、SIAM Journal on Algebraic and Discrete Methods、5 (1): 61–68、doi :10.1137/0605009、MR 0731857。
^ Witold Litwin、Tadeusz Morzy、Gottfried Vossen (1998 年 8 月 19 日)。データベースと情報システムの進歩。Springer Science+Business Media。p . 254。ISBN 9783540649243。
^ Hagerup, Torben; Tholey, Torsten (2001)、「ほぼ最小空間での効率的な最小完全ハッシュ」、STACS 2001、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp. 317–326、doi：10.1007/3-540-44693-1_28、ISBN 978-3-540-41695-1、 2023-11-12取得
^ Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020)、「RecSplit: 再帰分割による最小完全ハッシュ」、2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)、Proceedings、pp. 175–185、arXiv : 1910.06416、doi : 10.1137/1.9781611976007.14。
^ Jenkins, Bob (2009 年 4 月 14 日)、「order-preserving minimal perfect hashing」、Black, Paul E. (ed.)、Dictionary of Algorithms and Data Structures、米国国立標準技術研究所、 2013 年 3 月 5 日取得
^ Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (1991 年 7 月)、「順序保存型最小完全ハッシュ関数と情報検索」(PDF)、ACM Transactions on Information Systems、9 (3)、ニューヨーク、NY、米国: ACM: 281–308、doi :10.1145/125187.125200、S2CID 53239140。
^ Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus ; Vigna, Sebastiano (2008 年 11 月)、「モノトーン最小完全ハッシュの理論と実践」、Journal of Experimental Algorithmics、16、Art. no. 3.2、26pp、doi :10.1145/1963190.2025378、S2CID 2367401。
^ Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (2023年1月)、「Tight Bounds for Monotone Minimal Perfect Hashing」、2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) の議事録、フィラデルフィア、ペンシルバニア州: Society for Industrial and Applied Mathematics、pp. 456–476、arXiv : 2207.10556、doi :10.1137/1.9781611977554.ch20、ISBN 978-1-61197-755-4、2023-04-27取得
^ ab Timothy A. Davis. 「第 5 章ハッシュ」: サブセクション「最悪の場合の O(1) アクセスのハッシュテーブル」
^ ラスムス・パーグ; Rodler、Flemming Friche (2004)、「Cuckoo hashing」、Journal of Algorithms、51 (2): 122–144、doi :10.1016/j.jalgor.2003.12.002、MR 2050140。

さらに読む

Richard J. Cichelli. Minimal Perfect Hash Functions Made Simple、Communications of the ACM、Vol. 23、No. 1、1980 年 1 月。
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第3版。MIT Press、2009年。ISBN 978-0262033848。セクション11.5：完全ハッシュ、pp. 267、277–282 。
ファビアーノ・C・ボテーリョ、ラスムス・パーグ、ニヴィオ・ジビアーニ。「データ管理アプリケーションに最適なハッシュ」。
ファビアーノ・C・ボテーリョとニヴィオ・ジビアーニ。「非常に大きなキーセットに対する外部完全ハッシュ」。第 16 回情報および知識管理に関する ACM 会議 (CIKM07)、ポルトガル、リスボン、2007 年 11 月。
Djamal Belazzougui、Paolo Boldi、Rasmus Pagh、Sebastiano Vigna。「単調な最小完全ハッシュ: O(1) アクセスによるソート済みテーブルの検索」。第 20 回 ACM-SIAM 離散数学シンポジウム (SODA) の議事録、ニューヨーク、2009 年。ACM プレス。
Marshall D. Brain および Alan L. Tharp。「大規模ワードセットのほぼ完璧なハッシュ」。ソフトウェア - 実践と経験、第 19 巻 (10)、967-078、1989 年 10 月。John Wiley & Sons。
Douglas C. Schmidt、「GPERF: 完全なハッシュ関数ジェネレーター」、C++ レポート、SIGS、第 10 巻、第 10 号、1998 年 11 月/12 月。

外部リンク

gperf はオープンソースのC および C++ の完全ハッシュジェネレータです (非常に高速ですが、小さなセットでしか動作しません)
ボブ・ジェンキンスによる最小完全ハッシュ（ボブアルゴリズム）
cmph: C 最小完全ハッシュライブラリ、多数の (最小) 完全ハッシュのオープンソース実装 (大きなセットでも機能)
Sux4J: Java のオープンソースのモノトーン最小完全ハッシュ
MPHSharp: C# での完璧なハッシュメソッド
BBHash: ヘッダーのみの C++ での最小完全ハッシュ関数
Perfect::Hash は、C コードを作成する Perl の完璧なハッシュジェネレータです。一見の価値がある「先行技術」セクションがあります。

[DynamicPerfectHashing-1] ディーツフェルビンガー、マーティン;アンナ・カーリン;クルト州;マイヤー・アウフ・デア・ハイデ、フリードヘルム。ローナート、ハンス。Tarjan、Robert E. (1994)、「動的完全ハッシュ: 上限と下限」、SIAM Journal on Computing、23 (4): 738–761、doi :10.1137/S0097539791194094、MR 1283572。

[inventor-2] フレッドマン、マイケル L. ;コムロス, ヤーノス島; Szemerédi、Endre (1984)、「Storing a Sparse Table with $O$ $(1)$ Worst Case Access Time」、Journal of the ACM、31 (3): 538、doi : 10.1145/828.1884、MR 0819156、S2CID 5399743

[3] Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006)、「ネットワークアプリケーションのための完全ハッシュ」、2006 IEEE 国際情報理論シンポジウム、pp. 2774–2778、doi :10.1109/ISIT.2006.261567、ISBN 1-4244-0505-X、S2CID 1494710

[CHD-4] ベラゾウギ、ジャマル;ボテーリョ、ファビアーノ C. Dietzfelbinger、Martin (2009)、「Hash、displace、compress」(PDF)、Algorithms - ESA 2009 (PDF)、Lecture Notes in Computer Science、vol. 5757、ベルリン: Springer、682–693 ページ、CiteSeerX 10.1.1.568.130、doi :10.1007/978-3-642-04128-0_61、ISBN 978-3-642-04127-3、MR 2557794。

[5] Fredman, Michael L. ; Komlós, János (1984)、「分離システムのサイズと完全ハッシュ関数のファミリについて」、SIAM Journal on Algebraic and Discrete Methods、5 (1): 61–68、doi :10.1137/0605009、MR 0731857。

[6] Witold Litwin、Tadeusz Morzy、Gottfried Vossen (1998 年 8 月 19 日)。データベースと情報システムの進歩。Springer Science+Business Media。p . 254。ISBN 9783540649243。

[7] Hagerup, Torben; Tholey, Torsten (2001)、「ほぼ最小空間での効率的な最小完全ハッシュ」、STACS 2001、ベルリン、ハイデルベルク：Springer Berlin Heidelberg、pp. 317–326、doi：10.1007/3-540-44693-1_28、ISBN 978-3-540-41695-1、 2023-11-12取得

[RecSplit-8] Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020)、「RecSplit: 再帰分割による最小完全ハッシュ」、2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)、Proceedings、pp. 175–185、arXiv : 1910.06416、doi : 10.1137/1.9781611976007.14。

[9] Jenkins, Bob (2009 年 4 月 14 日)、「order-preserving minimal perfect hashing」、Black, Paul E. (ed.)、Dictionary of Algorithms and Data Structures、米国国立標準技術研究所、 2013 年 3 月 5 日取得

[10] Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (1991 年 7 月)、「順序保存型最小完全ハッシュ関数と情報検索」(PDF)、ACM Transactions on Information Systems、9 (3)、ニューヨーク、NY、米国: ACM: 281–308、doi :10.1145/125187.125200、S2CID 53239140。

[11] Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus ; Vigna, Sebastiano (2008 年 11 月)、「モノトーン最小完全ハッシュの理論と実践」、Journal of Experimental Algorithmics、16、Art. no. 3.2、26pp、doi :10.1145/1963190.2025378、S2CID 2367401。

[12] Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (2023年1月)、「Tight Bounds for Monotone Minimal Perfect Hashing」、2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) の議事録、フィラデルフィア、ペンシルバニア州: Society for Industrial and Applied Mathematics、pp. 456–476、arXiv : 2207.10556、doi :10.1137/1.9781611977554.ch20、ISBN 978-1-61197-755-4、2023-04-27取得

[davis-13] Timothy A. Davis. 「第 5 章ハッシュ」: サブセクション「最悪の場合の O(1) アクセスのハッシュテーブル」

[14] ラスムス・パーグ; Rodler、Flemming Friche (2004)、「Cuckoo hashing」、Journal of Algorithms、51 (2): 122–144、doi :10.1016/j.jalgor.2003.12.002、MR 2050140。

応用