集合、辞書とハッシュ法 第8回 集合と辞書 ～ データ構造（4）～

（問1）解答 a d b c e f 1 3 2 4 5 1 3 a 4 5 d -1 2 b c e f [0] [1] [2] [3] [4] label left child right f [5] a 1 3 d b 2 4 5 c e f

集合(Set) B b A c a f e 要素aが集合Aに属する ： 要素aが集合Aに属さない ： a ∈ A Aの要素の個数（Aの位数(cardinality) : |A|＜∞のとき、Aは有限集合(finite set) 集合Aのその要素も集合Bの要素となっているときAはBの部分集合(subset)： A⊆BかつA≠BのときAはBの真部分集合(proper subset)： a ∈ A a ∈ A |A| B A⊆B b A c A⊂B a f e

集合と要素 B b A c a f e 有限集合は通常… 要素をすべて列挙して記述する A = { a, c, e, f } 集合と要素 　 有限集合は通常… 要素をすべて列挙して記述する A = { a, c, e, f } B = { a, b, c, e, f } 要素の並べ方によって区別しない A = { a, c, e, f } = { a, e, f, c } B b A c a f e

和集合、積集合、差集合 p.49 A B a d b c 和集合(union) A∪B = { a, b, c, d } 積集合(共通集合, intersection)　A∩B = { b } 差集合(difference) A-B = { a, c } A B a d b c

空集合、互いに素 p.49 E B A a b c 空集合(empty set) φ 要素を1つも持たない集合 E = φ 互いに素(disjoint) A∩B = φ 併合(merge) A∩B = φ のときにA∪Bを求めること 集合族(family of sets) 集合の集合 B A a b c

集合に関する基本的演算と操作 C A B a c b UNION（A, B, C） C ← A∪B = {a, b, c} 集合に関する基本的演算と操作　　 UNION（A, B, C） C ← A∪B　= {a, b, c} INTERSECTION(A, B, C) C ← A∩B = φ DIFFERENCE(A, B, C) C ← A – B = {a, c} MERGE(A, B, C) 　 A∩B ＝φ （AとBは互いに素）のとき C ← A ∪ B A∩B ≠ φ のとき，未定義またはエラー C A B a c b

集合に関する基本的演算と操作2 A A A MEMBER（ｘ, A） x ∈ A : yes を返す x ∈ A : no を返す INSERT(x, A) DELETE(x, A) EMPTY(A) A x A x A 空集合φ

配列による集合の実現 すべての要素が普遍集合＝｛0, 1，2，…，N-1｝から選ばれ、Nがあまり大きくないものとすると右図のように表現できる 配列による集合の実現　　 すべての要素が普遍集合＝｛0, 1，2，…，N-1｝から選ばれ、Nがあまり大きくないものとすると右図のように表現できる 配列A [0] [1] 1 [2] 1 [3] A={1,2,4}のときの例 i ∈ A のとき１、 i ∈ A のとき０で表現 割当を逆にしてもよい [4] 1 [5] [6] [7]

積集合を求める void intersection(int *A, int *B, int *C){ int i; for ( i = 0; i < N; i++ ) C[i] = A[i] * B[i]; } 1 [0] [3] [1] [2] [4] [5] [6] [7] A 1 [0] [3] [1] [2] [4] [5] [6] [7] B C [0] [1] [2] 1 [3] [4] 1 [5] [6] [7]

連結リストによる集合の実現 普遍集合がうまく定義できない場合や、Nが大きい場合は連結リストで表現すると良い 連結リストによる集合の実現　　 普遍集合がうまく定義できない場合や、Nが大きい場合は連結リストで表現すると良い 領域量はO(|A|) MEMBER, INSERT, DELETEはO(|A|)で実行可能 INTERSECTION, DIFFERENCEはO(|A||B|)かかる A = { a, c, e, f } f a c e init A

辞書（Dictionary） 集合Aに対し、以下の3つの演算のみが適用されるときAを辞書と呼ぶ INSERT 挿入．データ（レコード）を登録する． DELETE 削除．与えられた値(検索キー)と同じデータ（レコード）を探し出して，削除する． MEMBER　 　与えられた値(検索キー)と同じデータ(レコード)が存在すればyes，存在しなければnoを出力する．

概念図 検索キー orange 辞書D MEMBER(“orange”, D) ⇒ yes MEMBER(“banana”, D) ⇒ no apple orange tomato 検索キー orange MEMBER(“orange”, D) ⇒　yes MEMBER(“banana”, D) ⇒　no 辞書D

ハッシュ法(hashing) 辞書は、しばしばハッシュ表を用いて実現される ハッシュ法では，検索キーの値を，データが格納される位置(配列の添字)に直接関連付ける これにより，データの個数によらず，データの探索が一定時間で行える 計算量　O (1)　(一定時間)

ハッシュ法の概要 ハッシュ法による探索 h(x) 線形探索 ハッシュ関数 x=“apple” 4 (ハッシュ値) ハッシュテーブル 4　(ハッシュ値) Table[4]にアクセス ハッシュテーブル banana kiwi apple orange mango table[0] table[1] table[2] table[3] table[4] table[5] table[6] table[7] 線形探索 違う 違う 違う 見つけた！ キー”apple” はどこ？ banana orange mango apple kiwi 先頭から順番に探していく必要がある

用語 ハッシュ関数(hash function) h(x) : キーの値x を配列の添字へ写像する関数 用語　　　　　　　　　　　　　　 ハッシュ関数(hash function) h(x) : キーの値x を配列の添字へ写像する関数 ハッシュ値(hash value) : ハッシュ関数h(x)が返す値 ハッシュ表(hash table) : データを格納する配列 バケット(bucket) : ハッシュ表の各要素

100の剰余をとることで，ハッシュ値が0～99の範囲に収まる ハッシュ関数の例 int hashfunc(char *s) { int i = 0; while (*s) i += *s++; return i % 100; } s a p p l e \0 文字列 97 112 101 108 文字 コード 530 % 100 = ハッシュ値 30 各文字の文字コードを足しこむ 100の剰余をとることで，ハッシュ値が0～99の範囲に収まる

文字コード ASCIIコード American Standard Code for Information Interchange 文字コード　　　　　　　 6×16+1＝97 ASCIIコード American Standard Code for Information Interchange 1文字１byte(8bit)で表現 char型が表現できる範囲 -128　～　0　～　+127 　　　　　　　128種類

衝突（コリジョン, collision） 異なるキーに対して同一のハッシュ値が生成されることを、コリジョン（衝突）という コリジョンが発生した場合の対策には以下の２通りの方法がある　（教科書と異なる名称なので注意　） チェイン法 (chaining) 　　　 　＝　外部ハッシュ法 オープンアドレス法 (open addressing)　＝　内部ハッシュ法 h(x) ハッシュ関数 衝突 x=“apple” 4 (ハッシュ値) x=“almond” 4　(ハッシュ値)

注意：用語の別名 D. E. Knuth, “The Art of Computer Programming,” Vol. 3:Sorting and Searching, Addison-Wesley, 1973 チェイン法（chaining) オープンアドレス法(open addressing) N. Wirth, “Algorithms + Data Structures = Programs,” Prentice Hall, 1976 直接チェイン法(direct chaining) A. V. Aho, J. E. Hopcroft, J. D. Ullman, “Data Structures and Algorithms,” Addison-Wesley, 1983 オープンハッシュ法(open hashing) クローズドハッシュ法（closed hashing) この呼び方を使用 こちらの呼び名を 使っている本の方が多い オープンが 逆なので注意!!!!

チェイン法(chaining) 同一のハッシュ値を持つデータを連結リストで処理 データの格納 almond kiwi orange table[0] kiwi orange banana ハッシュ値 4 table[1] table[2] mango 衝突 table[3] apple table[4] almond table[5] バケット数6のハッシュテーブル

チェイン法におけるデータの探索 データの探索 orange kiwi orange banana mango almond apple 違う 見つけた！ ハッシュ値 0 table[0] kiwi orange banana table[1] table[2] mango table[3] almond apple table[4] table[5]

チェイン法の解析 あらかじめデータの個数を見積もり， それに見合った数のバケットを用意する チェイン法の解析　　　 データの個数Nに対してバケット数Bが十分大きい場合 一定時間　O(1)　で探索可能 使用されないバケットが発生する可能性あり（メモリの無駄） table[0] table[1] table[2] table[3] table[4] table[5] table[6] table[7] table[8] table[9] データの個数Nに対してバケット数Bが小さい場合 探索に時間がかかる　（　最悪でO(N)　） 空きバケットは減少 table[0] あらかじめデータの個数を見積もり， それに見合った数のバケットを用意する

ハッシュ関数の効率 効率のよいハッシュ関数 ⇒データが各バケットに一様に割当てられる 効率のよくないハッシュ関数 ⇒データが特定のバケットに偏る table[0] table[0] table[1] table[1] table[2] table[2] table[3] table[3] table[4] table[4] table[5] table[5]

オープンアドレス法(open addressing) すでにバケットが使用されていた場合，空いている別のバケットにデータを保存 データの 格納 table[0] banana table[1] almond kiwi table[2] 衝突 ハッシュ値 4 table[3] apple table[4] 再ハッシュ ハッシュ値 5 almond table[5] orange table[6] バケット数8の ハッシュテーブル 空いてる table[7]

オープンアドレス法におけるデータの探索 データの 探索 banana almond kiwi apple 再ハッシュ almond table[0] banana table[1] almond kiwi table[2] ハッシュ値 4 違う table[3] apple table[4] 再ハッシュ ハッシュ値 5 almond table[5] orange 見つけた！ table[6] table[7]

空のバケットの区別 データが削除されたのか，使われたことがないのかを区別しない場合 lemon 別のバケットに入っているかもしれない… table[0] 別のバケットに入っているかもしれない… ハッシュ値 1 banana table[1] 再ハッシュ kiwi table[2] table[3] ハッシュ値 3 再ハッシュ apple table[4] ハッシュ値 5 table[5] 再ハッシュ orange table[6] almond table[7]

空のバケットの区別（deletedとempty） データが削除された (deleted)のか，使われたことがないのか(empty)を区別することで，emptyのバケットを見つけた時点で探索を打ち切れる lemon 0: empty -1: deleted table[0] ハッシュ値 1 banana table[1] 再ハッシュ kiwi table[2] -1 table[3] ハッシュ値 3 再ハッシュ apple table[4] ハッシュ値 5 table[5] 探索終了 orange table[6] almond table[7]

再ハッシュ(rehashing) １次ハッシュ バケットがふさがっていた場合，循環的に直後のバケットを調べることになる ⇒ふさがったバケットが並びがちになる B = 8 の場合 lemon h(x) = 0 i : 再ハッシュの回数 grape table[0] h1(x) = 1 banana table[1] h2(x) = 2 kiwi table[2] h3(x) = 3 table[3]

3以外のバケットをランダムな順番で調べられる 衝突をランダムに処理する方法 1からB-1までの数字が必ず1回だけランダムに出現する数列d1, d2, … ,dB-1を用い, 次式により求める 例）数列{ 5, 1, 2, 4, 3, 6, 7}を用いた場合(B=8) キーh(x)=3のとき　0, 4, 5, 7, 6, 1, 2 ランダムな数列をどうやって作るかがポイント ⇒シフトレジスタを利用するなど 3以外のバケットをランダムな順番で調べられる

探索時に調べるバケット数（探索1回あたりの平均） オープンアドレス法の解析 探索時に調べるバケット数（探索1回あたりの平均） 再ハッシュ時に 順番に バケットを調べる場合 ランダムな数によって データが見つかった場合 (探索成功) データが見つからない場合 (探索失敗) αはハッシュ表の使用率

探索成功時の比較バケット数 80％ 3.0個 2.0個 90％ 5.5個 2.6個 ハッシュ表の 使用率 α 再ハッシュ時に 順番に バケットを調べる場合 ランダムな数によって 80％ 3.0個 2.0個 90％ 5.5個 2.6個

ハッシュ法の比較 チェイン法 オープンアドレス法 登録データ数 N の上限 なし = バケット数B 操作の効率 N ≧B のとき急速に低下 ハッシュ法の比較　　　　　 チェイン法 オープンアドレス法 登録データ数 N　の上限 なし (ただし，データ数が多すぎると探索時間が長くなる) =　バケット数B 操作の効率 N ≧B　のとき急速に低下 N が B に近づくにつれ急速に低下． データ数N の目安 ２B 　≧　 N 0.9B 　≧　 N

乱数列の生成例 d1 =5 <<1 k d2 =1 B=8(=23 ), k=3, di=5の場合 d3 =2 d4 =4 k 乱数列の生成例　 d1 =5 <<1 k d2 =1 B=8(=23 ), k=3, di=5の場合 d3 =2 d4 =4 1～7の乱数が 得られた k d5 1 =3 d6 1 =6 1 1 k=5でもうまくいくが， その他のkではうまくいかない k 1 d7 =7 1

1～B-1の乱数をうまく生成できるk をあらかじめ見つけておく必要がある シフトレジスタによる乱数列の生成 B ： 2のべき乗の数 （例： 21,22,23, …） k ： 1～B-1までの間のある定数 di : 最初の値 ① diを2倍 （1ビット左シフト） ② 結果がBを超えていたら，Bを減算し，減算結果と，あらかじめ決めておいたkとの排他的論理和をとる 1～B-1の乱数をうまく生成できるk をあらかじめ見つけておく必要がある 乱数が得られる

乱数列の生成例 d1 1 =5 1 <<1 k 1 d2 1 =1 B=8(=23 ), k=3, di=5の場合 d3 1 乱数列の生成例　 d1 1 =5 1 <<1 k 1 d2 1 =1 B=8(=23 ), k=3, di=5の場合 d3 1 =2 d4 1 =4 1 1～7の乱数が 得られた k 1 d5 1 =3 d6 1 =6 1 1 k=5でもうまくいくが， その他のkではうまくいかない k 1 d7 =7 1

まとめ 集合 辞書とハッシュ法

本日の課題 バケット数5のハッシュ表を考える．ハッシュ関数h(x)= x mod 5 を用いて,空のハッシュ表に数値データ x ={23,　48,　35,　4,　10}を格納する場合について以下の問に答えよ． （問1）　チェイン法を用いてデータを格納した場合，ハッシュ表はどうなるか？図を描け． （問2）　オープンアドレス法を用いてデータを格納した場合，ハッシュ表はどうなるか？図を描け．ただし再ハッシュには一次ハッシュを使用するものとする．