１９９８／０７／０５
注意１：このページは、回線を切断した後でゆっくりご覧になってください（テキストを印刷する場合は、その取り扱いに注意してください）。
注意２：背景が白地の画面を長時間見つめていると頭が痛くなってしまいますので、ここは背景をグレーにしています。
問１ 次の流れ図の説明及び流れ図を読んで、設問に答えよ。
［流れ図の説明］
配列Ａ(1)〜Ａ(n)に格納されている正の整数データを、ハッシュ法を用いてテーブルに登録する処理の流れ図である。
ハッシュ法は、表の探索及び表へのエントリの登録，更新を効率よく行う際などに用いられる手法の一つである。この手法はハッシュ関数と呼ぶ計算式を用いて、対象データを限定された範囲の値（ハッシュ値）に変換し、この値を利用してテーブル上の格納位置を決定する。ここではハッシュ関数として、次の式を用いる。
ハッシュ値＝整数データを１５で割った余り＋１
ハッシュ法の特徴は、異なるデータのハッシュ値が等しくなる場合がある（これを衝突という）ことである。この流れ図では、衝突が生じた場合の解決方法として、ハッシュ値が等しいデータ同士をチェーンでつなぐ方式を用いている。
テーブルは図に示すように、整数データ（ｄａｔａ）とチェーン（ｃｈｎ）の二つの要素からなるレコードの配列で構成されている。テーブルの先頭１５レコード（添字の値が１から１５まで）は、ハッシュ値が各添字の値に等しい最初の整数データを格納するための領域である。添字が１６以降のレコードは、ハッシュ値が等しい２個目以降の後続データを発生した順に格納するための領域である。
テーブル（ｄａｔａ及びｃｈｎ）の初期値として、すべての要素に０を格納しておく。ハッシュ値の等しいデータがある場合には、後続データを格納した場所の添字の値をチェーンに格納する。
例えば、図は配列Ａに格納されている四つの整数データ（７５，１００，２５３，３５５）を順にテーブルへ登録した状態を示すものである。整数データ１００及び３５５はハッシュ値が１１で同じ値となり、整数データ１００のレコードのチェーンには整数データ３５５のレコードの添字の値１６が格納されている。
設問 流れ図中の（ ）に入れる正しい答えを、解答群の中から選べ。
ａに関する解答群
ア ０ イ １ ウ １５ エ １６ オ ｎ
ｂ，ｃに関する解答群
| ア | ｄａｔａ（ｈａｓｈ） | イ | ｄａｔａ（ ｊ ） | ウ | ｄａｔａ（ ｋ ） | エ | ｃｈｎ（ｈａｓｈ） |
| オ | ｃｈｎ（ ｊ ） | カ | ｃｈｎ（ ｋ ） | キ | ｋ | ク | ｈａｓｈ |
今週はハッシュ法（によるテーブル登録）に関する問題というよりも、リスト要素の追加に関する問題と考えた方がいいでしょう。だけどせっかくですので、ここでハッシュ法について簡単に触れておきます。
ハッシュ法とは、アクセスする要素をハッシュ関数（問題にあるように、余りをとる関数が一般的）により変換し、変換した値からアクセスする位置を見つける探索手法です。
データを登録する際、求めたハッシュ値（ハッシュ関数の値）の位置にすでにデータが格納されている状態のことを、衝突（コリジョン）といいます。またこのとき、先に格納されているデータ（問題では１００）をホームデータ，後に格納しようとしたデータ（問題では３５５）をシノニムデータといいます。
衝突が発生した場合に備えた対処法としては、チェーン法（オープンハッシュ法）とオープンアドレス法（クローズドハッシュ法）があります。今週の流れ図の処理は、チェーン法によって衝突に備えていました。
ちなみにオープンアドレス法は、衝突が発生した時、テーブル（ハッシュ表）に空いてる位置が見つかるまで、再ハッシュを行う方式です。
さて問題の解説です。
流れ図の処理はチェーン法によって衝突に備えていました。チェーン法は、同じハッシュ値のデータをリスト構造によって表現する方式です。以下の図を参照してください（四角中の斜め線はリストの終わりを意味する）。
データ１００，３５５，５５は同じハッシュ値１１を持ちます。そこで、最初の１００から３５５にポイントし、さらに３５５から５５にポイントします。
問題ではこのリスト構造を、配列を用いて表現していました。
ｂについて
ａを解答するにはｊの意味を把握しなければなりませんが、ｊは流れ図の後半で出てきますので後回しにしましょう。
空欄ｂの処理に流れるのは、ｄａｔａ(ｈａｓｈ)＝０の時です。ｄａｔａ(ｈａｓｈ)の値が０になるのは、今回テーブルに登録するＡ(i)と同じハッシュ値のデータが、まだテーブルに登録されていないことを意味します（テーブルに登録するＡ(1)〜Ａ(n)の値は正の整数だから．．．登録されていれば絶対に０にならない）。
つまり、ｄａｔａ(ｈａｓｈ)の領域が空いているのですから、そのままその位置にＡ(i)を格納すればよいでしょう。
ａについて
空欄ｃの処理に流れるのは、今回テーブルに登録するＡ(i)と同じハッシュ値のデータが、すでにテーブルに登録されている時です（ｂの解説の逆です）。
Ａ(i)と同じハッシュ値のデータがすでにテーブルに登録されている場合は、Ａ(i)は添字が１６以降の要素に格納しなければなりません（問題文より）。
探索ループの１つ後に、”Ａ(i)→ｄａｔａ(j)”の処理がありますので、「格納する要素の添字はｊである」と分かります。
さらに、探索ループの２つ後に、”ｊ＋１→ｊ”の処理が見えます。
するとｊは増加する方向に進むのですから、ｊの初期値としては”採りうる最も小さい値”で初期化する必要があります。よって求める答えは１６です。
ｃについて
リストに新たな要素を追加する場合、追加する要素の１つ手前の要素のポインタ（次にチェーンするためのデータ）を更新する必要があります（ポインタは本問題におけるｃｈｎの値です）。
例えば、上図でデータ５５の後にデータ８５を追加するとすれば、追加前の５５のポインタは０（リストの終わり）ですが、これを８５へのポインタに更新する必要があります。
結論から言えば、本問題で衝突が発生した場合もこの処理を行わなければなりません。これが”ｊ→（ ｃ ）”の処理です。
”探索”ループ中の”ｃｈｎ(ｈａｓｈ)→ｈａｓｈ”では、リストの要素を１つづつ進める処理を行います。この処理を行った結果ｈａｓｈが０になった時に”探索”ループを脱出していますが、ｈａｓｈが０になるのは、リストの末尾まで達した時です（添字は１から始まるので、チェーンがあれば絶対に０にならない）。
また”ｃｈｎ(ｈａｓｈ)→ｈａｓｈ”の前に”ｈａｓｈ→ｋ”の処理がありますので、ｋはｈａｓｈが指す要素の一つ手前の要素の添字になっています。
以上を総合して、空欄ｃは、今回格納した要素の一つ手前の要素のポインタ部分つまりｃｈｎ(k)を、今回格納した要素の添字つまりｊで更新する処理が入ります。
今週は以上です。
ではまた来週。