HOME»基本情報技術者平成15年春期»午前問14
基本情報技術者平成15年春期 午前問14
問14
アルファベット3文字で構成されるキーがある。次の式によってハッシュ値hを決めるとき，キー"SEP"と衝突するのはどれか。ここで，a mod bは，aをbで割った余りを表す。
h＝(キーの各アルファベットの順位の総和) mod 27
h＝(キーの各アルファベットの順位の総和) mod 27
- APR
- FEB
- JAN
- NOV
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
イ
解説
キーの値から関数によって、データの格納場所などを求める方法をハッシュ法と言います。ハッシュ法では、異なるキー値から同じハッシュ値が得られることがあり、これを衝突（シノニム）といいます。
設問の指示に従って、キー"SEP"のハッシュ値を計算します。各アルファベットを表に当てはめると、S=19、E=5、P=16なので、
h＝(19＋5＋16) mod 27
＝40 mod 27＝13
キー"SEP"のハッシュ値hは13となります。同じ手順で選択肢それぞれのキーについてもハッシュ値hを計算し、一致するものを探します。
設問の指示に従って、キー"SEP"のハッシュ値を計算します。各アルファベットを表に当てはめると、S=19、E=5、P=16なので、
h＝(19＋5＋16) mod 27
＝40 mod 27＝13
キー"SEP"のハッシュ値hは13となります。同じ手順で選択肢それぞれのキーについてもハッシュ値hを計算し、一致するものを探します。
- A=1、P=16、R=18なので、
(1＋16＋18) mod 27＝35 mod 27＝8
ハッシュ値は一致しません。 - F=6、E=5、B=2なので、
(6＋5＋2) mod 27＝13 mod 27＝13
キー"SEP"とハッシュ値が一致するので衝突が発生します。 - J=10、A=1、N=14なので、
(10＋1＋14) mod 27＝25 mod 27＝25
ハッシュ値は一致しません。 - N=14、O=15、V=22なので、
(14＋15＋22) mod 27＝51 mod 27＝24
ハッシュ値は一致しません。