アルゴリズムとプログラミングアルゴリズムとデータ構造

ハッシュ法によるデータ管理において、異なるキーが同じハッシュ値を返す現象を何と呼ぶか。

ア.オーバーフロー

イ.衝突（コリジョン）正解

ウ.フラグメンテーション

エ.デッドロック

解説

別のキーが同じ住所に届けられてしまう＝「衝突（collision）」。郵便番号が同じ家が2軒できてしまった状態です。

なぜイが正解か

ハッシュ法ではキーをハッシュ関数で短い値に変換し、それを格納先の添字として使います。異なるキーが偶然同じハッシュ値になる現象が「衝突（コリジョン）」で、チェイン法（連結リストで束ねる）やオープンアドレス法（別の空きを探す）などで解決します。

なぜアは間違いか

オーバーフローは数値が表現可能範囲を超える現象。ハッシュテーブルでは「あふれ域」を指すこともありますが、選択肢としての「異なるキーが同じハッシュ値」はあくまで「衝突」です。

なぜウは間違いか

フラグメンテーションは記憶領域が細切れになって使いにくくなる現象。メモリ管理やディスク管理の用語で、ハッシュ衝突とは別物です。

なぜエは間違いか

デッドロックは複数プロセスが互いの資源解放を待ち続けて止まる現象。同時実行制御の話題であり、ハッシュ関数の値被りとは無関係です。

出典: AI生成問題（学習用）

← 前の問題

単方向連結リストの先頭にノードを1個挿入する操作の計算量として、適切なものはどれか。

次の問題 →

完全二分木に要素を格納したヒープ（最大ヒープ）の性質として、正しいものはどれか。