4-6 データの探索

令和5年7月修了試験  問15

ハッシュ法の説明として,適切なものはどれか。

解答 ア

【頭の準備体操】
ハッシュ法は,ハッシュ関数を用いてレコードのキー値からレコードの格納アドレスを求めることでアクセスする方法。

令和6年1月修了試験  問6

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

h = (キーの各アルファベットの順位の総和) mod 27


アルファベット順位
A1
B2
C3
D4
E5
F6
G7
H8
I9
J10
H11
L12
M13
 
アルファベット順位
N14
O15
P16
Q17
R18
S19
T20
U21
V22
W23
X24
Y25
Z26

解答 イ

【頭の準備体操】
ハッシュ値が同じ値になり格納アドレスが衝突することをシノニムという。

“SEP”のハッシュ値。S=19,E=5,P=16なので,
h=(19+5+16) mod 27 =40 mod 27=13

令和6年度公開  問2

キーが小文字のアルファベット1文字(a,b,…,zのいずれか)であるデータを,大きさが10のハッシュ表に格納する。ハッシュ関数として,アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは,昇順に連続した2進数が,アルファベット順にコードとして割り当てられている。

解答 エ

【頭の準備体操】
ハッシュ値が同じ値になり格納アドレスが衝突することをシノニムという。

「ASCIIコードでは,昇順に連続した2進数が,アルファベット順にコードとして割り当てられている」とあるが,ASCIIコードが示されていないので,アルファベットのASCIIコードを10進表記法で表した,次の表を例に考える。
ここで,ASCIIコードを10進表記法で表したときの1の位の数(0~9)を用いて,大きさが10のハッシュ表に格納する。


1 2 3 4 5 6 7 8 9 10 11 12 13
a b c d e f g h i j k l m
14 15 16 17 18 19 20 21 22 23 24 25 26
n o p q r s t u v w x y z