午前問8
キーが小文字のアルファベット1文字（a, b, …、 z のいずれか）であるデータを、大きさが10のハッシュ表に格納する。ハッシュ関数として、アルファベットのASCIIコードを10進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは、昇順に連続した2進数が、アルファベット順にコードとして割り当てられている。
| a と i | |
| b と r | |
| c と l | |
| d と x |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- エ
解説
ハッシュ表では、キーから算出したハッシュ値が同じ場合に衝突が発生します。
本問では、ASCIIコードがアルファベット順に連続して割り当てられているという性質を利用し、10で割った余り（1の位）をハッシュ値としています。
そのため、アルファベット上で文字間の差が10の倍数離れた文字は同じ1の位となり、同一ハッシュ値となって衝突が起こります。
本問では、ASCIIコードがアルファベット順に連続して割り当てられているという性質を利用し、10で割った余り（1の位）をハッシュ値としています。
そのため、アルファベット上で文字間の差が10の倍数離れた文字は同じ1の位となり、同一ハッシュ値となって衝突が起こります。
| ア. | a と i |
| 文字間の差は8なので衝突しない。 | |
| イ. | b と r |
| 文字間の差は16なので衝突しない。 | |
| ウ. | c と l |
| 文字間の差は9なので衝突しない。 | |
| エ. | d と x |
| 文字間の差は10なので衝突する。 |