ハッシュ

問題

応用情報技術者平成23年特別 午前問8

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

• a と i
• b と r
• c と l
• d と x

答え

dとx

解説

ハッシュ

ハッシュ、ハッシュ値 – データから算出した小さな値。各データを区別・表現する目的に用いる。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ハッシュとは、ハッシュドビーフと言うように、もともとは肉を細切れにしたものを意味します。

そこからの類推で、データの確認や探索のために、あるデータを何らかの方法で要約して表現したものがハッシュと呼ばれます。また、この要約の方法はハッシュ関数を呼びます。

データを要約、短く表現する以上、他のデータとハッシュ値が重複する可能性があります。これをハッシュ値の衝突やシノニムと呼びます。

問題のハッシュ関数は、「アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする」 です。

また、「ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている」とあるので、アルファベットを並べた以下のような表を作ると、衝突が起こるキーの組み合わせを調べることができます。

よって衝突が起こるのは、ハッシュ値が3となる、dとxの場合です。