辞書(Dictionary)・連想配列(Associative array)・ハッシュ(Hash)・マップ(Map)のデータ構造

2019年11月25日データ構造入門,データ構造,map

辞書はどのようなデータ構造か

「辞書」は「連想配列」・「ハッシュ」・「マップ」とも呼ばれるデータ構造の1つです。

鍵(key)の集合で構成されており、それぞれのkeyは1つの値と結びついています。keyを指定することで、それが指し示す値を取得することができるのです。

これは通常使われる紙の『辞書』と似ています。紙の『辞書』は単語がkeyとなり、その単語の意味が値になっています。keyとなる単語を使って調べることで、単語の意味を取得することができるのです。

具体例

例えば、あるクラスの数学のテストの成績を辞書に保存しましょう。生徒の名前をkeyとして、テストの点数を値として紐付けます。Pythonでのプログラムは以下のようになります。

math_test = {“koji”:89, “takashi”:54, “risa”:72, “aoi”:79}

このようにすると、例えば “risa”の点数を知りたいときは、

>>> math_test[“risa”]
72

などとすると取得することができます。

よく使われる命令

辞書の実装によって用意されている命令は変わります。辞書型のデータ構造が組み込まれているプログラミング言語において、よく使われる操作をまとめました。

追加(add)・挿入(insert)

keyと値のペアを、新しく辞書に追加します。

Pythonなら、math_test[“ken”]=45 などとすると新たにデータが追加されます。

再配置(reassign)・値の代入

keyに対応する値を、別のものに変更します。

Pythonなら、辞書への追加と同様に、math_test[“risa”]=92 などとすると、72から92へとデータが変更されます。

除去(remove)・削除(delete)

keyと値のペアを辞書から削除します。これはkeyで削除する対象を指定します。

Pythonなら、del math_test["risa"]などとすると、"risa"のデータが辞書から削除されます。

値の検索(lookup)

keyに対応する値を辞書内で検索して取得します。

Pythonなら、math_test[“risa”]で"risa"のデータを取得できます。

辞書の実装方法

多くのプログラム言語では、辞書型のデータ構造が提供されているので、自分で実装する機会は少ないです。

どのように実装されているかはプログラミング言語によって変わりますが、平衡2分探索木・ハッシュテーブルなどを利用して実装されることがあります。

実装時に気にするポイントとしては、

  • キー(key)の重複を許さない
  • 高速に要素へアクセスができる
  • メモリの使用量が大きくなりすぎない

などがあります。

ハッシュテーブルでの実装詳細

辞書の実装方法として最も使われる、ハッシュテーブルを用いた実装を簡単に説明します。

辞書のkeyをハッシュ関数によってハッシュ化し、その値をindexとして配列にデータを保管します。データの検索時も、keyをハッシュ化することで、同じ場所に保管されたデータにアクセスができます。

(ハッシュ関数を簡単に説明すると、データを入力として、そのデータを適当な値に変換してくれる関数のことです。)

keyをそのままindexとして、値を配列に保管しない理由としては、配列の大きさが決定できないことが挙げられます。keyが非常に大きいと、配列の大きさが足りないかもしれません。適当なハッシュ関数を用いることで、indexをある範囲に限定できるのです。

ハッシュ化した別のkeyが同じ値になってしまうこともあります(衝突)。この場合は、配列の各要素をリスト構造にすることで、複数の要素を同じindexでアクセスできるようにする連鎖法(separate chaining)や、2つめのkeyの値をズラして配列の空いている場所に保存する開番地法(open addressing)などがあります。

似ているデータ構造との違い

配列との違い

配列はindexを0(または1)からの整数値としてデータにアクセスしていました。例えば、\({3,1,5,6,11\}\)という配列に対しては、indexが0の要素は3、1の要素は1、2の要素は5、などと配列の値を取得することができました。

このように配列はデータの位置を使ってデータを取得しています。

辞書はこのindexはありません。代わりに値の取得のために鍵(key)の集合を持っており、これを使ってデータを取得します。

setとの違い

setつまり集合は、重複のない要素の集まりをもったデータ構造です。

辞書はキー(key)をsetの形で保持していますが、それぞれのkeyに値が紐付いている点が違います。