ハッシュテーブル

ハッシュテーブル
ハッシュテーブル
タイプ	順序なし連想配列
発明した	1953
手術
ビッグオー記法による時間計算量
手術	平均
検索	Θ(1)
入れる	Θ(1)
消去	Θ(1)
空間の複雑さ
空間	Θ( n )

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

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

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

ハッシュ化は、空間と時間のトレードオフの一例である。メモリが無限であれば、キー全体をインデックスとして直接使用して、1回のメモリアクセスで値を見つけることができる。一方、時間が無限であれば、キーを考慮せずに値を格納し、二分探索または線形探索を使用して要素を取得できる。^{[ 7 ]}^{： 458}

多くの状況において、ハッシュテーブルは平均的に検索木や他のテーブル検索構造よりも効率的であることがわかります。そのため、ハッシュテーブルは、連想配列、データベースのインデックス、キャッシュ、セットなど、多くの種類のコンピュータソフトウェアで広く使用されています。^[⁸^]多くのプログラミング言語には、 Python の辞書、Java の HashMap、C++ の unordered_map、Go のマップなど、ハッシュの複雑さをプログラマから抽象化する組み込みのハッシュテーブル構造が用意されています。^[⁹^]

歴史

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

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

概要

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

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

負荷率

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

$n$ はハッシュテーブル内で使用されているエントリの数です。
$m$ バケツの数です。

ハッシュテーブルのパフォーマンスは、負荷係数に応じて低下する。 $\alpha$ [ ¹¹^]^：² 大きな極限で^は $m$ そして $n$ 各バケットは統計的に期待値を持つポアソン分布に従います。 $\lambda =\alpha$ 理想的なランダムハッシュ関数の場合。

このソフトウェアは通常、負荷係数が $\alpha$ ある定数以下に留まり、 $\displaystyle \alpha _{\max }}$ これにより、良好なパフォーマンスが維持されます。そのため、負荷係数が一定以上になるとハッシュテーブルのサイズを変更したり、「再ハッシュ」したりするのが一般的なアプローチです。 $\alpha$ 到達する $\displaystyle \alpha _{\max }}$ 同様に、負荷率が一定値以下になると、テーブルのサイズも変更される可能性があります。 $\alpha _{\max }/4$ [ ¹³^]

別個のチェーンに対する荷重係数

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

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

別個の連鎖では、 $\displaystyle \alpha _{\max }}$ 最高のパフォーマンスを発揮する値は通常1から3の間である。^{[ 13 ]}

オープンアドレッシングの負荷係数

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

負荷率が1に近づくと、オープンアドレッシングのパフォーマンスが非常に悪くなります。^{[ 13 ]}

したがって、オープンアドレッシングを使用するハッシュテーブルは、負荷係数が増加するとサイズ変更または再ハッシュする必要があります。 $\alpha$ アプローチ1. ^{[ 13 ]}

オープンアドレッシングの場合、最大負荷係数の許容値は $\displaystyle \alpha _{\max }}$ 0.6～0.75の範囲であるべきである。^{[ 15 ]}^{[ 16 ]}^{： 110}

ハッシュ関数

ハッシュ関数 $h:U\rightarrow \{0,...,m-1\}$ 宇宙を地図化する $U$ テーブル内のインデックスまたはスロットへのキー、つまり、 $h(x)\in \{0,...,m-1\}$ のために $x\in U$ ハッシュ関数の従来の実装は、テーブルのすべての要素が整数ユニバースから派生するという整数ユニバースの仮定に基づいています。 $U=\{0,...,u-1\}$ ビット長は $u$ コンピュータアーキテクチャのワードサイズ内に収まる。^[¹¹^]^：²

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

整数宇宙の仮定

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

除算によるハッシュ化

除算によるハッシュ化の方式は次のとおりです。^{[ 11 ]}^{: 2} $h(x)\ =\ x\,{\bmod {\,}}m,$ どこ $h(x)$ はハッシュ値です $x\in S$ そして $m$ テーブルのサイズです。

乗算によるハッシュ化

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

文字列ハッシュ

一般的に、ハッシュ関数のキーとして文字列が使用されます。C ++ プログラミング言語の第 3 版では、初期値がゼロの符号なし整数を繰り返し 1 ビット左シフトし、次の文字の整数値と XOR 演算する単純なハッシュ関数が説明されています。このハッシュ値は、テーブルのサイズで剰余演算されます。^{[ 20 ]}左シフトが循環的でない場合、文字列の長さは、符号なし整数のビットサイズより少なくとも 8 ビット小さくする必要があります。文字列を整数にハッシュ化するもう 1 つの一般的な方法は、多項式ローリングハッシュ関数を使用することです。

ハッシュ関数の選択

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

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

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

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

衝突解決

A search algorithm that uses hashing consists of two parts. The first part is computing a hash function which transforms the search key into an array index. The ideal case is such that no two search keys hash to the same array index. However, this is not always the case and impossible to guarantee for unseen given data.^[4]^:515 Hence the second part of the algorithm is collision resolution. The two common methods for collision resolution are separate chaining and open addressing.^[7]^:458

Separate chaining

In separate chaining, the process involves building a linked list with key–value pair for each search array index. The collided items are chained together through a single linked list, which can be traversed to access the item with a unique search key.^[7]^:464 Collision resolution through chaining with linked list is a common method of implementation of hash tables. Let $T$ and $x$ be the hash table and the node respectively, the operation involves as follows:^[19]^:258

Chained-Hash-Insert(T, k) insertxat the head of linked listT[h(k)] Chained-Hash-Search(T, k) search for an element with keykin linked listT[h(k)] Chained-Hash-Delete(T, k) deletexfrom the linked listT[h(k)]

If the element is comparable either numerically or lexically, and inserted into the list by maintaining the total order, it results in faster termination of the unsuccessful searches.^[4]^:520–521

Other data structures for separate chaining

If the keys are ordered, it could be efficient to use "self-organizing" concepts such as using a self-balancing binary search tree, through which the theoretical worst case could be brought down to $O(\log {n})$ , although it introduces additional complexities.^[4]^:521

動的完全ハッシュでは、ルックアップの複雑さを軽減するために2レベルのハッシュテーブルが使用され、 $O(1)$ 最悪の場合。この手法では、 $k$ エントリは完全なハッシュテーブルとして整理され、 $\displaystyle k^{2}}$ スロットは、最悪ケースの検索時間を一定に保ち、挿入の償却時間を短縮します。^{[ 25 ]}ある研究では、配列ベースの分離連鎖は、高負荷時において標準的なリンクリスト方式と比較して97%高いパフォーマンスを発揮することが示されています。^{[ 26 ]}^{： 99}

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

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

分離連鎖実装のリンクリストは、リンクリストのノードがメモリ全体に分散している場合、空間的局所性（参照の局所性）のためにキャッシュを意識しない可能性があり、挿入および検索時のリスト走査は CPUキャッシュの非効率性を招く可能性がある。^[²⁶^]^：⁹¹

分離連鎖による衝突解決のキャッシュ意識の高いバリアントでは、通常リンクリストや自己平衡二分探索木が使用される場所に、よりキャッシュフレンドリーであることがわかっている動的配列が使用されます。これは、配列の連続割り当てパターンが、変換ルックアサイドバッファなどのハードウェアキャッシュプリフェッチャによって利用され、アクセス時間とメモリ消費が削減されるためです。^[²⁸^]^[²⁹^]^[³⁰^]

オープンアドレッシング

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

よく知られているプローブ配列には以下が含まれる。

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

オープンアドレッシングのパフォーマンスは、負荷係数が増加するとプローブシーケンスが増加するため、分離チェイニングと比較して遅くなる可能性がある。 $\alpha$ 1に近づく。^{[ 13 ]}^{[ 26 ]}^{: 93}完全に満たされたテーブルの場合、負荷係数が1に達すると、プロービングは無限ループになる。 ^{[ 7 ]}^{: 471}線形プロービングの平均コストは、ハッシュ関数がテーブル全体に要素を均等に分散させてランを回避する能力に依存する。ランが発生すると検索時間が増加するためである。^[⁷^]^:⁴⁷²

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

スロットは連続した位置に配置されているため、線形プロービングは参照の局所性によりCPUキャッシュの利用効率を高め、メモリレイテンシを低減する可能性がある。^[³²^]

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

結合ハッシュ

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

カッコウハッシュ

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

ホップスコッチハッシュ

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

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

ロビンフッドのハッシュ化

ロビンフッドハッシュは、オープンアドレスベースの衝突解決アルゴリズムです。衝突は、アイテムがハッシュされたバケット、つまり「ホームロケーション」から最も遠い要素、つまり最も長いプローブシーケンス長（PSL）の要素を優先することで解決されます。 ^{[ 37 ]}^{: 12}これは、金持ちから盗んで貧しい人々に分け与えた伝説の英雄的なアウトロー、ロビンフッドにちなんで名付けられました。

ロビンフッドハッシュは理論上の検索コストを変更しませんが、バケット上のアイテムの分布の分散に大きな影響を与えます^[³⁸^]^：² 、つまりハッシュテーブルにおけるロングランの形成に対処します^[³⁹^] 。ロビンフッドハッシュを使用するハッシュテーブル内の各ノードは、追加のPSL値を格納するように拡張する必要があります[ ⁴⁰^]^。 $x$ 挿入される鍵となる。 $x{.}{\text{psl}}$ （増分）PSLの長さは $x$ 、 $T$ ハッシュテーブルと $j$ インデックスの場合、挿入手順は次のとおりです。^{[ 37 ]}^{： 12-13}^{[ 41 ]}^{： 5}

もし $x{.}{\text{psl}}\ \leq \ T[j]{.}{\text{psl}}$ : 外部プローブを試みることなく、反復処理は次のバケットに進みます。
もし $x{.}{\text{psl}}\ >\ T[j]{.}{\text{psl}}$ : アイテムを挿入する $x$ バケツの中へ $j$ ; 交換 $x$ と $T[j]$ -なるがままに $x'$ ; プローブを続行します $(j+1)$ 挿入する th バケット $x'$ すべての要素が挿入されるまで、この手順を繰り返します。

動的なサイズ変更

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

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

一般的に、元のハッシュテーブルの2倍のサイズの新しいハッシュテーブルがプライベートに割り当てられ、元のハッシュテーブルのすべての項目は、項目のハッシュ値を計算して挿入操作を行うことで、新しく割り当てられたハッシュテーブルに移動されます。リハッシュは単純ですが、計算コストが高くなります。^{[ 44 ]}^{： 478-479}

一括再検討の代替案

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

クリーン $\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$ バケツ。
クリーン $\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$ バケツ。
コマンドが実行されます。

線形ハッシュ

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

パフォーマンス

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

ハッシュ関数がユニバースの要素を均一に分散し、テーブルに格納される要素がユニバースからランダムに抽出される場合に、最高のパフォーマンスが得られます。この場合、連鎖ハッシュでは、検索が成功するまでの期待時間は ${\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++11unordered_mapの標準ライブラリには、任意の型のキーと値を格納するための機能が含まれています。^{[ 56 ]}
Goの組み込み関数は、型mapの形式でマップ型を実装しており、これは多くの場合 (ただし保証されているわけではない) ハッシュテーブルです。^[⁵⁷^]
Javaプログラミング言語にはHashSet、、、、および汎用HashMapコレクションが含まれています。^[⁵⁸^]LinkedHashSetLinkedHashMap
Pythonの組み込み関数は、型dictの形式でハッシュテーブルを実装しています。^[⁵⁹^]
Rubyの組み込み関数は、HashRuby 2.4 以降、オープンアドレッシングモデルを使用しています。^{[ 60 ]}
Rustプログラミング言語にはHashMap、HashSetRust標準ライブラリの一部としてが含まれています。^{[ 61 ]}
.NET標準ライブラリにはとが含まれているためHashSet、Dictionary[ ^{62 ] [}^{63 ] C} #やVB.NETなどの言語から使用できます。^{[ 64 ]}

注記

↑最悪の場合の期待時間計算量が O(log² (1 - α )⁻¹ ) となるアプローチがあります。ここでαは負荷係数です。^{[ 1 ]}

参考文献

↑ Martin Farach-Colton; Andrew Krapivin; William Kuszmaul. Optimal Bounds for Open Addressing Without Reordering . 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2501.02305 . doi : 10.1109/FOCS61266.2024.00045 .
1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280 . ISBN 978-0-262-03384-8。
↑ Mehlhorn, Kurt ; Sanders, Peter (2008). "ハッシュテーブルと連想配列" (PDF) .アルゴリズムとデータ構造. Springer. pp. 81–98 . doi : 10.1007/978-3-540-77978-0_4 . ISBN 978-3-540-77977-3。
1 2 3 4 5 6 7ドナルド・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およびMcGraw-Hill. pp. 221–252 . ISBN 978-0-262-53196-2。
1 2 3 4 5セッジウィック、ロバート；ウェイン、ケビン（2011）。アルゴリズム。第1巻（第4版）。アディソン・ウェスリー・プロフェッショナル–プリンストン大学コンピュータサイエンス学部経由。
↑ Silberschatz, A.; Korth, HF; Sudarshan, S. (2020). Database System Concepts (7th ed.). McGraw-Hill .
↑ Goodrich, MT; Tamassia, R.; Goldwasser, MH (2014). Data Structures and Algorithms in Java (6th ed.). Wiley .
1 2 3 Konheim, Alan G. (2010).コンピュータサイエンスにおけるハッシュ関数. doi : 10.1002/9780470630617 . ISBN 978-0-470-34473-6。
1 2 3 4 5 6 7 8 9 10 11 12 Mehta, Dinesh P.; Mehta, Dinesh P.; Sahni, Sartaj 編 (2004). Handbook of Data Structures and Applications . doi : 10.1201/9781420035179 . ISBN 978-0-429-14701-2。
↑コーメン、TH; CE、ライザーソン。Rivest, ルイジアナ州;スタイン、C. (2009)。アルゴリズム入門(第 3版)。MIT を押します。
1 2 3 4 5 6 7 Mayers, Andrew (2008). "CS 312: ハッシュテーブルと償却分析" .コーネル大学、コンピュータサイエンス学部。2021年4月26日のオリジナルからアーカイブ済み。 2021年10月26日にcs.cornell.edu経由で取得。
1 2 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 .
1 2 Owolabi, Olumide (2003 年 2 月). 「いくつかのハッシュ関数の経験的研究」. Information and Software Technology . 45 (2): 109–112 . doi : 10.1016/S0950-5849(02)00174-X .
1 2 Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006). Perfect Hashing for Network Applications . 2006 IEEE International Symposium on Information Theory. pp. 2774–2778 . doi : 10.1109/ISIT.2006.261567 . ISBN 1-4244-0505-X. S2CID 1494710 .
↑ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009). "Hash, displace, and compress" (PDF) . Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009, Proceedings . Lecture Notes in Computer Science . Vol. 5757. Berlin: Springer. pp. 682– 693. CiteSeerX 10.1.1.568.130 . doi : 10.1007/978-3-642-04128-0_61 . MR 2557794 .
1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「第 11 章: ハッシュテーブル」.アルゴリズム入門(第 2版).マサチューセッツ工科大学. ISBN 978-0-262-53196-2。
↑ストロストルップ、ビャルネ (1997). C++ プログラミング言語第 3 版. マサチューセッツ州リーディング: Addison-Wesley. p. 503. ISBN 0-201-88954-4。
↑ Pearson, Karl (1900). 「相関のある変数体系の場合、確率からの偏差の与えられた体系が、ランダムサンプリングから生じたと合理的に想定できるような基準について」 . Philosophical Magazine . Series 5. 50 (302): 157– 175. doi : 10.1080/14786440009463897 .
↑ Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review . 51 (1): 59–72 . doi : 10.2307/1402731 . JSTOR 1402731 .
1 2 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. Bibcode : 1981JCoSS..22..265W . doi : 10.1016/0022-0000(81)90033-7 .
↑ Demaine, Erik; Lind, Jeff (2003年春)。「講義2」（PDF）。6.897 ：高度なデータ構造。MITコンピュータ科学・人工知能研究所。2010年6月15日のオリジナルからアーカイブ（PDF）。 2008年6月30日取得。
1 2 3 Culpepper, J. Shane; Moffat, Alistair (2005). "Enhanced Byte Codes with Restricted Prefix Properties". String Processing and Information Retrieval . Lecture Notes in Computer Science. Vol. 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月)「文字列のためのスケーラブルでキャッシュとスペース効率の良いトライのエンジニアリング」The VLDB Journal . 19 (5): 633–660 . doi : 10.1007/s00778-010-0183-9 .
↑ Askitis, Nikolas; Zobel, Justin (2005年10月)「文字列ハッシュテーブルにおけるキャッシュを考慮した衝突解決」第12回国際文字列処理・情報検索会議（SPIRE 2005）論文集、第3772巻/2005年、 91～ 102ページ、doi : 10.1007/11575832_11、ISBN 978-3-540-29740-6。
↑ Askitis, Nikolas (2009). "整数キーのための高速かつコンパクトなハッシュテーブル" (PDF) .第32回オーストラリアコンピュータサイエンス会議 (ACSC 2009) 議事録. 第91巻113–122ページISBN 978-1-920682-72-92011年2月16日にオリジナル（PDF）からアーカイブされました。 2010年6月13日に取得。
↑テネンバウム、アーロン M.ランサム、イェディヤ。オーゲンシュタイン、モーシェ J. (1990)。C を使用したデータ構造。プレンティス・ホール。456～ 461ページ、456ページ472.ISBN 978-0-13-199746-2。
1 2パグ、ラスムス;ロドラー、フレミング・フリッシュ (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。
1 2 3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "11 ハッシュテーブル", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill , pp. 221–252 , ISBN 0-262-03293-7。
1 2 3 Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing . New York, United States: 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。
1 2 3 4 5 6 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "ホップスコッチハッシュ".分散コンピューティング. Lecture Notes in Computer Science. Vol. 5218. pp. 350–364 . doi : 10.1007/978-3-540-87779-0_24 . ISBN 978-3-540-87778-3。
1 2セリス、ペドロ（1986）。ロビンフッドハッシュ(PDF)。カナダ、オンタリオ州:ウォータールー大学、コンピューターサイエンス学部。ISBN 978-0-315-29700-5. OCLC 14083698 . 2021年11月1日にオリジナルからアーカイブ（PDF）されました。2021年11月2日に取得。
↑ Poblete, PV; Viola, A. (2019年7月) 「ランダムプロービングモデルにおけるロビンフッドとその他のハッシュアルゴリズムの分析（削除ありとなし）」 . Combinatorics, Probability and Computing . 28 (4): 600– 617. doi : 10.1017/S0963548318000408 . S2CID 125374363 .
↑クラークソン、マイケル (2014)。「講義 13: ハッシュテーブル」。コーネル大学、コンピュータサイエンス学部。2021年 10 月 7 日のオリジナルからアーカイブ済み。2021年11 月 1 日取得– cs.cornell.edu 経由。
↑ Gries, David (2017). "JavaHyperTextとデータ構造：ロビンフッドハッシュ" (PDF) .コーネル大学、コンピュータサイエンス学部。2021年4月26日のオリジナルからアーカイブ(PDF) 。2021年11月2日に取得– cs.cornell.edu経由。
↑ Celis, Pedro (1988年3月28日). External Robin Hood Hashing (PDF) (技術報告書). Bloomington, Indiana: Indiana University , Department of Computer Science. 246. 2021年11月3日にオリジナルからアーカイブ(PDF) 。 2021年11月2日に取得。
↑ Goddard, Wayne (2021). "Chapter C5: Hash Tables" (PDF) . Clemson University . 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). "ハッシュと衝突". Data Structures Using C. Oxford University Press. pp. 464–488 . ISBN 978-0-19-809930-7。
1 2 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). "Linear hashing: A new tool for file and table addressing" (PDF) . Proc. 6th Conference on Very Large Databases . Carnegie Mellon University . pp. 212– 223. 2021 年 5 月 6 日のオリジナルからアーカイブ(PDF) 。2021年11 月 10 日取得– cs.cmu.edu 経由。
1 2 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月)「セルラーネットワークをオーバーレイするデバイス間通信におけるキャッシュヒット率の最大化」China Communications . 17 (2): 232– 238. Bibcode : 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). "Set & Hash Tables" (PDF) . Texas State University . 2022年4月1日時点のオリジナルよりアーカイブ済み。 2022年3月26日取得。{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)
↑ "転置表 - チェスプログラミング wiki" . chessprogramming.org . 2021年2月14日のオリジナルからアーカイブ済み。2020年5月1日に取得。
↑ 「JavaScript のデータ型とデータ構造 - JavaScript | MDN」。developer.mozilla.org。2022年7 月 24 日取得。
↑ "マップ - 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リハッシュ最適化" . 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 Class (System.Collections.Generic)" . learn.microsoft.com . 2024年1月16日取得.
↑ "VB.NET HashSet の例" . Dot Net Perls .

さらに読む

タマシア、ロベルト；グッドリッチ、マイケル 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月)「ハッシュアルゴリズムの選択」。Software : Practice and Experience . 20 (2): 209–224 . doi : 10.1002/spe.4380200207 . hdl : 10092/9691 . S2CID 12854386 .

外部リンク

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

[2] 最悪の場合の期待時間計算量が O(log² (1 - α )⁻¹ ) となるアプローチがあります。ここでαは負荷係数です。^{[ 1 ]}

[Farach-Colton_2024-1] Martin Farach-Colton; Andrew Krapivin; William Kuszmaul. Optimal Bounds for Open Addressing Without Reordering . 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2501.02305 . doi : 10.1109/FOCS61266.2024.00045 .

[Cormen_et_al-3] 1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280 . ISBN 978-0-262-03384-8。

[ms-4] Mehlhorn, Kurt ; Sanders, Peter (2008). "ハッシュテーブルと連想配列" (PDF) .アルゴリズムとデータ構造. Springer. pp. 81–98 . doi : 10.1007/978-3-540-77978-0_4 . ISBN 978-3-540-77977-3。

[knuth-5] 1 2 3 4 5 6 7ドナルド・E・クヌース(1998年4月24日).コンピュータプログラミングの技法：第3巻：ソートと検索(第2版). Addison-Wesley Professional . ISBN 978-0-201-89685-5。

[leiser-6] Leiserson, Charles E. (2005年秋). "講義13：償却アルゴリズム、テーブル倍増、ポテンシャル法" .コース MIT 6.046J/18.410J アルゴリズム入門. 2009年8月7日にオリジナルからアーカイブ済み。

[cormen-7] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "第11章：ハッシュテーブル".アルゴリズム入門（第2版）. MIT PressおよびMcGraw-Hill. pp. 221–252 . ISBN 978-0-262-53196-2。

[algo1rob-8] 1 2 3 4 5セッジウィック、ロバート；ウェイン、ケビン（2011）。アルゴリズム。第1巻（第4版）。アディソン・ウェスリー・プロフェッショナル–プリンストン大学コンピュータサイエンス学部経由。

[9] Silberschatz, A.; Korth, HF; Sudarshan, S. (2020). Database System Concepts (7th ed.). McGraw-Hill .

[10] Goodrich, MT; Tamassia, R.; Goldwasser, MH (2014). Data Structures and Algorithms in Java (6th ed.). Wiley .

[Konheim-11] 1 2 3 Konheim, Alan G. (2010).コンピュータサイエンスにおけるハッシュ関数. doi : 10.1002/9780470630617 . ISBN 978-0-470-34473-6。

[hashhist-12] 1 2 3 4 5 6 7 8 9 10 11 12 Mehta, Dinesh P.; Mehta, Dinesh P.; Sahni, Sartaj 編 (2004). Handbook of Data Structures and Applications . doi : 10.1201/9781420035179 . ISBN 978-0-429-14701-2。

[13] コーメン、TH; CE、ライザーソン。Rivest, ルイジアナ州;スタイン、C. (2009)。アルゴリズム入門(第 3版)。MIT を押します。

[cornell08-14] 1 2 3 4 5 6 7 Mayers, Andrew (2008). "CS 312: ハッシュテーブルと償却分析" .コーネル大学、コンピュータサイエンス学部。2021年4月26日のオリジナルからアーカイブ済み。 2021年10月26日にcs.cornell.edu経由で取得。

[plank-15] 1 2 James S. Plank および Brad Vander Zanden。「CS140 講義ノート - ハッシュ」。

[16] Maurer, WD; Lewis, TG (1975 年 3 月). "ハッシュテーブルメソッド". ACM Computing Surveys . 7 (1): 5–19 . doi : 10.1145/356643.356645 . S2CID 17874775 .

[owo03-17] 1 2 Owolabi, Olumide (2003 年 2 月). 「いくつかのハッシュ関数の経験的研究」. Information and Software Technology . 45 (2): 109–112 . doi : 10.1016/S0950-5849(02)00174-X .

[Yi06-18] 1 2 Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006). Perfect Hashing for Network Applications . 2006 IEEE International Symposium on Information Theory. pp. 2774–2778 . doi : 10.1109/ISIT.2006.261567 . ISBN 1-4244-0505-X. S2CID 1494710 .

[CHD-19] Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009). "Hash, displace, and compress" (PDF) . Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7–9, 2009, Proceedings . Lecture Notes in Computer Science . Vol. 5757. Berlin: Springer. pp. 682– 693. CiteSeerX 10.1.1.568.130 . doi : 10.1007/978-3-642-04128-0_61 . MR 2557794 .

[cormenalgo01-20] 1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「第 11 章: ハッシュテーブル」.アルゴリズム入門(第 2版).マサチューセッツ工科大学. ISBN 978-0-262-53196-2。

[21] ストロストルップ、ビャルネ (1997). C++ プログラミング言語第 3 版. マサチューセッツ州リーディング: Addison-Wesley. p. 503. ISBN 0-201-88954-4。

[chernoff-22] Pearson, Karl (1900). 「相関のある変数体系の場合、確率からの偏差の与えられた体系が、ランダムサンプリングから生じたと合理的に想定できるような基準について」 . Philosophical Magazine . Series 5. 50 (302): 157– 175. doi : 10.1080/14786440009463897 .

[plackett-23] Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review . 51 (1): 59–72 . doi : 10.2307/1402731 . JSTOR 1402731 .

[:0-24] 1 2 Wang, Thomas (1997 年 3 月)。「Prime Double Hash Table」。1999年 9 月 3 日のオリジナルからアーカイブ。2015年5 月 10 日取得。

[25] Wegman, Mark N.; Carter, J.Lawrence (1981 年 6 月) 「新しいハッシュ関数と認証および集合等価性におけるその使用」 . Journal of Computer and System Sciences . 22 (3): 265– 279. Bibcode : 1981JCoSS..22..265W . doi : 10.1016/0022-0000(81)90033-7 .

[26] Demaine, Erik; Lind, Jeff (2003年春)。「講義2」（PDF）。6.897 ：高度なデータ構造。MITコンピュータ科学・人工知能研究所。2010年6月15日のオリジナルからアーカイブ（PDF）。 2008年6月30日取得。

[nick05-27] 1 2 3 Culpepper, J. Shane; Moffat, Alistair (2005). "Enhanced Byte Codes with Restricted Prefix Properties". String Processing and Information Retrieval . Lecture Notes in Computer Science. Vol. 3772. pp. 1–12 . doi : 10.1007/11575832_1 . ISBN 978-3-540-29740-6。

[28] Willard, Dan E. (2000). "融合木の観点から計算幾何学、ファン・エムデ・ボアス木、ハッシュを考察する". SIAM Journal on Computing . 29 (3): 1030–1049 . doi : 10.1137/S0097539797322425 . MR 1740562 . 。

[29] Askitis, Nikolas; Sinha, Ranjan (2010年10月)「文字列のためのスケーラブルでキャッシュとスペース効率の良いトライのエンジニアリング」The VLDB Journal . 19 (5): 633–660 . doi : 10.1007/s00778-010-0183-9 .

[30] Askitis, Nikolas; Zobel, Justin (2005年10月)「文字列ハッシュテーブルにおけるキャッシュを考慮した衝突解決」第12回国際文字列処理・情報検索会議（SPIRE 2005）論文集、第3772巻/2005年、 91～ 102ページ、doi : 10.1007/11575832_11、ISBN 978-3-540-29740-6。

[31] Askitis, Nikolas (2009). "整数キーのための高速かつコンパクトなハッシュテーブル" (PDF) .第32回オーストラリアコンピュータサイエンス会議 (ACSC 2009) 議事録. 第91巻113–122ページISBN 978-1-920682-72-92011年2月16日にオリジナル（PDF）からアーカイブされました。 2010年6月13日に取得。

[tenenbaum90-32] テネンバウム、アーロン M.ランサム、イェディヤ。オーゲンシュタイン、モーシェ J. (1990)。C を使用したデータ構造。プレンティス・ホール。456～ 461ページ、456ページ472.ISBN 978-0-13-199746-2。

[Cuckoo-33] 1 2パグ、ラスムス;ロドラー、フレミング・フリッシュ (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。

[clrs-34] 1 2 3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), "11 ハッシュテーブル", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill , pp. 221–252 , ISBN 0-262-03293-7。

[chen87-35] 1 2 3 Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing . New York, United States: Oxford University Press . ISBN 978-0-19-504182-8– Archive.org経由。

[36] パー、ラスムス;ロドラー、フレミング・フリッシュ (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。

[nir08-37] 1 2 3 4 5 6 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "ホップスコッチハッシュ".分散コンピューティング. Lecture Notes in Computer Science. Vol. 5218. pp. 350–364 . doi : 10.1007/978-3-540-87779-0_24 . ISBN 978-3-540-87778-3。

[waterloo86-38] 1 2セリス、ペドロ（1986）。ロビンフッドハッシュ(PDF)。カナダ、オンタリオ州:ウォータールー大学、コンピューターサイエンス学部。ISBN 978-0-315-29700-5. OCLC 14083698 . 2021年11月1日にオリジナルからアーカイブ（PDF）されました。2021年11月2日に取得。

[39] Poblete, PV; Viola, A. (2019年7月) 「ランダムプロービングモデルにおけるロビンフッドとその他のハッシュアルゴリズムの分析（削除ありとなし）」 . Combinatorics, Probability and Computing . 28 (4): 600– 617. doi : 10.1017/S0963548318000408 . S2CID 125374363 .

[cornell14-40] クラークソン、マイケル (2014)。「講義 13: ハッシュテーブル」。コーネル大学、コンピュータサイエンス学部。2021年 10 月 7 日のオリジナルからアーカイブ済み。2021年11 月 1 日取得– cs.cornell.edu 経由。

[41] Gries, David (2017). "JavaHyperTextとデータ構造：ロビンフッドハッシュ" (PDF) .コーネル大学、コンピュータサイエンス学部。2021年4月26日のオリジナルからアーカイブ(PDF) 。2021年11月2日に取得– cs.cornell.edu経由。

[indiana88-42] Celis, Pedro (1988年3月28日). External Robin Hood Hashing (PDF) (技術報告書). Bloomington, Indiana: Indiana University , Department of Computer Science. 246. 2021年11月3日にオリジナルからアーカイブ(PDF) 。 2021年11月2日に取得。

[43] Goddard, Wayne (2021). "Chapter C5: Hash Tables" (PDF) . Clemson University . pp. 15–16 . 2023年12月4日取得.

[44] Devadas, Srini; Demaine, Erik (2011年2月25日). "アルゴリズム入門: ハッシュテーブルのサイズ変更" (PDF) .マサチューセッツ工科大学、コンピュータサイエンス学科。2021年5月7日のオリジナルからアーカイブ(PDF) 。2021年11月9日にMIT OpenCourseWare経由で取得。

[45] Thareja, Reema (2014). "ハッシュと衝突". Data Structures Using C. Oxford University Press. pp. 464–488 . ISBN 978-0-19-809930-7。

[scott03-46] 1 2 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経由。

[47] Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing" (PDF) . Proc. 6th Conference on Very Large Databases . Carnegie Mellon University . pp. 212– 223. 2021 年 5 月 6 日のオリジナルからアーカイブ(PDF) 。2021年11 月 10 日取得– cs.cmu.edu 経由。

[dijk10-48] 1 2 Dijk, Tom Van (2010). "ハッシュテーブルのパフォーマンスの分析と改善" (PDF) .オランダ:トゥエンテ大学. 2021年11月6日のオリジナルからアーカイブ(PDF) . 2021年12月31日取得.

[49] Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). "第2章：探索". Atallah (編)『アルゴリズムと計算理論ハンドブック』CRC Press. pp. 2–6 . ISBN 0849326494。

[50] レフ・バナコウスキー。「インデックスと外部ソート」。pl:Polsko-Japońska Akademia Technik Komputerowych。2022年3月26日のオリジナルからアーカイブ。2022 年3 月 26 日に取得。

[51] Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (2020年2月)「セルラーネットワークをオーバーレイするデバイス間通信におけるキャッシュヒット率の最大化」China Communications . 17 (2): 232– 238. Bibcode : 2020CComm..17b.232Z . doi : 10.23919/jcc.2020.02.018 . S2CID 212649328 .

[52] Bottommley, James (2004年1月1日). 「キャッシングの理解」 . Linux Journal . 2020年12月4日のオリジナルからアーカイブ済み。 2022年4月16日取得。

[53] Jill Seaman (2014). "Set & Hash Tables" (PDF) . Texas State University . 2022年4月1日時点のオリジナルよりアーカイブ済み。 2022年3月26日取得。{{cite web}}: CS1 maint: bot: 元の URL の状態が不明です (リンク)

[54] "転置表 - チェスプログラミング wiki" . chessprogramming.org . 2021年2月14日のオリジナルからアーカイブ済み。2020年5月1日に取得。

[55] 「JavaScript のデータ型とデータ構造 - JavaScript | MDN」。developer.mozilla.org。2022年7 月 24 日取得。

[56] "マップ - JavaScript | MDN" . developer.mozilla.org . 2023年6月20日. 2023年7月15日取得.

[57] 「プログラミング言語 C++ - 技術仕様書」（PDF）。国際標準化機構。pp. 812–813 。 2022年1月21日にオリジナル（PDF）からアーカイブ。2022年2月8日に取得。

[58] 「Goプログラミング言語仕様」 . go.dev . 2023年1月1日取得。

[59] "レッスン: 実装 (Java™ チュートリアル > コレクション)" . docs.oracle.com . 2017 年 1 月 18 日のオリジナルからアーカイブ済み。2018年4 月 27 日取得。

[60] Zhang, Juan; Jia, Yunwei (2020). "機械学習に基づくRedisリハッシュ最適化" . Journal of Physics: Conference Series . 1453 (1): 3. Bibcode : 2020JPhCS1453a2048Z . doi : 10.1088/1742-6596/1453/1/012048 . S2CID 215943738 .

[61] Jonan Scheffler (2016年12月25日)。「Ruby 2.4 リリース: ハッシュの高速化、統一整数、丸め処理の改善」。heroku.com 。2019年7月3日のオリジナルからアーカイブ済み。 2019年7月3日に取得。

[62] "doc.rust-lang.org"。2022年12月8日にオリジナルからアーカイブされました。2022年12月14日に取得。

[63] "HashSet クラス (System.Collections.Generic)" . learn.microsoft.com . 2023 年7 月 1 日取得.

[64] tnet-bot. "Dictionary Class (System.Collections.Generic)" . learn.microsoft.com . 2024年1月16日取得.

[65] "VB.NET HashSet の例" . Dot Net Perls .

[ a ]

[ 2 ]

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[

[

[

[

[ 12 ]

13

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[

[

[

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[

[ 37 ]

[

[

40

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[

[ 46 ]

[

48

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[

[

[

[ 60 ]

[ 61 ]

62 ] [

63 ] C

[ 64 ]

[ 1 ]

歴史

概要

負荷率

別個のチェーンに対する荷重係数

オープンアドレッシングの負荷係数

ハッシュ関数

整数宇宙の仮定

除算によるハッシュ化

乗算によるハッシュ化

文字列ハッシュ

ハッシュ関数の選択

衝突解決

Separate chaining

Other data structures for separate chaining

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

オープンアドレッシング

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

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

結合ハッシュ

カッコウハッシュ

ホップスコッチハッシュ

ロビンフッドのハッシュ化

動的なサイズ変更

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

一括再検討の代替案

線形ハッシュ

パフォーマンス

アプリケーション

連想配列

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

キャッシュ

セット

転置表

実装

関連項目

注記

参考文献

さらに読む

外部リンク