修了試験 2020-01-26実施分 基本情報技術者試験 問9

解説

正解は3です。 16進数のデータを8で割った余りをハッシュ値とし、最初に同じハッシュ値（衝突）が出るデータを探す問題です。 8で割った余りは、2進数の下位3ビットに等しいので、16進数の下1桁だけで求められます。 【計算】 1Aは下1桁Aが10なので、10÷8の余りで2です。 35は下1桁5なので、5です。 3Bは下1桁Bが11なので、3です。 54は下1桁4なので、4です。 8Eは下1桁Eが14なので、6です。 A1は下1桁1なので、1です。 AFは下1桁Fが15なので、7です。 B2は下1桁2なので、2です。 B2のハッシュ値2は、最初の1Aと同じなので、ここで初めて衝突が起こります。 【選択肢別解説】 1：× 54のハッシュ値は4で、それまでの2、5、3と重なりません。 衝突は起こりません。 2：× A1のハッシュ値は1で、それまでの2、5、3、4、6と重なりません。 3：○ B2のハッシュ値は2で、1Aのハッシュ値2と一致します。 これが最初の衝突です。 4：× B3のハッシュ値3は3Bと衝突しますが、B2より後に格納されるので最初の衝突ではありません。 【ポイント】 16は8の倍数なので、16進数を8で割った余りは下1桁を8で割った余りと同じです。