新人研修発表 平成１３年５月１４日（月） 探索アルゴリズム　ハッシュ法について 株式会社　エーアイネット・テクノロジ 　　　　　　　　　須田　哲生.

Presentation on theme: "新人研修発表 平成１３年５月１４日（月） 探索アルゴリズム　ハッシュ法について 株式会社　エーアイネット・テクノロジ 　　　　　　　　　須田　哲生."— Presentation transcript:

1 新人研修発表 平成１３年５月１４日（月） 探索アルゴリズム　ハッシュ法について 株式会社　エーアイネット・テクノロジ 　　　　　　　　　須田　哲生

2 なぜハッシュ法？ 高速探索法と言われるハッシュ法だが何故高速なのか？ 他の探索法と何が違うのか？ → アルゴリズムの理解が必要
→　　アルゴリズムの理解が必要 本当に高速なのか？ →　　検証を行う

3 目的 ①　他の探索法との比較を行い 　　　ハッシュ法の高速探索の理由を探る ②　コーディングを行い 　　　ハッシュ法の性能を検証する

4 ハッシュ法とは 格納されたデータの個数によらず 探索・削除・挿入などの操作を一定時間で行う ことができる高速な探索アルゴリズムである

5 ハッシュ法の特徴 キーから計算によりデータの格納場所を決定 （ハッシュ関数の利用） <文字列データ> a b c d e \0
　　　　　　　　　　　　　　　　　　　　（ハッシュ関数の利用） <文字列データ> a b c d e \0 97 98 99 100 101 + = 395 1 2 395 mod 4 (配列数) = 3 (ハッシュ値) 3 （ハッシュ表）

6 ハッシュ法の特徴 異なるキーでもデータ格納場所が同じになることがある （衝突の発生） 1 2 3 a b c d \0 97 98 99
　　　　　　　　　　　　　　　　　　　　　　　　　（衝突の発生） 1 2 3 a b c d \0 97 98 99 100 + 394 mod 4 = 2 2 a c d e \0 97 99 100 101 + 394 4 mod = 2

7 衝突対策 衝突が起こらないように ① テーブルサイズを大きくする ② ハッシュ関数を工夫する 衝突が起きたときに ① テーブルの空き欄を探す
①　テーブルサイズを大きくする ②　ハッシュ関数を工夫する 衝突が起きたときに ①　テーブルの空き欄を探す ②　外部にリストをつなげる

8 衝突回避 最適なハッシュ関数の利用 a b c d e \0 +99 +100 +101 1 2 3 97 +98
1 2 3 97 ×A +98 = 97A4+98A3+99A2+100A+101 ( A = 37 とする ) = mod ４（配列数） = 2

9 衝突時対策 同じ表内で空き欄を探す オープンアドレス指定法 1 2 3 4 5 6 7 8 9 10 11 12 7 ハッシュ値 ＝ １
ハッシュ値　＝　１ 1 2 3 4 5 6 7 8 9 10 11 12 データが入っている　→ データが入っている　→ 同じ表内で空き欄を探す 7

10 衝突時対策 外部にリストをつなげる 外部連鎖法（チェーン法） 1 2 3 4 5 6 7 8 9 10 11 12 1‘ 1‘
ハッシュ値　＝　１ 1 2 3 4 5 6 7 8 9 10 11 12 1‘ 1‘ ←　データが入っている 外部にリストをつなげる

11 他の探索法 ① 逐次探索法 端から順にデータを比較しながら探索 ② ２分探索木
①　逐次探索法 端から順にデータを比較しながら探索 ②　２分探索木 ツリーの根（ルート）から探索を開始し下に向かう経路を、各節点（ノード）　　とのデータの比較から選択する

12 他の探索法 ① 逐次探索法 aaa bbb ddd eee ggg hhh jjj mmm ppp kkk aaa bbb ddd eee
①　逐次探索法 キー　＝　kkk aaa bbb ddd eee ggg hhh jjj mmm ppp kkk aaa bbb ddd eee ggg hhh jjj 7 mmm ppp kkk kkk kkk

13 他の探索法 ② ２分探索木 ggg ddd mmm eee jjj ppp aaa bbb hhh kkk kkk キー ＝ kkk
②　２分探索木 キー　＝　kkk ( ggg < kkk) ggg ( mmm > kkk) ddd mmm ( iii < kkk) eee jjj ppp aaa ( kkk = kkk) bbb hhh kkk kkk

14 これまでのまとめ なぜハッシュ法は高速探索ができるのか？ ハッシュ関数を用いた 対象データへの一意的なアプローチ

15 検証 本当にハッシュ探索法は速いのか？ 他の探索法との比較 逐次探索法（リスト構造） < 条件 >
格納データ　　　　スペルチェック用文字列 格納データ数　　　　　　２００００件 探索データ数　　　　２００件×１００回

16 検証 本当にハッシュ探索法は速いのか？ テスト項目 Test 1 ： 無作為に選択（２００単語）
逐次探索　　　　　　　　　　　リスト構造 ハッシュ探索　　　　　　リスト構造（チェーン法） ハッシュテーブルサイズ　　　　４４９

17 検証結果 探索時間の比較 本当にハッシュ探索法は速かった テスト 1 テスト 2 逐次探索 147.7 242.7 ハッシュ法 0.22
0.28 単位 [s]

18 最後に ハッシュ法のアルゴリズムをより深く知ることで 実際にプログラムを組んでみることができた
動かしてみることで高速であるということを納得できた

19

20