4 ハッシュマップ

4.1 基本的な考え方

単語のスペルから直に配列の添え字の値が導くことが出来れば，

の計算量で済む．これはとても高速である．たとえば，表1に示した単語データベースのようなものを配列に格納することを考える．ただし，以下の条件を課す．

スペルが同じで意味の異なる単語は無いものとする．
スペルは最大，アルファベットで9文字とする．

次のようにすれば，スペルから配列の値を求めることができる．

アルファベットに対して，整数を割り当てる．aが1，bが2， cが3, $\cdots$ ,zが26のようにである．もうひとつアルファベット長い場合(空白)が必要で，それは0を割り当てる．このようにすれば，英単語は整数で表現できる．
apple $\rightarrow$ (1,16,16,12,5,0,0,0,0) pineapple $\rightarrow$ (16,9,14,5,1,16,16,12,5)
これを9次元配列に格納することもできるが，少し工夫して1次元配列a[i]に格納することを考える．つぎの演算により，添え字iを求めれば1次元配列とすることができる．

$\displaystyle i=a_1\times27^0+a_2\times27^1+a_3\times27^2+a_4\times27^3+a_5\times27^4+a_6\times27^5+a_7\times27^6+a_8\times27^7+a_9\times27^8$

このようにスペルから直接添え字の値が計算できる配列に英単語を格納すると，とても高速に探索，削除，追加ができるデータ構造となる．すべて，計算量のオーダーはである．しかし，この方法をよく考えると大きな問題がある．巨大なメモリー空間が必要なのである．配列の最大の添え字は， $1\times27^9-1=7625597484986$ となりとても現在のコンピューターで取り扱うことができない．

このような配列に単語を格納すると，ほとんどその中は空になる．単語の数はそれほど多くない．諸君の英和辞典の単語数を調べてもよく分かる．そこで，この配列の添え字を 0～99999に圧縮することを考える．新たな添え字をjとすると，

	j=i%100000;

とすれば良い．100000で割った余りとすれば，0～99999の値が得られる．このようにして，データにアクセスする方法をハッシュ法と言う．得られた値(0～ 99999)をハッシュ値と言い，キーを変数として，それを求める関数をハッシュ関数と言う．

このようにすると，明らかに以下の問題点がある．

異なるキーで同じハッシュ値となる場合がある．

これについて，以降，教科書に沿って説明する．

4.2 ハッシュ値の決め方

ハッシュを使う場合，配列にそのままデータを入れないで，データを表すポインターを入れる方が便利である．ポインターが表すものを構造体とすれば，かなり柔軟に対応できる．後で述べるがハッシュ値の重複(衝突)対策でリストやツリー構造を使う場合も対応が容易である．

ハッシュ法を使うためには，教科書に書いてあるとおり，以下のような動作が必要である．

ハッシュ表を用意する．これは，ポインターを格納する配列である．
ハッシュ関数(ハッシュ値)を決める．

ハッシュ表は，データを示すポインターを入れる配列である．キーを決めるとハッシュ関数を計算してハッシュ値が決まる．このハッシュ値がこの配列の添え字の値となる．そして，そこに格納されている配列の値(ポインター)により，データにアクセスする．

ハッシュ表を作るときにはデータ数よりも大きいことが望ましい．そうしないと，異なったキーでも同じハッシュ値となり，衝突が発生し，データの探索スピードが落ちてしまう．衝突の問題は後で述べるので，ここではハッシュ関数の作り方を説明する．ハッシュ表の大きさは素数とすることが望ましい．こうすることにより，キーのどのビットが変化してもハッシュ値の値を変化させることができる．

ハッシュ関数は，一般に，次の2つの手順により成り立っている．

キーからなにがしかの演算を行い整数値を導き出す．
導き出された整数をなにがしかの演算により，ハッシュ表(配列)の大きさの整数に直す．

最初のキーから整数値を導き出す方法は，いろいろある．これについては，教科書の方法を説明する．一方，これをハッシュ表の大きさの整数に直す方法は，大体決まっている．キーから導き出された整数をハッシュ表の大きさで割って，その余りとするのである．

4.3 ハッシュ値の重複対策

異なるキーであっても，同じハッシュ値となることがある．これが多いとハッシュ法の効果が薄いのであるが，どうしても避けることができない．プログラマーはその対策を講じなくてはならない．教科書に書かれている方法は，次の通りである．

リストを用いる方法(教科書 p.222 Fig.7-7)
2分木を用いる方法(教科書 p.224 Fig.7-9)
再ハッシュ(教科書 p.222 Fig.7-8　p.224 Fig.7-10)

これらについては，教科書を用いて説明する．

ホームページ: Yamamoto's laboratory
著者: 山本昌志

Yamamoto Masashi
2006-01-30