オープンアドレス法(閉ハッシュ)を使って重複した値を格納したい

ハッシュ技法のオープンアドレス法で辞書構造を作る勉強をしており、1〜3までの整数値を5回連続で配列を用いた(閉ハッシュの)辞書構造に格納し、その格納した配列の位置と値をそれぞれ表示させたいと思っております。
1,2,3,1,2,3…1,2,3の計15個をそれぞれが格納されるハッシュ値(格納される位置)と共に表示させるといった具合です。
そこで以下のようなdict class()とlist class()のそれぞれのメソッドを用いて、プログラムを書いて実行したところ、実行結果は
1:1 2:2 3:3(:の左が格納位置)となって全部で15件と表示され、1,2,3のハッシュ値が5回重複しているにも関わらずそれぞれ埋まってる筈の1,2,3の格納位置にぶち込まれてしまいました…
私の浅学の知識では、5回重複する1,2,3の値は再ハッシュされて別の格納空間へ移動する筈だという認識でした。

何故この様になってしまうのでしょうか？再ハッシュをして値を別の格納空間に入れるにはどうすれば良いでしょうか？

ご教授頂ければ幸いです。

プログラム


class dict { // 配列を用いた閉ハッシュ辞書構造
static final int HASHBASE=101; // 省略時最大セル数
static final int UNUSED=0; // 未使用
static final int USING=1; // 使用中
static final int DELETED=2; // 削除
int N; // 要素数 0<= N <= MAX
int[] value; // ハッシュ空間
int[] stat ; // 要素状態
dict() { // コンストラクタ
int k ;
N=0 ;
value = new int[HASHBASE] ;
stat = new int[HASHBASE] ;
for (k=0;k<HASHBASE; k++ )
stat[k]=UNUSED ;
}
int hash( int v ) { return v % HASHBASE ; }

void print() { // 表示
int k ;
for (k=0; k<HASHBASE; k++)
if (stat[k]==USING)
System.out.print( k + ":" + value[k] + " ");
System.out.println() ;
}


void insert( int val ) { // 挿入 O(1), 最悪 O(N)
int k, k1 ;
k=hash( val ) ;
for (k1=0; k1 < HASHBASE; k1++) {
if ((stat[(k+k1)%HASHBASE]==USING) &&
(value[(k+k1)%HASHBASE] == val)) {
return ; // ダブリ
} else if (stat[(k+k1)%HASHBASE]!=USING) {
value[(k+k1)%HASHBASE] = val ;
stat[(k+k1)%HASHBASE] = USING ;
N++ ;
return ;
}
}
return ; // 空きが無かった
}
int count() { return N ; }





}



class list { // 配列を用いたリスト構
static final int MAX=100;
int N; // 要素数
int[] value; // 整数の配列
list() { // コンストラクタ
N=0 ; value=new int[MAX];
}

int insert (int k, int val ) { // 位置 k の直前に val を挿入
int k1 ;
for (k1=N-1; k1>=k; k1--) {
value[k1+1]=value[k1] ; // 移動
}
value[k]=val ;
N++;
return( k ) ;
}



void print() { // 表示
int k ;
for (int k1=0; k1<N; k1++)
System.out.print( value[k1] + " " ) ;
System.out.println() ;
}




}



public class renshu01 {//メインクラス

	public static void main(String[] args) {
		Scanner stdin = new Scanner( System.in ) ;
		dict S = new dict() ;
		int val = 0;
		int t,k;
		int N=0;
	for(k=0;k<5;k++) {
		for (t=0;t<3;t++) {
			val=val+1;
			S.insert( val ) ;;
			N++;
			}
       val=0;
	}
	S.print();
	

		System.out.println("全部で" + N + "件") ;



	}

}

実行結果

1:1 2:2 3:3 
全部で15件

＊オープンアドレス法のメソッドに関してなのですが、これはとある教材を見よう見真似でただ書き写しただけです…

行動規範の内容に同意します

回答1件

ベストアンサー

1:1 2:2 3:3(:の左が格納位置)となって全部で15件と表示され、

15件と表示されるのはNがただのループ数を数えているだけだからではないですか？

1,2,3のハッシュ値が5回重複しているにも関わらずそれぞれ埋まってる筈の1,2,3の格納位置にぶち込まれてしまいました…

私はこの挙動は正しく思います。
今回のHASHBASEは101ですから、以下のように循環します。

hash(1) == 1
hash(2) == 2
...
hash(100) == 100
hash(101) == 0
hash(102) == 1

ハッシュの衝突というのはこの例でいえば、1と102の時などを指します。
1と1も同じハッシュ値になりますが、元の値が同じ値ですから、これはハッシュの衝突とはいいません。

2回目の「1」を記録するときに既に「1」は入っていますから、何もしません。これは以下の実装箇所がそうなっていますよね。

if ((stat[(k+k1)%HASHBASE]==USING) &&
(value[(k+k1)%HASHBASE] == val)) {
return ; // ダブリ
}

そうなると、2個目の「1」は記録されないので、データ上は1,2,3の3つしか入ってない形になるでしょう。
もし、データ構造として2個の「1」を記録したいのであれば、それはちゃんとそのように実装しなければなりません。
また、ハッシュ値の衝突がおきるような値、1と102、もしくは、102と1の順で入れた場合にどのようになるか観察するのが良いかと思います。

投稿2021/07/08 22:18