平成22年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

データを1つずつ探すのはやめて、「計算式（ハッシュ関数）」で一発でデータの格納場所を割り出す

データの探し方「ハッシュ探索法」の問題だよ。端から順に調べる「順次探索」や、並び替えてから真ん中で分けていく「二分探索」と違って、ハッシュ探索は「キーの値を計算式に入れて、出てきた数値の場所を見に行く」というやり方をするんだ。だから、データの個数が増えても、ほぼ一発（計算量 O(1)）で見つけ出せる最強のスピードを持っているよ！

この問題で問われていること

探索スピードがデータ数に関係なく最も速い（平均の比較回数が極めて少ない）けれど、あらかじめキーから住所を計算して格納する専用のテーブル構造が必要になるハッシュ探索の特徴を選ぼう。

Search Method Comparison

hash-based lookup has the smallest average search cost when the key determines the storage location directly

sequential search: linear\nbinary search: sorted table\nhash search: direct location from key

確認ポイント

• 平均計算量で比較する。
• ハッシュはキーから場所を決める。
• 二分探索には整列が必要です。

正解

ア

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア（正解）

正解だよ。aはコード順にきれいに並んでいるから、辞書で真ん中を開いて前後を絞るような「2分探索」が一番向いているよ。bは使用頻度が高いものが前にあるから、窓口で前から順に呼ぶ「線形探索」だと、よく使うものほど早く見つかるよ。cはコードから置き場所が一発で決まるから、住所を計算して直接部屋に行く「ハッシュ表探索」がぴったりだよ。

選択肢イ

不正解だよ。aの2分探索は合っているけど、bをハッシュ表探索、cを線形探索にしているのが逆なんだ。bは置き場所を計算して決めている表ではなく、よく使う順に並べた表だから前から探す線形探索向き。cこそ、コードから場所が決まる表なのでハッシュ表探索向きだよ。

選択肢ウ

不正解だよ。cのハッシュ表探索は合っているけど、aとbが逆だよ。aはコード順に並んでいるから、電話帳を真ん中から開くように探せる2分探索が有利。bは使用頻度順で、コード順ではないから2分探索は使いにくく、前から順に見る線形探索が向いているよ。

選択肢エ

不正解だよ。aを線形探索、bをハッシュ表探索、cを2分探索にしているけど、どれも最適ではないよ。aはコード順なので2分探索、bはよく使う順なので線形探索、cはコードから場所が決まるのでハッシュ表探索が自然。合鍵を決まった棚番号で探す場面なのに、端から順に探したり辞書引きしたりしている感じだよ。