データ構造とアルゴリズム
要素数が多く、負荷率を0.5程度に保ったハッシュテーブルで、線形探査のオープンアドレス法が、チェイン法(連結リストでつなぐ方法)より速くなりやすい理由として最も適切なものはどれか。
- A衝突したときに調べる次の位置が隣の要素なので、同じキャッシュラインやすぐ次のラインに載っていることが多く、メモリへのアクセスが少なく済むから
- Bオープンアドレス法では衝突がまったく起こらないから
- Cチェイン法ではハッシュ関数を2回以上計算する必要があるから
答えと解説を見る
正解：A. 衝突したときに調べる次の位置が隣の要素なので、同じキャッシュラインやすぐ次のラインに載っていることが多く、メモリへのアクセスが少なく済むから
現在のCPUでは、キャッシュミスで主記憶を読む時間が、比較などの計算よりずっと長くかかります。線形探査では衝突しても隣の位置を調べるので、多くの場合同じキャッシュラインの中で済み、プリフェッチも効きます。チェイン法では、リストの次の要素がメモリ上の離れた場所にあることが多く、ポインタをたどるたびにキャッシュミスが起こりやすくなります。計算量のオーダーが同じでも、メモリのアクセスの仕方によって実際の速さは大きく変わります。ただし、線形探査は負荷率が高くなると埋まった位置が固まって急に遅くなるので、負荷率を低めに保ちます。
- A. 正しい。隣の位置を調べるだけなので、キャッシュに載ったデータで済みやすくなります。
- B. オープンアドレス法でも衝突は起こり、隣の位置を調べて対処します。
- C. ハッシュ関数の計算はどちらも1回で、違いはメモリのアクセスの仕方にあります。