ハッシュ探索

Hash Search はっしゅたんさく

最頻出 ⚪ 旧用語テクノロジ系基礎理論

意味・解説

ハッシュ関数を使ってデータの格納位置を直接計算し、高速に探索するアルゴリズム。

キーからハッシュ値を計算し、その値を配列のインデックスとして使用する。理想的な場合はO(1)で探索できる。衝突（異なるキーが同じハッシュ値になる）の処理が必要。

名前から部屋番号を計算で求めて、一発でその部屋に行くイメージです。

【メリット】

・理想的にはO(1)で探索可能

・データ量に関係なく一定時間

【衝突対策】

・チェイン法: 同じハッシュ値のデータをリストで管理

・オープンアドレス法: 空いている場所を探す

辞書型データ構造は内部でハッシュ探索を使い、キーからO(1)で値を取得できる。

分類: 探索アルゴリズム