アルゴリズムa 第12回


ハッシュ法

データが n個あっても、上記の[手順2]の計算時間が一定であれば、 計算量は O(1)

ただし、「衝突(異なるデータを同じ場所に登録しようとする)」 が起きた時の回避方法が必要となる。

用語英語説明
ハッシュ表hash table[手順1]の表
バケットbucketハッシュ表の中でデータを1個記憶する場所
ハッシュ関数hash function[手順2]の計算に使う関数
ハッシュ値hash value[手順2]の計算値

実現方法

ハッシュ値の衝突

異なるデータに対して、同じハッシュ値が得られた場合。

p.179 ハッシュ値の衝突例
ハッシュ表:バケットの個数が100
ハッシュ関数: 「文字列の中の各文字のアスキーコードの和」 mod 100
------------------------------------------------------------------
  文字列1:        f   i   v   e
  ASCII(16進数)   66  69  76  65
  ASCII(10進数)  102 105 118 101  ⇒ 合計=426 ⇒ ハッシュ値=26
------------------------------------------------------------------
  文字列1:        n   i   n   e
  ASCII(16進数)   6d  69  6d  65
  ASCII(10進数)  110 105 110 101  ⇒ 合計=426 ⇒ ハッシュ値=26
------------------------------------------------------------------
データは "five" と "nine" で異なるのにハッシュ値は 26 で同じとなる。→衝突

では、衝突が起きた時どうすればよいだろうか?


チェイン法

探索:まず「ハッシュ値を計算してバケットの場所を求めて」、それから 「バケットに連結されているリストを線形探索する」。

データの追加・削除:まず「ハッシュ値を計算してバケットの場所を求めて」、 それから「連結リストの挿入・削除を行う」。

プログラム例(List8.2:p.181〜p.186, List8.3:p.188-189):
  ハッシュ関数:
    文字列のアスキーコードの和を求めて(MyKey.hash(): p.188 l.34-43)、
    ハッシュ表の大きさで割った余り(HashC.hash(): p.183, l.68-71)
解析
バケットの数: B
データの総数: N
ハッシュ関数がデータを均等に振り分けると仮定すると、
  1個のバケットに登録されているデータの個数=N/B
探索の計算量: O(1 + N/B)
  ハッシュの計算量: O(1)
  連結リストの線形探索: O(N/B)

もしも、BNよりもはるかに大きければ(B>>N)、 N/Bは(非常に小さいから)定数とみなせるので、全体の計算量は O(1)とみなすことができる


オープンアドレス法

衝突が起きた時(ハッシュ値がぶつかった時)、再び別のハッシュ値を計算する。

最も簡単なハッシュ値の再計算方法:
  衝突したら、その次の(隣の)バケットを選ぶ。
  もし、そこも埋まっていたらさらにその隣を選ぶ。
  空きバケットを発見するまで、この手順を繰り返す。

  hk(x) = (h(x) + k) mod B

例: p.194〜p.197

ハッシュ表の大きさ=バケットの個数=10
データの総数=6個 (このうち5個のデータを登録する)
各データのハッシュ値を次の表のように仮定する。
データabcdef
ハッシュ値158566

登録

インデックス 0 1 2 3 4 5 6 7 8 9
初期状態 . . . . . . . . . .
aを追加 . a . . . . . . . .
bを追加 . a . . . b . . . .
cを追加 . a . . . b . . c .
dを追加 . a . . . b d . c .
eを追加 . a . . . b d e c .

dを追加したとき、バッシュ値は5であるが、すでにbが登録されている ので次(インデックスは6)に登録した。

eを追加したとき、バッシュ値は6であるが、すでにeが登録されている ので次(インデックスは7)に登録した。

探索

インデックス 0 1 2 3 4 5 6 7 8 9
現在の状態 . a . . . b d e c .

bはハッシュ値5であるが、その場所で発見できる。

eはハッシュ値6であるが、その場所で発見できない。 その場合は次(隣)を探索し、7で発見できる

fはハッシュ値6であるが、その場所で発見できない。 次々と隣を(繰り返し)探索するが発見できない。 9に空のバケットがあるので、結局存在しないことがわかる(探索失敗)。

削除

インデックス 0 1 2 3 4 5 6 7 8 9
元の状態 . a . . . b d e c .
dを削除 . a . . . b . e c .
e,fの探索が変 . a . . . b . e c .
改善方法 . a . . . b 削除 e c .

dを登録してあるバケット(6)から単に削除してそのバケットを空にすると、 衝突したデータの探索が正しく動作しなくなる。 →削除した場合は、「空」ではなく「削除済み」という印を入れておく。 「削除済み」では探索を終了しない。

再ハッシュに関する考察 p.207

「ハッシュ値がぶつかったら次のバケットへ」という方針では、 データが塊になりやすい。

→「再ハッシュでバケットをランダムに選択する」とよい。

題名
ハッシュ表の大きさ(=バケットの数)がBであるとすると、
1,2, ..., (B-1) を並び替えて
  n1, n2, ..., nB-1
とし、再計算を次の式で行う。

  hk(x) = (h(x) + nk) mod B

例: p.208

ハッシュ表の大きさ: B=10 とする。

ハッシュ値を再計算するための計算式に、次のような数字を 順番に使う。

再計算用オフセット n1 n2 n3 n4 n5 n6 n7 n8 n9
6 1 4 7 2 9 8 3 5
niは 1, 2, ..., 9を並び替えたもの。
再計算したハッシュ値 h1(x) h2(x) h3(x) h4(x) h5(x) h6(x) h7(x) h8(x) h9(x)
h(x)=3の時 9 4 7 0 5 2 1 6 8
h(x)=4の時 0 5 8 1 6 3 2 7 9

この方法を取ると「データの塊ができにくい」のが利点。

解析 p.209 table8.2

α = ハッシュ表の使用率 = 登録したデータ数/全バケット数
隣のバケットへランダム数列で選んだバケットへ
発見できた場合
1 - α/2
---------
 1 ー α
1/α loge 1/(1-α)
発見できずの場合
1/2 + 1/2(1-α)2
1/(1-α)

隣りのバケットへ

α 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95
平均値 1.03 1.06 1.09 1.13 1.17 1.21 1.27 1.33 1.41 1.50 1.61 1.75 1.93 2.17 2.50 3.00 3.83 5.50 10.5

ランダムな数列

α 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95
平均値 1.03 1.05 1.08 1.12 1.15 1.19 1.23 1.28 1.33 1.39 1.45 1.53 1.62 1.72 1.85 2.01 2.23 2.56 3.15
ハッシュ関数: うまく全体にばらまくことのできる方法が必要
    → 均等なハッシュ値を生成

ハッシュ値の応用



アルゴリズムb 演習


課題提出〆切は次回の講義の開始時刻です。

課題12a

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai12a
提出ファイルHashOpenAddress.java
コメント欄:TestHashOpenAddress.javaにhashdata02.txtを入力として与えた時の出力
Bucket.java
授業で配布するプリントを参照して下さい。
HashOpenAddress.java
授業で配布するプリントを参照して下さい。
TestHashOpenAddress.java
授業で配布するプリントを参照して下さい。
hashdata01.txt
授業で配布するプリントを参照して下さい。
TestHashOpenAddress.javaの実行例
授業で配布するプリントを参照して下さい。
hashdata02.txt
授業で配布するプリントを参照して下さい。

課題12b

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai12b
提出ファイルHashOpenAddressRand.java
コメント欄:TestHashOpenAddressRand.javaにhashdata02.txtを入力として与えた時の出力

ハッシュ値の再計算に、ランダム数列を用いるように変更して下さい。

HashOpenAddressRand.javaへの変更点


TestHashOpenAddressRand.javaへの変更点


TestHashOpenAddressRand.javaの実行例
授業で配布するプリントを参照して下さい。