データ構造とアルゴリズム
ハッシュテーブルの衝突を処理する方法として、チェイン法(同じ位置の要素を連結リストでつなぐ)とオープンアドレス法(表の中の空いている別の位置を探す)を比べた説明として正しいものはどれか。負荷率は、格納した要素数を表の大きさで割った値とする。
- Aチェイン法では負荷率が1を超えても格納できるが、オープンアドレス法では表の大きさを超えて格納できず、負荷率が1に近づくと探索の回数が急に増える
- Bオープンアドレス法では衝突が起こらないので、負荷率によらず探索は1回で済む
- Cチェイン法では、負荷率がいくら高くなっても探索の手間は変わらない
答えと解説を見る
正解：A. チェイン法では負荷率が1を超えても格納できるが、オープンアドレス法では表の大きさを超えて格納できず、負荷率が1に近づくと探索の回数が急に増える
チェイン法は同じ位置の要素をリストにつなぐので、要素数が表の大きさを超えても格納できますが、平均のリストの長さは負荷率に比例して伸び、探索の手間も増えます。オープンアドレス法は表の中だけに格納するので要素数は表の大きさまでで、負荷率が1に近づくと空きを探す回数が急に増えます。どちらの方法でも、負荷率が決めた値(例えば0.5〜0.75程度)を超えたら表を大きくして全要素を入れ直す(リハッシュ)のが普通です。オープンアドレス法でも衝突は起こり、空いた位置を探すことで対処しています。
- A. 正しい。格納できる数と、負荷率が高いときの探索の増え方の違いを正しく述べています。
- B. オープンアドレス法でも衝突は起こり、空いている別の位置を探して対処します。
- C. リストの平均の長さは負荷率に比例するので、負荷率が高いと探索の手間が増えます。