問題
問2
キーが小文字のアルファベット1文字（a，b，…，zのいずれか）であるデータを， 大きさが10のハッシュ表に格納する。ハッシュ関数として，アルファベットのASCIIコードを10進表記で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。
- aとi
- bとr
- cとl
- dとx
[出典：基本情報技術者試験 令和6年度(科目A) 問2]
正解
正解は「エ」です。
解説
この問題は「ASCIIコードの1の位を使ったハッシュ関数」における「衝突（コリジョン）」の発生を問うものです。ハッシュ関数とは、データを特定のルールに従って数値（ハッシュ値）に変換する処理で、ここでは「文字のASCIIコードの1の位の数」を使ってハッシュ表の格納先（0〜9）を決めることになります。
ASCIIコードとは、文字に対して割り振られている数値です。たとえば、a〜z（小文字アルファベット）は以下のような番号が割り当てられています：
- a：97
- b：98
- c：99
- d：100
- i：105
- l：108
- r：114
- x：120
これらの数値を10進表記で見て、1の位（下1桁）の値を取り出します。たとえば a = 97 なので1の位は「7」、b = 98 →「8」、c = 99 →「9」、d = 100 →「0」、i = 105 →「5」、l = 108 →「8」、r = 114 →「4」、x = 120 →「0」です。
選択肢エの「dとx」を見ると、d=100（1の位は0）、x=120（1の位は0）となっており、どちらも1の位が同じなので、同じハッシュ値になります。これが「衝突（コリジョン）」です。
一方、他の選択肢のペアはそれぞれ1の位が異なるため、衝突は起こりません。したがって正解は「エ（dとx）」です。
- ア(aとi):
a=97（1の位：7）、i=105（1の位：5）であり、1の位が異なるため衝突は起こりません。 - イ(bとr):
b=98（1の位：8）、r=114（1の位：4）なので、1の位が異なり、衝突しません。 - ウ(cとl):
c=99（1の位：9）、l=108（1の位：8）であり、1の位が異なるため衝突は起きません。
難易度
この問題は、ASCIIコードの知識と1の位を取得するという処理の理解が求められます。表計算や文字コードに馴染みのある受験者には比較的易しく感じられますが、普段文字コードに触れない初学者にとっては調べる作業が手間に感じられる可能性があります。そのため、難易度は「普通」と言える問題です。
用語補足
ASCIIコード：
アルファベットや記号などに割り当てられた数値コードです。例えば、小文字のaは97、bは98と順に割り振られています。コンピュータでは文字の保存や比較にこの数値を使います。
ハッシュ関数：
データを一定の規則で変換して、ハッシュ値と呼ばれる値に変える関数です。例えば「aのASCIIコードの1の位を使う」といったルールもハッシュ関数の一種です。
衝突（コリジョン）：
異なるデータが同じハッシュ値になってしまう現象です。ハッシュ表では1つの場所に複数のデータを入れようとすると衝突が起こり、対策が必要です。
対策
ASCIIコード表を一度確認し、a〜zやA〜Zのコードをある程度覚えておくと、今回のような問題に対応しやすくなります。また、ハッシュ関数の計算ルールに従って1の位や剰余計算などを正確に行う練習をしておくと、ハッシュや衝突に関する出題に対応できるようになります。
