新人研修発表 平成１３年５月１４日（月） 探索アルゴリズム ハッシュ法について 株式会社 エーアイネット・テクノロジ 須田 哲生
なぜハッシュ法？ 高速探索法と言われるハッシュ法だが何故高速なのか？ 他の探索法と何が違うのか？ → アルゴリズムの理解が必要 → アルゴリズムの理解が必要 本当に高速なのか？ → 検証を行う
目的 ① 他の探索法との比較を行い ハッシュ法の高速探索の理由を探る ② コーディングを行い ハッシュ法の性能を検証する
ハッシュ法とは 格納されたデータの個数によらず 探索・削除・挿入などの操作を一定時間で行う ことができる高速な探索アルゴリズムである
ハッシュ法の特徴 キーから計算によりデータの格納場所を決定 （ハッシュ関数の利用） <文字列データ> 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 （ハッシュ表）
ハッシュ法の特徴 異なるキーでもデータ格納場所が同じになることがある （衝突の発生） 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
衝突対策 衝突が起こらないように ① テーブルサイズを大きくする ② ハッシュ関数を工夫する 衝突が起きたときに ① テーブルの空き欄を探す ① テーブルサイズを大きくする ② ハッシュ関数を工夫する 衝突が起きたときに ① テーブルの空き欄を探す ② 外部にリストをつなげる
衝突回避 最適なハッシュ関数の利用 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 とする ) = 186896943 mod ４（配列数） = 2 186896943
衝突時対策 同じ表内で空き欄を探す オープンアドレス指定法 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
衝突時対策 外部にリストをつなげる 外部連鎖法（チェーン法） 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‘ ← データが入っている 外部にリストをつなげる
他の探索法 ① 逐次探索法 端から順にデータを比較しながら探索 ② ２分探索木 ① 逐次探索法 端から順にデータを比較しながら探索 ② ２分探索木 ツリーの根（ルート）から探索を開始し下に向かう経路を、各節点（ノード） とのデータの比較から選択する
他の探索法 ① 逐次探索法 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
他の探索法 ② ２分探索木 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
これまでのまとめ なぜハッシュ法は高速探索ができるのか？ ハッシュ関数を用いた 対象データへの一意的なアプローチ
検証 本当にハッシュ探索法は速いのか？ 他の探索法との比較 逐次探索法（リスト構造） < 条件 > 格納データ スペルチェック用文字列 格納データ数 ２００００件 探索データ数 ２００件×１００回
検証 本当にハッシュ探索法は速いのか？ テスト項目 Test 1 ： 無作為に選択（２００単語） 逐次探索 リスト構造 ハッシュ探索 リスト構造（チェーン法） ハッシュテーブルサイズ ４４９
検証結果 探索時間の比較 本当にハッシュ探索法は速かった テスト 1 テスト 2 逐次探索 147.7 242.7 ハッシュ法 0.22 0.28 単位 [s]
最後に ハッシュ法のアルゴリズムをより深く知ることで 実際にプログラムを組んでみることができた 動かしてみることで高速であるということを納得できた