集合、辞書とハッシュ法
第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の位数(cardinality) :
|A|＜∞のとき、Aは有限集合(finite set)
：
B
集合Aのその要素も集合Bの要素となって
いるときAはBの部分集合(subset)：
A⊆BかつA≠BのときAはBの真部分集合
(proper subset)：
A
a
b
c
f e
3
集合と要素
有限集合は通常…
要素をすべて列挙して記述する
A={
}
B={
}
B
要素の並べ方によって区別しない
A = { a, c, e, f } = { a, e, f, c }
A
a
b
c
f e
4
和集合、積集合、差集合
和集合(union)
A∪B = {
}
積集合(共通集合, intersection)
A∩B = {
}
差集合(difference)
A-B = {
}
p.49
A
a
B
b
d
c
5
空集合、互いに素
φ
要素を1つも持たない集合
E=φ
A∩B = φ
p.49
E
A
a c
B
b
A∩B = φ のときにA∪Bを求めること
集合族(family of sets)
集合の集合
6
集合に関する基本的演算と操作
UNION（A, B, C）
INTERSECTION(A, B, C)
DIFFERENCE(A, B, C)
MERGE(A, B, C)
A∩B ＝φ （AとBは互いに素）のとき
A∩B ≠ φ のとき，未定義またはエラー
A
a c
C
b
B
7
集合に関する基本的演算と操作2
MEMBER（ｘ, 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 のとき１、 i ∈ A のとき０で表現
割当を逆にしてもよい
[4]
[5]
[6]
[7]
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]
10
連結リストによる集合の実現
普遍集合がうまく定義できない場合や、Nが大きい
場合は連結リストで表現すると良い
A = { a, c, e, f }
init
a
A
c
領域量は
MEMBER, INSERT, DELETEは
INTERSECTION, DIFFERENCEは
e
f
で実行可能
かかる
11
辞書（Dictionary）
集合Aに対し、以下の3つの演算のみが適用されると
きAを
と呼ぶ
INSERT
挿入．データ（レコード）を登録する．
DELETE
削除．与えられた値(検索キー)と同じデータ（レコー
ド）を探し出して，削除する．
MEMBER
与えられた値(検索キー)と同じデータ(レコード)が存在
すれば
，存在しなければ
を出力する．
12
概念図
検索キー
orange
MEMBER(“orange”, D)
⇒ yes
MEMBER(“banana”, D)
⇒ no
辞書D
13
ハッシュ法(hashing)
辞書は、しばしば
を用いて実現される
ハッシュ法では，検索キーの値を，データが格納
される位置(配列の添字)に直接関連付ける
これにより，データの個数によらず，データの探
索が一定時間で行える
計算量
(一定時間)
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
文字コード
6×16+1＝97
American Standard
Code for Information
Interchange
1文字１byte(8bit)で表現
char型が表現できる範囲
-128 ～ 0 ～ +127
128種類
18
衝突（コリジョン, collision）
異なるキーに対して同一のハッシュ値が生成されるこ
とを、
という
x=“apple”
h(x)
4 (ハッシュ値)
x=“almond”
ハッシュ関数
4 (ハッシュ値)
衝突
コリジョンが発生した場合の対策には以下の２通りの
方法がある （教科書と異なる名称なので注意 ）
＝ 外部ハッシュ法
＝ 内部ハッシュ法
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が十分
場合
• 一定時間
で探索可能
• 使用されないバケットが発生する可能性あり（メモリの無駄）
table[0]
table[1]
table[2]
データの個数Nに対してバケット数Bが
• 探索に時間がかかる （
• 空きバケットは減少
場合
）
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)
１次ハッシュ
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
の目安
(ただし，データ数が多すぎる
と探索時間が長くなる)
低下
れ急速に低下．
２B ≧ 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
© Copyright 2024 ExpyDoc
