ハッシュ法

ハッシュ表：バケットの個数が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 で同じとなる。→衝突

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

% 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]]
]

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

*** java/HashOpenAddress.java	Sun Sep  5 16:27:40 2021
--- java/HashOpenAddressRand.java	Sun Sep  5 16:27:40 2021
***************
*** 1,13 ****
! public class HashOpenAddress {
      Bucket[] table;
      int nElement;
      // データが登録されていない場合はBucketにnullが入っている
      // 登録後で消去されたBucketにはkeyにnullが入っている
  
!     public HashOpenAddress() { this(53); }
!     public HashOpenAddress(int n) {
  	nElement = 0;
  	table = new Bucket[n];
      }
      private int hash(String key) {
  	int sum=0;
--- 1,24 ----
! import java.util.*;
! public class HashOpenAddressRand {
      Bucket[] table;
      int nElement;
+     int[] rt;			// 再ハッシュ計算につかう表
      // データが登録されていない場合はBucketにnullが入っている
      // 登録後で消去されたBucketにはkeyにnullが入っている
  
!     public HashOpenAddressRand() { this(53); }
!     public HashOpenAddressRand(int n) {
  	nElement = 0;
  	table = new Bucket[n];
+ 	rt = new int[n];	// 再ハッシュ表の初期化
+ 	for (int i=0; i<n; i++) rt[i]=i;
+ 	Random rand = new Random(12345);
+ 	for (int i=1; i<n; i++) { // rt[0] should be 0
+ 	    int j = rand.nextInt(n-1)+1;
+ 	    int tmp = rt[i];
+ 	    rt[i] = rt[j];
+ 	    rt[j] = tmp;
+ 	}
      }
      private int hash(String key) {
  	int sum=0;
***************
*** 15,22 ****
  	    sum += (int) key.charAt(i);
  	return sum % table.length;
      }
!     private int rehash(int h) {
! 	return (h+1) % table.length;
      }
      public Object find(String key) {
  	int h = hash(key);
--- 26,33 ----
  	    sum += (int) key.charAt(i);
  	return sum % table.length;
      }
!     private int rehash(int h,int count) {
! 	return (h-rt[count-1]+rt[count]+table.length) % table.length;
      }
      public Object find(String key) {
  	int h = hash(key);
***************
*** 25,31 ****
  	while (b != null && count <table.length) {
  	    if (key.equals(b.key)) return b.data;
  	    count++;
! 	    h = rehash(h);
  	    b = table[h];
  	}
  	return null;
--- 36,42 ----
  	while (b != null && count <table.length) {
  	    if (key.equals(b.key)) return b.data;
  	    count++;
! 	    h = rehash(h,count);
  	    b = table[h];
  	}
  	return null;
***************
*** 39,45 ****
  	while (b != null && count <table.length) {
  	    if (b.key == null) break;
  	    count++;
! 	    h = rehash(h);
  	    b = table[h];
  	}
  	if (count >= table.length) throw new RuntimeException("table overflow");
--- 50,56 ----
  	while (b != null && count <table.length) {
  	    if (b.key == null) break;
  	    count++;
! 	    h = rehash(h,count);
  	    b = table[h];
  	}
  	if (count >= table.length) throw new RuntimeException("table overflow");
***************
*** 58,64 ****
  		return true;
  	    }
  	    count++;
! 	    h = rehash(h);
  	    b = table[h];
  	}
  	return false;
--- 69,75 ----
  		return true;
  	    }
  	    count++;
! 	    h = rehash(h,count);
  	    b = table[h];
  	}
  	return false;

*** java/TestHashOpenAddress.java	Sun Sep  5 16:27:45 2021
--- java/TestHashOpenAddressRand.java	Sun Sep  5 16:27:45 2021
***************
*** 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);

$ 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]]
]