辞書はどのようなデータ構造か「辞書」は「連想配列」・「ハッシュ」・「マップ」とも呼ばれるデータ構造の1つです。鍵(key)の集合で構成されており、それぞれのkeyは1つの値と結びついています。keyを指定することで、それが指し示す値を取得することができるのです。これは通常使われる紙の『辞書』と似ています。紙の『辞書』は単語がkeyとなり、その単語の意味が値になっています。keyとなる単語を使って調べることで、単語の意味を取得することができるのです。あるクラスの数学のテストの成績を辞書に保存しましょう。生徒の名前をkeyとして、テストの点数を値として紐付けます。Pythonでのプログラムは以下のようになります。math_test[“risa”]72などとすると取得することができます。辞書の実装によって用意されている命令は変わります。辞書型のデータ構造が組み込まれているプログラミング言語において、よく使われる操作をまとめました。追加(add)・挿入(insert)keyと値のペアを、新しく辞書に追加します。すると新たにデータが追加されます。再配置(reassign)・値の代入keyに対応する値を、別のものに変更します。すると、72から92へとデータが変更されます。除去(remove)・削除(delete)keyと値のペアを辞書から削除します。これはkeyで削除する対象を指定します。math_test["risa"]などとすると、"risa"のデータが辞書から削除されます。値の検索(lookup)keyに対応する値を辞書内で検索して取得します。Pythonなら、math_test[“risa”]で"risa"のデータを取得できます。多くのプログラム言語では、辞書型のデータ構造が提供されているので、自分で実装する機会は少ないです。どのように実装されているかはプログラミング言語によって変わりますが、平衡2分探索木・ハッシュテーブルなどを利用して実装されることがあります。実装時に気にするポイントとしては、キー(key)の重複を許さない高速に要素へアクセスができるメモリの使用量が大きくなりすぎないなどがあります。辞書の実装方法として最も使われる、ハッシュテーブルを用いた実装を簡単に説明します。辞書のkeyをハッシュ関数によってハッシュ化し、その値をindexとして配列にデータを保管します。データの検索時も、keyをハッシュ化することで、同じ場所に保管されたデータにアクセスができます。(ハッシュ関数を簡単に説明すると、データを入力として、そのデータを適当な値に変換してくれる関数のことです。)keyをそのままindexとして、値を配列に保管しない理由としては、配列の大きさが決定できないことが挙げられます。keyが非常に大きいと、配列の大きさが足りないかもしれません。適当なハッシュ関数を用いることで、indexをある範囲に限定できるのです。ハッシュ化した別のkeyが同じ値になってしまうこともあります(衝突)。addressing)などがあります。似ているデータ構造との違い配列との違い配列はindexを0(または1)からの整数値としてデータにアクセスしていました。\({3,1,5,6,11\}\)という配列に対しては、indexが0の要素は3、1の要素は1、2の要素は5、などと配列の値を取得することができました。このように配列はデータの位置を使ってデータを取得しています。辞書はこのindexはありません。代わりに値の取得のために鍵(key)の集合を持っており、これを使ってデータを取得します。setとの違いsetつまり集合は、重複のない要素の集まりをもったデータ構造です。辞書はキー(key)をsetの形で保持していますが、それぞれのkeyに値が紐付いている点が違います。ソートアルゴリズムの中でも、最も基本的なアルゴリズムの一つです。マージソートは分割統治法を用いたソートアルゴリズムの1つです。コメントをキャンセルメールアドレスが公開されることはありません。*次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。上に表示された文字を入力してください。