ハッシュ法の説明として,適切なものはどれか。
解答 ア
【頭の準備体操】
ハッシュ法は,ハッシュ関数を用いてレコードのキー値からレコードの格納アドレスを求めることでアクセスする方法。
アルファベット3文字で構成されるキーがある。次の式によってハッシュ値hを決めるとき,キー“SEP”と衝突するのはどれか。ここで,a mod bは,aをbで割った余りを表す。
解答 イ
【頭の準備体操】
ハッシュ値が同じ値になり格納アドレスが衝突することをシノニムという。
“SEP”のハッシュ値。S=19,E=5,P=16なので,
h=(19+5+16) mod 27
=40 mod 27=13
キーが小文字のアルファベット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 |