[データ構造] 連想配列

連想配列

連想配列（れんそうはいれつ、英語: associative array）とは、コンピュータプログラミングにおいて、添え字にスカラー数値以外のデータ型(文字列型等)も使用できる配列である。抽象データ型のひとつ。連想リスト、連想コンテナ、辞書（あるいはカタカナでディクショナリ英語: dictionary）、ハッシュ（英語: hash）、マップ（英語: map）とも呼ばれる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

連想配列は、「キーと値のペア」の集合から成るデータ構造で、キーはその集合の中で唯一のものとなります。

ハッシュテーブルや平衡2分探索木を使い実装されます。

ハッシュテーブルを用いた連想配列では、多くの操作を\( O(1)\) で行うことができます。

連想配列の操作

基本的に、連想配列で「ソート」は考えません。

追加

新しい「キーと値のペア」の追加を行います。

削除

「キーと値のペア」の削除を行います。

更新

既に存在する「キーと値のペア」の更新を行います。

検索

キーから値を検索します。

ハッシュテーブル

ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

連想配列の「キーと値のペア」で、キーがインデックスでになると、それは配列になります。

例えば、以下のような配列を考えます。

インデックス	値
0
1
2	apple
3
4	banana

array_fruites でarray_fruites[2]とすればappleを取得できます。

array_fruites[4]=orange とすれば値の書き換えを行えます。

これら配列の操作は\( O(1)\)で行えます。

配列のインデックスを、キーとして数値以外で表現できれば、連想配列になります。

このため、インデックスとキーの変換を行うのがハッシュテーブルです。

ハッシュ関数

以下のようなハッシュテーブルを考えます。

ここで、キーからインデックスへの変換を行う関数は、ハッシュ関数と呼ばれます。

ハッシュ関数 (ハッシュかんすう、英: hash function) あるいは要約関数^[1]とは、任意のデータから、別の（多くの場合は短い固定長の）値を得るための操作、または、その様な値を得るための関数のこと。ハッシュ関数から得られた値のことを要約値やハッシュ値または単にハッシュという。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

ハッシュ関数には色々関数が考えられますが、ここでは、単純な剰余演算を考え、\(n\)をキーを整数として表現した値、\(m\)を配列の総数として、ハッシュ関数を\(h(n) = n mod m \)とします。\(m\)には、出力の一様性が成り立つよう素数を使うのが良いとされています（直感的には、剰余演算だから、偶数より奇数の方が答えに偏りがなさそうで、さらに奇数より素数を使った方が偏らなさそうな感じ）。

例えば、もしキーが整数であれば、剰余演算を使うことでインデックスに変換し、もしキーがアルファベットであればASCII の文字コードを使い整数に変換してから剰余演算を使います。

衝突

ハッシュ関数では、異なるキーが同じハッシュ値になる場合があり、衝突と呼びます。

例えば、 \(h(n) = n mod m \) で \(m=11\)とすると、\(n=9\) と \(n=20\)はともに \(9\)で同じハッシュ値になってしまいます。

衝突が起こってしまった場合、チェイン法かオープンアドレス法を使い衝突を解決します。

チェイン法

ハッシュ値の衝突が起こったとき、値の保存に連結リストを使うことで、同じインデックスに複数の値を保持します。

ただし、衝突が多くなると\( O(1)\)での操作が難しくなり、またメモリ効率も悪化してしまいます。

しかし、同じインデックスに複数の値が保持できるので、確保しているスロットの量に関わらず複数の値を保持できます。

オープンアドレス法

ハッシュ値の衝突が起こったとき、別の空いているインデックスを探し、そちらに値を保持します。

空いたインデックスの探し方として、例えば次の空いているインデックスに値を保持する線形走査法や、インデックスを1、2、4、8…と増やす2次操作法、ハッシュ値をさらにハッシュ化する再ハッシュ法などがあります。

しかし、空いているインデックスをどんどん埋めていくので、チェイン法とは異なり確保したスロットの分しか値を保持できません。

連想配列の計算量

	平均	最悪
空間	\(O (N)\)	\(O (N)\)
探索	\(O (1)\)	\(O (N)\)
挿入	\(O (1)\)	\(O (N)\)
削除	\(O (1)\)	\(O (N)\)

連想配列も配列なのでキーが分かっていればとても速く、基本的には\(O(1)\) で動作します。

ただし衝突が起こると最悪 \(O (N)\)になってしまうので、「衝突の起こりにくいハッシュ関数の選択」「衝突が起こった場合の対処方法」の面で工夫が必要になります。

ハッシュテーブルの動的拡張

load factor

“load factor”とは、\(n\)をハッシュテーブルへのエントリ数、\(N\)を配列のサイズとして、\(n / N \)で表され、もし0であればハッシュテーブルは空、1であればハッシュテーブルはいっぱいであることを表します。

“load factor” が1に近い場合は衝突がたくさん起こってしまうので計算の時間的な効率が悪く、逆に0に近い場合はメモリの空間的な効率が悪いというトレードオフの関係になっているので、 “load factor” の値の調節、つまりエントリ数 \(n\) に応じた配列のサイズ \(N\) の適度な調節が必要になります。

Python では、 “load factor” が2/3 を超えるとハッシュテーブルの拡張が行われるそうです。

Dictionary size reduces upon increasing one element

しかし、ハッシュ値はハッシュテーブルのサイズによって決まるので、動的拡張が行われると全てのハッシュ値の再計算が行われるので、\( O(N)\)の計算量になってしまいます。（ちなみに、動的拡張の際に配列のサイズを指数的に拡張することで、償却解析という見方では \( O(1)\)の計算量とみなすこともできます。）