データ構造とアルゴリズム
大きさ7のハッシュテーブル(位置0〜6)に、ハッシュ関数 h(k) = k mod 7 でキー10、17、24、3をこの順に格納する。衝突したときは、位置を1つずつ後ろへずらして(6の次は0)空いている位置を探す線形探査法を使う。キー3が格納される位置はどれか。
- A位置3
- B位置4
- C位置6
答えと解説を見る
正解：C. 位置6
4つのキーはどれも7で割った余りが3なので、すべて位置3を最初に調べます。10は位置3に入り、17は位置3が埋まっているので位置4、24は位置3、4が埋まっているので位置5に入ります。3は位置3、4、5が埋まっているので、位置6に格納されます。このように線形探査法では、埋まった位置が固まって並び(クラスタ)、後から来るキーほど調べる回数が増えます。
- A. ハッシュ値そのものの位置ですが、すでに10が入っています。
- B. 17が入った位置です。その後ろの5にも24が入っています。
- C. 正しい。位置3、4、5が埋まっているので、空いている位置6に入ります。