BohYoh.com《基本情報技術者試験》2003年度＝平成15年度・春期午前問14

基本情報技術者試験

2003年度＝平成15年度・春期

午前

問14

　アルファベット3文字で構成されるキーがある。次の式によってハッシュ値h を決めるとき、キー“SEP”と衝突するのはどれか。ここで、a mod b は、a をb で割った余りを表す。

　　h ＝（キーの各アルファベットの順位の総和）mod 27

アルファベット	順位
A	1
B	2
C	3
D	4
E	5
F	6
G	7
H	8
I	9
J	10
K	11
L	12
M	13

アルファベット	順位
N	14
O	15
P	16
Q	17
R	18
S	19
T	20
U	21
V	22
W	23
X	24
Y	25
Z	26

　ア　APR

　イ　FEB

　ウ　JAN

　エ　NOV

解答

　イ

解説

　ハッシュ法は、キー値に対して何らかの変換関数を適用することによって、そのデータを格納する配列の添字を求める手法です。なお、変換関数のことをハッシュ関数と呼びます。

　文字列“SEP”のハッシュ値は、次のように求められます。
　　SEPのハッシュ値＝ (19 + 5 + 16) mod 27 ＝ 40 mod 27 ＝ 13
　選択肢のハッシュ値を順に求めていきます。
　　APRのハッシュ値＝ (1 + 16 + 18) mod 27 ＝ 35 mod 27 ＝ 8
　　FEBのハッシュ値＝ (6 + 5 + 2) mod 27 ＝ 13 mod 27 ＝ 13
これで、選択肢イのFEBのハッシュ値がSEPと等しくなり、衝突することが分かります。