dictionary - 地図と辞書の違いは何ですか？

Question

マップは、キーを値にマップするデータ構造であることを私は知っています。辞書は同じではありませんか？地図と辞書の違いは何ですか¹？

_{1.私はそれらが言語XまたはYでどのように定義されているかを尋ねていません（これは一般的に人々がここでSOで求めているようです）、理論の違いは何ですか？}

score 313 · Accepted Answer

同じことを表す2つの用語：

「マップ」はJava、C++で使用されます
「辞書」は.Net、Pythonで使用されます
「連想配列」はPHPで使用されます

「マップ」は正しい数学用語ですが、関数型プログラミングでは別の意味を持つため、避けています。

一部の言語ではさらに他の用語（Javascriptでは「Object」、Rubyでは「Hash」、Luaでは「Table」）を使用しますが、プログラミングでもこれらはすべて別々の意味を持つため、避けたいと思います。

詳細については、こちらをご覧ください。

score 21 · Accepted Answer

一方はもう一方の古い用語です。通常、「辞書」という用語は、数学用語「マップ」が定着する前に使用されていました。また、辞書にはキータイプの文字列が含まれる傾向がありますが、それはどこでも100％当てはまるわけではありません。

score 18 · Accepted Answer

コンピュータサイエンス用語の要約：

ディクショナリは、要素のセットを表すデータ構造であり、挿入、削除、およびメンバーシップのテストが含まれます。要素は、必ずしもそうではありませんが、別個のキー部分と値部分で構成されている場合があります。
マップは、キーのセットを格納できる連想データ構造であり、それぞれが1つ（または場合によっては複数-C ++マルチマップなど）の値に関連付けられ、キーのみが指定された既存のエントリにアクセスして消去することができます。

討論

この質問への回答は、プログラマーが使用した特定の言語またはシステムでより具体的な意味を与えられた用語を見たために複雑になりますが、この質問は、「理論上」言語にとらわれない比較を求めています。これは、コンピューティングサイエンスの用語で意味します。。

説明された用語

オックスフォード大学コンピュータサイエンス辞書には次のリストがあります。

辞書要素の挿入と削除、およびメンバーシップのテストをサポートできる要素のセットを表すデータ構造

たとえば、挿入して削除を開始できる一連の要素{A、B、C、D ...}があり、「Cは存在しますか？」とクエリできます。。

ただし、コンピューティングサイエンスのマップの概念は、数学言語用語のマッピングに基づいています。これは、オックスフォード辞書で次のように定義されています。

マッピング特定のセット（ドメイン）の各要素を2番目のセット（範囲）の1つ以上の要素に関連付ける操作。

そのため、マップデータ構造は、特定のセットの要素（マップでは「キー」と呼ばれます）から、関連する「値」と呼ばれる2番目のセットの1つ以上の要素に移動する方法を提供します。
「...または2番目のセットのより多くの要素」の側面は、実装によってサポートできます。2つの異なる方法があります。
- 多くのマップ実装は、キーの一意性を強制し、各キーを1つの値にのみ関連付けることができますが、その値は、より単純なデータ型の多くの値を含むデータ構造自体である可能性があります。たとえば、{{1、{"one" 、"ichi"}、{2、{"two"、 "ni"}}}は、文字列のペア/セットで構成される値を示しています。
- 他のマップ実装では、キーを複製して、それぞれが同じ値または異なる値にマッピングできます。これは、「各[key]要素を...複数の[value]要素に関連付ける」場合を機能的に満たします。たとえば、{{1、 "one"}、{1、 "ichi"}、{2、 "two"}、{2、"ni"}}。

辞書と地図の対比

したがって、上記の厳密なComp Sci用語を使用すると、インターフェイスがすべての辞書に必要とされない追加の操作をサポートする場合にのみ、辞書はマップになります。

個別のキーおよび値コンポーネントを持つ要素を格納する機能
キーのみを指定して値を取得および消去する機能

ささいなひねり：

マップインターフェイスは、{key、value}ペアがコンテナ内にあるかどうかのテストを直接サポートしていない可能性があります。これは、要素が{key、value}ペアである辞書の要件です。マップにはキーをテストする機能さえないかもしれませんが、最悪の場合、キーによる値の取得の試行が成功するか失敗するかを確認できます。気になる場合は、期待値を取得したかどうかを確認できます。

視聴者に明確に伝える

⚠上記のすべてにもかかわらず、上記で説明した厳密なコンピューティングサイエンスの意味で辞書を使用する場合は、最初に聴衆があなたをフォローしたり、用語を共有して擁護したりするときに感銘を受けることを期待しないでください。この質問に対する他の回答（および彼らの賛成票）は、ほとんどのプログラマーの経験において、「辞書」が「マップ」と同義である可能性がどれほどあるかを示しています。より広く明確に理解される用語を選択してみてください。例：

連想コンテナ：値の取得とキーによる消去を伴うキーと値のペアを格納するコンテナ
ハッシュマップ：連想コンテナのハッシュテーブル実装
一意のキーを適用するハッシュセット：要素/値を個別のキー/値コンポーネントを含むものとして扱わずに格納するディクショナリのハッシュテーブル実装。要素の重複は挿入できません。
重複キーをサポートするバランスバイナリツリーマップ：..。

CompSciの用語と特定の実装との相互参照

C++標準ライブラリ

マップ：map、、、、multimap_unordered_mapunordered_multimap
他の辞書：set、、、、multisetunordered_setunordered_multiset
注：イテレータを使用するか、要素を消去して、、、などstd::findのメンバーシップをテストできますが、要素の検索はO（N）で非常に非効率的であるため、コンテナインターフェイスはそれを直接サポートしていません。場合によっては、挿入/消去は非効率的であり、これらの操作をサポートすると、コンテナが意味する意図的に制限されたAPIが損なわれます。たとえば、sは、一部のキーに関してではなく、前面と背面でのみ消去/ポップをサポートする必要があります。検索を調整するためにコードでより多くの作業を行う必要があるため、プログラマーはより効率的な検索を使用してコンテナーデータ構造に切り替えることができます。arrayvectorlistdequedeque

...後で他の言語を追加する可能性があります/自由に編集してください...

score 14 · Accepted Answer

私の2セント。

辞書はJavaの抽象クラスですが、マップはインターフェースです。Javaは多重継承をサポートしていないため、クラスがDictionaryを拡張する場合、他のクラスを拡張することはできません。

そのため、マップインターフェイスが導入されました。

辞書クラスは廃止され、Mapの使用が推奨されます。

score 3 · Accepted Answer

通常、マップはハッシュテーブルに基づいていると思います。注文されていないストアを意味します。辞書は注文された店を意味します。

Trieと呼ばれるツリーベースの辞書があります。

Lispでは、次のようになります。

(a (n (d t)) n d )

これは単語をカプセル化します：

a
と
蟻
と
広告

上から葉へのトラバースは単語を生成します。

score 2 · Accepted Answer

本当に同じことではありません。マップは辞書のサブセットです。辞書は、ここでは挿入、削除、および検索機能を持つものとして定義されています。Javaで使用されるマップ（これによる）は、値にマップするキーが1対1の関数として厳密にマップされる必要がある辞書です。辞書には、1つの値への複数のキーマップ、または複数の値への1つのキーマップ（ハッシュテーブルでのチェーンなど）が含まれる場合があります（Twitterハッシュタグ検索など）。

より「現実の世界」の例として、辞書で単語を検索すると、同じ単語の多くの定義が得られ、別のエントリ（他の単語を参照）を指すエントリが見つかると、いくつかの単語が表示されます。同じ定義のリストについて。現実の世界では、地図ははるかに広く、名前の場所や座標の名前を指定できますが、最も近い隣人や他の属性（人口など）を見つけることもできるので、IMHOはマップタイプにはグラフベースの実装がある可能性がありますが、特に値に最も近いネイバーやその他の属性はすべて値のデータメンバーである可能性があるため、常にキーと値のペアのみを想定するのが最善です。

Javaマップは、1対1の要件にもかかわらず、値がコレクション自体として一般化されている場合、または値が他の場所に格納されているコレクションへの単なる参照である場合、一般化されたディクショナリのようなものを実装できます。

JavaメンテナはADT定義のメンテナではなく、Javaの決定はJava専用であることを忘れないでください。

score 1 · Accepted Answer

1

かなり一般的なこの概念の他の用語：連想配列とハッシュ。

于 2010-05-21T17:18:25.333 に答える

score 1 · Accepted Answer

はい、同じです。「連想配列」をミックスに追加できます。

使用Hashtable またはHashofterは、実装を指します。

score 0 · Accepted Answer

これらは、同じ概念の2つの異なる用語です。
HashtableまたHashMap、同じ概念を参照してください。

score 0 · Accepted Answer

純粋に理論的なレベルです。

ディクショナリは、リンクされた値を見つけるために使用できる値です。マップは、別の値を見つける方法についての指示を提供する値です

単純な配列でさえ正しい値にマップするインデックスを持っているため、非線形アクセスを許可する（つまり、最初に取得するか最後に取得するだけの）すべてのコレクションはマップです。したがって、辞書はマップの一種ですが、マップは可能な機能のはるかに広い範囲です。

実際には、通常は名前を定義するマッピング関数であるため、HashMapは、ハッシュアルゴリズムを使用してキーを値にリンクするマップされたデータ構造ですが、ディクショナリはキーを値にリンクする方法を指定しません。したがって、リンクリスト、ツリー、またはその他のアルゴリズムを介して保存できます。使用の終わりから、あなたは通常、それらが機能するだけのアルゴリズムを気にしないので、ジェネリック辞書を使用し、アルゴリズムのタイプを予測する必要がある場合にのみ他の構造の1つにシフトします

score -1 · Accepted Answer

主な違いは、マップでは、すべてのエントリ（値とキーのペア）に一意のキーが必要なことです。衝突が発生した場合、つまり、新しいエントリがすでにコレクションにあるエントリと同じキーを持っている場合は、衝突処理が必要です。

通常、衝突は個別の連鎖を使用して処理します。または線形プロービング。

辞書を使用すると、複数のエントリを同じキーにリンクできます。

マップが個別の連鎖を実装している場合、それは辞書に似ている傾向があります。

score -2 · Accepted Answer

私は現在データ構造クラスにいます。私の理解では、dict（）データ型は、dictionary = {}として、またはキーと値を使用して初期化することもでき、基本的にリスト/配列データ型と同じです。スタックとキューを実装するために使用されます。したがって、dict（）は型であり、マップは結果のデータ構造であり、リスト型を使用してスタックまたはキューのデータ構造を実装することを選択するのと同じ方法で、辞書データ型を使用して実装することを選択できます。

dictionary - 地図と辞書の違いは何ですか？

12 に答える 12

討論

説明された用語

辞書と地図の対比

視聴者に明確に伝える

CompSciの用語と特定の実装との相互参照

C++標準ライブラリ

Related

Reference