問8 ハッシュとシノニム
キーが小文字のアルファベット1文字(a,b,...,zのいずれか)であるデータを、大きさが10のハッシュ表に格納する。ハッシュ関数として、アルファベットのASCIIコードを10進記法で表したときの1の位の値を用いることにする。衝突が起こるキーの組み合わせはどれか。ASCIIコードでは、昇順に連続した2進数が、アルファベット順にコードとして割り当てられている。
- aとi
- bとr
- cとl
- dとx
ハッシュとはファイルの内容を短い文字列で表現するものです。大きなファイル同士でも小さなコストで同一かどうか判定できたりします。
今回はASCIIコード化したときの1の位ということですから、ハッシュで表現できる情報は10通りしかありません。ためしに、aのハッシュキーを0とおいたときのリストを作ってみましょう。
a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 |
dとxが同じハッシュキー3を利用していますから、衝突(シノニム)が発生しています。答えは4です。