連想配列

コンピュータサイエンスにおいて、連想配列、マップ、シンボルテーブル、または辞書は、キーと値のペアのコレクションを格納する抽象データ型であり、各キーはコレクション内で最大で1回出現します。数学的には、連想配列は有限ドメインを持つ関数です。^[1]「検索」、「削除」、「挿入」の各操作をサポートしています。

辞書問題は、連想配列を実装する効率的なデータ構造を設計するという古典的な問題です。^[2] 辞書問題に対する2つの主要な解決策は、ハッシュテーブルと検索木です。^{[3] [4] [5] [6]直接アドレス指定された}配列、二分探索木、またはその他のより特殊な構造 を使用して問題を解決できる場合もあります。

多くのプログラミング言語には連想配列が基本データ型として含まれており、他の多くの言語では連想配列をサポートするソフトウェア ライブラリが提供されています。コンテンツ アドレス可能メモリは、連想配列を直接ハードウェア レベルでサポートする形式です。

連想配列には、メモ化やデコレータパターンなどの基本的なプログラミングパターンを含む多くの用途があります。^[7]

この名前は、数学で知られている結合法則に由来するものではありません。むしろ、値とキーの関連付けから生じています。連想プロセッサと混同しないでください。

連想配列では、キーと値の関連付けは「マッピング」と呼ばれることが多く、同じ単語が新しい関連付けを作成するプロセスを指すために使用されることもあります。

連想配列に対して通常定義される操作は以下の通りである: ^{[3] [4] [8]}

挿入または置く

コレクションに新しいペアを追加し、キーを新しい値にマッピングします。既存のマッピングは上書きされます。この操作の引数は、キーと値です。${\displaystyle (キー,値)}$

削除または削除

コレクションからペアを削除し、指定されたキーとその値のマッピングを解除します。この操作の引数はキーです。${\displaystyle (キー,値)}$

検索、発見、取得

指定されたキーにバインドされている値 (存在する場合) を検索します。この操作の引数はキーであり、操作から値が返されます。値が見つからない場合、一部の検索関数は例外を発生させますが、他の検索関数はデフォルト値 (ゼロ、null、またはコンストラクターに渡された特定の値など) を返します。

連想配列には、マッピングの数を決定したり、すべてのマッピングをループする反復子を構築したりするなどの他の操作も含まれる場合があります。このような操作では、マッピングが返される順序は通常、実装によって定義されます。

マルチマップは、複数の値を単一のキーに関連付けることを可能にすることで連想配列を一般化します。^[9]双方向マップは、マッピングが双方向に動作する関連する抽象データ型です。各値は一意のキーに関連付けられている必要があり、2番目の検索操作は値を引数として受け取り、その値に関連付けられたキーを検索します。

連想配列の演算は様々な性質を満たす必要がある: ^[8]

• 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] [10]}

キーが狭い範囲に制限されている場合に使用できるもう 1 つの非常に単純な実装手法は、配列への直接アドレス指定です。指定されたキーkの値は配列セルA [ k ] に格納されます。または、 kのマッピングがない場合は、マッピングがないことを示す特別なセンチネル値がセルに格納されます。この手法は単純かつ高速で、各辞書操作には一定の時間がかかります。ただし、この構造に必要なスペースはキー空間全体のサイズであるため、キー空間が小さい場合を除き、実用的ではありません。^[5]

辞書を実装するための2つの主要なアプローチは、ハッシュテーブルと検索ツリーです。^{[3] [4] [5] [6]}

連想配列の最も頻繁に使用される汎用実装は、ハッシュ テーブルです。ハッシュ テーブルは、各キーを配列の個別の「バケット」に分割するハッシュ関数と組み合わせた配列です。ハッシュ テーブルの基本的な考え方は、インデックスを介して配列の要素にアクセスする操作は、単純で一定時間の操作であるということです。したがって、ハッシュ テーブルの操作の平均的なオーバーヘッドは、キーのハッシュの計算と、配列内の対応するバケットへのアクセスだけです。そのため、ハッシュ テーブルは通常 O(1) 時間で実行され、通常は他の実装よりもパフォーマンスが優れています。

ハッシュテーブルは衝突を処理できなければなりません。衝突とは、ハッシュ関数によって2つの異なるキーが配列の同じバケットにマッピングされることです。この問題に対する最も一般的な2つのアプローチは、分離連鎖とオープンアドレッシングです。^{[3] [4] [5] [11]}分離連鎖では、配列は値自体を格納するのではなく、ハッシュに一致するすべての値を格納する別のコンテナー（通常は連想リスト）へのポインターを格納します。対照的に、オープンアドレッシングでは、ハッシュ衝突が見つかった場合、テーブルは配列内の空き場所を探して、通常は配列内の次の位置を調べて、決定論的な方法で値を保存します。

テーブルがほとんど空の場合、オープン アドレッシングは個別チェーニングよりもキャッシュ ミス率が低くなります。ただし、テーブルに要素が増えると、オープン アドレッシングのパフォーマンスは急激に低下します。さらに、エントリが非常に小さい (ポインターのサイズの 4 倍未満) 場合を除き、ほとんどの場合、個別チェーニングではメモリの使用量が少なくなります。

もう一つの一般的なアプローチは、 AVL木や赤黒木などの自己バランス二分探索木を使用して連想配列を実装することです。^[12]

ハッシュ テーブルと比較すると、これらの構造には長所と短所があります。自己バランス型二分探索木の最悪のパフォーマンスはハッシュ テーブルよりも大幅に優れており、ビッグ O 表記法での時間計算量はO(log n ) です。これはハッシュ テーブルとは対照的です。ハッシュ テーブルでは、最悪のパフォーマンスではすべての要素が 1 つのバケットを共有するため、時間計算量は O( n ) になります。さらに、すべての二分探索木と同様に、自己バランス型二分探索木は要素を順序どおりに維持します。したがって、要素のトラバースは最小から最大のパターンに従いますが、ハッシュ テーブルをトラバースすると、要素が一見ランダムな順序になることがあります。ツリーベースのマップは順序どおりであるため、範囲クエリ (2 つの境界間のすべての値を検索) も満たすことができますが、ハッシュマップは正確な値しか検索できません。ただし、ハッシュ テーブルの平均時間計算量は O(1) の自己バランス型二分探索木よりもはるかに優れており、適切なハッシュ関数が使用されている場合は、最悪のパフォーマンスになることはほとんどありません。

自己バランス型二分探索木は、分離連鎖を使用するハッシュテーブルのバケットを実装するために使用できます。これにより、平均的なケースの定数検索が可能になりますが、最悪の場合のパフォーマンスは O(log n ) になります。ただし、これにより実装に余分な複雑さが生じ、小さなハッシュテーブルではパフォーマンスがさらに低下する可能性があります。小さなハッシュテーブルでは、ツリーへの挿入とバランス調整にかかる時間が、リンクリストまたは同様のデータ構造のすべての要素に対して線形検索を実行するために必要な時間よりも長くなります。^{[13] [14]}

連想配列は、不均衡二分探索木や、基数木、トライ、ジュディ配列、ファン・エムデ・ボアズ木などの特定の種類のキーに特化したデータ構造に格納することもできますが、これらの実装の相対的なパフォーマンスはさまざまです。たとえば、ジュディ木はハッシュテーブルよりも効率が悪いことがわかっていますが、慎重に選択されたハッシュテーブルは、処理できるデータ型の制限が大きい可能性があるものの、一般的に適応型基数木よりも効率的に機能します。^[15]これらの代替構造の利点は、クエリがマッピングのセットに存在しない場合に、クエリされたキーに最も近いキーを持つマッピングを見つけるなど、追加の連想配列操作を処理できることにあります。

辞書の基本的な定義では、順序は必須ではありません。列挙の固定順序を保証するために、連想配列の順序付きバージョンがよく使用されます。順序付き辞書には 2 つの意味があります。

• 列挙の順序は、ソートによって与えられたキーセットに対して常に決定論的である。これはツリーベースの実装の場合であり、その代表例の1つは<map>C++のコンテナである。^[16]
• 列挙の順序はキーに依存せず、挿入順序に基づきます。これは、 .NET Frameworkの「順序付き辞書」や、 JavaおよびPythonのLinkedHashMapの場合です。^{[17] [18] [19]}

後者の方が一般的です。このような順序付き辞書は、連想リストを使用するか、通常の辞書の上に二重リンクリストを重ねるか、実際のデータをスパース（順序なし）配列から密な挿入順序付き配列に移動することで実装できます。

連想配列は、どのプログラミング言語でもパッケージとして実装でき、多くの言語システムでは標準ライブラリの一部として提供されています。言語によっては、標準システムに組み込まれているだけでなく、配列のような添え字を使用する特殊な構文を持つものもあります。

連想配列の組み込み構文サポートは、1969 年にSNOBOL4によって「テーブル」という名前で導入されました。TMGは、文字列キーと整数値を持つテーブルを提供しました。MUMPSは、オプションで永続的な多次元連想配列をキー データ構造にしました。SETLは、セットとマップの 1 つの可能な実装としてそれらをサポートしました。AWK に始まり、Rexx、Perl、PHP、Tcl、JavaScript、Maple、Python、Ruby、Wolfram Language、Go、Lua を含むほとんどの最新のスクリプト言語は、連想配列を主要なコンテナータイプとしてサポートしています。さらに多くの言語では、特別な構文のないライブラリ関数として使用できます。

Smalltalk、Objective-C、.NET、^[20] Python、REALbasic、Swift、VBA、Delphi ^[21]では、これらは辞書と呼ばれ、Perl、Ruby、Seed7ではハッシュと呼ばれ、C++、C#、Java、Go、Clojure、Scala、OCaml、Haskell ではマップと呼ばれます（map (C++)、unordered_map (C++)、および を参照Map）。Common LispとWindows PowerShellでは、これらはハッシュテーブルと呼ばれます（両方ともこの実装を通常使用するため）。Maple と Lua では、これらはテーブルと呼ばれます。PHPとRでは、すべての配列は連想配列にすることができますが、キーは整数と文字列に限定されます。JavaScript（JSONも参照）では、すべてのオブジェクトは文字列値のキーを持つ連想配列として動作しますが、 Map と WeakMap 型は任意のオブジェクトをキーとして受け取ります。 Luaでは、すべてのデータ構造の基本的な構成要素として使用されます。Visual FoxProでは、コレクションと呼ばれます。D言語も連想配列をサポートしています。^[22]

連想配列を使用する多くのプログラムでは、そのデータをコンピュータファイルなどのより永続的な形式で保存する必要があります。この問題の一般的な解決策は、アーカイブ化またはシリアル化と呼ばれる一般化された概念であり、元のオブジェクトのテキストまたはバイナリ表現を作成し、それをファイルに直接書き込むことです。これは、内部データをテキストに変換する標準関数を含む、.Net や Cocoa などの基盤となるオブジェクト モデルで最も一般的に実装されています。プログラムは、これらのメソッドを呼び出すことで、任意のオブジェクトのグループの完全なテキスト表現を作成できます。これらのメソッドは、ほとんどの場合、基本の連想配列クラスにすでに実装されています。^[23]

非常に大きなデータセットを使用するプログラムの場合、このような個別のファイル ストレージは適切ではなく、データベース管理システム(DB) が必要です。一部の DB システムでは、データをシリアル化し、シリアル化されたデータとキーを保存することで、連想配列をネイティブに保存します。その後、キーを使用して参照することで、データベースから個々の配列を読み込んだり保存したりできます。これらのキー値ストアは長年にわたって使用されており、より一般的なリレーショナル データベース(RDB) と同じくらい長い歴史がありますが、標準化されていないなどの理由から、特定のニッチな役割に限定されて使用されていました。ほとんどの場合、これらの役割には RDB が使用されていましたが、オブジェクトを RDB に保存すると複雑になる可能性があり、オブジェクト リレーショナル インピーダンス ミスマッチと呼ばれる問題があります。

2010 年頃以降、クラウド コンピューティングに適した高性能データベースと、それを使用するプログラムの内部構造により近いデータベースの必要性が高まり、キーバリュー ストア市場が復活しました。これらのシステムは、連想配列をネイティブ形式で保存および取得できるため、一般的な Web 関連のワークフローのパフォーマンスを大幅に向上できます。

• タプル
• 関数（数学）

無料辞書の Wiktionary で連想配列を調べてください。

• NIST のアルゴリズムとデータ構造の辞書: 連想配列