スライド タイトルなし

集合、辞書とハッシュ法
第8回
集合と辞書
~ データ構造(4)~
1
(問1)解答
[0]
[1]
[2]
[3]
[4]
[5]
label
left
child
right
child
a
b
c
d
e
f
1
-1
-1
4
-1
-1
3
2
-1
5
-1
-1
0
b
a
3
1
2
c
d
4
5
e
f
2
集合(Set)

要素aが集合Aに属する
:

a∈ A
要素aが集合Aに属さない : a ∈ A
Aの要素の個数(Aの位数(cardinality) : |A|

|A|<∞のとき、Aは有限集合(finite set)



集合Aのその要素も集合Bの要素となって
いるときAはBの部分集合(subset): A⊆B
A⊆BかつA≠BのときAはBの真部分集合
(proper subset): A⊂B
B
A
a
b
c
f e
3
集合と要素
有限集合は通常…
 要素をすべて列挙して記述する
A = { a, c, e, f }
B = { a, b, c, e, f }
B
要素の並べ方によって区別しない
A = { a, c, e, f } = { a, e, f, c }

A
a
b
c
f e
4
和集合、積集合、差集合



p.49
和集合(union)
A∪B = { a, b, c, d }
積集合(共通集合, intersection)
A∩B = { b }
差集合(difference)
A-B = { a, c }
A
a
B
b
d
c
5
空集合、互いに素
E
空集合(empty set) φ
要素を1つも持たない集合
E=φ
A
 互いに素(disjoint)
a c
A∩B = φ
 併合(merge)
A∩B = φ のときにA∪Bを求めること
 集合族(family of sets)
集合の集合
p.49

B
b
6
集合に関する基本的演算と操作




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 ≠ φ のとき,未定義またはエラー
A
a c
C
b
B
7
集合に関する基本的演算と操作2

MEMBER(x, A)

INSERT(x, A)


DELETE(x, A)
EMPTY(A)
x ∈ A : yes を返す
x ∈ A : no を返す
x
A
A
x
A
空集合φ
8
配列による集合の実現

すべての要素が普遍集合={0, 1,2,
…,N-1}から選ばれ、Nがあまり大きく
ないものとすると右図のように表現でき
る
配列A
[0]
[1]
[2]
[3]
A={1,2,4}のときの例
i ∈ A のとき1、 i ∈ A のとき0で表現
割当を逆にしてもよい
[4]
[5]
[6]
[7]
0
1
1
0
1
0
0
0
9
積集合を求める
void intersection(int *A, int *B, int *C){
A
int i;
for ( i = 0; i < N; i++ )
[0] 0 [0]
C[i] = A[i] * B[i];
[1] 1 [1]
}
[2] 1 [2]
[3]
[4]
[5]
[6]
[7]
0
1
0
0
0
[3]
[4]
[5]
[6]
[7]
B
0
0
1
1
1
0
0
0
C
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[7]
0
0
1
0
1
0
0
0
10
連結リストによる集合の実現

普遍集合がうまく定義できない場合や、Nが大きい
場合は連結リストで表現すると良い
A = { a, c, e, f }
init
a
A



c
e
f
領域量はO(|A|)
MEMBER, INSERT, DELETEはO(|A|)で実行可能
INTERSECTION, DIFFERENCEはO(|A||B|)かかる
11
辞書(Dictionary)
集合Aに対し、以下の3つの演算のみが適用されると
きAを辞書と呼ぶ
 INSERT
挿入.データ(レコード)を登録する.
 DELETE
削除.与えられた値(検索キー)と同じデータ(レコー
ド)を探し出して,削除する.
 MEMBER
与えられた値(検索キー)と同じデータ(レコード)が存在
すればyes,存在しなければnoを出力する.

12
概念図
検索キー
orange
MEMBER(“orange”, D)
⇒ yes
MEMBER(“banana”, D)
⇒ no
辞書D
13
ハッシュ法(hashing)




辞書は、しばしばハッシュ表を用いて実現される
ハッシュ法では,検索キーの値を,データが格納
される位置(配列の添字)に直接関連付ける
これにより,データの個数によらず,データの探
索が一定時間で行える
計算量 O (1) (一定時間)
14
ハッシュ法の概要
ハッシュ法による探索
キー”apple” は
どこ?
x=“apple”
h(x)
ハッシュ関数
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
15
用語

ハッシュ関数(hash function) h(x) : キーの値x を配列
の添字へ写像する関数

ハッシュ値(hash value) : ハッシュ関数h(x)が返す値

ハッシュ表(hash table) : データを格納する配列

バケット(bucket) : ハッシュ表の各要素
16
ハッシュ関数の例
int hashfunc(char *s)
{
int i = 0;
while (*s)
i += *s++;
return i % 100;
}
文字列
文字
コード
a p p l e \0
97 112 112 108 101
各文字の文字コード
を足しこむ
0
530
%
100
=
100の剰余をとることで,
ハッシュ値が0~99の範
囲に収まる
s
ハッシュ値 30
17
文字コード

ASCIIコード
American Standard
Code for Information
Interchange

6×16+1=97
1文字1byte(8bit)で表現
char型が表現できる範囲
-128 ~ 0 ~ +127
128種類
18
衝突(コリジョン, collision)


異なるキーに対して同一のハッシュ値が生成されるこ
とを、コリジョン(衝突)という
x=“apple”
h(x)
4 (ハッシュ値)
x=“almond”
ハッシュ関数
4 (ハッシュ値)
衝突
コリジョンが発生した場合の対策には以下の2通りの
方法がある (教科書と異なる名称なので注意 )


チェイン法 (chaining)
= 外部ハッシュ法
オープンアドレス法 (open addressing) = 内部ハッシュ法
19
注意:用語の別名

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)
オープンアドレス法(open addressing)
A. V. Aho, J. E. Hopcroft, J. D. Ullman, “Data
Structures and Algorithms,” Addison-Wesley,
1983


オープンハッシュ法(open hashing)
クローズドハッシュ法(closed hashing)
オープンが
逆なので注意!!!!
20
チェイン法(chaining)

同一のハッシュ値を持つデータを連結リストで処理
データの格納
almond
table[0]
ハッシュ値 4
table[1]
table[2]
衝突
kiwi
orange
banana
mango
table[3]
apple
table[4]
table[5]
バケット数6のハッシュテーブル
almond
21
チェイン法におけるデータの探索
データの探索
orange
違う
見つけた!
ハッシュ値 0
table[0]
kiwi
orange
banana
table[1]
table[2]
mango
table[3]
table[4]
almond
apple
table[5]
22
チェイン法の解析
データの個数Nに対してバケット数Bが十分大きい場合
• 一定時間 O(1) で探索可能
• 使用されないバケットが発生する可能性あり(メモリの無駄)
table[0]
table[1]
table[2]
データの個数Nに対してバケット数Bが小さい場合
• 探索に時間がかかる ( 最悪でO(N) )
• 空きバケットは減少
table[3]
table[4]
table[0]
table[5]
table[6]
table[7]
table[8]
あらかじめデータの個数を見積もり,
それに見合った数のバケットを用意する
table[9]
23
ハッシュ関数の効率
効率のよいハッシュ関数
⇒データが各バケットに一様
に割当てられる
効率のよくないハッシュ関数
⇒データが特定のバケットに偏る
table[0]
table[0]
table[1]
table[1]
table[2]
table[2]
table[3]
table[3]
table[4]
table[4]
table[5]
table[5]
24
オープンアドレス法(open addressing)

すでにバケットが使用されていた場合,空いている
別のバケットにデータを保存
データの
格納
table[0]
table[1]
banana
table[2]
kiwi
table[4]
apple
table[5]
almond
table[6]
orange
table[7]
ハッシュ値 4
衝突
table[3]
バケット数8の
ハッシュテーブル
almond
再ハッシュ
ハッシュ値 5
空いてる
25
オープンアドレス法におけるデータの探索
データの
探索
table[0]
table[1]
banana
table[2]
kiwi
almond
ハッシュ値 4
違う
table[3]
table[4]
apple
table[5]
almond
table[6]
orange
再ハッシュ
見つけた!
ハッシュ値 5
table[7]
26
空のバケットの区別

データが削除されたのか,使われたことがないのか
を区別しない場合
lemon
table[0]
別のバケットに
入っているかもし
れない…
table[1]
banana
table[2]
kiwi
再ハッシュ
ハッシュ値 3
table[3]
table[4]
ハッシュ値 1
apple
再ハッシュ
ハッシュ値 5
table[5]
table[6]
orange
table[7]
almond
再ハッシュ
27
空のバケットの区別(deletedとempty)

データが削除された (deleted)のか,使われたことが
ないのか(empty)を区別することで,emptyのバケット
を見つけた時点で探索を打ち切れる
0: empty
-1: deleted
lemon
table[0]
ハッシュ値 1
table[1]
banana
table[2]
kiwi
再ハッシュ
table[3]
-1
ハッシュ値 3
table[4]
apple
table[5]
0
table[6]
orange
table[7]
almond
再ハッシュ
ハッシュ値 5
探索終了
28
再ハッシュ(rehashing)

1次ハッシュ
B = 8 の場合
lemon
hi ( x)  (h( x)  i) modB
i : 再ハッシュの回数
バケットがふさがっていた
場合,循環的に直後のバ
ケットを調べることになる
⇒ふさがったバケットが並び
がちになる

h(x) = 0
table[0]
grape
table[1]
banana
table[2]
table[3]
kiwi
h1(x) = 1
h2(x) = 2
h3(x) = 3
29
衝突をランダムに処理する方法

1からB-1までの数字が必ず1回だけランダムに出
現する数列d1, d2, … ,dB-1を用い, 次式により求める
hi ( x)  (h( x)  di ) modB
例)数列{ 5, 1, 2, 4, 3, 6, 7}を用いた場合(B=8)
キーh(x)=3のとき 0, 4, 5, 7, 6, 1, 2
3以外のバケットを
ランダムな順番で
調べられる
ランダムな数列をどうやって作るかがポイント
⇒シフトレジスタを利用するなど

30
オープンアドレス法の解析
探索時に調べるバケット数(探索1回あたりの平均)
再ハッシュ時に
順番に
バケットを調べる場合
再ハッシュ時に
ランダムな数によって
バケットを調べる場合
データが見つかった
場合
(探索成功)
1 / 2
1
1
log e

1
データが見つからな
い場合
(探索失敗)
1
1

2 2(1   2 )
1
1
1
αはハッシュ表の使用率
 
登録したデータ数
全バケット数
31
探索成功時の比較バケット数
ハッシュ表の
使用率
α
再ハッシュ時に
順番に
バケットを調べる場合
再ハッシュ時に
ランダムな数によって
バケットを調べる場合
80%
3.0個
2.0個
90%
5.5個
2.6個
32
ハッシュ法の比較
チェイン法
オープンアドレス法
= バケット数B
登録データ数
N の上限
なし
操作の効率
N ≧B のとき急速に N が B に近づくにつ
データ数N
の目安
(ただし,データ数が多すぎる
と探索時間が長くなる)
低下
れ急速に低下.
2B ≧ N
0.9B ≧ N
33
乱数列の生成例
d1
=5
<<1
k

B=8(=23 ), k=3, di=5の場合
1~7の乱数が
得られた
d2
d3
d4
k
d5
d6
k=5でもうまくいくが,
その他のkではうまくいかない
=1
=2
=4
k
d7
0
1
1 1
0
1
1
0
1
1
0
0
1
=3
=6
1 1 1 =7
34
シフトレジスタによる乱数列の生成



B : 2のべき乗の数 (例: 21,22,23, …)
k : 1~B-1までの間のある定数
di : 最初の値
1~B-1の乱数をうまく生成できるk を
あらかじめ見つけておく必要がある
① diを2倍 (1ビット左シフト)
② 結果がBを超えていたら,Bを減算し,減算
結果と,あらかじめ決めておいたkとの排他
的論理和をとる
乱数が得られる
35
乱数列の生成例
d1
k

B=8(=23 ), k=3, di=5の場合
1~7の乱数が
得られた
d2
d3
d4
k
d5
d6
k=5でもうまくいくが,
その他のkではうまくいかない
k
d7
1
1 0
0
0
0
1
1 0
0
0
1
1
0
1
0
0
1
1
0
1
1
0
0
0
1
=5
<<1
0
1
1 1
0
1
1
0
1
1
0
0
1
=3
=6
=1
=2
=4
1 1 1 =7
36
まとめ

集合

辞書とハッシュ法
37
本日の課題
バケット数5のハッシュ表を考える.ハッシュ関数
h(x)= x mod 5 を用いて,空のハッシュ表に数値
データ x ={23, 48, 35, 4, 10}を格納する場合
について以下の問に答えよ.
(問1) チェイン法を用いてデータを格納した場合,ハッシュ表はどうなるか?
図を描け.
(問2) オープンアドレス法を用いてデータを格納した場合,ハッシュ表はどう
なるか?図を描け.ただし再ハッシュには一次ハッシュを使用するもの
とする.
38