アルゴリズムと
データ構造
第8回
探索
前回の復習
キュー
抽象データ型としてのキュー
単方向リストによるキューの実現
循環配列（リングバッファ）によるキューの実現
前回の演習問題の答え
問題１：
次のような一連の操作を実行した後のキューQの内容を
示しなさい。
Enq(Q,a), Enq(Q,b), Enq(Q,c), Deq(Q), Deq(Q),
Enq(Q,d), Deq(Q), Enq(Q,e).
練習問題
① Enq(Q,a)
② Enq(Q,b)
de
abc
③ Enq(Q,c)
④ Deq(Q)
⑤ Deq(Q)
c
⑥ Enq(Q,d)
b
⑦ Deq(Q)
a
⑧ Enq(Q,e)
Q
前回の演習問題の答え
問題２：
アルゴリズムenqueue(Q,x)をプログラムとして実現しなさい。
Enqueue(Q, x){
if (number < max){
number ← number+1;
tail ← (tail mod max) + 1;
Q[tail] ← x;
}
else{
print(“Queue Q over flows.”)
}
}
前回の演習問題の答え
#include <stdio.h>
#define max 256 /*キューの最大サイズ*/
struct queue
/*配列(構造体)によるキュー*/
{
int number;
int tail;
char element[max]; /*キューに保存するデータは文字に限る*/
};
void enqueue(struct queue *Q, char x){
if (Q->number < max){
Q->number = Q->number+1;
Q->tail = (Q->tail mod max) + 1;
Q->element[Q->tail] = x;
}
else{
print(“Queue Q over flows.”);
}
}
探索
探索とは
データの集合から、目的とする値を持った要素を
探し出すこと
探し出す値の項目：キー
データの一部
キーの指定方法はさまざま
一致、範囲指定、近接など
探索失敗する（見つからない）こともあり
探索
探索アルゴリズム
用途、目的、実行速度、対象のデータ構造などに
より使い分け
探索以外にどのような操作を行うかも考慮
単に見つかればOK→計算時間が短ければよい
データの追加や削除もあり→追加や削除のコストがあ
まり大きくならないように
線形探索
線形探索（逐次探索）とは
目的とするキー値と一致するまでデータを先頭か
ら順に探索
探索の終了
探索すべき値と等しい要素があった場合
探索すべき値と等しい要素がなく末端を通り越した場合
探索のコスト
n項目あれば平均n/2回
線形探索
7を探索
6
4
3
7
1
9
8
1
9
8
探索成功
5を探索
6
4
3
7
探索失敗
線形探索
線形探索プログラム（無限ループ版）
int search(const int a[], int n, int key) {
int i = 0;
while (1) {
if (i == n) return (-1);
if (a[i] == key) return (i);
i++;
}
}
/* 無限ループ */
/* 探索失敗 */
/* 探索成功 */
/* 次の要素 */
線形探索
線形探索プログラム（for版）
int search(const int a[], int n, int key) {
int i;
for (i = 0; i < n; i++)
if (a[i] == key) return (i);
return (-1);
}
/* 探索成功 */
/* 探索失敗 */
線形探索
番兵法
データの末尾まで探索したかのチェックを省略
末尾にキー値を格納：番兵
データ内に一致する値がなくても必ず番兵と一致
一致位置が末尾なら探索失敗と判断
番兵法
7を探索
6
4
3
7
1
9
8
番兵
探索成功
5を探索
6
4
3
7
7
1
9
8
5
探索失敗
線形探索
番兵法による線形探索（無限ループ版）
int search(const int a[], int n, int key) {
int i = 0;
a[n] = key;
/* 末尾に番兵を配置 */
while (1) {
/* 無限ループ */
if (a[i] == key) break;
/* 探索成功 */
i++;
/* 次の要素 */
}
return (i == n ? -1 ： i);
/* 末尾なら探索失敗 */
}
線形探索
番兵法による線形探索（for版）
int search(const int a[], int n, int key) {
int i;
a[n] = key;
/* 末尾に番兵を配置 */
for (i = 0; ; i++)
/* ループ終了条件不要 */
if (a[i] == key) break;
/* 探索成功 */
return (i == n ? -1 ： i);
/* 末尾なら探索失敗 */
}
2分探索 （binary search）
2分探索とは
要素があらかじめソート（整列）されているデータ
から効率よく探索を行うアルゴリズム
中央の値に着目し、その値より大きいか小さいか
で探索範囲を半分に絞り込み
探索のコスト
n項目あれば平均log(2)n回
2分探索
39を探索
5
7
15
28
29
31
39
58
< 39探索成功
6を探索
5
7
15
< 6 探索失敗
>6 >6
28
29
31
>6
39
58
68
70
95
> 39
68
70
95
2分探索
探索アルゴリズム
• 探索範囲の先頭の添字をpl、末尾の添字をpr、中央の添字をpcと表すことにする。
• 探索開始時におけるplは0、prはn-1、pcは(n-1)/2である。
Key＝a[pc]のとき
探索成功
Key > a[pc]のとき
探索範囲をa[pc+1] ~ a[pr]に絞り込むことができる。plの値をpc+1に更新する。
Key < a[pc]のとき
探索範囲をa[pl] ~ a[pc-1]に絞り込むことができる。prの値をpc-1に更新する。
アルゴリズムの終了条件は、以下に示す条件(c1)と(c2)のいずれかがせいりつすることである。
(c1) a[pc]とKeyが一致した
(c2) 探索範囲がなくなった
2分探索
pl
39を探索
5
7
15
28
29
pc plplpc pr
pc
31
68
39
58
< 39探索成功
pl pc
plpr
pl pc
plpc pr
6を探索
5
7
15
< 6 探索失敗
>6 >6
28
pr
pc
29
31
>6
pr
70
95
> 39
pr
39
58
68
70
95
ハッシュ法
ソート済み配列の操作
データの追加：格納位置からあとの配列をすべて
1つずつ移動し、格納位置をあける必要あり
データの削除：削除位置からあとの配列をすべて
1つずつ移動し、削除位置を埋める必要あり
ハッシュ法とは
格納する値を元に、簡単な計算で格納位置を求
め、効率よく格納、探索を行う方法
ハッシュ法(hashing)
特徴
ハッシュ法では，検索キーの値を，データが格納される位置(配列の添字)
に直接関連付ける
これにより，データの個数によらず，データの探索が一定時間で行える
計算量 O (1) (一定時間)
用語
ハッシュ関数(hash function) h(x) : キーの値x を配列の添字
へ写像する関数
ハッシュ値(hash value) : ハッシュ関数h(x)が返す値
ハッシュ表(hash table) : データを格納する配列
バケット(bucket) : ハッシュ表の各要素
ハッシュ法の概要
ハッシュ法による探索
キー”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
ハッシュ関数の例
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
文字コード
ASCIIコード
American Standard
Code for Information
Interchange
1文字１byte(8bit)で表現
char型が表現できる範囲
-128 ～ 0 ～ +127
128種類
6×16+1＝97
ハッシュ法
ハッシュ法の原理
キー値からハッシュ値（配列の場合は添え字）を
求める：ハッシュ関数
キー値
5
6
14
20
29
34
37
51
69
75
13で割った剰余
5
6
1
7
3
8
11
12
4
10
5
6
7
8
9
10
11
12
5
6
20
34
-
75
37
51
0
1
2
3
4
-
14
-
29
69
ハッシュ法
ハッシュ法による要素の挿入
0
1
2
3
4
-
14
-
29
69
5
6
7
8
9
10
11
12
5
6
20
34
-
75
37
51
5
6
7
8
9
10
11
12
5
6
20
34
35
75
37
51
35を挿入：35=13x2+9 ハッシュ値9
添え字9の位置に挿入
0
1
2
3
4
-
14
-
29
69
衝突（コリジョン, collision）
異なるキーに対して同一のハッシュ値が生成されるこ
とを、コリジョン（衝突）という
x=“apple”
x=“almond”
h(x)
ハッシュ関数
4 (ハッシュ値)
衝突
4 (ハッシュ値)
コリジョンが発生した場合の対策には以下の２通りの
方法がある
チェイン法 (chaining)
＝ 外部ハッシュ法
同一ハッシュ値を持つ要素を線形リストで管理
オープンアドレス法 (open addressing) ＝ 内部ハッシュ法
空きバケットが見つかるまでハッシュの繰り返し
注意：用語の別名
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)
オープンが
逆なので注意!!!!
チェイン法(chaining)
同一のハッシュ値を持つデータを連結リストで処理
例１：
0
1
13
14
2
3
4
5
6
7
8
29
69
17
5
6
33
20
46
34
69
17を挿入
33を挿入
46を挿入
33を削除
ハッシュ値7
ハッシュ値4
20
9
10
11
12
75
37
51
チェイン法(chaining)
例2：
データの探索
orange
見つけた！
違う
ハッシュ値 0
table[0]
kiwi
orange
table[1]
table[2]
mango
table[3]
table[4]
table[5]
almond
apple
banana
チェイン法の解析
データの個数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]
あらかじめデータの個数を見積もり，
それに見合った数のバケットを用意する
ハッシュ関数の効率
効率のよいハッシュ関数
⇒データが各バケットに一様
に割当てられる
効率のよくないハッシュ関数
⇒データが特定のバケットに偏る
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)
衝突が起きたら再ハッシュ
ハッシュ関数のほかに再ハッシュ関数
空きバケットを求め順にたぐる→線形探査法
衝突をランダムに処理する方法
要素削除のときの問題
すでに削除されたのと同じ要素が再ハッシュで配置さ
れていた場合、たどり着けない→削除済みフラグ
方法1．再ハッシュ(rehashing)
すでにバケットが使用されていた場合，空いている別のバ
ケットにデータを保存
１次ハッシュ
B = 8 の場合
lemon
hi ( x) (h( x) i ) mod B
i : 再ハッシュの回数
バケットがふさがっていた
場合，循環的に直後のバ
ケットを調べることになる
⇒ふさがったバケットが並び
がちになる
h(x) = 0
table[0] grape
table[1] banana
table[2] kiwi
table[3]
h1(x) = 1
h2(x) = 2
h3(x) = 3
再ハッシュ(rehashing)
例3：
0
1
2
3
4
-
14
-
29
69
18を挿入
5
6
7
8
9
10
11
12
5
6
18
-
34
-
75
37
51
18
18
18
衝突 衝突
再ハッシュ値7：添え字7の位置に挿入
ハッシュ値5：添え字5の位置に挿入
再ハッシュ値6：添え字6の位置に挿入
再ハッシュ(rehashing)
例4：
データの
格納
table[0]
table[1] banana
almond
table[2] kiwi
table[3]
ハッシュ値 4
衝突
table[4] apple
再ハッシュ
table[5] almond
バケット数8の
ハッシュテーブル
table[6] orange
table[7]
ハッシュ値 5
空いてる
再ハッシュ(rehashing)
例4：
データの
探索
table[0]
table[1] banana
almond
table[2] kiwi
table[3]
ハッシュ値 4
違う
table[4] apple
再ハッシュ
table[5] almond
table[6] orange
table[7]
見つけた！
ハッシュ値 5
方法２：衝突をランダムに処理する方法
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以外のバケットを
ランダムな順番で
調べられる
ランダムな数列をどうやって作るかがポイント
⇒シフトレジスタを利用するなど
シフトレジスタによる乱数列の生成
B ： 2のべき乗の数 （例： 21,22,23, …）
k ： 1～B-1までの間のある定数
di : 最初の値
1～B-1の乱数をうまく生成できるk をあら
かじめ見つけておく必要がある
① diを2倍 （1ビット左シフト）
② 結果がBを超えていたら，Bを減算し，減算
結果と，あらかじめ決めておいたkとの排他
的論理和をとる
乱数が得られる
乱数列の生成例
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 1 1
=7
=1
=2
=4
41
空のバケットの区別
データが削除されたのか，使われたことがないのか
を区別しない場合
table[0]
別のバケットに入っ
ているかもしれない
…
table[1] banana
table[2] kiwi
table[3]
table[4] apple
table[5]
table[6] orange
table[7] almond
lemon
ハッシュ値 1
再ハッシュ
ハッシュ値 3
再ハッシュ
ハッシュ値 5
再ハッシュ
空のバケットの区別（deletedとempty）
データが削除された (deleted)のか，使われたことが
ないのか(empty)を区別することで，emptyのバケット
を見つけた時点で探索を打ち切れる
0: empty
-1: deleted
lemon
table[0]
ハッシュ値 1
table[1] banana
table[2] kiwi
table[3]
再ハッシュ
ハッシュ値 3
-1
table[4] apple
table[5]
再ハッシュ
ハッシュ値 5
0
table[6] orange
table[7] almond
探索終了
オープンアドレス法の解析
探索時に調べるバケット数（探索1回あたりの平均）
再ハッシュ時に
順番に
バケットを調べる場合
再ハッシュ時に
ランダムな数によって
バケットを調べる場合
データが見つかった
場合
(探索成功)
1 / 2
1
1
log e
1
データが見つからな
い場合
(探索失敗)
1
1
2 2(1 2 )
1
1
αはハッシュ表の使用率
登録したデータ数
全バケット数
1
探索成功時の比較バケット数
ハッシュ表の
使用率
α
再ハッシュ時に
順番に
バケットを調べる場合
再ハッシュ時に
ランダムな数によって
バケットを調べる場合
80％
3.0個
2.0個
90％
5.5個
2.6個
ハッシュ法の比較
チェイン法
オープンアドレス法
= バケット数B
登録データ数
N の上限
なし
操作の効率
N ≧B のとき急速に N が B に近づくにつ
データ数N
の目安
(ただし，データ数が多すぎる
と探索時間が長くなる)
低下
れ急速に低下．
２B ≧ N
0.9B ≧ N
まとめ
探索
線形探索
番兵による線形探索
2分探索
ハッシュ法
ハッシュ法によるデータの格納・探索
衝突を処理する方法
チェイン法
再ハッシュ(rehashing)
オープンアドレス法
ランダムに処理する方法
演習問題
バケット数5のハッシュ表を考える．ハッシュ関数
h(x)= x mod 5 を用いて,空のハッシュ表に数値データ
x ={23, 48, 35, 4, 10}を格納する場合について以
下の問に答えよ．
（問1） チェイン法を用いてデータを格納した場合，ハッシュ表はどうなるか？
図を描け．
（問2） オープンアドレス法（再ハッシュ）を用いてデータを格納した場合，ハッ
シュ表はどうなるか？図を描け．
名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する
提出先：
工学部電子情報実験研究棟５階
NO.5506室のドアのポストに入れてください
締め切り時間：
来週月曜日（6月9日） 午前９時まで
© Copyright 2024 ExpyDoc
