明解 Javaによるアルゴリズムとデータ構造 3_探索

3-2 線形探索

単純な線形探索(順次探索)

1インデックスにつき、2つの条件文をチェックするコストが発生

1. if index >= array.size() then search failed
2. if array[i] = key then search succeeded

番兵法

1インデックスにつき、1つの条件文チェックでOK。単純な線形探索に比べて時間計算量が半分。

• 一手間加える: 検索対象 array を1インデックス分拡張し、末尾要素に検索対象を代入
  • if array[i] = key のみで良い
  • return 時に、 i == 拡張したarray.size() ? -1 : i を仕込んどいて、-1 なら探索失敗って感じ

3-4 ハッシュ法

ハッシュ法 - データ追加/削除のコストを抑える

• チェイン法(オープンハッシュ法)
  • 同一ハッシュ値のデータを、線形リストを用いてバケットに収納
• オープンアドレス法(クローズドハッシュ法)
  • 同一ハッシュ値のデータは、再ハッシュにより、空いているバケットを探して収納
    • 線形探査法(linear probing) - 空きバケットに出会うまで再ハッシュを試行

明解 Javaによるアルゴリズムとデータ構造