ハッシュ法

アルゴリズムとデータ構造
第14週データ探索：ハッシュ法、木構造探索法
2015年1月15日
金岡晃
授業計画
第9週
(11/27)
休講
第1週
(9/25)
データ構造とアルゴリズムの基
礎
第2週
(10/2)
アルゴリズムの効率、線型構造、第10週
スタックと待ち行列
(12/4)
第3週
(10/9)
＜演習＞アルゴリズムの効率、
線型構造、スタックと待ち行列
第11週
(12/11)
休講
第4週
(10/16)
文字列照合（KMP法、BM法）
＋＜演習＞
第12週
(12/18)
第5週
(10/23)
休講
データ整列：ヒープソート
法、クイックソート法＋＜
演習＞
第6週
(10/30)
木の構造、木の走査、二分木、
決定木
第13週
(1/8)
データ探索：ハッシュ法、
木構造探索法 →休講
第7週
(11/13)
＜演習＞木の構造、木の走査、
二分木、決定木
第14週
(1/15)
データ探索：ハッシュ法、
木構造探索法＋＜演習＞
1/29
期末試験
第8週
(11/20)
中間試験
1
2015/1/15
グラフ構造と最短路問題＋
＜演習＞
アルゴリズムとデータ構造
アルゴリズムとデータ構造
【復習】第12週
データ整列：ヒープソート法、ク
イックソート法
2
2015/1/15
アルゴリズムとデータ構造
整列法の分類（１）
選択による方法
単純選択法、ヒープ整列法
選択：複数のデータの中から最大あるいは
最小のものを選ぶ動作
挿入による方法
単純挿入法（シャトル整列
法）、シェル法
挿入：すでに整列している複数のデータの
並びの適切な位置に、あらたな1枚を追加
挿入する操作
交換による方法
単純交換法（バブルソート
法）、クイックソート法
3
交換：注目した2枚の順番が逆になってい
たら入れ替える動作
2015/1/15
アルゴリズムとデータ構造
整列法の分類（２）
併合による方法
併合整列法（マージソート
法）、多ウェイ併合法
併合：整列している2つのデータの並びを
統合して1つにする操作
分配による方法
バケット整列法
4
分配：データの先頭を見て、グループに大
まかに仕分ける操作
2015/1/15
アルゴリズムとデータ構造
ヒープ整列法
1次元配列データ𝑎 1 , ⋯ , 𝑎[𝑛]は、二分木の物理構造とみなすことができる。
第𝑖要素𝑎 𝑖 の左の子と右の子を、それぞれ
𝑎 2𝑖 , 𝑎 2𝑖 + 1 と考えれば、1次元配列と二分木との
間を一意に対応づけることができる。
𝑖
2𝑖
2𝑖 + 1
ヒープ整列法（Heapsort）
1次元配列を二分木と見なして整列する方法
ヒープ：親子関係にある任意の2つの節において、子節の値が親節の
値を超えないような準完全二分木
ヒープでは最大のデータは根に保持される特徴を利用する
5
2015/1/15
アルゴリズムとデータ構造
ヒープ整列法のアルゴリズム
6
2015/1/15
アルゴリズムとデータ構造
クイックソート
クイックソート法（Quick Sort）
基準値となるキーを選択し、基準値より小さい数のデータ集合と基準値より
大きい数のデータ集合に分ける。
それぞれの集合についても、同じく基準値となるキーを選択し、2つのデー
タ集合に分ける。
要素が1つ以下の集合となった場合、その集合は確定となる。
7
2015/1/15
アルゴリズムとデータ構造
クイックソートのアルゴリズム
straight-sort(x, y)は
単純な方法を使うことを
意味している
8
2015/1/15
アルゴリズムとデータ構造
課題の解説
9
2015/1/15
アルゴリズムとデータ構造
演習（その10）
Floydのアルゴリズム
演習：下のグラフに対し、Floydのアルゴリズムを適用した場合、最終的に出力
される配列costの情報を示せ
配列costの初期状態
𝑆
4
𝐷
2
3
𝐴
1
𝐵
2
1
𝐶
𝐸
S
A
B
C
D
E
S
0
3
∞
∞
4
∞
A
3
0
1
1
∞
∞
B
∞
1
0
∞
∞
2
C
∞
1
∞
0
∞
∞
D
4
∞
∞
∞
0
2
E
∞
∞
2
∞
2
0
𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝑆}
10
2015/1/15
アルゴリズムとデータ構造
演習（その11）
ヒープソート、クイックソート
演習：下記の1次元配列データをヒープソート、クイックソートで処理したとき
の、処理の過程を出力するプログラムを作成せよ。
過程の記述は配列の各値がどう変化していったかのみ記載すれば良いものとす
る。
クイックソートでは、select(k)を、どういう基準で選択したかを明確にプログラ
ム内にコメントとして記載すること。また、straight-sort()を利用する閾値は10で
はなく3とする。
11
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
a[10]
30
40
80
35
60
70
55
10
20
50
2015/1/15
アルゴリズムとデータ構造
アルゴリズムとデータ構造
第14週
データ探索：ハッシュ法、木構造探
索法
12
2015/1/15
アルゴリズムとデータ構造
本日の到達目標と概要
• 到達目標
– データ探索と、その実現方法としてのハッシュ法と木構造探索法の
理解
• 概要
– データ探索
– 単純な手法：線型探索、二分探索
– ハッシュ法
• ハッシュ法概要
• ハッシュ関数
• 開番地法と連鎖法
– 木構造探索法
• 二分木探索法
• 平衡二分木
• AVL木
• B木
• 桁探索木
13
2015/1/15
アルゴリズムとデータ構造
データ探索
辞書を引く
運賃を調べる
名前を思い出す
いずれも
データの探索
コンピュータによる探索
14
ファイル構造に基づく探索
構造探索
ファイル構造に基づかない探索
内容探索、連想探索
2015/1/15
アルゴリズムとデータ構造
探索におけるレコードの指定
指定の仕方
一致型、最近接型、区間型
複数条件指定
「家賃が7万円以下で、駅から10分以内の物件」
今日の講義では
• 探索に用いられるフィールドが1つ
• 一致型の探索
• レコードを「キー」と呼ぶ
15
2015/1/15
アルゴリズムとデータ構造
単純な探索方法：線型探索と二分探索
線型探索
•
•
•
目的のキーを求めて表の先頭番地から順に調べていくもっとも単純な方法
逐次検索ともいわれる。
追加は効率的に行える（データの最後に追加する）が、探索と削除に時間がかかる
追加：𝑂(1)
探索と削除：それぞれ𝑂(𝑛)
二分探索
•
•
•
16
キーの値が昇順に並んでいるときに適用可能な手法
中央のキー（データが𝑛個ある場合は 𝑛 + 1 /2（の四捨五入か切り上げか切り捨
て）番目のキー）との大小関係を調べる
• 一致なら探索終了
• 探索キーが大なら、後半の中での中央のキーを選択し、調べる
• 探索キーが小なら、前半の中での中央のキーを選択し、調べる
追加は効率的ではないが探索が効率的
追加：𝑂(𝑛)
探索：それぞれ𝑂(log 𝑛)
2015/1/15
アルゴリズムとデータ構造
ハッシュ法
キーの値から探索・格納・削除の番地を決定する手法。
キーの値を順番に置くのではなくハッシュする（ばらまく）
ハッシュ（Hash）
意味：寄せ集め、ごたまぜ
17
2015/1/15
アルゴリズムとデータ構造
ハッシュ関数
ハッシュを行う関数
仮定：キーが小文字アルファベット8文字まで
キーのパターン数は 278 − 1
表のサイズを𝑁とすると、なるべく衝突を
さけるためにパターンを上手にばらつかせ
なければならないが、 𝑁がパターン数より
小さい場合は衝突を避けられない
なるべく衝突が
起こらないように
ハッシュ関数を設計する
利用される手法
除算法（Division）：キーのビット列を2進数と見なして表サイズの剰余を用いる
• 乱数法（平方採中法(mid-square）とも）：
乱数生成の種（Seed）としてキーを用いて、乱数を出力する
折り返し法（Folding）
• キーのビット列を適当に分断してそれらの和を計算する
•
•
•
ハッシュ関数は暗号でも重要な意味を持つ
18
2015/1/15
アルゴリズムとデータ構造
用語：同族
同族（Synonym、同義語）
ハッシュ関数の出力が一緒になる入力値
•
19
2015/1/15
アルゴリズムとデータ構造
ハッシュ法
ハッシュ関数を用意し、キーを入力にしてハッシュ関数により得られた結果を番
地として使う
衝突が起きた場合には対応が必要
• 空いている番地を探す：開番地法（開アドレス法）
• 衝突が起こったときに代わりの番地へのポインタを入れるように
する：連鎖法
開番地法の具体例：線型走査法（Linear Search）
• 得られた結果に一定の間隔𝑑を足し、空いているか確認し、空いていればそ
の番地を使う
• 空いていない場合、間隔𝑑をさらに足すことを繰り返す
• この手法での一定の間隔をハッシュ増分（Hash Increment）と呼ぶ
20
2015/1/15
アルゴリズムとデータ構造
ハッシュ法：具体例
0
1
元データ
2
iwahashi
enomoto
ooba
サイズ𝑁 = 11の
表に入れる
4
5
6
kazama
7
kurosawa
8
tada
9
yamagata
ハッシュ関数
3
10
ℎ0 𝐾 = #𝐶1 𝑚𝑜𝑑 𝑁
アルファベットの順番（1~26）
データの1文字目
衝突が起きた場合はハッシュ増分2の線型走査法を使う
ℎ𝑖 𝐾 = ℎ0 𝐾 + 2𝑖 𝑚𝑜𝑑 𝑁
21
2015/1/15
アルゴリズムとデータ構造
ハッシュ法：具体例
22
2015/1/15
アルゴリズムとデータ構造
探索効率
• ハッシュ法のキーの探索は、番地を求めることと同じ
• 探索の効率は衝突の回数に依存する
クラスタ（Cluster）
• ひとたび互いに𝑑番地離れたキー同士が塊を形成し始めると加速度的に成長し
て探索効率を急激に低下させてしまう
• この塊をクラスタと呼ぶ
第1種クラスタ（Primary Cluster）：同族でないキー同士の塊部分
第2種クラスタ：同族同士の部分（Secondary Cluster）
前スライドの例での平均探索回数：1+1+1+2+3+2+6/7＝2.29
23
2015/1/15
アルゴリズムとデータ構造
開番地法
線型走査法（Linear Search）
• 得られた結果に一定の間隔𝑑を足し、空いているか確認し、空いていればその
番地を使う
• 空いていない場合、間隔𝑑をさらに足すことを繰り返す
• この手法での一定の間隔をハッシュ増分（Hash Increment）と呼ぶ
• クラスタが発生する
ℎ𝑖 𝐾 = ℎ0 𝐾 + 𝑑𝑖 𝑚𝑜𝑑 𝑁
2次走査（Quadratic Search）法
• クラスタの発生を抑える
ℎ𝑖 𝐾 = ℎ0 𝐾 + 𝑎𝑖 + 𝑏𝑖 2 𝑚𝑜𝑑 𝑁
24
2015/1/15
アルゴリズムとデータ構造
連鎖法
• キー𝐾の番地を調べるときにℎ0 (𝐾)にすでにほかのキーが入っている場合、同
じ値を持つキーが次にどこに入っているかの番地（ポインタ）を持つ
連鎖リスト
連合連鎖（Coalesced Chaining）法：
• 連鎖リストをたどって最後の要素を見つける
• 空き番地を見つけ、そこに格納
• 最後の要素のポインタ部に格納した番地を入れる
分離連鎖（Separate Chaining）法：
• 先に入っている同族でないキーを追い出してキーKを格納
• 同族が連鎖するようにする
• 追い出されたキーを空き番地に格納
25
2015/1/15
アルゴリズムとデータ構造
演習（その12）
ハッシュ法
演習：スライド「ハッシュ法：具体例」と同じデータを、同じく𝑁 = 11の表に
ハッシュ法を用いて格納するとする。
ハッシュ関数を以下とした場合の、ハッシュ表への格納状態（表）と、平均探
索回数を求めるプログラムを作成せよ
ℎ0 𝐾 = #𝐶1 × 26 + #𝐶2 𝑚𝑜𝑑 𝑁
ℎ𝑖 𝐾 = ℎ0 𝐾 + 3𝑖 𝑚𝑜𝑑 𝑁
26
2015/1/15
アルゴリズムとデータ構造
演習（その12）：実行イメージ
> java HashSearch
0: iwahashi
1: tada
2: kazama
3:
ここに書いてある
4: ooba
値は適当です。
5: yamagata
自分で解いてみましょう
6:
7:
8: kurosawa
9: enomoto
10:
---Average Num of Search: 1.17
27
2015/1/15
アルゴリズムとデータ構造
二分木探索法
• 各節に1つのキーを格納
• 節の左部分木にはその節のキーよりも小さい値のキーを格納
• 節の右部分木にはその節のキーよりも大きい値のキーを格納
60, 30, 75, 45 ,15 ,90
というキーを順に格納
キーの削除：
• 削除したいキー𝐾の検索
• 𝐾が葉であれば即座に消去
• 𝐾が節であれば直前あるいは直後の大
きさのキーを𝐾の節に持ってくる
28
2015/1/15
アルゴリズムとデータ構造
平衡二分木
60, 30, 75, 45 ,15 ,90
というキーを順に格納する場合
二分探索木の問題点：
登録順序により木の形状が大きくかわる
90, 75, 15, 60 30, 45
というキーを順に格納する場合
節のレベル
• 探索時に木のポインタをたどる回数
平衡係数（Balance Factor）
• 二分木の任意の節での、(左部分木の高さ-右部分木の高さ）の値
• どの節においても平衡係数がある一定の範囲に収まっている場合、高さ平
衡二分木（Height Balanced Binary Tree）あるいは単に平衡二分木とい
う
29
2015/1/15
アルゴリズムとデータ構造
AVL木
• G. Adelson-VelskiiとY. Landisの２人により提案された
• キーを追加していく過程で、平衡性が破れたら直ちに二分木の構造を手直
ししてつねに平衡性を維持できるような機構を備える
30
2015/1/15
アルゴリズムとデータ構造
AVL木
単回転（Single Rotation）と複回転（Double Rotation）
• 節Aを根の方向に移動し、それに押し出されるように節Pを節Aの右の子に
移動する操作
• 単回転を２回行うことを複回転と言う
31
2015/1/15
アルゴリズムとデータ構造
B木
• R. BayerとE. McCreightにより提案された順序付き多進木
• 定義
• 根以外の節には、 𝑚個以上、 2𝑚個以下のキーが格納される。それら
のキー（ 𝑛個とする）を𝑎 1 , 𝑎 2 , 𝑎 3 , ⋯ , 𝑎[𝑛]とする。
• 根には１個以上2𝑚個以下のキーが格納される
• 葉はすべて同一レベルにある
• 葉以外の節には、部分木へのポインタが𝑛 + 1個ある。これらのポイン
タを𝑝 0 , 𝑝 1 , ⋯ , 𝑝 𝑛 とする。
• 任意の節において、キー列𝑎 1 , 𝑎 2 , 𝑎 3 , ⋯ , 𝑎[𝑛]は昇順に整列してい
る。また、葉以外の任意の節について、キー𝑎 𝑖 の大きさは、 𝑝 𝑖 − 1
の指す部分木内のどのキーよりも大きく、 𝑝 𝑖 の指す部分木内のどの
キーよりも小さい 1 ≤ 𝑖 ≤ 𝑛
32
2015/1/15
アルゴリズムとデータ構造
B木の構成
33
2015/1/15
アルゴリズムとデータ構造
B木：キー追加
キー45の追加（単純追加の場合）
キー20の追加（分割による場合）
34
2015/1/15
アルゴリズムとデータ構造
B木：キー削除（１）
キー15の削除（単純削除の場合）
キー32の削除（アンダーフローによる場合）
35
2015/1/15
アルゴリズムとデータ構造
B木：キー削除（２）
キー70の削除（連結による場合）
36
2015/1/15
アルゴリズムとデータ構造
桁探索（Digital Search）木
• 目的のキーを構成している英数字やビット（桁）を順に見つつ、分岐先を
判断しながら探索や格納を進めていく方法
37
2015/1/15
アルゴリズムとデータ構造
桁探索木：トライ
• キーを格納するのは葉のみに限定し、内部節には桁に関する分岐情報のみ
を保持するようにしたもの
38
2015/1/15
アルゴリズムとデータ構造
B木の節の物理構造
key[0]
key[1]
…
…
BTreeNode[0]
BTreeNode[1]
public class BTreeNode {
public int dimension;
public BTreeNode[] node;
public int[] key;
public BinTreeNode(int inDimension){
dimension = inDimension;
node[] = new
BTreeNode[2*dimension+1];
key[] = new int[2*dimension];
…
}
}
39
2014/10/30
アルゴリズムとデータ構造
演習（その13）
B木
演習：下図のような2次のB木があるものとする。これに、まずキー50を追加し、
その後、キー10を削除し、さらにその後にキー43を削除するものとする。それ
ぞれの処理が終わった直後のB木を図示せよ。
入力：なし（B木データはプログラム中に記載してよい）
出力：B木の状態
40
2015/1/15
アルゴリズムとデータ構造
演習（その13）：実行イメージ
 java Btree
ここに書いてある
値は適当です。
自分で解いてみましょう
root : 13, 40, 68, 88
node1: 3, 10
node2: 15, 20, 30, 33
node3: ……
……
41
2015/1/15
アルゴリズムとデータ構造
本日の到達目標と概要
• 到達目標
– データ探索と、その実現方法としてのハッシュ法と木構造探索法の
理解
• 概要
– データ探索
– 単純な手法：線型探索、二分探索
– ハッシュ法
• ハッシュ法概要
• ハッシュ関数
• 開番地法と連鎖法
– 木構造探索法
• 二分木探索法
• 平衡二分木
• AVL木
• B木
• 桁探索木
42
2015/1/15
アルゴリズムとデータ構造
締切と提出方法：演習その12, 13
• 締切
– 3週間後（2月5日）の16:10まで
• 提出方法
– 電子メール
• メールアドレス
– [email protected]
– メールのタイトルに「アルゴリズムとデータ構造第7回課題」と書
いてください
– 作ったプログラムをメールに添付してください。
• 注意事項
– 必ず金岡から受領確認メールを返します。
• 必ず日本語で受領確認メールを返します
• 英語のメールはエラーメール（アドレスが間違っている）の可
能性が高いです
– メールで提出がされていないものは未提出とみなします
43
2015/1/15
アルゴリズムとデータ構造
試験について
• 日時
– 2015年1月29日（木）3限・4限
• 形式
– 筆記試験
• 持ち込みあり
– PC、スマートフォン、タブレットの持ち込みも可
– ネットワーク接続可
• 教室は掲示で確認すること
• 時間
– 13:00-14:30の90分
• 試験範囲
– 初回から今回までの配布資料と教科書内の該当する箇所
44
2015/1/15
アルゴリズムとデータ構造

Download Report