明解 Javaによるアルゴリズムとデータ構造 3_探索
3-2 線形探索
単純な線形探索(順次探索)
1インデックスにつき、2つの条件文をチェックするコストが発生
- if index >= array.size() then search failed
- 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) - 空きバケットに出会うまで再ハッシュを試行
- 同一ハッシュ値のデータは、再ハッシュにより、空いているバケットを探して収納
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る