ハッシュ表

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

ハッシュ表
タイプ順序付けられていない連想配列
発明された1953年
ビッグO表記時間計算量
アルゴリズム 平均 最悪の場合
スペース O(n[1] O(n
検索 O(1) O(n
入れる O(1) O(n
消去 O(1) O(n
ハッシュテーブルとしての小さな電話帳

コンピューティングでは、ハッシュテーブルハッシュマップ)は、連想配列の抽象データ型を実装するデータ構造であり、キーにマップできる構造ですハッシュテーブルは、ハッシュ関数を使用して、ハッシュコードとも呼ばれるインデックスを計算し、バケットまたはスロットの配列に入れます。このインデックスから、目的の値を見つけることができます。ルックアップ中に、キーがハッシュされ、結果のハッシュは、対応する値が格納されている場所を示します。

理想的には、ハッシュ関数は各キーを一意のバケットに割り当てますが、ほとんどのハッシュテーブルの設計では不完全なハッシュ関数が採用されているため、ハッシュ関数が複数のキーに対して同じインデックスを生成するハッシュ衝突が発生する可能性があります。このような衝突は通常、何らかの方法で対処されます。

適切にディメンション化されたハッシュテーブルでは、各ルックアップの平均コスト(命令の数)は、テーブルに格納されている要素の数とは無関係です。多くのハッシュテーブルの設計では、キーと値のペアを任意に挿入および削除することもできます償却[2])。操作あたりの平均コストは一定です。[3] [4]

多くの場合、ハッシュテーブルは、検索ツリーやその他のテーブルルックアップ構造よりも平均して効率的であることがわかります。このため、これらは多くの種類のコンピュータソフトウェア、特に連想配列データベースインデックス作成キャッシュ、およびセットで広く使用されています。

歴史

ハッシュのアイデアは、さまざまな場所で独立して生まれました。1953年1月、Hans Peter Luhnは、チェーンを使用したハッシュを使用したIBMの内部覚書を作成しました。[5] Gene AmdahlElaine M. McGrawNathaniel Rochester、およびArthur Samuelは、ほぼ同時にハッシュを使用してプログラムを実装しました。線形プロービング(互いに素なステッピング)を使用したオープンアドレッシングはAmdahlの功績によるものですが、Ershov(ロシア)も同じ考えを持っていました。[5]

ハッシュ

ハッシュを使用する利点は、レコードのテーブルアドレスをキーから直接計算できることです。ハッシュは関数を意味します 、キーに適用した場合、ハッシュを生成しますしかし、潜在的に大きくなる可能性がある場合、ハッシュ結果はハッシュテーブル(またはスロット)の有限エントリにマップする必要があります。いくつかの方法を使用して、キーをハッシュテーブルのサイズにマップできます。最も一般的な方法は除算法で、スロットの計算にモジュラー演算が使用されます。[6] :110 

これは多くの場合、2つのステップで行われます。

ハッシュ関数の選択

基本的な要件は、関数がハッシュ値の一様分布を提供する必要があることです。不均一な分布は、衝突の数とそれらを解決するためのコストを増加させます。均一性は、設計によって保証するのが難しい場合がありますが、統計的検定、たとえば、離散一様分布のピアソンのカイ2乗検定を使用して経験的に評価できます。[7] [8]

分散は、アプリケーションで発生するテーブルサイズに対してのみ均一である必要があります。特に、テーブルサイズを正確に2倍および2倍にする動的サイズ変更を使用する場合、ハッシュ関数は、サイズが2の累乗である場合にのみ均一である必要があります。ここで、インデックスはハッシュ関数のビットの範囲として計算できます。一方、一部のハッシュアルゴリズムでは、サイズを素数にすることを好みます。[9]モジュラス演算は、いくつかの追加の混合を提供する場合があります。これは、ハッシュ関数が不十分な場合に特に役立ちます。

オープンアドレッシングスキームの場合、ハッシュ関数はクラスタリング、つまり2つ以上のキーの連続するスロットへのマッピングも回避する必要がありますこのようなクラスタリングにより、負荷率が低く、衝突の頻度が低い場合でも、ルックアップコストが急騰する可能性があります。人気のある乗法ハッシュ[3]は、クラスタリングの動作が特に悪いと言われています。[9]

暗号化ハッシュ関数は、モジュロリダクションまたはビットマスキングのいずれかによって、任意のテーブルサイズに適したハッシュ関数を提供すると考えられていますまた、悪意のあるユーザーがサーバーのハッシュテーブルに多数の衝突を生成するように設計されたリクエストを送信してネットワークサービスを妨害しようとするリスクがある場合にも適切です。ただし、より安価な方法(データにシークレットソルトを適用するなど)によって妨害のリスクを回避することもできます。暗号化ハッシュ関数の欠点は、計算が遅くなることが多いことです。つまり、任意のサイズの均一性が必要ない場合は、非暗号化ハッシュ関数の方が望ましい場合があります。[要出典]

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

ユニバーサルハッシュ関数は、ハッシュ関数が関数によってハッシュされるキーから独立している方法で、ハッシュ関数をランダムに選択するアプローチです。セットからの2つの異なるキー間の衝突の可能性はどこカーディナリティです[10] :264 

完璧なハッシュ関数

すべてのキーが事前にわかっている場合は、完全なハッシュ関数を使用して、衝突のない完全なハッシュテーブルを作成できます。[11]最小限の完全なハッシュが使用される場合、ハッシュテーブル内のすべての場所も使用できます。[12]

完全なハッシュにより、すべての場合で一定時間のルックアップが可能になります。これは、ルックアップの時間が平均して短いが、たとえばすべてのキーがいくつかの値にハッシュされる場合など、 非常に長くなる可能性があるほとんどのチェーンおよびオープンアドレス法とは対照的です。

主な統計

ハッシュテーブルの重要な統計は、次のように定義される 負荷率です。

どこ

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

ハッシュテーブルのパフォーマンスは、負荷率に関連して悪化します()すなわちとしてアプローチ1。したがって、負荷率が理想値を超えた場合は、ハッシュテーブルのサイズを変更する(つまり「再ハッシュ」する)ことが不可欠です。サイズが小さい場合は、ハッシュテーブルのサイズを変更することも効率的です。これは通常、負荷率が下がったときに行われます。[13]一般に、0.6および0.75の負荷率が許容値です。[14] [6] :110 

衝突の解決

ハッシュを使用する検索アルゴリズムは、2つの部分で構成されています。最初の部分は、検索キーを配列インデックスに変換するハッシュ関数を計算することです。理想的なケースは、2つの検索キーが同じ配列インデックスにハッシュされない場合ですが、理論的には不可能であるため、常にそうであるとは限りません。[15] :515 したがって、アルゴリズムの2番目の部分は衝突解決です。衝突解決の2つの一般的な方法は、個別のチェーンとオープンアドレス法です。[16] :458 

個別の連鎖

個別の連鎖によって解決されたハッシュ衝突
バケット配列内のヘッドレコードとの個別のチェーンによるハッシュ衝突。

ハッシュは時空のトレードオフの一例です。メモリが無限であるという条件が存在する場合、(潜在的に巨大な)配列のインデックスとしてキーを使用する単一のメモリアクセスは値を取得します。これは、可能なキー値が巨大であることも意味します。一方、時間が無限の場合は、値を可能な限り最小限のメモリに格納し、配列を介した線形検索を使用して要素を取得できます。[16] :458 個別の連鎖では、プロセスには、キーと値のペアを持つリンクリストの構築が含まれます検索配列インデックスごとに。衝突したアイテムは、単一のリンクリストを介してチェーンされ、一意の検索キーを使用してアイテムにアクセスするためにトラバースできます。[16] :464 連鎖による、つまりリンクリストを使用した衝突解決は、一般的な実装方法です。させてそれぞれハッシュテーブルとノードである場合、操作には次のようになります。[10] :258 

Chained-Hash-Insert(T、x)
  挿入リンクリストの先頭に 
連鎖ハッシュ検索(T、k) キーを持つ要素を検索しますリンクリスト内
連鎖-ハッシュ-削除(T、x) 消去リンクリストから

要素のキーが順序付けられている場合、キーが数値的または字句的に比較可能であるときに順序を維持することによってアイテムを挿入するのが効率的であるため、挿入が高速になり、検索が失敗します。[15] :520-521 ただし、リンクリストを使用する標準的な方法は、リストのノードがメモリ全体に分散しているため、空間的な局所性参照の局所性)がほとんどないため、キャッシュを意識しません。 CPUキャッシュの効率的な使用[17] :91 

他の構造との個別の連鎖

キーが順序付けられている場合、自己バランス二分探索木を使用するなどの「自己組織化」の概念を使用すると効率的である可能性があります、それは追加の複雑さを導入しますが。[15] :521 

キャッシュを意識したバリアントでは、リンクリストまたは自己平衡型バイナリ検索ツリーが通常、個別のチェーンを介した衝突解決のために展開される場所で、よりキャッシュに適していることがわかっ動的配列が使用されます。これは、配列の連続した割り当てパターンが原因であるためです。トランスレーションルックアサイドバッファなどのハードウェアキャッシュプリフェッチャーによって悪用される可能性があり、その結果、アクセス時間とメモリ消費が削減されます。[18] [19] [20]

動的完全ハッシュでは、2つのレベルのハッシュテーブルを使用して、ルックアップの複雑さを軽減し、保証します。最悪の場合。このテクニックでは、エントリは、完全なハッシュテーブルとして編成されます一定の最悪の場合のルックアップ時間を提供し、挿入のための低い償却時間を提供するスロット。[21]ある研究では、高負荷下での標準のリンクリスト方式と比較した場合、アレイベースの個別チェーンのパフォーマンスが97%向上することが示されています。[17] :99 

各バケットにフュージョンツリーを使用するなどの手法でも、すべての操作で一定の時間が発生する可能性が高くなります。[22]

オープンアドレス法

線形プロービング(間隔= 1)を使用したオープンアドレス法によって解決されたハッシュ衝突。「TedBaker」には固有のハッシュがありますが、それでも以前に「JohnSmith」と衝突した「SandraDee」と衝突したことに注意してください。
このグラフは、大きなハッシュテーブル(キャッシュのサイズをはるかに超える)で要素を検索するために必要なCPUキャッシュミスの平均数を、チェーンおよび線形プロービングと比較しています。線形プロービングは、参照の局所性が優れているためパフォーマンスが向上しますが、テーブルがいっぱいになると、パフォーマンスが大幅に低下します。

オープンアドレッシングと呼ばれる別の戦略では、すべてのエントリレコードがバケット配列自体に格納されます。新しいエントリを挿入する必要がある場合は、ハッシュされたスロットから開始して、占有されていないスロットが見つかるまで、いくつかのプローブシーケンスでバケットが検査されます。エントリを検索するとき、ターゲットレコードが見つかるか、未使用の配列スロットが見つかるまで、バケットが同じ順序でスキャンされます。これは、テーブルにそのようなキーがないことを示します。[23]「オープンアドレス法」という名前は、アイテムの場所(「アドレス」)がハッシュ値によって決定されないことを意味します。(この方法は クローズドハッシュとも呼ばれます。通常は個別のチェーンを意味する「オープンハッシュ」または「クローズドアドレッシング」と混同しないでください。

よく知られているプローブシーケンスは次のとおりです。

  • 線形プロービング。プローブ間の間隔は固定されています(通常は1)。スロットは連続した場所に配置されているため、線形プロービングは、参照の局所性により、 CPUキャッシュの使用率を向上させる可能性があります。[24]
  • 二次プロービング。元のハッシュ計算によって与えられた開始値に二次多項式の連続する出力を追加することにより、プローブ間の間隔が増加します。
  • ダブルハッシュ。プローブ間の間隔は2番目のハッシュ関数によって計算されます。

実際には、衝突解決のためにバケットの配列と組み合わせて使用​​すると、オープンアドレッシングのパフォーマンスは個別のチェーンよりも遅くなります[17] :93 。負荷率は1に近づきます。[13]負荷率が1に達すると(完全にテーブルがいっぱいの場合)、検索ミスがテーブルを介して無限ループになるため、負荷率を1未満に維持する必要があります。[16] :471 線形プロービング平均コストは、選択したハッシュ関数がテーブル全体にキーを均一に分散して回避できるかどうかによって異なります。クラスター化は、クラスターの形成により検索時間が長くなり、非効率になるためです。[16] :472 

合体ハッシュ

結合ハッシュは、バケットまたはノードがテーブル内でリンクする、個別のチェーンとオープンアドレッシングの両方のハイブリッドです。[25] :6–8 このアルゴリズムは、固定メモリ割り当てに最適です[25] :4 この方法は、次の衝突ノードの位置を追跡する各バケットへのポインターパラメーターを提供し、元のインデックスで衝突した各ノードの追跡可能なチェーンを作成するという点で、個別のチェーンに似ています。また、挿入されたすべての要素が、ハッシュ関数が最初に割り当てたインデックスに特に配置されているわけではないため、オープンアドレス法の傘下にも当てはまります。これは、個別の連鎖に見られる特性ではありません。合体ハッシュの衝突は、ハッシュテーブルでインデックスが最大の空のスロットを特定することで解決され、衝突する値がそのスロットに挿入されます。バケットのポインタは、衝突するハッシュアドレスを含む挿入されたノードの場所にリンクされています。[25] :8 

合体ハッシュのパフォーマンスは、すべてのバリアントの中で最高の1つです。[26]「合体ハッシュの実装」というタイトルの比較研究で、ジェフリー・スコット・ビッターは、平均して、合体ハッシュが線形プロービング、ダブルハッシュ、セパレートチェーンなどの他の方法を実行することを発見しました。 60%。ただし、合体ハッシュを使用した削除の最悪のケースは非常にコストがかかり、最も悪名高い欠点です。潜在的に長いポインタのチェーンをたどるだけでなく、削除が発生すると、ハッシュテーブルからの要素の削除を考慮して、ポインタを再割り当てする必要があります。これは非常に複雑なプロセスであることがわかります。

カッコウハッシュ

カッコウハッシュは、保証を提供するオープンアドレッシング衝突解決技術の形式です。最悪の場合のルックアップの複雑さと挿入のための一定の償却時間。衝突は、それぞれが独自のハッシュ関数を持つ2つのハッシュテーブルを維持することで解決され、衝突したスロットは指定されたアイテムに置き換えられ、スロットの占有された要素は他のハッシュテーブルに置き換えられます。このプロセスは、すべてのキーがテーブルの空のバケットに独自の場所を持つまで続きます。プロシージャが無限ループに入った場合(しきい値ループカウンタを維持することで識別されます)、両方のハッシュテーブルが新しいハッシュ関数で再ハッシュされ、プロシージャが続行されます。[27] :124–125 

石けり遊びのハッシュ

石けり遊びハッシュは、カッコウハッシュ線形プロービング、バケットの近隣の概念を介したチェーンの要素を組み合わせたオープンアドレッシングベースのアルゴリズムです。これは、「仮想」バケットとも呼ばれる、任意の占有バケットの周囲の後続バケットです。[28] :351–352 アルゴリズムは、ハッシュテーブルの負荷率が90%を超えたときに、より優れたパフォーマンスを提供するように設計されています。また、同時設定で高いスループットを提供するため、サイズ変更可能な同時ハッシュテーブルの実装に最適です[28] :350 石けり遊びハッシュの近傍特性は、近傍内の任意のバケットから目的のアイテムを見つけるコストが、バケット自体でそれを見つけるコストに非常に近いという特性を保証します。アルゴリズムは、他のアイテムを置き換えるためにコストがかかる可能性があるため、その近隣にアイテムを入れようとします。[28] :352 

ハッシュテーブル内の各バケットには、追加の「ホップ情報」が含まれています。これは、 H -1エントリ内の現在の仮想バケットに最初にハッシュされたアイテムの相対距離を示すためのHビットビット配列です。[28] :352 みましょう挿入されるキーと、キーがハッシュされるバケットになります。アルゴリズムの近傍特性が誓約されるように、挿入手順にはいくつかのケースが関係しています。[28] :352-353  if空で、要素が挿入され、ビットマップの左端のビットが1に設定されます。空でない場合は、テーブル内の空のスロットを見つけるために線形プロービングが使用され、バケットのビットマップが更新されてから挿入されます。空のスロットが近傍の範囲内にない場合、つまりH -1の場合、各バケットの後続のスワップおよびホップ情報ビット配列操作は、その近傍不変プロパティに従って実行されます[28] :353 

石けり遊びのハッシュは非周期的です。つまり、カッコウのハッシュのように無限ループに陥ることはありません。このため、ハッシュテーブルがいっぱいの場合、または負荷率が小さい場合は、カッコウハッシュよりもうまく機能します。カッコウハッシュでは、衝突後の挿入の成功はハッシュ関数に依存しますが、ホップスコッチハッシュではそうではありません。単純なハッシュ関数は、パフォーマンスに大きな違いがなく、複雑なハッシュ関数と同じ結果を得ることができます。

ロビンフッドハッシュ

ロビンフードハッシュは、オープンアドレッシングベースの衝突解決アルゴリズムです。衝突は、その「ホームロケーション」、つまりアイテムがハッシュされたバケットから最も遠い、または最長のプローブシーケンス長(PSL)の要素の変位を優先することによって解決されます。[29] :12 ロビンフードハッシュは理論的な検索コストを変更しませんが、バケット上のアイテム分布の分散に大きく影響します。 [30] :2 つまり、ハッシュテーブルでのクラスター形成の処理です。[31]ロビンフードハッシュを使用するハッシュテーブル内の各ノードは、追加のPSL値を格納するために拡張する必要があります。[32]しましょう挿入するキーになります、(インクリメンタル)PSLの長さハッシュテーブルになり、インデックスとして、挿入手順は次のとおりです。[29] :12-13  [33] :5 

  • もしも:反復は、外部プローブを試行せずに次のバケットに入ります。
  • もしも:アイテムを挿入バケツに; スワップ-なるがままに; からプローブを続行します挿入するstバケット; すべての要素が挿入されるまで、この手順を繰り返します。

動的サイズ変更

挿入を繰り返すと、ハッシュテーブルのエントリ数が増え、その結果、負荷率が高くなります。償却を維持するためルックアップおよび挿入操作のパフォーマンスでは、ハッシュテーブルのサイズが動的に変更され、テーブルのアイテムが新しいハッシュテーブルのバケットに再ハッシュされます[13]。テーブルサイズが異なるとハッシュ値が異なるため、アイテムをコピーできないためです。モジュロ演算による[34]過度のメモリ使用を避けるために、サイズに比べてエントリが少ないハッシュテーブルでサイズ変更を実行できます[35]

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

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

オールアットワンスリハッシュの代替手段

一部のハッシュテーブルの実装、特にリアルタイムシステムでは、タイムクリティカルな操作を中断する可能性があるため、ハッシュテーブルを一度に拡大する代償を払うことができません。動的なサイズ変更を回避できない場合、解決策は、再ハッシュ中のストレージブリップ(通常は新しいテーブルのサイズの50%)を回避し、メモリ断片回避して、古いハッシュテーブル。[37] :2–3 このような場合、再ハッシュ操作は、ハッシュテーブルのバケットが変更されないままになるように、古いハッシュテーブルに割り当てられた以前のメモリブロックを拡張することによって段階的に実行されます。償却再ハッシュの一般的なアプローチには、2つのハッシュ関数を維持することが含まれます新しいハッシュ関数に従ってバケットのアイテムを再ハッシュするプロセスは、クリーニングと呼ばれます。これは、次のような操作をカプセル化することにより、コマンドパターンを介して実装されます。を通して バケット内の各要素が再ハッシュされ、その手順が次のようになるようなラッパー: [37] :3 

  • 綺麗バケツ。
  • 綺麗バケツ。
  • コマンドが実行されます

線形ハッシュ

線形ハッシュは、一度に1バケットずつテーブルの動的な拡大または縮小を可能にするハッシュテーブルの実装です。[38]

分散ハッシュテーブルのハッシュ

テーブルのサイズ変更のコストを削減する別の方法は、テーブルのサイズ変更時にほとんどの値のハッシュが変更されないようにハッシュ関数を選択することです。このようなハッシュ関数は、ディスクベースの分散ハッシュテーブルで広く使用されており、再ハッシュには非常にコストがかかります。テーブルのサイズが変更されたときにほとんどの値が変更されないようにハッシュを設計する問題は、分散ハッシュテーブルの問題として知られています。最も一般的な4つのアプローチは、ランデブーハッシュコンシステントハッシュコンテンツアドレス可能ネットワークアルゴリズム、およびKademlia距離です。

パフォーマンス

ハッシュテーブルのパフォーマンスは、準乱数を生成するハッシュ関数の能力に依存します)ハッシュテーブルのエントリの場合キー、バケット数、およびハッシュ関数を示します。ハッシュ関数が同じものを生成する場合個別のキーの場合()、これにより衝突が発生します。これはいくつかの方法で処理する必要があります。一定の時間計算量()ハッシュテーブルでの操作は、ハッシュ関数が衝突するインデックスを生成しないことを前提としています。したがって、ハッシュテーブルのパフォーマンスは、インデックスを分散するために選択したハッシュ関数の能力に正比例します。[39] :1 ただし、このようなハッシュ関数の構築は実際には実行不可能です。そのため、実装は、より高いパフォーマンスを実現するために、ケース固有の衝突解決手法に依存します。[39] :2 

アプリケーション

連想配列

ハッシュテーブルは、多くの種類のメモリ内テーブルを実装するために一般的に使用されます。これらは、連想配列を実装するために使用されます。[40]

データベースの索引付け

ハッシュテーブルは、ディスクベースのデータ構造およびデータベースインデックスdbmなど)としても使用できますが、これらのアプリケーションではBツリーの方が一般的です。マルチノードデータベースシステムでは、ハッシュテーブルは通常、ノード間で行を分散するために使用され、ハッシュ結合のネットワークトラフィックを削減します。

キャッシュ

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

セット

特定のキーを持つエントリを回復することに加えて、多くのハッシュテーブル実装は、そのようなエントリが存在するかどうかも判断できます。

したがって、これらの構造を使用して、特定のキーが指定されたキーのセットに属しているかどうかを記録するだけのセットデータ構造[41]を実装できますこの場合、エントリ値に関係するすべての部分を削除することにより、構造を単純化できます。ハッシュは、静的セットと動的セットの両方を実装するために使用できます。

オブジェクト表現

PerlPythonJavaScriptLuaRubyなどのいくつかの動的言語は、ハッシュテーブルを使用してオブジェクトを実装します。この表現では、キーはオブジェクトのメンバーとメソッドの名前であり、値は対応するメンバーまたはメソッドへのポインターです。

独自のデータ表現

一部のプログラムでは、ハッシュテーブルを使用して、同じ内容の複数の文字列が作成されないようにすることができます。そのために、プログラムで使用されているすべての文字列は、ハッシュテーブルとして実装された単一の文字列プールに格納されます。このプールは、新しい文字列を作成する必要があるたびにチェックされます。この手法は、ハッシュconsingという名前でLispインタープリターに導入され、他の多くの種類のデータ(シンボリック代数システムの式ツリーデータベースのレコード、ファイルシステムのファイル、二分決定図など)で使用できます。 。

転置テーブル

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

実装

プログラミング言語で

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

C ++ 11には、任意の型unordered_mapのキーと値を格納するための標準ライブラリが含まれています[43]

Javaプログラミング言語には、、、、およびHashSetジェネリックコレクション含まれます。[44]HashMapLinkedHashSetLinkedHashMap

Pythonの組み込みは、dictの形式でハッシュテーブルを実装します[45]

Rubyハッシュテーブルは、Ruby2.4以降のオープンアドレッシングモデルを使用します。[46]

も参照してください

参考文献

  1. ^ コルメン、トーマスH .; レイザーソン、チャールズE。; リベスト、ロナルドL。; スタイン、クリフォード(2009)。アルゴリズム入門(第3版)。マサチューセッツ工科大学。pp。253–280。ISBN  978-0-262-03384-8
  2. ^ Charles E. Leiserson償却アルゴリズム、テーブルダブリング、ポテンシャル法 2009年8月7日、 Wayback Machine Lecture 13、コースMIT 6.046J / 18.410Jアルゴリズム入門— 2005年秋
  3. ^ a b Knuth、ドナルド(1998)。The Art of ComputerProgramming3:並べ替えと検索(第2版)。アディソン-ウェスリー。pp。513–558。ISBN  978-0-201-89685-5
  4. ^ コルメン、トーマスH .; レイザーソン、チャールズE。; リベスト、ロナルドL。; スタイン、クリフォード(2001)。「第11章:ハッシュテーブル」。アルゴリズム入門(第2版)。MITPressとMcGraw-Hill。pp。221–252  _ ISBN 978-0-262-53196-2
  5. ^ a b Mehta、Dinesh P。; サルタージ・サーニ(2004年10月28日)。データ構造とアプリケーションのハンドブックp。9-15。ISBN 978-1-58488-435-4
  6. ^ a b Owolabi、Olumide(2003年2月1日)。「いくつかのハッシュ関数の実証的研究」情報およびソフトウェア技術ポートハーコート大学数学およびコンピュータサイエンス学部。45(2)。doi10.1016 / S0950-5849(02)00174-X –ScienceDirect経由
  7. ^ ピアソン、カール(1900)。「変数の相関システムの場合の可能性からの偏差の所与のシステムは、それがランダムサンプリングから生じたと合理的に推測できるようなものであるという基準に基づいて」フィロソフィカルマガジンシリーズ5.50(302):157–175。土井10.1080 / 14786440009463897
  8. ^ プラケット、ロビン(1983)。「カール・ピアソンとカイ二乗検定」。国際統計レビュー51(1):59–72。土井10.2307 / 1402731JSTOR1402731_  
  9. ^ a b Wang、Thomas(1997年3月)。「プライムダブルハッシュテーブル」1999年9月3日にオリジナルからアーカイブされました2015年5月10日取得
  10. ^ a b コルメン、トーマスH .; レイザーソン、チャールズE。; リベスト、ロナルドL。; スタイン、クリフォード(2001)。「第11章:ハッシュテーブル」。アルゴリズム入門(第2版)。マサチューセッツ工科大学ISBN 978-0-262-53196-2
  11. ^ ルー、イー; プラバカール、バラジ; Bonomi、Flavio(2006)、「ネットワークアプリケーションのパーフェクトハッシュ」、2006 IEEE International Symposium on Information Theory:2774–2778、doi10.1109 / ISIT.2006.261567
  12. ^ Belazzougui、Djamal; ボテリョ、ファビアーノC。; Dietzfelbinger、Martin(2009)、"Hash、displace、and compress" (PDF)Algorithms—ESA 2009:17th Annual European Symposium、Copenhagen、Denmark、September 7-9、2009、Proceedings(PDF)Lecture Notes in Computer Science、vol。5757、ベルリン:Springer、pp。682–693、CiteSeerX 10.1.1.568.130doi10.1007 / 978-3-642-04128-0_61MR 2557794   
  13. ^ a b c Mayers、Andrew(2008)。「CS312:ハッシュテーブルと償却分析」コーネル大学、コンピュータサイエンス学部。2021年4月26日にオリジナルからアーカイブされました2021年10月26日–cs.cornell.edu経由で取得
  14. ^ Maurer、WD; ルイス、TG(1975年3月1日)。「ハッシュテーブルメソッド」ACMコンピューティング調査ACMのジャーナル1(1):14。doi10.1145 /356643.356645
  15. ^ a b c ドナルドE.クヌース(1998年4月24日)。The Art of Computer Programming:Volume 3:Sorting andSearchingアディソン-ウェスリープロフェッショナル。ISBN 978-0-201-89685-5
  16. ^ a b c d e セッジウィック、ロバート; ウェイン、ケビン(2011)。アルゴリズム1(4版)。Addison-Wesley Professional – Princeton University、Department of ComputerScience経由。
  17. ^ a b c Askitis、Nikolas; ゾーベル、ジャスティン(2005)。「文字列ハッシュテーブルでのキャッシュを意識した衝突解決」文字列処理と情報検索に関する国際シンポジウムシュプリンガーサイエンス+ビジネスメディア土井10.1007 / 11575832_1ISBN 978-3-540-29740-6
  18. ^ Askitis、ニコラス; シンハ、ランジャン(2010)。「文字列のスケーラブルでキャッシュおよびスペース効率の高い試行のエンジニアリング」。VLDBジャーナル17(5):634。doi10.1007 / s00778-010-0183-9ISSN1066-8888_ S2CID432572_  
  19. ^ Askitis、ニコラス; ゾーベル、ジャスティン(2005年10月)。文字列ハッシュテーブルでのキャッシュを意識した衝突解決第12回国際会議、文字列処理および情報検索(SPIRE 2005)の議事録3772/2005。pp。91–102。土井10.1007 / 11575832_11ISBN 978-3-540-29740-6
  20. ^ Askitis、ニコラス(2009)。整数キーの高速でコンパクトなハッシュテーブル(PDF)第32回オーストラリアコンピュータサイエンス会議(ACSC 2009)の議事録91. pp。113–122。ISBN  978-1-920682-72-92011年2月16日にオリジナル (PDF)からアーカイブされました2010年6月13日取得
  21. ^ エリック・デメイン、ジェフ・リンド。6.897:高度なデータ構造。MITコンピューター科学人工知能研究所。2003年春。「アーカイブされたコピー」(PDF)2010年6月15日のオリジナルからアーカイブ(PDF)2008年6月30日取得 {{cite web}}: CS1 maint: archived copy as title (link)
  22. ^ ウィラード、ダンE.(2000)。「計算幾何学、van Emde Boasツリー、および融合ツリーの観点からのハッシュの調査」。SIAM Journal onComputing29(3):1030〜1049。土井10.1137 / S0097539797322425MR1740562_ 
  23. ^ Tenenbaum、Aaron M。; Langsam、Yedidyah; オーゲンスタイン、モシェJ.(1990)。Cを使用したデータ構造プレンティスホール。pp。456–461、p。472. ISBN 978-0-13-199746-2
  24. ^ Pagh、Rasmus ; Rodler、Flemming Friche(2001)。「カッコウハッシュ」。アルゴリズム— ESA2001コンピュータサイエンスの講義ノート。2161. pp。121–133。CiteSeerX10.1.1.25.4189_ 土井10.1007 / 3-540-44676-1_10ISBN  978-3-540-42493-2
  25. ^ a b c Vitter、Jeffery S。; チェン、ウェンチン(1987)。合体ハッシュの設計と分析アメリカ合衆国、ニューヨーク:オックスフォード大学出版局ISBN 978-0-19-504182-8–Archive.org経由
  26. ^ ヴィッター、ジェフリー・スコット(1982年12月)。「合体したハッシュの実装」ACMの通信25(12):911–926。土井10.1145 /358728.358745ISSN0001-0782_ 
  27. ^ Pagh、Rasmus ; Rodler、Flemming Friche(2001)。「カッコウハッシュ」。アルゴリズム— ESA2001コンピュータサイエンスの講義ノート。2161. CiteSeerX10.1.1.25.4189_ 土井10.1007 / 3-540-44676-1_10ISBN  978-3-540-42493-2
  28. ^ a b c d e f Herlihy、モーリス; シャビット、ニル; Tzafrir、Moran(2008)。「石けり遊びのハッシュ」分散コンピューティングに関する国際シンポジウム分散コンピューティング。ベルリン、ハイデルベルク:シュプリンガーパブリッシング5218土井10.1007 / 978-3-540-87779-0_24ISBN 978-3-540-87778-3– SpringerLink経由。
  29. ^ a b セリス、ペドロ(1986)。ロビンフッドハッシュ(PDF)カナダ、オンタリオ州:ウォータールー大学、コンピューターサイエンス学部。ISBN  031529700XOCLC14083698 _ 2021年11月1日のオリジナルからアーカイブ (PDF)2021年11月2日取得
  30. ^ Poblete、PV; ヴィオラ、A。(2018年8月14日)。「削除の有無にかかわらず、ランダムプロービングモデルの下でのロビンフッドおよび他のハッシュアルゴリズムの分析」組み合わせ論、確率およびコンピューティングケンブリッジ大学出版局28(4)。土井10.1017 / S0963548318000408ISSN1469-2163 _ 2021年11月1日– CambridgeCore経由で取得。 
  31. ^ クラークソン、マイケル(2014)。「講義13:ハッシュテーブル」コーネル大学、コンピュータサイエンス学部。2021年10月7日にオリジナルからアーカイブされました2021年11月1日–cs.cornell.edu経由で取得
  32. ^ グリース、デビッド(2017)。「JavaHyperTextとデータ構造:ロビンフードハッシュ」(PDF)コーネル大学、コンピュータサイエンス学部。2021年4月26日のオリジナルからアーカイブ(PDF)2021年11月2日–cs.cornell.edu経由で取得
  33. ^ セリス、ペドロ(1988年3月28日)。外部ロビンフードハッシュ(PDF)(テクニカルレポート)。インディアナ州ブルーミントン:インディアナ大学、コンピューターサイエンス学部。246. 2021年11月2日のオリジナルからアーカイブ(PDF)2021年11月2日取得
  34. ^ ゴダード、ウェイン(2021)。「ChaterC5:ハッシュテーブル」(PDF)クレムソン大学pp。15–16。2021年11月9日のオリジナルからアーカイブ(PDF)2021年11月9日–people.cs.clemson.edu経由で取得
  35. ^ Devadas、Srini; デメイン、エリック(2011年2月25日)。「アルゴリズムの概要:ハッシュテーブルのサイズ変更」(PDF)マサチューセッツ工科大学、コンピュータサイエンス学部。2021年5月7日のオリジナルからアーカイブ(PDF)2021年11月9日取得– MITOpenCourseWare経由
  36. ^ Thareja、Reema(2018年10月13日)。「ハッシュと衝突」。Cを使用したデータ構造(2版)。オックスフォード大学出版局ISBN 9780198099307
  37. ^ a b フリードマン、スコット; クリシュナン、アナンド; Leidefrost、Nicholas(2003年3月18日)。「組み込みおよびリアルタイムシステムのハッシュテーブル」(PDF)すべてのコンピュータサイエンスおよびエンジニアリング研究セントルイスのワシントン大学土井10.7936 / K7WD3XXV2021年6月9日のオリジナルからアーカイブ(PDF)2021年11月9日、ノースウェスタン大学コンピュータサイエンス学部経由で取得。
  38. ^ Litwin、Witold(1980)。「線形ハッシュ:ファイルとテーブルのアドレス指定のための新しいツール」(PDF)Proc。非常に大規模なデータベースに関する第6回会議カーネギーメロン大学pp。212–223。2021年5月6日のオリジナルからアーカイブ(PDF)2021年11月10日–cs.cmu.edu経由で取得
  39. ^ a b Dijk、Tom Van(2010)。「ハッシュテーブルのパフォーマンスの分析と改善」(PDF)オランダトゥエンテ大学2021年11月6日のオリジナルからアーカイブ(PDF)2021年12月31日取得
  40. ^ コルメン、トーマスH .; レイザーソン、チャールズE。; リベスト、ロナルドL。; Stein、Clifford(2001)、「11 Hash Tables」、Introduction to Algorithms(2nd ed。)、MIT Press and McGraw-Hill、pp。221–252、ISBN 0-262-03293-7
  41. ^ "Set(Java Platform SE 7)"docs.oracle.com2020年11月12日にオリジナルからアーカイブされました2020年5月1日取得
  42. ^ 「転置テーブル-Chessprogrammingwiki」chessprogramming.org2021年2月14日にオリジナルからアーカイブされました2020年5月1日取得
  43. ^ 「プログラミング言語C ++-技術仕様」(PDF)国際標準化機構pp。812–813。2022年1月21日にオリジナル(PDF)からアーカイブされました2022年2月8日取得
  44. ^ 「レッスン:実装(Java™チュートリアル>コレクション)」docs.oracle.com2017年1月18日にオリジナルからアーカイブされました2018年4月27日取得
  45. ^ チャン、ファン; Jia、Yunwei(2019)。「機械学習に基づくRedis再ハッシュの最適化」Journal of Physics:ConferenceSeries1453:3。
  46. ^ Jonan Scheffler(2016年12月25日)。「Ruby2.4のリリース:より高速なハッシュ、統一された整数、より優れた丸め」heroku.com2019年7月3日にオリジナルからアーカイブされました2019年7月3日取得

さらに読む

外部リンク