平成19年 春期 基本情報技術者 午前 問15

表探索におけるハッシュ法の特徴はどれか。

 ア  2分木を用いる方法の一種である。
 イ  格納場所の衝突が発生しない方法である。
 ウ  キーの関数値によって格納場所を決める。
 エ  探索に要する時間は表全体の大きさにほぼ比例する。


答え ウ


解説
キーワードで書いたように、ハッシュ法はキー(要素)の関数の結果によって格納場所を決める。
ハッシュ法は関数によっては、異なったキーで同じ格納場所が求められることがあり、あるキーの関数値で求められた格納場所にすでにデータが格納済みだったときのことを“衝突”と言う。なお、“衝突”が発生した場合の格納場所も決まった方法で求める。
また、ハッシュ法は関数で格納場所を求めるため、処理時間が配列の大きさが処理時間に影響せず一定である。


キーワード
・ハッシュ表

キーワードの解説
  • ハッシュ表
    整列・探索の方法の一つで、整列時は要素を探索用に定めた関数で処理して表(配列)のどこに格納するかを決定する。
    探索時は、探している数に対し関数で格納する位置を求めて、表のその位置に探している数があるかどうか探索結果を判断する。

もっと、「ハッシュ」について調べてみよう。

戻る 一覧へ 次へ