アルゴリズム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
ハッシュ関数: うまく全体にばらまくことのできる方法が必要
    → 均等なハッシュ値を生成

ハッシュ値の応用



アルゴリズムA 演習


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

課題12a

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai12a
提出ファイルHashOpenAddress.java
コメント欄:TestHashOpenAddress.javaにhashdata02.txtを入力として与えた時の出力
Bucket.java
public class Bucket {
    String key;
    Object data;
    public Bucket(String k,Object d) { key=k; data=d; }
    public String toString() {
	return "[" + key + "," + data + "]";
    }
}
HashOpenAddress.java
授業で配布するプリントを参照して下さい。
TestHashOpenAddress.java
import java.util.*;
public class TestHashOpenAddress {
    static class ExamMark {
	int english;
	int math;
	int physics;
	int chemistry;
	public ExamMark(int e,int m,int p,int c) {
	    english = e; math = m; physics = p; chemistry= c;
	}
	public String toString() {
	    return "["+english+","+math+","+physics+","+chemistry+"]";
	}
    }
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	HashOpenAddress hoa = new HashOpenAddress(11);
	while (sc.hasNext()) {
	    String line = sc.nextLine();
	    Scanner scLine = new Scanner(line);
	    String cmd = scLine.next();
	    if (cmd.equals("exit")) {
		break;
	    } else if (cmd.equals("insert")) {
		String id = scLine.next();
		int english = scLine.nextInt();
		int math = scLine.nextInt();
		int physics = scLine.nextInt();
		int chemistry = scLine.nextInt();
		hoa.insert(id, new ExamMark(english,math,physics,chemistry));
	    } else if (cmd.equals("find")) {
		String id =scLine.next();
		System.out.println(hoa.find(id));
	    } else if (cmd.equals("delete")) {
		String id =scLine.next();
		System.out.println(hoa.delete(id));
	    } else if (cmd.equals("show")) {
		System.out.println(hoa);
	    }
	}
    }
}
hashdata01.txt
insert a0000 89 90 68 53
insert a0008 73 80 52 69
insert a0015 70 92 55 78
insert a0017 68 73 82 82
insert a0026 53 89 82 76
insert a0027 85 72 63 68
insert a0033 85 72 63 68
show
delete a0017
find a0026
find a0006
show
exit
TestHashOpenAddress.javaの実行例
% javac TestHashOpenAddress.java
% java TestHashOpenAddress < hashdata01.txt
[                              ←showの出力
0:0[a0008,[73,80,52,69]]
1:0[a0017,[68,73,82,82]]
2:0[a0026,[53,89,82,76]]
3:3[a0000,[89,90,68,53]]
4:1[a0027,[85,72,63,68]]
5:null
6:null
7:null
8:null
9:9[a0015,[70,92,55,78]]
10:9[a0033,[85,72,63,68]]
]
true                           ←"delete a0017"の出力
[53,89,82,76]                  ←"find a0026"の出力
null                           ←"find a0006"の出力
[                              ←showの出力
0:0[a0008,[73,80,52,69]]
1:[null,[68,73,82,82]]         ←消去された項目のkeyはnullに変更される
2:0[a0026,[53,89,82,76]]
3:3[a0000,[89,90,68,53]]
4:1[a0027,[85,72,63,68]]
5:null
6:null
7:null
8:null
9:9[a0015,[70,92,55,78]]
10:9[a0033,[85,72,63,68]]
]
hashdata02.txt
insert b0007 89 90 68 53
insert b0015 73 80 52 69
insert b0016 70 92 55 78
insert b0024 68 73 82 82
insert b0033 53 89 82 76
insert b0042 85 72 63 68
insert b0051 85 72 63 68
show
delete b0042
find b0042
insert b0060 81 78 65 73
find b0060
show
exit

課題12b

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

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

HashOpenAddressRand.javaへの変更点


TestHashOpenAddressRand.javaへの変更点
*** TestHashOpenAddress.java	Fri Apr 25 18:49:28 2008
--- TestHashOpenAddressRand.java	Fri Apr 25 18:49:53 2008
***************
*** 1,5 ****
  import java.util.*;
! public class TestHashOpenAddress {
      static class ExamMark {
  	int english;
  	int math;
--- 1,5 ----
  import java.util.*;
! public class TestHashOpenAddressRand {
      static class ExamMark {
  	int english;
  	int math;
***************
*** 14,20 ****
      }
      public static void main(String[] args) {
  	Scanner sc = new Scanner(System.in);
! 	HashOpenAddress hoa = new HashOpenAddress(11);
  	while (sc.hasNext()) {
  	    String line = sc.nextLine();
  	    Scanner scLine = new Scanner(line);
--- 14,20 ----
      }
      public static void main(String[] args) {
  	Scanner sc = new Scanner(System.in);
! 	HashOpenAddressRand hoa = new HashOpenAddressRand(11);
  	while (sc.hasNext()) {
  	    String line = sc.nextLine();
  	    Scanner scLine = new Scanner(line);


TestHashOpenAddressRand.javaの実行例
$ javac TestHashOpenAddressRand.java HashOpenAddressRand.java
$ java TestHashOpenAddressRand <hashdata01.txt
[
0:0[a0008,[73,80,52,69]]
1:0[a0017,[68,73,82,82]]
2:1[a0027,[85,72,63,68]]
3:3[a0000,[89,90,68,53]]
4:0[a0026,[53,89,82,76]]
5:null
6:null
7:null
8:null
9:9[a0015,[70,92,55,78]]
10:9[a0033,[85,72,63,68]]
]
true
[53,89,82,76]
null
[
0:0[a0008,[73,80,52,69]]
1:[null,[68,73,82,82]]
2:1[a0027,[85,72,63,68]]
3:3[a0000,[89,90,68,53]]
4:0[a0026,[53,89,82,76]]
5:null
6:null
7:null
8:null
9:9[a0015,[70,92,55,78]]
10:9[a0033,[85,72,63,68]]
]