ハッシュ表の計算ツール

正解：B. 異なるキーから同じハッシュ値(格納する位置)が求まること

ハッシュテーブルは、キーからハッシュ関数で格納する位置を計算し、平均 O(1) で探索・挿入・削除ができるデータ構造です。キーの種類は表の大きさよりはるかに多いので、異なるキーが同じ位置になること(衝突)は避けられません。そのため、同じ位置の要素をリストにつなぐチェイン法や、空いている別の位置を探すオープンアドレス法などで衝突を処理します。同じキーからは必ず同じハッシュ値が求まらなければ探索ができず、ハッシュ値から元のキーが分かるかどうかは暗号に使う場合の性質で、衝突とは別の話です。

正解：C. 位置6

4つのキーはどれも7で割った余りが3なので、すべて位置3を最初に調べます。10は位置3に入り、17は位置3が埋まっているので位置4、24は位置3、4が埋まっているので位置5に入ります。3は位置3、4、5が埋まっているので、位置6に格納されます。このように線形探査法では、埋まった位置が固まって並び(クラスタ)、後から来るキーほど調べる回数が増えます。

正解：A. チェイン法では負荷率が1を超えても格納できるが、オープンアドレス法では表の大きさを超えて格納できず、負荷率が1に近づくと探索の回数が急に増える

チェイン法は同じ位置の要素をリストにつなぐので、要素数が表の大きさを超えても格納できますが、平均のリストの長さは負荷率に比例して伸び、探索の手間も増えます。オープンアドレス法は表の中だけに格納するので要素数は表の大きさまでで、負荷率が1に近づくと空きを探す回数が急に増えます。どちらの方法でも、負荷率が決めた値(例えば0.5〜0.75程度)を超えたら表を大きくして全要素を入れ直す(リハッシュ)のが普通です。オープンアドレス法でも衝突は起こり、空いた位置を探すことで対処しています。

正解：A. 衝突したときに調べる次の位置が隣の要素なので、同じキャッシュラインやすぐ次のラインに載っていることが多く、メモリへのアクセスが少なく済むから

現在のCPUでは、キャッシュミスで主記憶を読む時間が、比較などの計算よりずっと長くかかります。線形探査では衝突しても隣の位置を調べるので、多くの場合同じキャッシュラインの中で済み、プリフェッチも効きます。チェイン法では、リストの次の要素がメモリ上の離れた場所にあることが多く、ポインタをたどるたびにキャッシュミスが起こりやすくなります。計算量のオーダーが同じでも、メモリのアクセスの仕方によって実際の速さは大きく変わります。ただし、線形探査は負荷率が高くなると埋まった位置が固まって急に遅くなるので、負荷率を低めに保ちます。