応用情報技術者試験 令和6年秋 午前問6 解説付き過去問
問題
自然数をキーとするデータを、ハッシュ表を用いて管理する。
キーxのハッシュ関数h(x)を
h(x)＝x mod n
とすると、任意のキーaとbが衝突する条件はどれか。 ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。
h(x)＝x mod n
とすると、任意のキーaとbが衝突する条件はどれか。 ここで、nはハッシュ表の大きさであり、x mod nはxをnで割った余りを表す。
正解
解説
この問題では、ハッシュ関数とその衝突条件についての理解が試されています。ハッシュ関数h(x) = x mod nは、キーxをハッシュ表の大きさnで割った余りを返す関数です。
- ハッシュ関数の定義
ハッシュ関数h(x) = x mod nは、キーxをnで割ったときの余りをハッシュ値として返します。この関数により、ハッシュ表のインデックスが決定され、データが格納される位置が指定されます。 - 衝突の発生条件
二つのキーaとbが同じハッシュ値を持つためには、h(a)とh(b)が等しくなければなりません。すなわち、a mod n = b mod nである必要があります。これは、(a - b) mod n = 0、つまりa - bがnの倍数であることを意味します。
したがって、キーaとbが衝突する条件は「a - bがnの倍数」であることから、選択肢「a－bがnの倍数」が正解です。