スライド 1

４章ハッシュとバケット
杉原厚吉．（２００１）.「データ構造とアルゴリズム」.
東京：共立出版.
6月17日分
情報知能学科「アルゴリズムとデータ構造」
担当：白井英俊
4.2 ハッシュ法(hash)
hash : 切り刻む
• ハッシュ法は
参考：ハヤシライス
検索を O(1) で行う方法
hashed beef rice
…「格納されているデータの個数に依存しな
い、一定の計算量で検索できる」ということ
・ハッシュ関数(hash function)
h(x) : 整数xに対し、ある定数m以下の非負整
数を返す関数
ハッシュ関数 h(x)
h(x) : 整数xに対し、ある定数m以下の非負整数を返す
関数
その心：格納すべきデータを S ={x1,x2,…,xn}、それを
記憶する配列Ａの大きさを m とする
どの項目xi も配列Aのどこかに入れる
なるべくSのデータがAの中に散らばって入るように
「 xi と xi を入れるAのインデックスとを対応付けた
い」 ⇒ この対応を与えるのがハッシュ関数 h(x)
つまり、h(xi)
xi を入れるAのインデックス
ハッシュテーブル(hash table)
ハッシュ値の衝突(collision)
• ハッシュ関数を考える時に気をつけること
ハッシュ値の衝突(collision)
異なるデータxi と xj に対し
関連：誕生日問題
h(xi) = h(xj)
23人いれば0.5以上の確率
で同じ誕生日の人たちがいる
となることが起こりうる
… なるべくそうならないハッシュ関数が望ましい
参考：
364 363 362
342
*
*
* ...*
 0.46
365 365 365
365
ハッシュ値の衝突の解決策
• 再ハッシュなどいろいろな解決策がある
（確率的に絶対起こるので、その対策が必要）
教科書(p.38-39)の解決策：
配列（ハッシュテーブル）の要素を「線形リス
トの先頭へのポインタ」とする
同じハッシュ値を持つデータは、このリストに
入れておく
ハッシュ値の衝突の解決策（図示）
ハッシュテーブル
0
線形リスト
1
2
…
xi
h(xj) = h(xi)
…
xk
h(xk)
…
m-1
xj
ハッシュテーブル作成の例
3 55, 77, 10
• S={3,
10, 12
12, 16
16} の要素からハッシュテー
ブルを作成する。ここではハッシュ関数として、
h(x) = x mod 5 を採用するものとする。
xを5で割った余り
0
1
注：リストの順番は
任意（どうでもよい）
ので、新しい要素を
リストの最後ではなく
先頭に入れたほうが
本当は効率的
2
3
4
ハッシュ法による検索
データxがハッシュテーブルAに格納されているか？
1) xに対するハッシュ関数の値 h(x) を求める
2) h(x)をインデックスとする配列の要素 A[h(x)]
を取り出す
3) その値が線形リストで、そのリスト中に x があ
ればそれを返す。さもなければ nil を返す。
これはデータの大きさ n に依存しない手間
(後述する注意参照）
ハッシュ法による検索の例
(1) 12を検索
(2) 11を検索
0
1
2
3
4
12 mod 5=2から2のリストを探索
11 mod 5=1から1のリストを探索
5 Not 10
Found!
16 Matched!
7
12
3
X
X
記憶されているデータ:
S={3, 5, 7, 10, 12, 16}
ハッシュ法の計算量
• 検索の計算量はデータの大きさ n に依存しない
ように見える
• ただし、｢ハッシュ関数 h」の作り方に依存する
最悪のケース: どの要素 x に対しても h(x) が同
じ値を返すなら ⇒ 計算量は O(n)
• 平均的には、ハッシュテーブルの大きさを m と
すると、配列のそれぞれの要素には n／m 個の
データが格納される
• 経験的には、 m ≧ 2*n なら O(1)
Rubyのハッシュと使用例
• Rubyではハッシュは「連想配列」とも呼ばれる数では
なく任意のオブジェクトがインデックスとして使える
例:
h = { 3 => “abc”, “x” => 12}
3や”x”がインデックスと
してハッシュhに値を記憶
別な方法：
h = Hash.new
空っぽのハッシュを作る
h[3] = “abc” ; h[“x”] = 12
要素の参照方法は「配列」と同じ
ハッシュでは、登録されていないインデックスを指定
エラーにはならず、(デフォルトでは) nilを返す
すると… h[“xy”]
Rubyのハッシュと使用例(続)
# Usage(使い方): ruby hashSample.rb sampleEnglish.txt
分析対象のファイル
file =ARGV[0]
# ファイル名を取得
words = Hash.new(0) # ハッシュを新たにつくる。未登録のインデックスには
# nilではなく0を値として返すようにする
inf = open(file,“r”) # ファイルを開く
while (a = inf.gets) # 繰り返し：ファイルから一行ずつ読みこむ
wlist = a.split(/[-‘\W\s]+/) # 文字以外のところで切り離し、単語の配列にする
for w in wlist # 単語の配列からひとつずつ単語を取り出し
w = w.tr(“A-Z”, “a-z”) # 大文字を小文字に変換し
words[w] += 1 # 単語(w)をハッシュのインデックスとし、値(出現数)を１増やす
end # for
end # while
inf.close # ファイルを閉じる
for x in words.keys # ハッシュのインデックスの配列(hash.keys)に対して
print x,“ => ”,words[x],“\n”
# 単語と出現数を表示する
end # for
実行例
• sampleEnglish.txtを対象とすると…
me => 1
is => 1
convinced => 1
play => 1
dark => 1
turning => 1
it => 4
distinctly => 1
upon => 1
relate => 1
am => 1
legatee => 1
father => 1
sad => 1
know => 1
started => 1
easterly => 1
the => 11
an => 3
man => 1
dead => 2
come => 1
rashly => 1
remarkable => 1
or => 1
there => 4
don => 1
up => 1
him => 1
doubt => 1
very => 1
sometimes => 2
firm => 1
otherwise => 1
night => 1
be => 4
wonderful => 1
as => 1
…
ハッシュの演習（出欠課題）
• 演習4.3
m = 20
h(x) = xをmで割った余り（剰余）
とした時、
(1) 次の10個のデータを格納するハッシュテーブ
ルを作れ（図示せよ）。
32, 76, 105, 200, 282, 888, 28, 168, 56, 1219
(2) 「28を検索する」様子を述べよ
(3) 「49を検索する」様子を述べよ
ハッシュの演習
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
32
ハッシュの演習
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
32
4.3 バケット法(本講では省略）
• 「n個のデータの中から与えられたデータxに最も近
いデータを探す」という問題を考える
–『同じ』データを探すなら、O(1)のハッシュ法
–『数』なら、一直線上にデータを並べられるから、二分探索
法もある---O(n)
データが2次元や3次元の座標で与えられていたらどうか？
関連問題：「ある文書」に最も近い文書をデータベースから
探し出すー情報検索
文書を「n次元の特徴ベクトル」で表現すれば、今の問題
と同じになる
n個のキーワードに対し、文書がそれを
含めば1、含まなければ0として実現可能
バケット法（続）
• ここでは2次元（平面）上にデータがあるとする
• 仮定：データの個数をnとする。すべてのデータはx
座標もy座標も 0～1の範囲にあるとする
• 方法： n に最も近い整数を k とする
[0, 1] × [0, 1] の平面を k×k に分割する
x
y
バケット法（続）:平面の分割
k -1
こ
の
一
つ
一
つ
が
バ
ケ
ッ
ト
2
1
0
0 1 2 3 4 5 6
k -1
平均的には｢一つのバケットに一つのデー
タが入っている」
バケット法（続）:データをバケットに
• すべてのデータをその座標に基づいてバ
ケットに入れる
• 同じバケットに複数のデータが入る可能
性がある⇒リストにしておく
例点Pi の座標を(xi, yi)とする
→ ( [k* xi], [k*yi]) のバケットに入れる
問題：点Qj =(xj, yj)に最も近いデータは？
答え： ( [k* xj], [k*yj]) のバケットを調べる
X とする
Xの中にデータがあれば、教科書p.41図5に
あるように、Xも含めXの周囲のバケット21個
の中のデータに対し、 Qjとの距離を求める
k = n >> 21
ならば、この計算量は定数、つまり O(1)とみ
なせる
問題：点Qj =(xj, yj)に最も近いデータを求める
(続き）
• Xの中にデータがなければ、
まずXの周辺の「近い」バケットから順に空
でないバケットを探す。
その中のデータとQj との距離 d を求める。
Xから距離 d 以内のすべてのバケットを調べ、
最も距離の小さいデータを応える。
… この手間も、先と同様、平均的に O(1) とみ
なせる―少なくとも全部のデータを調べる方法
O(n)よりも小さな計算量で実行可能
4.4 バケット・ソート
• バケット・ソート（基数ソート）とは
郵便番号や学籍番号のように、ソートす
るキー(数）の範囲があらかじめ分かって
いて、かつその範囲の中でソートすべき
対象が偏りなく分散している場合に有効
な方法
バケットソートの例
• 教科書(p.42-43)から
n 枚の葉書を7桁の郵便番号の小さい順番に並べる―先
の条件が(まあまあ)満たされている
• 手順:
1) 0, 1, 2, …, 9のラベルのついた箱を用意
2) 郵便番号の｢1の位」に注目し、その番号と一致する箱
に入れる
3) すべて入れ終わったら、ラベル0,1,2,…,9の順に箱から
取り出し、上下を引っくり返して重ねる(上から1の位が
987…10となる）
4) 2), 3)を「10の位」「100の位」と順に繰り返す
5) 最後の「1000万の位」の時、9, 8, 7, …, 0の順に取り出
して順に積み重ねると、昇順にソートされている。
バケットソートの計算量
• n枚の葉書を郵便番号の小さい順で並べる:
手順:
1) 0, 1, 2, …, 9のラベルのついた箱を用意
2) 郵便番号の｢1の位」に注目し、その番号と一致する箱に入れる
3) すべて入れ終わったら、ラベル0,1,2,…,9の順に箱から取り出し、
1の位が上から9,8,7,…1,0となるように積み重ねる
4) 2), 3)を「10の位」「100の位」と順に繰り返す(「 nの位」で
行ったら、nの位が上から9,8,7,…1,0となり、かつ底にある葉書が
上になるように積み重ねる)
5) 最後の「1000万の位」の時、9, 8, 7, …, 0の順に箱から取り出し
て積み重ねると、昇順にソートされている。
2）から5)まではO(n)。従って、O(n*7)=O(n)
他の「高速」ソートの方法がO(n *log(n))であるから、
これは速い！何か問題点はないだろうか？
例題：3桁の数でやってみる(1の位に注目）
056 927 234 048 804 055 565 585
457 369 552 488 642 274 500 783
087 528 749 092 043 618 194 795
0
1
2
3
4
5
6
7
8
9,8,7，…という順番で数を取り出し積み重ねる
369, 749, 048, 488, 528, 618, 927, 457, 087, 056, …
9
例題：3桁の数でやってみる(10の位に注目）
369 749 048 488 528 618 927 457
087 056 055 565 585 795 234 804
274 194 783 043 552 642 092 500
0
1
2
3
4
5
6
7
8
9
9,8,7，…という順番で「底の物が先頭」になるよう数を
取り出し積み重ねる
795, 194, 092, 488, 087, 585, 783, 274, 369, 565, …
例題：3桁の数でやってみる(100の位に注目）
795 194 092 488 087 585 783 274
369 565 457 056 055 552 749 048
043 642 234 528 927 618 804 500
0
1
2
3
4
5
6
7
8
9
1,2,3，…という順番で「上が先」になるよう数を取り出す
結果: 043, 048, 055, 056, 087, 092, 194, 234,274,369, 457, 488,
500, 528, 552, 565, 585, 618, 642, 749, 783, 795, 804, 927
バケットソートの練習（出欠課題）
(1)2桁の数でやってみる 0から9までの箱を用意。２回の操作
70, 16, 29, 40, 11, 88, 81, 19, 01, 63, 37, 71
42, 12, 68, 85, 98, 54, 07, 24
(2) 3桁の数でやってみる 0から9までの箱を用意。３回の操作
068, 297, 324, 084, 840, 505, 631, 152,
576, 693, 523, 985, 426, 742, 050, 937,
708, 852, 497, 102, 304, 861, 419, 679
紙と鉛筆でやる場合：０から９までの箱を描き、そこに次々と数を書き入れる
次に０から9までの箱を別に書き、前に作った箱のうち９の箱から順に取
り出して、新たな箱に書き入れていく
PC上でやる場合：エディタで０から9に対応する行を作り、箱にみたてる

Download Report