Loading article…
コンピュータサイエンスでは、連想配列、キーバリューストア、マップ、シンボルテーブル、または辞書は、キーと値のペアのコレクションを格納する抽象データ型であり、各キーはコレクション内に最大で 1 回出現します。数学的には、連想配列は有限ドメインの関数です。[ 1 ] これは、「検索」、「削除」、「挿入」操作をサポートします。
辞書問題は、連想配列を実装する効率的なデータ構造を設計するという古典的な問題です。[ 2 ] 辞書問題に対する主な解決策は、ハッシュテーブルと検索木です。[ 3 ] [ 4 ] [ 5 ] [ 6 ]直接アドレス指定配列、二分検索木、またはその他のより特殊な構造 を使用して問題を解決できる場合もあります。
多くのプログラミング言語は連想配列を基本データ型として含んでいる一方、他の多くの言語は連想配列をサポートするソフトウェアライブラリを提供している。内容アドレス指定可能なメモリは、連想配列に対するハードウェアレベルでの直接的なサポートの一形態である。
連想配列には、メモ化[ 7 ]やデコレータパターン[ 8 ]などの基本的なプログラミングパターンを含む多くの用途があります。この名前は、数学で知られている結合法則 に由来するものではありません。むしろ、値とキーの関連付けから生じています。連想プロセッサと混同してはいけません。
連想配列において、キーと値の関連付けはしばしば「マッピング」と呼ばれます。同じ用語は、新しい関連付けを作成するプロセスを指す場合にも使用されることがあります。
連想配列に対して通常定義されている操作は次のとおりです。[ 3 ] [ 4 ] [ 9 ]
連想配列には、マッピングの数を判定したり、すべてのマッピングをループ処理するイテレータを構築したりするなど、その他の操作も含まれる場合があります。このような操作の場合、マッピングが返される順序は通常、実装依存です。
マルチマップは、1 つのキーに複数の値を関連付けることができるようにすることで、連想配列を一般化します。[ 10 ]双方向マップは、マッピングが双方向で動作する関連する抽象データ型です。各値は一意のキーに関連付けられる必要があり、2 番目のルックアップ操作は値を引数として受け取り、その値に関連付けられたキーを検索します。
連想配列の操作は、次のさまざまな特性を満たす必要があります。[ 9 ]
lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)lookup(k, new()) = fail例外failまたはデフォルト値remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))remove(k, new()) = new()ここでk、jと はキー、vは値、Dは連想配列、はnew()新しい空の連想配列を作成します。
図書館が行った貸出の記録をデータ構造で表現するとします。図書館にある各書籍は、一度に1人の利用者が借りることができます。ただし、1人の利用者が複数の書籍を借りる場合もあります。そのため、どの書籍がどの利用者に貸し出されているかという情報は、書籍をキー、利用者を値とする連想配列で表現できます。PythonまたはJSONの表記法を用いると、データ構造は次のようになります。
{ "高慢と偏見" : "アリス" , "嵐が丘" : "アリス" , "大いなる遺産" : "ジョン" }キー「Great Expectations」で検索すると「John」が返されます。Johnが本を返却すると削除操作が発生し、Patが本を借り出すと挿入操作が発生し、異なる状態になります。
{ "高慢と偏見" : "アリス" , "カラマーゾフの兄弟" : "パット" , "嵐が丘" : "アリス" }マッピングが非常に少ない辞書の場合、マッピングのリンクリストである連想リストを使用して辞書を実装するのが理にかなっている場合があります。この実装では、基本的な辞書操作を実行するのにかかる時間は、マッピングの総数に対して線形です。ただし、実装は簡単で、実行時間における定数係数は小さいです。[ 3 ] [ 11 ]
キーが狭い範囲に制限されている場合に使用できる、もう1つの非常にシンプルな実装手法は、配列への直接アドレス指定です。特定のキー k の値は配列セルA [ k ] に格納されます。kに対応するマッピングがない場合は、マッピングがないことを示す特別な番兵値がセルに格納されます。この手法はシンプルで高速であり、各辞書操作は定数時間で完了します。ただし、この構造に必要なスペースはキースペース全体のサイズと同じであるため、キースペースが小さい場合を除いて実用的ではありません。[ 5 ]
辞書を実装するための主なアプローチは、ハッシュテーブルまたは検索ツリーの2 つです。[ 3 ] [ 4 ] [ 5 ] [ 6 ]
連想配列の最も一般的な汎用実装はハッシュテーブルです。ハッシュテーブルとは、配列とハッシュ関数を組み合わせたもので、各キーを配列内の個別の「バケット」に分割します。ハッシュテーブルの基本的な考え方は、インデックスを使用して配列の要素にアクセスする操作が、単純で定数時間の操作であるということです。そのため、ハッシュテーブルの操作における平均的なオーバーヘッドは、キーのハッシュ値の計算と、配列内の対応するバケットへのアクセスのみとなります。このように、ハッシュテーブルは通常O(1)の時間で動作し、他の実装よりも優れたパフォーマンスを発揮します。
ハッシュ テーブルは衝突を処理できなければなりません。衝突とは、ハッシュ関数によって 2 つの異なるキーが配列の同じバケットにマッピングされることです。この問題に対する最も一般的な 2 つのアプローチは、分離連鎖とオープン アドレス指定です。[ 3 ] [ 4 ] [ 5 ] [ 12 ]分離連鎖では、配列は値自体を格納せず、ハッシュに一致するすべての値を格納する別のコンテナ (通常は連想リスト) へのポインタを格納します。対照的に、オープン アドレス指定では、ハッシュ衝突が見つかった場合、テーブルは配列内の空き場所を探して、通常は配列内の次の位置を調べて、決定論的に値を格納します。
テーブルがほとんど空の場合、オープンアドレッシングはセパレートチェイニングよりもキャッシュミス率が低くなります。しかし、テーブルに要素が増えるにつれて、オープンアドレッシングのパフォーマンスは指数関数的に低下します。さらに、エントリが非常に小さい場合（ポインタの4倍未満）を除き、ほとんどの場合、セパレートチェイニングの方がメモリ使用量が少なくなります。
もう1つの一般的なアプローチは、 AVL木や赤黒木などの自己平衡二分探索木で連想配列を実装することです。[ 13 ]
ハッシュテーブルと比較すると、これらの構造には長所と短所の両方があります。自己平衡二分探索木の最悪ケースのパフォーマンスはハッシュテーブルよりも大幅に優れており、ビッグオー記法では時間計算量はO(log n )です。これは、最悪ケースのパフォーマンスで全ての要素が単一のバケットを共有するため、時間計算量がO( n )となるハッシュテーブルとは対照的です。さらに、全ての二分探索木と同様に、自己平衡二分探索木は要素を順序付けたままにします。そのため、要素の走査は最小値から最大値の順になりますが、ハッシュテーブルを走査すると要素がランダムな順序になる場合があります。順序付けされているため、ツリーベースのマップは範囲クエリ（2つの境界間の全ての値を検索）にも対応できますが、ハッシュマップは正確な値しか検索できません。ただし、ハッシュテーブルの平均時間計算量はO(1)と自己平衡二分探索木よりもはるかに優れており、適切なハッシュ関数を使用すれば最悪ケースのパフォーマンスが発生する可能性は非常に低くなります。
自己平衡二分探索木は、分離連鎖を使用するハッシュテーブルのバケットを実装するために使用できます。これにより、平均ケースでは定数ルックアップが可能になりますが、最悪の場合のパフォーマンスは O(log n ) になります。ただし、これにより実装に余分な複雑さが加わり、小さなハッシュテーブルでは、木への挿入と平衡化にかかる時間が、リンクリストや同様のデータ構造のすべての要素に対して線形探索を実行するのに必要な時間よりも長くなるため、パフォーマンスがさらに悪化する可能性があります。[ 14 ] [ 15 ]
連想配列は、不均衡な二分探索木や、基数木、トライ木、ジュディ配列、ファン・エムデ・ボアス木などの特定のキータイプに特化したデータ構造に格納することもできますが、これらの実装の相対的なパフォーマンスは異なります。たとえば、ジュディ木はハッシュテーブルよりも効率が悪いことがわかっていますが、慎重に選択されたハッシュテーブルは、一般的に適応型基数木よりも効率が良く、処理できるデータ型に大きな制約がある可能性があります。[ 16 ]これらの代替構造の利点は、クエリがマッピングのセットに存在しない場合に、クエリされたキーに最も近いキーを持つマッピングを見つけるなど、追加の連想配列操作を処理できることにあります。
辞書の基本的な定義では、順序は規定されていません。列挙の順序を固定するために、連想配列の順序付きバージョンがよく使用されます。順序付き辞書には、次の2つの意味があります。
std::mapC++の（ツリーマップ）コンテナが挙げられます。[ 17 ]LinkedHashMapの「順序付き辞書」の場合です。[ 18 ] [ 19 ] [ 20 ]後者の方が一般的です。このような順序付き辞書は、連想リストを使用したり、通常の辞書の上に二重リンクリストを重ねたり、実際のデータを疎な（順序付けされていない）配列から密な挿入順序配列に移動したりすることで実装できます。
連想配列は、どのプログラミング言語でもパッケージとして実装でき、多くの言語システムでは標準ライブラリの一部として提供されています。一部の言語では、標準システムに組み込まれているだけでなく、配列のような添え字を用いる特別な構文も用意されています。
連想配列の組み込み構文サポートは、1969 年にSNOBOL4で「table」という名前で導入されました。[ 21 ] TMG は文字列キーと整数値を持つテーブルを提供しました。MUMPSは、オプションで永続化可能な多次元連想配列を主要なデータ構造としました。SETLは、セットとマップの可能な実装の 1 つとして連想配列をサポートしました。AWK [ 22 ]から始まり、 Rexx、Perl、PHP、Tcl、JavaScript、Maple、Python、Ruby、Wolfram Language、Go、Luaを含むほとんどの最新のスクリプト言語は、主要なコンテナ型として連想配列をサポートしています。さらに多くの言語では、特別な構文なしでライブラリ関数として利用できます。
Smalltalk、Objective-C、.NET、[ 23 ] Python、REALbasic、Swift、VBA、Delphi [ 24 ]では、辞書と呼ばれます。PerlとRubyではハッシュと呼ばれます。C++、C#、Java、Go、Clojure、Scala、OCaml、Haskell ではマップと呼ばれます( map ( C ++ ) 、 unordered_map ( C ++ )、およびを参照)。Common LispとWindows PowerShell ではハッシュテーブルと呼ばれます(どちらも通常この実装を使用するため)。Maple と Lua ではテーブルと呼ばれます。PHPとRでは、キーが整数と文字列に制限されている点を除いて、すべての配列が連想配列になります。JavaScript ( JSONも参照) では、すべてのオブジェクトが文字列値のキーを持つ連想配列として動作しますが、Map 型と WeakMap 型は任意のオブジェクトをキーとして受け取ります。 Luaでは、これらはすべてのデータ構造の基本構成要素として使用されます。Visual FoxProでは、これらはコレクションと呼ばれます。D言語も連想配列をサポートしています。[ 25 ]Map
連想配列を使用する多くのプログラムでは、そのデータをコンピュータ ファイルなどのより永続的な形式で保存する必要があります。この問題に対する一般的な解決策は、アーカイブまたはシリアル化として知られる汎用的な概念であり、元のオブジェクトのテキストまたはバイナリ表現を生成し、それをファイルに直接書き込むことができます。これは、.Net や Cocoa などの基盤となるオブジェクト モデルで実装されるのが一般的で、内部データをテキストに変換する標準関数が含まれています。プログラムは、これらのメソッドを呼び出すことで、任意のオブジェクト グループの完全なテキスト表現を作成できます。これらのメソッドは、ほとんどの場合、基本連想配列クラスに既に実装されています。[ 26 ]
非常に大きなデータセットを使用するプログラムでは、このような個別のファイルストレージは適切ではなく、データベース管理システム(DB) が必要です。一部の DB システムでは、データをシリアル化してシリアル化されたデータとキーを保存することにより、連想配列をネイティブに保存します。個々の配列は、キーを使用して参照することで、データベースからロードまたは保存できます。これらのキーと値のストアは長年にわたって使用されており、より一般的なリレーショナル データベース(RDB) と同じくらい長い歴史がありますが、標準化の欠如などの理由により、その使用は特定のニッチな役割に限定されていました。ほとんどの場合、これらの役割には RDB が使用されていましたが、オブジェクトを RDB に保存することは複雑になる可能性があり、これはオブジェクトリレーショナル インピーダンス ミスマッチとして知られる問題です。
2010年頃以降、クラウドコンピューティングに適した高性能データベース、そしてそれらを使用するプログラムの内部構造により密接に適合するデータベースへのニーズの高まりにより、キーバリューストア市場は再び活況を呈するようになりました。これらのシステムは、連想配列をネイティブな方法で保存および取得できるため、一般的なWeb関連のワークフローにおけるパフォーマンスを大幅に向上させることができます。
標準テンプレートライブラリ...そのコンテナの一部（set<T>、map<T1, T2>、multiset<T>、multimap<T1, T2>テンプレート）は、一般的に
赤黒木
と呼ばれる特殊な
自己平衡二分探索木
を使用して構築されます。
ダグ・マキロイ
とマイク・シャピロによって何度も提案されていた
。SNOBOL4 の開発の非常に遅い段階である 1969 年半ばにテーブルが SNOBOL4 に追加されたのは、ダグの粘り強い働きかけの結果であった。
配列要素は非数値で命名できるため、
awkは
Snobolテーブルの連想メモリに似た機能を持ちます。