解説 5月31日B

n個のデータがソートさえしてあれば、そのデータに対して二分探索するための計算量は O(logn)である。しかし、そもそもn個のデータをソートする計算量は一般に O(n logn)である。

ハッシュ法はこのようにとてもよい探索法であるが、唯一の欠点はハッシュテーブルを作成、記憶するために必要なメモリが大きいことである。ただし、大きいと言っても、2n以上の大きさがあればよいので、実用上はあまり問題にならない。

ハッシュ法の中心は、データを記憶するための配列と、配列の指標を計算するためのハッシュ関数である。ここでデータは「キー(key)」と格納すべき「値」という二つの要素を持つものとする（ここで、キーと値が一致しても構わない）。ハッシュ法における探索では、まずキーを「ハッシュ関数」によりある範囲の整数に変換する。この数をハッシュ値という。そしてこのハッシュ値を指標として配列の要素を取り出す。これが記憶されたデータ(の「値」)に相当する。みて分かるように、ハッシュ法における探索で必要な手間は、キーをハッシュ関数により数(ハッシュ値)に変換すること(これ自体は計算量O(1))と、配列から指標により要素を取りだすこと(これも計算量O(1))だけである。このような理由からとても速い探索なのである。

しかしながら、世の中には落とし穴がいくつかある。ハッシュ法では次のような落とし穴が待ち構えている:

なおこれにはいろいろな解決策がある。どのような解決策をとるにせよ、それぞれの問題に対する解決策を実装して、ハッシュ法により探索が行えるようにしたデータ構造をハッシュテーブルという。

ハッシュ関数

データを記憶するための配列のサイズをmとする。ハッシュ関数はキーを0からm-1までの整数に変換する関数である。こうすれば、ハッシュ関数の値を配列の指標として使える。

具体的に書こう。格納すべきデータ(のキー)を S ={x1,x2,…,xn}とし、データを記憶するための配列をAとする(配列の大きさはmとする)。ここで簡単のため、xiは数としよう。ハッシュ法で探索するには、どの項目xi も配列Aのどこかに入れなければならない。そして、なるべくデータがAの中に散らばって入るようにしたい(少なくとも、同じところには入れられないので)。こここでデータxiに配列の指標を与えるのがハッシュ関数である。

課題1-1

Rubyでは、ハッシュ関数としてどのようなものが使われているかをウェブページやマニュアルなどを使って調べ、その仕組みをなるべく具体的に説明せよ。

課題1-2

キーが数ならば剰余関数でもハッシュ関数として使えなくはない。しかしキーが"abc"のような文字列では（そもそも割り算ができないので）剰余関数は使えない。そこで、キーが文字列の場合でも数を返すようなハッシュ関数を作りなさい。そして、そのハッシュ関数が"abc"と"abcdef"に対してどのようなハッシュ値を返すかを示しなさい。ただし配列のサイズmを113とする。
[ヒント]

文字は計算機の中では数として表されています。特にアルファベットの場合、その数のことをASCII(アスキー)コードと呼んでいます。次は文字列"ABCxyz"を構成する一つ一つの文字のASCIIコードを表示するプログラムです。これをもとに考えてみてください。

 str = "ABCxyz"           # 対象とする文字列
 for i in 0..str.size-1   # iを0からstr-1までの数として、以下を繰り返す
    p str[i]              # 対応する文字のASCIIコードを表示
 end # for i

この結果は次のとおりです:

ハッシュ値の衝突

どのようにハッシュ関数を工夫しようとも、データ数が多くなると、異なるデータが同じハッシュ値をもつことは避けられない(つまり違うキーに対しハッシュ関数が同じ値を返すことが起こる)。この現象をハッシュ値の衝突という。

教科書39ページにあるように、データ数がnであるとすると配列の大きさmを 2n程度にとれば、探索の計算量がO(1)というハッシュテーブルが作成できることが知られている。しかしこのように配列の大きさを十分大きくとったとしても、それでもハッシュ値の衝突は確率的に起こるのである。

課題1-3

ハッシュテーブルのための配列の大きさm=20、ハッシュ関数h(x)=x % m(つまり整数xをmで割った余り)としたとき、次の10個の数を格納するハッシュテーブルを作れ。ただしハッシュ値の衝突の対策として、(1)線形探査法と(2)チェイン法、のそれぞれによるものを答えること。

   32, 76, 105, 200, 282, 888, 28, 168, 56, 1219