ハッシュ法の格納場所と衝突をどう見分けるか
基本情報技術者試験 平成30年度春期 午前 問7 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
表探索におけるハッシュ法の特徴はどれか。
- ア
2分木を用いる方法の一種である。
- イ
格納場所の衝突が発生しない方法である。
- ウ
キーの関数値によって格納場所を決める。
- エ
探索に要する時間は表全体の大きさにほぼ比例する。
会話形式の解説
講師格納場所を何から決めるかに注目しましょう。ハッシュ法では、キーを関数に入力します。
受験者二分木を使う方法もキーを探しますが、格納場所の決め方が違うのですか。
講師はい。二分木では節点をたどってキーを探します。ハッシュ法はキーの関数値から格納場所を決めるので、二分木を用いる方法の一種ではありません。
受験者それなら、キーの関数値によって格納場所を決めるという説明が正解ですね。
講師そのとおりです。ただし、関数で決めるからといって、異なるキーが必ず異なる場所になるわけではありません。
受験者異なるキーから同じ場所が求められたら、衝突が起こるのですね。
講師はい。したがって、衝突が発生しないという説明は誤りです。
受験者探索時間が表全体の大きさにほぼ比例する、という説明はどう考えればよいですか。
講師表の全件を順に調べるかどうかを確かめます。ハッシュ法はキーから求めた場所を手掛かりに探すため、その説明も当てはまりません。
受験者格納場所の決め方で見分ければ、二分木や全件を順に調べる探索と区別できますね。衝突の可能性も忘れないようにします。
講師その整理でよいです。関数値で場所を決めることと、衝突が起こり得ることを一緒に押さえましょう。
まとめ
ハッシュ法は、キーに関数を適用し、その値を使って格納場所を決めます。したがって、正解は「キーの関数値によって格納場所を決める」です。二分木の節点をたどる方法とは異なり、異なるキーが同じ場所に対応して衝突することもあります。表の全件を順に調べる方式ではないため、探索時間が表全体の大きさにほぼ比例するという説明も当てはまりません。
解答・解説
正解はウです
この問題のテーマ
ハッシュ法がキーから格納場所を決める仕組みを問う問題です。
解き方の考え方
各選択肢が、格納場所の決め方と一致するかを確かめます。あわせて、衝突が起こる可能性と、探索時に表全体を調べる必要があるかを見ます。
選択肢ごとの解説
- ×ア 2分木を用いる方法の一種である。二分木を用いる探索は、木の節点をたどって目的のキーを探します。ハッシュ法はキーに関数を適用して格納場所を決めるので、二分木を用いる方法の一種ではありません。
- ×イ 格納場所の衝突が発生しない方法である。異なるキーから同じ格納場所が求められることがあります。その場合に衝突が発生するため、衝突しないという説明は当てはまりません。
- ○ウ キーの関数値によって格納場所を決める。キーに関数を適用し、その結果を使って格納場所を決めます。選択肢の「キーの関数値によって」という説明が、この仕組みに一致します。
- ×エ 探索に要する時間は表全体の大きさにほぼ比例する。ハッシュ法では、キーから求めた格納場所を手掛かりに探索します。表の全件を順に調べる方式ではないので、探索時間が表全体の大きさにほぼ比例するとはいえません。
POINT
- ハッシュ法では、キーを関数に入力して格納場所を求めます。
- 異なるキーが同じ場所に対応する衝突は起こり得ます。
- 探索時間を考えるときは、表全体を順に調べる方式かどうかを区別します。