基本情報技術者試験 令和元年度 秋季 午前 問10
ハッシュ法についての問題。ついでに衝突時の話も。
--------------------------
令和元年度 秋期 午前 問10
10 進法で 5 桁の数 を、ハッシュ法を用いて配列に格納したい。ハッシュ関数を
とし、求めたハッシュ値に対応する位置の配列要素に格納する場合、54321 は配列のどの位置に入るか。
ここで、 は、
を 13 で割った余りとする。
--------------------------
解説
5 + 4 + 3 + 2 + 1 = 15
mod(15 , 13) = 2
なので正解は選択肢イの 2。
としか書くことがない。。。
ハッシュ法については以下の問題で少し書いてみてはいる。
折角なので、ハッシュ値が衝突した場合のことを書いてみる。
ハッシュ値が衝突することはコリジョン（collision）とも呼ばれる。英単語そのまま。
ハッシュ値が衝突するデータの集まりをシノニム（synonym）と呼ぶ。
この問題のように格納先が 13 種類（0 ～ 12）しかないと、かなり頻繁に衝突が起きる。
衝突が起きた場合にどうするか。
オープンアドレス法
衝突が起きたら、何らかの手順で次の空いている格納先を探す。
- 54321 が問題のとおり配列 2 に格納されている。
- 54388 は mod(28 , 13) = 2 となるが、配列 2 にはもう 54321 がいる。
- なので、一つ後ろの配列 3 に 54388 を格納する（線形走査法）
線形走査法埋は単純でわかりやすいが、連続して配列が埋まってしまうことで衝突が起こりやすくなってしまうデメリットがある。
ちょっとだけ改良したのが二重ハッシュ法。
- 54321 が問題のとおり配列 2 に格納されている。
- 54388 は mod(28 , 13) = 2 となるが、配列 2 にはもう 54321 がいる。
- 54388 に mod(28 , 13) とは別のハッシュ関数を当てはめて格納配列を決める。
そもそもの考え方を変えてみる。
直接連鎖法（ハッシュチェイン法）
格納先を一つの箱ではなく、連結リストとする。
- 54321 が問題のとおり配列 2（の 1 番目）に格納されている。
- 54388 は mod(28 , 13) = 2 となるので、配列 2（の 2 番目）に格納される。
連結リストが長くなってしまうと検索のときに結局時間がかかってしまう。
どちらにせよ、ハッシュ値が衝突しないような工夫が大事になる。
前後の問題はこちら。
