連想配列

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

コンピュータサイエンスでは連想配列マップシンボルテーブル、または辞書は、(キー、値)ペアのコレクション格納する抽象データ型であり、可能な各キーがコレクションに最大で1回表示されます。数学的には、連想配列は有限定義域を持つ関数です。[1]「ルックアップ」、「削除」、および「挿入」操作をサポートします。

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

多くのプログラミング言語には、プリミティブデータ型として連想配列が含まれており、他の多くのソフトウェアライブラリで利用できます。連想メモリは、連想配列のハードウェアレベルでの直接サポートの一形態です。

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

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

操作

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

連想配列に対して通常定義される操作は次のとおりです。[3] [4] [8]

  • 挿入または配置:新しいものを追加しますコレクションにペアリングし、キーを新しい値にマッピングします。既存のマッピングはすべて上書きされます。この操作の引数は、キーと値です。
  • 削除または削除:削除コレクションからペアを作成し、指定されたキーをその値からマッピング解除します。この操作の引数が鍵となります。
  • Lookupfind、またはget:指定されたキーにバインドされている値(存在する場合)を検索します。この操作の引数はキーであり、値は操作から返されます。値が見つからない場合、一部の連想配列実装は例外を発生させますが、他の実装はデフォルト値(ゼロ、null、コンストラクターに渡される特定の値など)を返します。

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

マルチマップは、複数の値を1つのキーに関連付けることができるようにすることで、連想配列を一般化します。[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の表記を使用すると、データ構造は次のようになります。

{ 
    "高慢と偏見"  "アリス" 
    "Wuthering Heights"  "アリス" 
    "大いなる期待"  "ジョン" 
}

キー「GreatExpectations」のルックアップ操作は「John」を返します。Johnが本を返すと、削除操作が発生し、Patが本をチェックアウトすると、挿入操作が発生し、別の状態になります。

{ 
    "高慢と偏見"  "アリス" 
    "ブラザーズカラマーゾフ"  "パット" 
    "Wuthering Heights"  "アリス" 
}

実装

マッピングの数が非常に少ない辞書の場合、マッピングリンクリストである連想リストを使用して辞書を実装することが理にかなっている場合があります。この実装では、基本的な辞書操作を実行する時間は、マッピングの総数に比例します。ただし、実装は簡単で、実行時間の一定の要因は小さいです。[3] [10]

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

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

ハッシュテーブルの実装

このグラフは、大きなハッシュテーブル(キャッシュのサイズをはるかに超える)で要素を検索するために必要なCPUキャッシュミスの平均数を、チェーンおよび線形プロービングと比較しています。線形プロービングは、参照の局所性が優れているためパフォーマンスが向上しますが、テーブルがいっぱいになると、パフォーマンスが大幅に低下します。

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

ハッシュテーブルは衝突を処理できる必要があります。ハッシュ関数が2つの異なるキーを配列の同じバケットにマップする場合。この問題に対する2つの最も普及しているアプローチは、個別のチェーンオープンアドレス法です。[3] [4] [5] [11]個別の連鎖では、配列は値自体を格納しませんが、ハッシュに一致するすべての値を格納する別のコンテナ(通常は関連付けリスト)へのポインタを格納します。一方、オープンアドレッシングでは、ハッシュの衝突が見つかった場合、テーブルは配列内の空のスポットを探して、通常は配列内の次の直接の位置を調べることにより、決定論的な方法で値を格納します。

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

ツリーの実装

自己平衡二分探索木

もう1つの一般的なアプローチは、 AVLツリー黒木などの自己平衡二分探索ツリーを使用して連想配列を実装することです。[12]

ハッシュテーブルと比較すると、これらの構造には長所と短所の両方があります。自己平衡二分探索木の最悪の場合のパフォーマンスは、ハッシュテーブルのパフォーマンスよりも大幅に優れており、O(log n )の大きなO表記では時間計算量が複雑になります。これは、最悪の場合のパフォーマンスに単一のバケットを共有するすべての要素が含まれるハッシュテーブルとは対照的であり、結果としてO(n)時間計算量。さらに、すべての二分探索木と同様に、自己平衡二分探索木は要素を順番に保持します。したがって、その要素をトラバースすることは、最小から最大のパターンに従いますが、ハッシュテーブルをトラバースすると、要素が一見ランダムな順序になる可能性があります。ただし、ハッシュテーブルの平均時間計算量は、O(1)の自己平衡二分探索木よりもはるかに優れており、優れたハッシュ関数を使用した場合、最悪の場合のパフォーマンスはほとんどありません

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

その他の木

連想配列は、不平衡二分探索木、または基数木試行Judy配列van Emde Boas木などの特定のタイプのキーに特化したデータ構造に格納することもできますが、これらの実装方法の能力はハッシュテーブルと比較して異なります。不定; たとえば、Judyツリーは、ハッシュテーブルよりも効率が低いことが示されていますが、慎重に選択されたハッシュテーブルは、一般に、適応基数ツリーと比較して効率が高く、処理できるデータの種類に大きな制限がある可能性があります。[15]これらの代替構造の利点は、クエリ自体がマッピングのセットに存在しない場合に、キーがクエリされたキーに最も近いマッピングを見つけるなど、連想配列の基本的な操作を超えた操作を処理できることから得られます。

比較

基礎となるデータ構造 ルックアップまたは削除 挿入 順序付けられました
平均 最悪の場合 平均 最悪の場合
ハッシュ表 O(1) O(n O(1) O(n 番号
自己平衡二分探索木 O(log n O(log n O(log n O(log n はい
不均衡な二分探索木 O(log n O(n O(log n O(n はい
キーと値のペアのシーケンシャルコンテナ
(例:関連付けリスト
O(n O(n O(1) O(1) 番号

注文辞書

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

  • 列挙の順序は、ソートによって特定のキーのセットに対して常に決定論的です。これはツリーベースの実装の場合であり、代表的なものの1つ<map>がC ++のコンテナです。[16]
  • 列挙の順序はキーに依存せず、代わりに挿入の順序に基づいています。これは、 .NETFrameworkおよびPythonの「順序付き辞書」の場合です[17] [18]

順序付けられた辞書の後者の意味は、より一般的に遭遇します。これらは、関連付けリストを使用するか、通常の辞書の上に二重にリンクされたリストをオーバーレイすることによって実装できます。後者のアプローチは、バージョン3.6より前のCPythonで使用されていたように、別の実装の潜在的により良い複雑さを維持するという利点があります。[19] CPython 3.6+は、ハッシュテーブルをkvペアの挿入順序付き配列とインデックスのスパース配列(「ハッシュテーブル」)に分割することにより、辞書を順序付けします。[20]

言語サポート

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

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

SmalltalkObjective-C.NET[21] PythonREALbasicSwiftVBADelphi [22]では、これらは辞書と呼ばれます。PerlRubySeed7では、ハッシュと呼ばれますC ++JavaGoClojureScalaOCamlHaskellでは、これらはマップと呼ばれます(マップ(C ++)を参照) unordered_map(C ++)、およびMap); CommonLispWindowsPowerShellではこれらはハッシュテーブルと呼ばれます(どちらも通常この実装を使用するため)。MapleとLuaでは、これらはテーブルと呼ばますPHPでは、キーが整数と文字列に制限されていることを除いて、すべての配列を関連付けることができます。JavaScript(JSONも参照)では、すべてのオブジェクトは文字列値のキーを持つ連想配列として動作しますが、MapタイプとWeakMapタイプは任意のオブジェクトをキーとして受け取ります。Luaでは、これらはすべてのデータ構造の基本的な構成要素として使用されます。Visual FoxProでは、これらはコレクションと呼ばれます。TheD言語は、連想配列もサポートしています。[23]

永久ストレージ

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

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

cの後。 2010年には、クラウドコンピューティングに適し、それらを使用するプログラムの内部構造をより厳密に一致させる高性能データベースの必要性が、キーバリューストア市場のルネッサンスにつながりました。これらのシステムは、連想配列をネイティブな方法で格納および取得できるため、一般的なWeb関連のワークフローのパフォーマンスを大幅に向上させることができます。

も参照してください

参考文献

  1. ^ コリンズ、グラハム; Syme、Donald(1995)。「有限マップの理論」​​。高階論理定理証明とその応用971:122–137。土井10.1007 / 3-540-60275-5_61
  2. ^ アンダーソン、アルネ(1989)。「辞書問題の最適な限界」。Proc。最適アルゴリズムに関するシンポジウムコンピュータサイエンスの講義ノート。シュプリンガーバーラグ。401:106–114。土井10.1007 / 3-540-51859-2_10ISBN 978-3-540-51859-4
  3. ^ a b c d e Goodrich、Michael T .; Tamassia、Roberto(2006)、 "9.1 The Map Abstract Data Type"、Data Structures&Algorithms in Java(4th ed。)、Wiley、pp。368–371
  4. ^ a b c d メールホルン、カート; Sanders、Peter(2008)、「4つのハッシュテーブルと連想配列」、アルゴリズムとデータ構造:基本ツールボックス(PDF)、Springer、81〜98ページ
  5. ^ a b c d コルメン、トーマス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
  6. ^ a b Dietzfelbinger、M.、Karlin、A.、Mehlhorn、K.、Meyer auf der Heide、F.、Rohnert、H.、and Tarjan、RE 1994. "Dynamic Perfect Hashing:Upper and Lower Bounds" Archived 2016-ウェイバックマシンで03-04 SIAM J.Comput。23、4(1994年8月)、738-761。 http://portal.acm.org/citation.cfm?id=182370 doi10.1137 / S0097539791194094
  7. ^ Goodrich&Tamassia(2006)、pp。597–599。
  8. ^ a b ブラック、ポールE。; スチュワート、ロブ(2020年11月2日)。「辞書」アルゴリズムとデータ構造の辞書2022年1月26日取得
  9. ^ Goodrich&Tamassia(2006)、pp。389–397。
  10. ^ 「関連付けリストの代わりにハッシュテーブルを使用する必要があるのはいつですか?」lisp-faq / part2。1996-02-20。
  11. ^ Klammer、F .; Mazzolini、L。(2006)、「連想マップのパスファインダー」、Ext。抄録GIS-l2006、GIS-I、pp。71–74
  12. ^ JoelAdamsとLarryNyhoff。 「STLの木」引用:「標準テンプレートライブラリ...そのコンテナの一部(set <T>、map <T1、T2>、multiset <T>、およびmultimap <T1、T2>テンプレート)は、通常、特別なテンプレートを使用して構築されています赤黒木と呼ばれる一種の自己平衡二分探索木です。」
  13. ^ クヌース、ドナルド(1998)。The Art of ComputerProgramming3:並べ替えと検索(第2版)。アディソン-ウェスリー。pp。513–558。ISBN 0-201-89685-0
  14. ^ Probst、Mark(2010-04-30)。「線形対二分探索」2016年11月20日取得
  15. ^ アルバレス、ビクター; リヒター、ステファン; 陳暁; イェンスのディットリッチ(2015年4月)。「適応基数木とハッシュテーブルの比較」。2015 IEEE 31st International Conference on DataEngineering韓国、ソウル:IEEE:1227–1238。土井10.1109 /ICDE.2015.7113370ISBN 978-1-4799-7964-6S2CID17170456 _
  16. ^ "std :: map"en.cppreference.com
  17. ^ "OrderedDictionaryクラス(System.Collections.Specialized)"MSドキュメント
  18. ^ 「コレクション—コンテナデータ型— Python3.9.0a3ドキュメント」docs.python.org
  19. ^ ディミトリスファサラキスヒリアード。「辞書-PythonのOrderedDictは、挿入された要素をどのように記憶しますか?」スタックオーバーフロー
  20. ^ ディミトリスファサラキスヒリアード。「辞書はPython3.6以降で注文されていますか?」スタックオーバーフロー
  21. ^ "Dictionary <TKey、TValue>クラス"MSDN。
  22. ^ 「System.Generics.Collections.TDictionary-RADStudioAPIドキュメント」docwiki.embarcadero.com 2017年4月18日取得
  23. ^ 「連想配列、Dプログラミング言語」デジタル火星。
  24. ^ 「アーカイブおよびシリアル化プログラミングガイド」、Apple Inc.、2012年

外部リンク