第8回探索とハッシュ法

Algorithms and Data Structures on C
第8回
探索とハッシュ法
Algorithms and Data Structures on C
今回の要点
• 探索とは？
– 探索には、挿入と削除も必要
• ハッシュとは？
– ハッシュ関数とハッシュ値
– 探索の計算量を実質的にO(1)に！？
– 衝突（collision）とは？
• チェイン法による対策
• オープンアドレス法による対策
– 効率のよいハッシュ関数
Algorithms and Data Structures on C
探索（Searching）とは？
• データ集合の中から、特定の値（キー）を持つデータを探し出
すこと
– 名前（キー）をもとにして個人データを探す
– コンパイラが、変数名（キー）からその値を探す
– 辞書の中の単語（キー）の意味を探す
• 探索のために必要な操作
–
–
–
–
挿入と削除は必要？
探索（find）
集合の構造が探索効率に
挿入（insert）
大きく影響するため
削除（delete）
この3つの操作を備えたデータの集合を辞書と呼ぶ
Algorithms and Data Structures on C
配列による辞書の探索
• 線形探索（リニアサーチ）
–
–
–
–
辞書の先頭から順番に探していく（=O(N)）
挿入は末尾に加えるだけ（=O(1)）
削除は要素を外して後ろをずらす（=O(N)）
トータルの計算量はO(N)
• 二分探索（バイナリサーチ）
–
–
–
–
探索領域を二分割しながら探す（=O(log2N)）
挿入は小さい順を保つ（=O(N)）
削除は要素を外して後ろをずらす（=O(N)）
トータルの計算量はO(N)
詳細は第2回を参照
Algorithms and Data Structures on C
ハッシュ法
• ハッシュ法（Hashing）とは
– データ数に関わらず、挿入、探索、削除を実質O(1)で行えるアルゴリ
ズム
– キーの値を、データの格納される位置（バケットの番号）に直接関連
付ける
– バケットに、番号でアクセスするのに要する計算量はO(1)である
山田太郎
468
佐藤花子
288
森洋一郎
キー
594
ハッシュ値
464
465
466
467
468
469
470
・
・
・
ハッシュ表
山田太郎のデータ
・
・
・
バケット
Algorithms and Data Structures on C
ハッシュ関数
• ハッシュ値はどのようにして得る？
– キー x からハッシュ値を得る関数＝ハッシュ関数 h(x)
• hash = （肉などを）細かく切り刻む、めちゃめちゃにする
– キーの値を用いて、何かの数字を返すような関数
– キーが違えば、戻り値も違う数字になるのが望ましい
山田太郎
64H+5EH+40H+3FH+6DH+26H = 1D4H
468
やまだたろう
佐藤花子
35H+48H+26H+4FH+4AH+33H = 120H
288
さとうはなこ
森洋一郎
62H+6AH+68H+26H+24H+41H+6DH+26H = 252H
もりよういちろう
h(x) = x のひらがなのＪＩＳコードの下2桁の和
594
Algorithms and Data Structures on C
衝突（collision）
• ハッシュ関数の問題点
– 異なるキーに対して、同じハッシュ値を生成すること
– 衝突（Collision）という
• 「やまだたろう」と「うただまろや」は常にハッシュ値が一致
• 文字は違っても、合計は同じになる可能性もある
• ハッシュ値をある範囲に収めるために、剰余演算を行うこともある（配列
が有限なため）ので、さらに同じなる可能性が増える
• 何らかの対策が必要
– チェイン法（chaining）
– オープンアドレス法（open addressing）
Algorithms and Data Structures on C
チェイン法（chaining）
• 同じハッシュ値を持つデータを線形リストでつなぐ方法
– ハッシュ値からバケットを探す
– バケットのリストをたどる（線形探索）
• 線形リストが長くなると、効率が落ちる
山田太郎
8
佐藤花子
8
森洋一郎
4
collision
バケットが10個しかないので、
10で割った余りにした
0
1
2
3
4
5
6
7
8
9
各バケットには、
線形リストへの
リンクが格納される
森
山田
佐藤
線形リストに格納する
Algorithms and Data Structures on C
チェイン法の性能１
• データ数N、バケット数B
• ハッシュ関数は、すべてのバケットに対して均等にハッシュ値を生成する
と仮定する
• 探索
– バケットを探すO(1)＋線形リストを探すO(N/B)
– 合計O(1+N/B)
• 挿入
– リストの先頭に挿入O(1)＋重複チェックO(N/B)
– 合計O(1+N/B)
• 削除
– リストから削除O(1)＋リストを検索O(N/B)
– 合計O(1+N/B)
Algorithms and Data Structures on C
チェイン法の性能２
• 計算量O(1+N/B)はどれくらい？
– データ数Nに対してバケット数Bが十分に大きい場合は、
N/Bは定数 → O(1+N/B)=O(1)
• 50個のバケットに200個のデータを入れる
• 1個のバケットのリストは高々4個程度
– データ数Nに対してバケット数Bが小さい場合は、N/BはN
の変数 → O(1+N/B)=O(N)
• 50個のバケットに10000個のデータを入れる
• 1個のバケットには平均で200個くらいのデータ
Algorithms and Data Structures on C
オープンアドレス法
（open addressing）
• 衝突が発生したときに、ある手順に従って別のバケットに
データを格納する（再ハッシュ）
– 最も簡単な再ハッシュ手順は、次の空いているバケットを探す方法
山田太郎
8
佐藤花子
8
森洋一郎
4
collision
再ハッシュ
0
1
2
3
4
5
6
7
8
9
4:森
8:山田
8:佐藤
Algorithms and Data Structures on C
再ハッシュ（rehashing）の方法
• キー x のハッシュ値 h(x) のバケットが既にふさがっている場合、再ハッ
シュ手順に従って次のハッシュ値 h1(x),h2(x),・・・を調べる。
• B（バケットの数）回繰り返しても見つからなければ、あきらめる（挿入でき
ない、または探索失敗）
• 再ハッシュ関数hk(x)
① hk(x)=(h(x)+k) mod B
② hk(x)=(h(x)+ck) mod B （cは定数）
③ hk(x)=(h(x)+nk) mod B （nkは１～Bのシャッフル系列）
• 単純な再ハッシュは、バケットの塊を引き起こす
– 近くのバケットが連続してふさがってしまう
– シャッフル系列を使用した方法が有効
Algorithms and Data Structures on C
削除と探索
• オープンアドレス法において、データを削除した際、バケットを単に空にす
ると、後の探索で問題がある
– それ以降のデータはないとして、探索が終了してしまう
• したがって、削除された場所には、「データはあったけれども削除された」
ということが分かるように特別なデータを書き込んでおく必要がある。
見つかる！
山田太郎
8
佐藤花子
8
森洋一郎
4
竹下五郎
8
データ追加
0
1
2
3
4
5
6
7
8
9
8:竹下
empty
empty
empty
4:森
empty
empty
empty
8:山田
8:佐藤
佐藤を削除
0
1
2
3
4
5
6
7
8
9
8:竹下
empty
empty
empty
4:森
empty
empty
empty竹下を検索
8:山田
empty
見つからない！
0
1
2
3
4
5
6
7
8
9
8:竹下
empty
empty
empty
4:森
empty
empty
empty
8:山田
deleted
Algorithms and Data Structures on C
オープンアドレス法の性能１
• 以下の計算量となることが知られている
– 探索1回当たりに調べるバケットの平均値
– ただし、αはハッシュ表の使用率
＝（登録したデータ数）／（全バケット数）
①のhk(x)
③のhk(x)
探索が
成功
1 / 2
1
1
loge

1
探索が
失敗
1
1

2
2 2(1   )
1
1
1
Algorithms and Data Structures on C
オープンアドレス法の性能２
6
①成功
平均バケット探索個数
5
②成功
単純
①失敗
実用上の
限界
②失敗
4
使用率80%
で3.0個
3
使用率90%
で2.6個
2
ランダム系列利用
1
0
0.2
0.4
0.6
ハッシュ使用率
0.8
1
Algorithms and Data Structures on C
ハッシュ関数
• チェイン法もオープンアドレス法も、均等なハッシュ値を生成するハッシュ
関数が前提
– すべての可能なキー値を対象としたときの均等（静的均等）では不十分
– 実際に使われるキー値に対して均等（動的均等）が望ましい
• よく使われるハッシュ関数
– 文字コードの和の剰余
h( x)   ord(ai ) mod B
ai はキーの i 番目の文字
– キーの値を2乗してその中央を取る（平方採中法）
h( x)  n 2 / K  mod B
ただし、 K  N 2 / B
n はキーの番号
Algorithms and Data Structures on C
ハッシュ法のまとめ
• ハッシュ法を使うと、探索、挿入、削除の操作が実質的にO(1)で可能に
なる。
• この高速性は「ハッシュ表が十分に大きい」ことを前提とする
• チェイン法
– データ数が、バケット数の数倍程度まで
– 最大1000個のデータの場合、最初に準備するべきバケットは400～500個程
度
– データが増えるとリストが長くなる
• オープンアドレス法
– データ数は、バケット数の80％～90％まで
– 最大1000個のデータの場合、使用率が約85％とすると、最初から1200個程
度のバケットが必要
– あとからの追加なし
Algorithms and Data Structures on C
課題141208
• 表1のようなハッシュ値を持つキーがある。このキーを用いて、0～9の10
個のバケットのハッシュ表に対して以下の操作を行うときのハッシュ表の
動きを示せ。ただし、オープンアドレス法を用い、再ハッシュは①の方法
を使うものとする。
–
–
–
–
–
•
•
•
•
キーAからEまでを順に挿入する
キーEを探索する
キーFを探索する
キーDを削除する
キーEを探索する
提出方法：ワードで作成し、メールで送付。
提出先：[email protected]
メールタイトル：”アルゴリズム課題141208”
期限：2014年12月14日（日）
キー
ハッシュ値
A
7
B
2
C
5
D
2
E
3
F
3
表1
Algorithms and Data Structures on C
探索とハッシュ
終了

Download Report