【データ構造】連想配列 辞書dict【基本講座】

【データ構造】連想配列 辞書dict【基本講座】

C言語から来た人には、馴染みのない言葉かもしれませんが、C++や他の言語から来た人には、お馴染みのデータ構造かもしれません。

出典:http://www.photo-ac.com/

ゼロから学ぶ データ構造 連想配列編

連想配列の特徴

連想配列とは、コンピュータプログラミングにおいて、添え字にスカラー数値以外のデータ型(文字列型等)も使用できる配列のことを言う。

連想リスト、連想コンテナ、辞書(ディクショナリ、dictionary)、ハッシュ(hash)、マップ(map)とも呼ばれます。

辞書(ディクショナリ、dictionary)は、要素を本文、キーを見出しになぞらえた者からそう呼ばれるようになった。

ハッシュ(hash)は、ハッシュテーブルにより実装されるところからそう呼ばれている。

抽象データ型としての連想配列

連想配列は、キーの重複が許されていません。連想配列(マップ)を拡張したマルチマップは、キーが重複したデータも上書きせずに保持できるデータ構造です。

連想配列で用いられる操作

追加・挿入

新しいキーと値を対に配列して、追加する。また、キーと値の間への新たな参照を生成する挿入がある。

再配置・置換

既存のキーと値を対にしたものを書き換える、再配置。きーさからの古い参照を新たな値への参照に再生成する置換がある。

除去・削除

キーと値を対に配列しそれを削除する。または、参照を消去する(除去できる)。

検索・参照

キーに束縛されている値を取り出す検索。引数はキーであり、キー束縛された値が戻り値になる参照がある。

連想配列の実装例

連想配列の実装例は、平衡2分探索木(赤黒木やAVL木など)やハッシュテーブルが有名で、B木や連想リスト、トライ木、基数木などがある。

配列と連想配列の違いは何ですか?

プログラミングにおける単純な配列は、特定のアドレスからのオフセット(ずれ)をインデックスとして、アドレスとオフセットによって目的の値を得ることができる。
また、連想配列は、要素とそれを紐づけできるような値(キー:key)のペアで表され、キーによって目的の値を求めることができる。

がんばらないでプログラマーになりたい人向けの学習方法とは?

【スクール】今流行りのプログラミングスクールについて徹底的に調べてみた