ハッシュ表の衝突はASCIIコードの差で見抜ける
基本情報技術者試験 令和6年度 問2 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
キーが小文字のアルファベット1文字(a，b，…，z のいずれか)であるデータを，大きさが10のハッシュ表に格納する。ハッシュ関数として，アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。
- ア
a と i
- イ
b と r
- ウ
c と l
- エ
d と x
会話形式の解説
講師今回はハッシュ表の衝突の問題です。衝突とは、異なるキーのハッシュ値が同じになって、同じ格納位置を指してしまうことです。注目点は、問題文の「アルファベット順に連続したコードが割り当てられている」という一文です。
受験者ASCIIコードの値を全部覚えていないと解けないのかと思って、手が止まりました。aが何番なのかも自信がありません。
講師具体的な値を知らなくても解けます。コードが1ずつ連続しているので、2文字のコードの差は、アルファベット上の順番の差と同じになります。では、2つの数の1の位が一致するのは、差がどうなっているときでしょうか。
受験者たとえば13と23や、7と27のように、差が10や20のときですか。つまり差が10の倍数なら1の位がそろう、ということでしょうか。
講師そのとおりです。1の位を取り出すのは、10で割った余りを求めるのと同じ操作なので、差が10の倍数なら余りが一致します。では、aとiの組から順番の差を数えてみましょう。
受験者aが1番目、iが9番目なので差は8です。10の倍数ではないので衝突しません。bとrは、bが2番目、rが18番目で差は16なので、これも違います。
講師正確です。実際のコードでも確かめておくと、小文字はaが97から始まります。aは97でハッシュ値7、iは105でハッシュ値5です。bは98で8、rは114で4なので、どちらの組も別の位置に入ります。
受験者cとlは、cが3番目、lが12番目で差は9です。10にかなり近いので、最初は衝突しそうに感じました。
講師そこが引っかけになりやすいところです。差が9では1の位はそろいません。cは99でハッシュ値9、lは108でハッシュ値8なので、1つずれます。「ほぼ10」ではなく「ちょうど10の倍数」かどうかを見るのが大切です。
受験者残りのdとxは、dが4番目、xが24番目で差は20です。10の倍数なので、この組が衝突するのですね。
講師はい。実際のコードでもdは100、xは120で、ハッシュ値はどちらも0になります。異なるキーが同じ位置に格納されることになるので、dとxの組で衝突が起こります。
受験者計算が苦手でも、順番の差を数えて10の倍数かを見るだけなら短時間で判定できそうです。
講師補足すると、一般に表の大きさがmで「mで割った余り」をハッシュ値にすると、差がmの倍数になるキー同士が衝突します。衝突は「シノニムの発生」とも呼ばれます。また、この問題ではハッシュ値が0〜9の10通りしかないので、26文字すべてを格納すれば必ずどこかで衝突が起こります。
まとめ
ASCIIコードを10進表記したときの1の位をハッシュ値にする場合、2つのキーが衝突するのはコードの差が10の倍数のときです。小文字のアルファベットはaの97から1ずつ連続してコードが割り当てられているので、コードの差はアルファベットの順番の差と同じになります。順番の差はaとiが8、bとrが16、cとlが9、dとxが20で、10の倍数になるのはdとxだけです。実際のコードでもdは100、xは120で、ハッシュ値はどちらも0になります。差が9の組は10に近いため間違えやすいですが、差がちょうど10の倍数かどうかを確かめれば判定できます。
解答・解説
正解はエです
この問題のテーマ
ASCIIコードの10進表記の1の位をハッシュ値にしたとき、どの2文字が同じ格納位置になる（衝突する）かを問う問題です。ハッシュ関数の性質と、文字コードが連続して割り当てられていることを組み合わせて考えます。
解き方の考え方
問題文にあるとおり、小文字はアルファベット順に連続したコードが割り当てられているので、2文字のコードの差はアルファベット上の順番の差と同じになります。1の位が一致するのは、コードの差が10の倍数のときです。そのため、ASCIIコードの具体的な値を覚えていなくても、各組の順番の差を数えれば判定できます。念のため、aを97とした実際のコードでも1の位を確かめます。
選択肢ごとの解説
- ×ア a と iaとiの組は、aが1番目、iが9番目なのでコードの差は8です。10の倍数ではないため、1の位は一致しません。実際のコードでは、aが97でハッシュ値は7、iが105でハッシュ値は5となり、別の位置に格納されます。
- ×イ b と rbとrの組は、bが2番目、rが18番目なのでコードの差は16です。10の倍数ではありません。実際のコードでは、bが98でハッシュ値は8、rが114でハッシュ値は4となり、衝突しません。
- ×ウ c と lcとlの組は、cが3番目、lが12番目なのでコードの差は9です。差が10に近いため一致しそうに見えますが、10の倍数ではありません。実際のコードでは、cが99でハッシュ値は9、lが108でハッシュ値は8となり、衝突しません。
- ○エ d と xdとxの組は、dが4番目、xが24番目なのでコードの差は20で、10の倍数です。実際のコードでも、dは100、xは120で、ハッシュ値はどちらも0になります。異なるキーが同じ位置に格納されることになるので、この組で衝突が起こります。
補足
一般に、表の大きさがmのときに「mで割った余り」をハッシュ値にすると、差がmの倍数になるキー同士が衝突します。この問題ではハッシュ値が0〜9の10通りしかないので、26文字すべてを格納すれば必ず衝突が起こります。ウのcとlのように差が9の組は「ほぼ10」なので間違えやすいですが、差がちょうど10の倍数になっているかを確かめれば判定できます。
POINT
- 異なるキーのハッシュ値が同じになり、同じ格納位置を指すことを衝突（シノニムの発生）といいます。
- 10進表記の1の位を取り出す操作は、10で割った余りを求める操作と同じです。
- 2つの値の1の位が一致するのは、その差が10の倍数のときです。
- 小文字アルファベットのASCIIコードは、aの97から順に1ずつ増えます。