ハッシュテーブル

コンピュータサイエンスにおいて、ハッシュテーブルは連想配列（辞書または単にマップとも呼ばれる）を実装するデータ構造です。連想配列はキーを値にマッピングする抽象データ型です。^[3]ハッシュテーブルはハッシュ関数を使用して、バケットまたはスロットの配列のインデックス（ハッシュコードとも呼ばれる）を計算し、そこから目的の値を見つけることができます。検索中にキーがハッシュされ、結果のハッシュは対応する値が格納されている場所を示します。ハッシュテーブルによって実装されたマップはハッシュマップと呼ばれます。

ほとんどのハッシュテーブル設計では、不完全なハッシュ関数が採用されています。ハッシュ関数が複数のキーに対して同じインデックスを生成するハッシュ衝突（ハッシュ衝突）は、通常何らかの方法で対処する必要があります。ハッシュ衝突に対処するための一般的な戦略としては、リンクリストを用いて複数の要素を同じスロットに格納するチェーニングや、プローブシーケンスに従って次の利用可能なスロットを検索するオープンアドレッシングなどがあります。^[4]

適切に次元化されたハッシュテーブルでは、各検索の平均時間計算量はテーブルに格納されている要素数に依存しません。多くのハッシュテーブル設計では、キーと値のペアの任意の挿入と削除も許可されており、その平均コストは操作ごとに償却定数です。 ^[5]^[4]^{: 513–558}^[6]

ハッシュは空間と時間のトレードオフの一例です。メモリが無限であれば、キー全体をインデックスとして直接使用し、1回のメモリアクセスでその値を検索できます。一方、処理時間が無限であれば、キーに関係なく値を保存し、二分探索または線形探索を使用して要素を取得できます。^[7]^{: 458}

多くの場合、ハッシュテーブルは平均して探索木やその他のテーブル検索構造よりも効率的であることが判明しています。ハッシュテーブルは、平均的なパフォーマンスが高速であるため、データベースのインデックス作成、キャッシュ、連想配列の実装などのタスクに、現代のソフトウェアシステムで広く使用されています。^[8]このため、ハッシュテーブルは多くの種類のコンピュータソフトウェア、特に連想配列、データベースのインデックス作成、キャッシュ、セットで広く使用されています。多くのプログラミング言語は、Pythonの辞書、JavaのHashMap、C++のunordered_mapなど、ハッシュの複雑さをプログラマから抽象化する組み込みのハッシュテーブル構造を提供しています。^[9]

歴史

ハッシュの概念は、それぞれ異なる場所で独立して生まれました。1953年1月、ハンス・ピーター・ルーンは、連鎖を用いたハッシュ法を用いた IBM社内メモを作成しました。オープン・アドレッシングの最初の例は、ルーンのメモを基に、AD・リンによって提案されました。^[4]^{: 547}ほぼ同時期に、IBMリサーチのジーン・アムダール、エレイン・M・マグロウ、ナサニエル・ロチェスター、アーサー・サミュエルは、 IBM 701 アセンブラにハッシュ法を実装しました。^[10]^{: 124}線形プローブを用いたオープン・アドレッシングはアムダールによるものとされていますが、アンドレイ・エルショフも独立して同じアイデアを考案していました。^[10]^{: 124–125}「オープン・アドレッシング」という用語は、W・ウェズリー・ピーターソンが大規模ファイルの検索問題を論じた論文の中で造語しました。^[11]^{: 15}

連鎖ハッシュ法に関する最初の論文は、素数を法とする剰余をハッシュ関数として用いるというアイデアを論じたアーノルド・デュメイによるものとされている。 ^[11]^{: 15}「ハッシュ」という言葉は、ロバート・モリスの記事で初めて発表された。^[10]^{: 126}線形プロービングの理論的分析は、コンハイムとワイスによって最初に提出された。^[11]^{: 15}

概要

連想配列は、キーと値のペアの集合を格納し、一意のキーという制約のもとで、挿入、削除、および検索（探索）が可能です。連想配列のハッシュテーブル実装では、長さの配列の一部に要素が格納されます（）。キーはハッシュ関数を用いてハッシュされ、ハッシュテーブル内のインデックス位置が計算されます（）。ハッシュテーブルの効率は負荷係数に依存します。負荷係数は、格納されている要素数と利用可能なスロット数の比として定義され、負荷係数が低いほど一般に操作が高速になります。^[12]このインデックスには、キーとそれに関連付けられた値の両方が格納されます。キーを値と一緒に格納することで、衝突が発生した場合でも、検索時にインデックスのキーを検証して正しい値を取得できます。妥当な仮定の下では、ハッシュテーブルは、自己平衡型二分探索木と比較して、検索、削除、および挿入操作の時間計算量の境界が優れています。^[11]^{: 1} $A$ $m$ $n$ $m\geq n$ $x$ $h$ $A[h(x)]$ $h(x)<m$

ハッシュテーブルは、各キーの格納値を省略し、キーが存在するかどうかのみを追跡することで、セットを実装するためにもよく使用されます。^[11]^{: 1}

荷重係数

負荷係数はハッシュテーブルの重要な統計量であり、次のように定義される： [ ^2] $\alpha$ ${\text{荷重係数}}\ (\alpha )={\frac {n}{m}},$

$n$ ハッシュテーブルで占有されるエントリの数です。
$m$ バケットの数です。

ハッシュテーブルのパフォーマンスは負荷係数に比例して低下します。^[11]^{: 2}およびが大きい限界では、各バケットは統計的にポアソン分布を持ち、理想的にはランダムなハッシュ関数が期待されます。 $\alpha$ $m$ $n$ $\lambda =\alpha$

ソフトウェアは通常、負荷係数が一定の定数未満に維持されるようにします。これは良好なパフォーマンスの維持に役立ちます。そのため、一般的なアプローチは、負荷係数がに達するたびにハッシュテーブルのサイズを変更、つまり「再ハッシュ」することです。同様に、負荷係数がを下回った場合にも、テーブルのサイズが変更されることがあります。^[13] $\alpha$ $\alpha _{\max}$ $\alpha$ $\alpha _{\max}$ $\alpha _{\max}/4$

個別連鎖の負荷係数

独立した連鎖ハッシュテーブルでは、バケット配列の各スロットにデータのリストまたは配列へのポインタが格納されます。^[14]

分離連鎖ハッシュテーブルは、負荷係数が増加するにつれて徐々にパフォーマンスが低下し、サイズ変更が絶対に必要となる固定ポイントはありません。^[13]

別々の連鎖では、最良のパフォーマンスが得られる値は通常1から3の間です。^[13] $\alpha _{\max}$

オープンアドレスの負荷係数

オープンアドレス方式では、バケット配列の各スロットには正確に1つの項目が保持されます。したがって、オープンアドレス方式のハッシュテーブルでは、負荷係数は1を超えることはできません。^[14]

負荷係数が1に近づくと、オープンアドレスのパフォーマンスは非常に悪くなります。^[13]

したがって、オープンアドレスを使用するハッシュテーブルは、負荷係数が1に近づくと、サイズを変更するか、再ハッシュする必要があります^。[13] $\alpha$

オープンアドレス方式の場合、許容される最大負荷係数の数値は0.6～0.75程度の範囲となる。^[15]^[16]^{: 110} $\alpha _{\max}$

ハッシュ関数

ハッシュ関数は、キーの集合をテーブル内のインデックスまたはスロットにマッピングします。つまり、に対してとなります。ハッシュ関数の従来の実装は、テーブルのすべての要素がから派生するという整数集合の仮定に基づいています。この場合、のビット長はコンピュータアーキテクチャのワードサイズ内に制限されます。^[11]^{: 2} $h:U\rightarrow \{0,...,m-1\}$ $U$ $h(x)\in \{0,...,m-1\}$ $x\in U$ $U=\{0,...,u-1\}$ $u$

ハッシュ関数が与えられた集合に対して完全であるとは、それがに対して単射的である場合、つまり各要素が内の異なる値にマッピングされる場合を言う。^[17]^[18]完全なハッシュ関数は、すべてのキーが事前にわかっている場合に作成できる。^[17] $h$ $S$ $S$ $x\in S$ ${0,...,m-1}$

整数宇宙仮定

整数宇宙仮定で使用されるハッシュ方式には、除算によるハッシュ、乗算によるハッシュ、ユニバーサルハッシュ、動的完全ハッシュ、静的完全ハッシュなどがあります。^[11]^：2ただし、除算によるハッシュが一般的に使用される方式です。^[19]^：264^[16]^：110

分割によるハッシュ

分割によるハッシュのスキームは次のとおりです: ^[11]^{: 2} ここではハッシュ値であり、はテーブルのサイズです。 $h(x)\ =\ x\,{\bmod {\,}}m,$ $h(x)$ $x\in S$ $m$

乗算によるハッシュ

乗算によるハッシュ法のスキームは以下のとおりです。^[11]^{: 2–3} ここで、は非整数の実数値定数、はテーブルのサイズです。乗算によるハッシュ法の利点は、が重要ではないことです。^[11]^{: 2–3}任意の値でハッシュ関数が生成されますが、ドナルド・クヌースは黄金比を使用することを提案しています。^[11]^{: 3} $h(x)=\lfloor m{\bigl (}(xA){\bmod {1}}{\bigr )}\rfloor$ $A$ $m$ $m$ $A$

文字列ハッシュ

一般的に、文字列はハッシュ関数のキーとして使用されます。Stroustrup ^[20]は、初期値がゼロである符号なし整数を1ビットずつ左シフトし、次の文字の整数値と排他的論理和をとる単純なハッシュ関数を説明しています。このハッシュ値は、テーブルサイズを法として求められます。左シフトが循環的でない場合、文字列の長さは符号なし整数のビット数よりも少なくとも8ビット短くなります。文字列を整数にハッシュするもう1つの一般的な方法は、多項式ローリングハッシュ関数を使用することです。

ハッシュ関数の選択

ハッシュ値の均一分布は、ハッシュ関数の基本要件です。不均一分布は衝突回数と衝突解決コストを増加させます。均一性は設計上保証することが困難な場合もありますが、統計的検定、例えば離散均一分布に対するピアソンのカイ二乗検定を用いて経験的に評価することができます。^[21]^[22]

分布は、アプリケーションで発生するテーブルサイズに対してのみ均一である必要があります。特に、テーブルサイズを正確に2倍または半分にする動的なサイズ変更を使用する場合、ハッシュ関数はサイズが2のべき乗の場合にのみ均一である必要があります。この場合、インデックスはハッシュ関数のビット範囲として計算できます。一方、一部のハッシュアルゴリズムでは、サイズを素数にすることが推奨されます。^[23]

オープンアドレス方式の場合、ハッシュ関数はクラスタリング（2つ以上のキーを連続するスロットにマッピングすること）も回避する必要があります。このようなクラスタリングは、負荷係数が低く衝突がまれであっても、検索コストを急上昇させる可能性があります。一般的な乗法ハッシュは、特にクラスタリング挙動が悪いと言われています。^[23]^[4]

K独立ハッシュ法は、特定のハッシュ関数が特定のハッシュテーブルに対して不正なキーセットを持たないことを証明する方法を提供します。線形プロービングやカッコウハッシュ法といった衝突解決スキームにおいて、K独立性の結果は数多く知られています。K独立性はハッシュ関数が機能することを証明できるため、そのようなハッシュ関数を可能な限り高速に見つけることに集中できます。^[24]

衝突解決

ハッシュを用いた検索アルゴリズムは2つの部分から構成されます。最初の部分は、検索キーを配列インデックスに変換するハッシュ関数の計算です。理想的なケースでは、2つの検索キーが同じ配列インデックスにハッシュされることはまずありません。しかし、これは常に当てはまるとは限らず、未知のデータに対しては保証できません。^[4]^{: 515}したがって、アルゴリズムの2番目の部分は衝突解決です。衝突解決には、セパレートチェイニングとオープンアドレッシングという2つの一般的な方法があります。^[7]^{: 458}

分離連鎖

分離連鎖法では、各検索配列のインデックスに対応するキーと値のペアを持つ連結リストを構築する。衝突した項目は単一の連結リストを介して連結され、このリストを走査することで、一意の検索キーを持つ項目にアクセスできる。 ^[7]^{: 464}連結リストを用いた連鎖法による衝突解決は、ハッシュテーブルの実装において一般的な方法である。ハッシュテーブルを、ノードをとすると、操作は以下のようになる。^[19]^{: 258} $T$ $x$

Chained-Hash-Insert( T , k )
  はリンクリストT [ h ( k )]の先頭にxを挿入する。   

連鎖ハッシュ検索( T , k )
  は、リンクリストT [ h ( k )]内のキーkを持つ要素を検索する。   

Chained-Hash-Delete( T , k ) は
  リンクリストT [ h ( k )]
からxを削除します。

要素が数値的または語彙的に比較可能であり、全体の順序を維持してリストに挿入された場合、失敗した検索の終了が速くなります。^[4]^：520–521

個別連鎖のためのその他のデータ構造

キーがの順序付けされている場合、自己バランス二分探索木などの「自己組織化」概念を使用すると効率的である可能性があり、これにより理論上の最悪ケースをまで下げることができるが、追加の複雑さが導入される。^[4]^{: 521} $O(\log {n})$

動的完全ハッシュ法では、2階層のハッシュテーブルを用いて、最悪の場合でも検索の複雑さが保証されるようにする。この手法では、エントリのバケットは、スロットを含む完全ハッシュテーブルとして編成され、最悪の場合でも検索時間が一定となり、挿入の償却時間が短くなる。^[25]ある研究によると、高負荷環境下において、配列ベースの分離連鎖法は標準的なリンクリスト法と比較して97%も性能が向上することが分かっている。^[26]^{: 99} $O(1)$ $k$ $k^{2}$

各バケットに融合ツリーを使用するなどの手法も、高い確率ですべての操作に一定の時間をもたらします。^[27]

キャッシュと参照の局所性

分離連鎖実装のリンクリストは、リンクリストのノードがメモリ上に散在している場合、空間的局所性（参照の局所性）のためにキャッシュを意識しない可能性があり、挿入および検索中のリストの走査によってCPUキャッシュの非効率性が生じる可能性があります。^[26]^{: 91}

キャッシュを考慮した分離連鎖による衝突解決の変種では、通常はリンクリストや自己バランス型二分探索木が使用される場所で、よりキャッシュフレンドリーであることが判明した動的配列が使用されます。これは、配列の連続した割り当てパターンが、ハードウェアキャッシュプリフェッチャー（例えば、トランスレーションルックアサイドバッファ）によって利用され、アクセス時間とメモリ消費を削減できるためです。^[28]^[29]^[30]

オープンアドレス

オープンアドレッシングは、別の衝突解決手法であり、すべてのエントリレコードがバケット配列自体に格納され、ハッシュ解決はプロービングによって実行されます。新しいエントリを挿入する必要がある場合、バケットはハッシュ先のスロットから始まり、プローブシーケンスに従って、空いているスロットが見つかるまで検査されます。エントリを検索する場合、バケットは同じシーケンスでスキャンされ、目的のレコードが見つかるか、未使用の配列スロットが見つかるまでスキャンされます。未使用の配列スロットが見つかると、検索は失敗となります。^[31]

よく知られているプローブ配列には以下のものがあります。

線形プロービングでは、プローブ間の間隔は固定されています（通常1）。^[32]
二次プロービングでは、二次多項式の連続出力を元のハッシュ計算によって与えられた値に追加することで、プローブ間の間隔が増加します。^[33]^{: 272}
二重ハッシュ法では、プローブ間の間隔は二次ハッシュ関数によって計算されます。^[33]^{: 272–273}

オープンアドレッシングは、負荷係数が1に近づくとプローブシーケンスが増加するため、セパレートチェーニングに比べてパフォーマンスが低下する可能性がある。 ^[13]^[26]^{: 93}負荷係数が1に達すると、テーブルが完全に埋められている場合、プローブは無限ループに陥る。 ^[7]^{: 471}線形プローブの平均コストは、クラスタリングを避けるために要素をテーブル全体に均一に分散させるハッシュ関数の能力に依存する。クラスタが形成されると検索時間が長くなるためである。^[7]^{: 472} $\alpha$

キャッシュと参照の局所性

スロットは連続した場所に配置されているため、線形プローブは参照の局所性によりCPUキャッシュの利用率を向上させ、メモリレイテンシを削減することができる。^[32]

オープンアドレスに基づくその他の衝突解決技術

合体ハッシュ

合体ハッシュは、バケットまたはノードがテーブル内でリンクする、セパレートチェイニングとオープンアドレッシングの両方を組み合わせたものです。^[34]^{: 6–8}このアルゴリズムは固定メモリ割り当てに最適です。^[34]^{: 4}合体ハッシュにおける衝突は、ハッシュテーブル上で最大のインデックスを持つ空きスロットを特定することで解決され、衝突した値はそのスロットに挿入されます。バケットは、衝突したハッシュアドレスを含む挿入されたノードのスロットにもリンクされます。^[34]^{: 8}

カッコウハッシュ

カッコウハッシュ法は、オープンアドレス衝突解決手法の一種であり、最悪のケースにおける検索複雑度と挿入処理における一定の償却時間を保証する。衝突は、それぞれ独自のハッシュ関数を持つ2つのハッシュテーブルを維持することで解決され、衝突したスロットは指定された項目に置き換えられ、そのスロットの占有されていた要素は別のハッシュテーブルに移動される。この処理は、すべてのキーがテーブルの空のバケットに独自の場所を確保するまで継続される。もしこの処理が無限ループに入った場合（閾値ループカウンタを維持することで識別される）、両方のハッシュテーブルは新しいハッシュ関数で再ハッシュされ、処理は継続される。^[35]^{: 124–125} $O(1)$

ホップスコッチハッシュ

ホップスコッチハッシュは、オープンアドレスベースのアルゴリズムであり、カッコウハッシュ、線形プローブ、チェイニングの要素を、バケットの近傍（占有されている特定のバケットの周囲の後続のバケット、いわゆる「仮想」バケット）の概念に基づいて組み合わせています。 ^[36]^{: 351–352}このアルゴリズムは、ハッシュテーブルの負荷率が90%を超えた場合に優れたパフォーマンスを発揮するように設計されています。また、並列処理設定においても高いスループットを提供するため、サイズ変更可能な並列ハッシュテーブルの実装に適しています。^[36]^{: 350}ホップスコッチハッシュの近傍特性は、近傍内の任意のバケットから目的のアイテムを見つけるコストが、バケット自体からそのアイテムを見つけるコストに非常に近いという特性を保証します。アルゴリズムは、他のアイテムを置き換えるコストが発生する可能性はありますが、近傍にアイテムを追加しようとします。^[36]^{: 352}

ハッシュテーブル内の各バケットには、追加の「ホップ情報」、つまり、現在の仮想バケットに元々ハッシュされたアイテムのH − 1エントリ以内の相対距離を示すHビットのビット配列が含まれます。^[36]^{: 352}挿入されるキーと、キーがハッシュされるバケットをそれぞれとします。挿入手順には、アルゴリズムの近傍特性が保証されるいくつかのケースが含まれます。^[36]^{: 352–353}が空の場合、要素が挿入され、ビットマップの左端のビットが1に設定されます。空でない場合、テーブル内の空きスロットを見つけるために線形プローブが使用され、バケットのビットマップが更新されてから挿入が行われます。空きスロットが近傍の範囲内、つまりH − 1にない場合、各バケットの後続のスワップおよびホップ情報ビット配列操作は、その近傍不変特性に従って実行されます。^[36]^{: 353} $k$ $Bk$ $Bk$

ロビンフッドハッシュ

ロビンフッドハッシュは、オープンアドレスに基づく衝突解決アルゴリズムです。衝突は、その「ホームロケーション」、つまりアイテムがハッシュされたバケットから最も遠い（つまりプローブシーケンス長（PSL）が最も長い）要素を移動させることで解決されます。 ^[37]^{: 12}ロビンフッドハッシュは理論的な検索コストを変更しませんが、バケット上のアイテムの分布の分散に大きな影響を与えます。^[38]^{: 2}つまり、ハッシュテーブルにおけるクラスター形成に対処するためです。 ^[39]ロビンフッドハッシュを使用するハッシュテーブル内の各ノードは、追加のPSL値を格納できるように拡張する必要があります。^[40]挿入するキーを、の（増分）PSL長を、ハッシュテーブルを、インデックスをとすると、挿入手順は以下のようになります。^[37]^{: 12–13}^[41]^{: 5} $x$ $x{.}{\text{psl}}$ $x$ $T$ $j$

の場合: 反復は外部プローブを試行せずに次のバケットに進みます。 $x{.}{\text{psl}}\ \leq \ T[j]{.}{\text{psl}}$
の場合: アイテムをバケットに挿入します。と交換します。を挿入するために番目のバケットからプローブを続行します。すべての要素が挿入されるまでこの手順を繰り返します。 $x{.}{\text{psl}}\ >\ T[j]{.}{\text{psl}}$ $x$ $j$ $x$ $T[j]$ $x'$ $(j+1)$ $x'$

動的なサイズ変更

挿入を繰り返すとハッシュテーブル内のエントリ数が増加し、結果として負荷係数が増加します。検索および挿入操作の償却パフォーマンスを維持するために、ハッシュテーブルは動的にサイズ変更され、テーブルの項目は新しいハッシュテーブルのバケットに再ハッシュされます。 ^{[13]テーブルサイズの変化は}モジュロ演算により異なるハッシュ値をもたらすため、項目をコピーすることはできません。^{[42]ハッシュテーブルがいくつかの要素を削除した後に「空になりすぎた」場合、過剰な}メモリ使用を避けるためにサイズ変更が実行されることがあります。^[43] $O(1)$

すべてのエントリを移動してサイズを変更する

一般的には、元のハッシュテーブルの2倍のサイズを持つ新しいハッシュテーブルがプライベートに割り当てらえられ、元のハッシュテーブルのすべてのアイテムは、そのアイテムのハッシュ値を計算し、その後挿入操作を行うことで、新しく割り当てられたハッシュテーブルに移動されます。再ハッシュは単純ですが、計算コストがかかります。^[44]^{: 478–479}

一度にすべてをやり直す代わりに

一部のハッシュテーブル実装、特にリアルタイムシステムでは、ハッシュテーブルを一度に拡大するコストを払うことができません。これは、時間的に重要な操作が中断される可能性があるためです。動的なサイズ変更を避けられない場合、解決策としては、再ハッシュ中にストレージのブリップ (通常は新しいテーブルのサイズの 50%) を回避するため、また古いハッシュテーブルによって発生した大きなメモリブロックの割り当て解除によってヒープ圧縮が引き起こされるメモリの断片化を回避するために、サイズ変更を段階的に実行することです。 ^[45]^{: 2–3}このような場合、再ハッシュ操作は、ハッシュテーブルのバケットが変更されないように、古いハッシュテーブルに割り当てられた以前のメモリブロックを拡張することによって段階的に実行されます。償却再ハッシュの一般的なアプローチでは、2 つのハッシュ関数とを維持します。新しいハッシュ関数に従ってバケットのアイテムを再ハッシュするプロセスはクリーニングと呼ばれ、これは、などの操作をカプセル化することによってコマンドパターンを通じて実装され、バケット内の各要素が再ハッシュされ、その手順は以下のとおりである：^[45]^：3 $h_{\text{old}}$ $h_{\text{new}}$ $\mathrm {追加} (\mathrm {キー} )$ $\mathrm {Get} (\mathrm {key} )$ $\mathrm {削除} (\mathrm {キー} )$ $\mathrm {検索} (\mathrm {キー} ,{\text{コマンド}})$

きれいなバケツ。 $\mathrm {表} [h_{\text{old}}(\mathrm {キー} )]$
きれいなバケツ。 $\mathrm {表} [h_{\text{new}}(\mathrm {キー} )]$
コマンドが実行されます。

線形ハッシュ

線形ハッシュはハッシュテーブルの実装であり、一度に1つのバケットごとにテーブルを動的に拡大または縮小することを可能にします。^[46]

パフォーマンス

ハッシュテーブルのパフォーマンスは、ハッシュテーブル内のエントリに対して準乱数（）を生成するハッシュ関数の能力に依存します。ここで、、はキー、バケットの数、となるハッシュ関数を表します。ハッシュ関数が異なるキーに対して同じ値（）を生成する場合、衝突が発生しますが、これはさまざまな方法で対処されます。ハッシュテーブルでの操作の一定時間計算量（）は、ハッシュ関数が衝突するインデックスを生成しないという条件を前提としています。したがって、ハッシュテーブルのパフォーマンスは、選択されたハッシュ関数のインデックス分散能力に正比例します。 ^[47]^{： 1}ただし、このようなハッシュ関数の構築は実際には実行不可能であるため、実装では、より高いパフォーマンスを実現するために、ケース固有の衝突解決手法に依存しています。 ^[47]^{： 2} $\sigma$ $K$ $n$ $h(x)$ $\sigma \ =\ h(K)\ \%\ n$ $\sigma$ $K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$ $O(1)$

ハッシュ関数がユニバースの要素を均一に分散させ、テーブルに格納される要素がユニバースからランダムに抽出される場合、最高の性能が得られる。この場合、連鎖ハッシュ法では、探索成功の期待値は、探索失敗の期待値はである。^[48] ${\textstyle 1+{\frac {\alpha }{2}}+\Theta \left({\frac {1}{m}}\right)}$ ${\textstyle e^{-\alpha }+\alpha +\Theta \left({\frac {1}{m}}\right)}$

アプリケーション

連想配列

ハッシュテーブルは、多くの種類のメモリ内テーブルの実装によく使用されます。また、連想配列の実装にも使用されます。^[33]

データベースのインデックス作成

ハッシュテーブルはディスクベースのデータ構造やデータベースインデックス（ dbmなど）としても使用されるが、これらのアプリケーションではBツリーがより一般的である。 ^[49]

キャッシュ

ハッシュテーブルは、主に低速なメディアに保存されているデータへのアクセスを高速化するための補助データテーブルであるキャッシュを実装するために使用できます。このアプリケーションでは、ハッシュの衝突は、衝突する2つのエントリのうち1つを破棄することで処理されます。通常、テーブルに現在保存されている古い項目を消去し、新しい項目で上書きすることで、テーブル内のすべての項目が一意のハッシュ値を持つようになります。^[50]^[51]

セット

ハッシュテーブルは、特定の順序なしに一意の値を格納できるセットデータ構造の実装に使用できます。セットは通常、要素の取得ではなく、コレクション内の値のメンバーシップをテストするために使用されます。^[52]

転置表

検索された各セクションに関する情報を格納する複雑なハッシュテーブルへの転置テーブル。^[53]

実装

多くのプログラミング言語は、組み込みの連想配列または標準ライブラリモジュールとして、ハッシュテーブル機能を提供します。

JavaScriptにおける「オブジェクト」とは、キーと値のペア（「プロパティ」と呼ばれる）の変更可能な集合体であり、各キーは文字列または一意性が保証された「シンボル」のいずれかです。それ以外の値は、キーとして使用される場合、まず文字列に変換されます。7つの「プリミティブ」データ型を除き、JavaScript におけるすべての値はオブジェクトです。^[54] ECMAScript 2015 ではMap、任意の値をキーとして受け入れるデータ構造も追加されました。^[55]
C++11には任意の型unordered_mapのキーと値を格納するための標準ライブラリが含まれています。^[56]
Goの組み込みでは、マップ型を型mapの形で実装しており、これは多くの場合ハッシュテーブルである（ただしハッシュテーブルである保証はない）。^[57]
Javaプログラミング言語には、、、ジェネリックHashSetコレクションがHashMap含まれます。^[58]LinkedHashSetLinkedHashMap
Pythonの組み込み関数は、型dictの形式でハッシュテーブルを実装します。^[59]
Rubyの組み込み関数はHashRuby 2.4以降、オープンアドレスモデルを採用しています。^[60]
Rustプログラミング言語にはHashMap、HashSetRust標準ライブラリの一部としてが含まれています。^[61]
.NET標準ライブラリには^[62]と^[63]が含まれているため、C#やVB.NETなどの言語から使用することができます。^[64]HashSetDictionary

参照

注記

^最悪のケースの 期待時間計算量がO(log ² (1 - α ) ^-1 )となるアプローチもある（αは負荷係数）。^[1]

参考文献

^ Martin Farach-Colton、Andrew Krapivin、William Kuszmaul.並べ替えなしのオープンアドレス指定の最適境界. 2024 IEEE 第65回コンピュータサイエンス基礎シンポジウム (FOCS). arXiv : 2501.02305 . doi :10.1109/FOCS61266.2024.00045.
^ ab コーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2009). 『アルゴリズム入門（第3版）』マサチューセッツ工科大学. pp. 253– 280. ISBN 978-0-262-03384-8。
^ メルホーン, カート;サンダース, ピーター(2008). 「ハッシュテーブルと連想配列」(PDF) .アルゴリズムとデータ構造. シュプリンガー. pp. 81– 98. doi :10.1007/978-3-540-77978-0_4. ISBN 978-3-540-77977-3。
^ abcdefg ドナルド・E.・クヌース（1998年4月24日）『コンピュータプログラミングの芸術：第3巻：ソートと検索』（第2版）Addison-Wesley Professional . ISBN 978-0-201-89685-5。
^ Leiserson, Charles E. (2005年秋). 「講義13：償却アルゴリズム、テーブル倍増、ポテンシャル法」. MIT アルゴリズム入門 6.046J/18.410J コース. 2009年8月7日時点のオリジナルよりアーカイブ。
^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「第11章ハッシュテーブル」.アルゴリズム入門（第2版）. MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2。
^ abcde Sedgewick, Robert ; Wayne, Kevin (2011). Algorithms. Vol. 1 (4 ed.). Addison-Wesley Professional –プリンストン大学コンピュータサイエンス学部経由.
^ Silberschatz, A.; Korth, HF; Sudarshan, S. (2020).データベースシステムの概念（第7版）. McGraw-Hill .
^ Goodrich, MT; Tamassia, R.; Goldwasser, MH (2014). 『Javaにおけるデータ構造とアルゴリズム』（第6版）. Wiley .
^ abc Konheim, Alan G. (2010).コンピュータサイエンスにおけるハッシュ. doi :10.1002/9780470630617. ISBN 978-0-470-34473-6。
^ abcdefghijkl Mehta, Dinesh P.; Mehta, Dinesh P.; Sahni, Sartaj編 (2004).データ構造とアプリケーションハンドブック. doi :10.1201/9781420035179. ISBN 978-0-429-14701-2。
^ タイ王国コーメン; CE、ライザーソン。Rivest, ルイジアナ州;スタイン、C. (2009)。アルゴリズム入門(第 3 版)。MIT を押します。
^ abcdefg Mayers, Andrew (2008). 「CS 312: ハッシュテーブルと償却分析」.コーネル大学コンピュータサイエンス学部. 2021年4月26日時点のオリジナルよりアーカイブ。2021年10月26日閲覧– cs.cornell.edu経由。
^ ab James S. PlankとBrad Vander Zanden. 「CS140 講義ノート -- ハッシュ」
^ Maurer, WD; Lewis, TG (1975年3月). 「ハッシュテーブル法」. ACM Computing Surveys . 7 (1): 5– 19. doi :10.1145/356643.356645. S2CID 17874775.
^ ab Owolabi, Olumide (2003年2月). 「いくつかのハッシュ関数の実証的研究」.情報ソフトウェア技術. 45 (2): 109– 112. doi :10.1016/S0950-5849(02)00174-X.
^ ab 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。
^ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009). 「ハッシュ、ディスプレイス、圧縮」(PDF) .アルゴリズム—ESA 2009: 第17回ヨーロッパシンポジウム、コペンハーゲン、デンマーク、2009年9月7～9日、議事録.コンピュータサイエンス講義ノート. 第5757巻. ベルリン: Springer. pp. 682– 693. CiteSeerX 10.1.1.568.130 . doi :10.1007/978-3-642-04128-0_61. MR 2557794.
^ ab Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「第11章ハッシュテーブル」.アルゴリズム入門（第2版）.マサチューセッツ工科大学. ISBN 978-0-262-53196-2。
^ Stroustrup, Bjarne (1997). 『C++プログラミング言語第3版』マサチューセッツ州リーディング: Addison-Wesley. p. 503. ISBN 0-201-88954-4。
^ ピアソン、カール(1900). 「相関変数システムの場合における、確率からの偏差の与えられたシステムが、ランダムサンプリングから生じたと合理的に想定できるという基準について」.哲学雑誌. シリーズ5. 50 (302): 157– 175. doi :10.1080/14786440009463897.
^ プラケット、ロビン(1983). 「カール・ピアソンとカイ2乗検定」.国際統計評論. 51 (1): 59– 72. doi :10.2307/1402731. JSTOR 1402731.
^ ab Wang, Thomas (1997年3月). 「Prime Double Hash Table」. 1999年9月3日時点のオリジナルよりアーカイブ。2015年5月10日閲覧。
^ Wegman, Mark N.; Carter, J. Lawrence (1981年6月). 「新しいハッシュ関数と認証および集合等価性におけるその利用」. Journal of Computer and System Sciences . 22 (3): 265– 279. doi : 10.1016/0022-0000(81)90033-7 .
^ Demaine, Erik; Lind, Jeff (2003年春). 「Lecture 2」(PDF) . 6.897: 高度なデータ構造. MITコンピュータサイエンス・人工知能研究所. 2010年6月15日時点のオリジナルよりアーカイブ(PDF) . 2008年6月30日閲覧.
^ abc Culpepper, J. Shane; Moffat, Alistair (2005). 「プレフィックス特性を制限した拡張バイトコード」.文字列処理と情報検索. コンピュータサイエンス講義ノート. 第3772巻. pp. 1– 12. doi :10.1007/11575832_1. ISBN 978-3-540-29740-6。
^ Willard, Dan E. (2000). 「融合木の観点から見た計算幾何学、ファン・エムデ・ボアズ木、そしてハッシュの考察」SIAM Journal on Computing . 29 (3): 1030– 1049. doi :10.1137/S0097539797322425. MR 1740562.。
^ Askitis, Nikolas; Sinha, Ranjan (2010年10月). 「スケーラブルでキャッシュ効率とスペース効率に優れた文字列のトライのエンジニアリング」. VLDB Journal . 19 (5): 633– 660. doi :10.1007/s00778-010-0183-9.
^ Askitis, Nikolas; Zobel, Justin (2005年10月). 「文字列ハッシュテーブルにおけるキャッシュを考慮した衝突解決」.第12回国際文字列処理・情報検索会議 (SPIRE 2005) の議事録. Vol. 3772/2005. pp. 91– 102. doi :10.1007/11575832_11. ISBN 978-3-540-29740-6。
^ Askitis, Nikolas (2009). 「整数キーのための高速かつコンパクトなハッシュテーブル」(PDF) .第32回オーストラレーシアコンピュータサイエンス会議 (ACSC 2009) の議事録. 第91巻. pp. 113– 122. ISBN 978-1-920682-72-9. 2011年2月16日時点のオリジナル（PDF）からアーカイブ。2010年6月13日閲覧。
^ テネンバウム、アーロン M.ランサム、イェディディヤ。オーゲンシュタイン、モーシェ J. (1990)。C を使用したデータ構造。プレンティス・ホール。456～ 461ページ、456ページ472.ISBN 978-0-13-199746-2。
^ ab パグ、ラスムス;ロドラー、フレミング・フリッシュ (2001)。「カッコーハッシング」。アルゴリズム — ESA 2001。コンピューターサイエンスの講義ノート。 Vol. 2161。121 ～ 133ページ。CiteSeerX 10.1.1.25.4189。土井：10.1007/3-540-44676-1_10。ISBN 978-3-540-42493-2。
^ abc コーメン、トーマス・H. ;レイソン、チャールズ・E. ;リベスト、ロナルド・L. ;スタイン、クリフォード(2001)、「11 ハッシュテーブル」、アルゴリズム入門（第2版）、MITプレスおよびマグロウヒル、pp. 221– 252、ISBN 0-262-03293-7。
^ abc Vitter, Jeffery S.; Chen, Wen-Chin (1987).合体ハッシュ法の設計と解析. ニューヨーク, アメリカ合衆国: Oxford University Press . ISBN 978-0-19-504182-8– Archive.orgより。
^ ラスムス・パーグ;ロドラー、フレミング・フリッシュ (2001)。「カッコーハッシング」。アルゴリズム — ESA 2001。コンピューターサイエンスの講義ノート。 Vol. 2161。121 ～ 133ページ。CiteSeerX 10.1.1.25.4189。土井：10.1007/3-540-44676-1_10。ISBN 978-3-540-42493-2。
^ abcdef モーリス・ハーリヒー、ニール・シャヴィット、モラン・ツァフリル (2008). 「ホップスコッチ・ハッシュ」.分散コンピューティング. コンピュータサイエンス講義ノート. 第5218巻. pp. 350– 364. doi :10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3。
^ ab セリス、ペドロ (1986)。ロビンフッドハッシュ(PDF)。カナダ、オンタリオ州:ウォータールー大学、コンピューターサイエンス学部。ISBN 978-0-315-29700-5. OCLC 14083698. 2021年11月1日時点のオリジナルよりアーカイブ（PDF）。 2021年11月2日閲覧。
^ Poblete, PV; Viola, A. (2019年7月). 「ランダムプロービングモデルにおけるRobin Hoodおよびその他のハッシュアルゴリズムの解析（削除の有無による）」.組合せ論、確率、計算. 28 (4): 600– 617. doi : 10.1017/S0963548318000408 . S2CID 125374363.
^ Clarkson, Michael (2014). 「Lecture 13: Hash tables」.コーネル大学、コンピュータサイエンス学部。2021年10月7日時点のオリジナルよりアーカイブ。2021年11月1日閲覧– cs.cornell.edu経由。
^ Gries, David (2017). 「JavaHyperTextとデータ構造：Robin Hood Hashing」（PDF） .コーネル大学、コンピュータサイエンス学部。2021年4月26日時点のオリジナルよりアーカイブ（PDF）。 2021年11月2日閲覧– cs.cornell.edu経由。
^ Celis, Pedro (1988年3月28日). 外部ロビンフッドハッシュ(PDF) (技術レポート). ブルーミントン、インディアナ州:インディアナ大学、コンピュータサイエンス学部. 246. 2021年11月3日時点のオリジナルよりアーカイブ(PDF) 。 2021年11月2日閲覧。
^ Goddard, Wayne (2021). 「C5章ハッシュテーブル」(PDF) .クレムソン大学. pp. 15– 16. 2023年12月4日閲覧。
^ Devadas, Srini; Demaine, Erik (2011年2月25日). 「アルゴリズム入門：ハッシュテーブルのサイズ変更」(PDF) .マサチューセッツ工科大学、コンピュータサイエンス学部. 2021年5月7日時点のオリジナルよりアーカイブ(PDF) . 2021年11月9日閲覧– MIT OpenCourseWare経由.
^ Thareja, Reema (2014). 「ハッシュと衝突」. C言語によるデータ構造. オックスフォード大学出版局. pp. 464– 488. ISBN 978-0-19-809930-7。
^ ab Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (2003年3月18日). 「組み込みシステムとリアルタイムシステムのためのハッシュテーブル」(PDF) . All Computer Science and Engineering Research . Washington University in St. Louis . doi :10.7936/K7WD3XXV. 2021年6月9日時点のオリジナルよりアーカイブ(PDF) . 2021年11月9日閲覧– Northwestern University , Department of Computer Science.
^ Litwin, Witold (1980). 「線形ハッシュ：ファイルとテーブルのアドレス指定のための新しいツール」（PDF） . Proc. 6th Conference on Very Large Databases . Carnegie Mellon University . pp. 212– 223. 2021年5月6日時点のオリジナルよりアーカイブ（PDF） . 2021年11月10日閲覧– cs.cmu.edu経由。
^ ab Dijk, Tom Van (2010). 「ハッシュテーブルのパフォーマンス分析と改善」(PDF) .オランダ：トゥウェンテ大学. 2021年11月6日時点のオリジナルよりアーカイブ(PDF) . 2021年12月31日閲覧。
^ Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). 「第2章探索」. Atallah (編). 『アルゴリズムと計算理論ハンドブック』 . CRC Press. pp. 2– 6. ISBN 0849326494。
^ レフ・バナコウスキー。「インデックスと外部ソート」。 pl:Polsko-Japońska Akademia Technik Komputerowych. 2022年3月26日のオリジナルからアーカイブ。2022 年3 月 26 日に取得。
^ Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (2020年2月). 「セルラーネットワークをオーバーレイするデバイス間通信におけるキャッシュヒット率の最大化」.中国通信. 17 (2): 232– 238.文献コード:2020CComm..17b.232Z. doi :10.23919/jcc.2020.02.018. S2CID 212649328.
^ Bottommley, James (2004年1月1日). 「キャッシュを理解する」. Linux Journal . 2020年12月4日時点のオリジナルよりアーカイブ。 2022年4月16日閲覧。
^ Jill Seaman (2014). 「セットテーブルとハッシュテーブル」(PDF) .テキサス州立大学. 2022年4月1日時点のオリジナルよりアーカイブ。 2022年3月26日閲覧。{{cite web}}: CS1 maint: bot: 元のURLステータス不明（リンク）
^ “Transposition Table - Chessprogramming wiki”. chessprogramming.org . 2021年2月14日時点のオリジナルよりアーカイブ。2020年5月1日閲覧。
^ 「JavaScript のデータ型とデータ構造 - JavaScript | MDN」。developer.mozilla.org . 2022年7月24日閲覧。
^ “Map - JavaScript | MDN”. developer.mozilla.org . 2023年6月20日. 2023年7月15日閲覧。
^ 「プログラミング言語C++ - 技術仕様」(PDF) .国際標準化機構. pp. 812– 813. 2022年1月21日時点のオリジナル(PDF)からアーカイブ。 2022年2月8日閲覧。
^ 「Goプログラミング言語仕様」go.dev . 2023年1月1日閲覧。
^ 「レッスン：実装（Java™チュートリアル > コレクション）」. docs.oracle.com . 2017年1月18日時点のオリジナルよりアーカイブ。2018年4月27日閲覧。
^ Zhang, Juan; Jia, Yunwei (2020). 「機械学習に基づくRedis rehash最適化」. Journal of Physics: Conference Series . 1453 (1): 3. Bibcode :2020JPhCS1453a2048Z. doi : 10.1088/1742-6596/1453/1/012048 . S2CID 215943738.
^ Jonan Scheffler (2016年12月25日). 「Ruby 2.4 リリース：ハッシュの高速化、統合整数、丸め処理の改善」heroku.com . 2019年7月3日時点のオリジナルよりアーカイブ。 2019年7月3日閲覧。
^ “doc.rust-lang.org”. 2022年12月8日時点のオリジナルよりアーカイブ。2022年12月14日閲覧。
^ 「HashSet クラス (System.Collections.Generic)」。learn.microsoft.com . 2023年7月1日閲覧。
^ dotnet-bot. 「Dictionary クラス (System.Collections.Generic)」. learn.microsoft.com . 2024年1月16日閲覧。
^ 「VB.NET HashSetの例」。Dot Net Perls。

さらに読む

Tamassia, Roberto; Goodrich, Michael T. (2006). 「第9章マップと辞書」. Javaにおけるデータ構造とアルゴリズム [Java 5.0対応] (第4版). ホーボーケン, ニュージャージー: Wiley. pp. 369–418. ISBN 978-0-471-73884-8。
McKenzie, BJ; Harries, R.; Bell, T. (1990年2月). 「ハッシュアルゴリズムの選択」.ソフトウェア：実践と経験. 20 (2): 209– 224. doi :10.1002/spe.4380200207. hdl : 10092/9691 . S2CID 12854386.

外部リンク

ウィキメディアコモンズには、ハッシュテーブルに関連するメディアがあります。

Wikibooksには「データ構造/ハッシュテーブル」に関する書籍があります。

ハッシュテーブルに関するNISTエントリ
オープンデータ構造 – 第5章 – ハッシュテーブル、Pat Morin
MITアルゴリズム入門：ハッシュ1 MIT OCW講義ビデオ
MITアルゴリズム入門：ハッシュ2 MIT OCW講義ビデオ