A-1アルゴリズム・プログラミング · アルゴリズム

シノニム対策

Collision Resolution

しのにむたいさく

ハッシュ表で、異なるキーが同じハッシュ値になって格納位置が重なる衝突（シノニム）に対処する方法。同じ位置のデータをリストでつなぐチェイン法（連鎖法）と、規則に従って別の空き位置を探して格納するオープンアドレス法がある。

共有:

関連キーワードの用語

キーをハッシュ関数で変換した値（ハッシュ値）を格納位置として、データを表に格納するデータ構造で、探索・挿入・削除を平均O(1)で行える。異なるキーが同じ位置になる衝突（シノニム）は、同じ位置の要素をリストでつなぐチェイン法か、別の空き位置を探すオープンアドレス法で処理する。表の埋まり具合（負荷率）が高いと衝突が増えて遅くなり、キーの順に取り出す処理には向かない。