問題
ハッシュ法で衝突解消にオープンアドレス法（線形探索）を用いる場合、テーブルサイズ 11 に対しキー 25 をハッシュ関数 h(k)=k mod 11 で格納する。位置 3 と 4 が既に埋まっているとき、25 が格納される位置はどれか。
選択肢
- 1位置 3
- 2位置 4
- 3位置 5
- 4位置 0
正解
3. 位置 5
詳しい解説を見る解説を閉じる
解説
25 mod 11 = 3 なので、まず位置 3 を試みるが既に使用中。線形探索（linear probing）では衝突時に隣接スロットを順に探すため、次は位置 4 を試みるがこれも使用中。さらに次の位置 5 が空いているのでそこに格納される。線形探索はキャッシュ効率が良い反面、連続した使用領域（一次クラスタリング）が形成されやすく、二次探索（h+i^2）や二重ハッシュ（h1+i*h2）で緩和する。チェイン法（連結リスト）と並ぶ代表的衝突解消法。
一問一答
全400問を繰り返し学習