オープンハッシュ法

[kew]

オープンハッシュ法によって2次元座標の一点を表現したデータを格納していくプログラムなのですが、衝突数をうまく表示させることができません。
1つ目のデータを格納するときの衝突数は0で正しい結果が出るのですが、2つ目ですでに衝突数が1と表示されてしまいます。試しにハッシュ値をそれぞれのデータに対して表示させてみたところ、1つ目と2つ目のデータのハッシュ値は全く異なるものになっており、衝突が起こることはありえないと思うのですが、実行結果を見ると衝突が起こっていることになっています。
下記のプログラムにおいて、衝突数はint insert_hash(POINT p)という関数のcountという変数で処理しています。本来このcountという変数は再ハッシュした回数を表していますが、再ハッシュした回数＝衝突数と見ても問題ないと考えこのようにしました。また、一度の衝突もなく登録に成功した場合はcount=0として出力するようにしています。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define B 30011
#define empty 0
#define occupied 1
#define deleted 2

typedef struct _point{
   int x;
   int y;
}POINT;

typedef struct h_array{
  POINT data;
  int status;
}HARRAY;

HARRAY H[B];

void init_hash(){
  int i;
  for(i=0;i<B;i++){
    H[i].status=empty;
  }
}

int h_1(POINT p,int count){
  return p.x*p.y*count%B;
}

int h_2(POINT p,int count){
  return (p.x+p.y)*count%B;
}

int search_hash(POINT p){
  int number;
  int b,init_b;
  number=0;
  b=h_1(p,number);
  init_b=b;
  do{
    if(H[b].status==occupied){
      if(H[b].data.x==p.x && H[b].data.y==p.y)return number+1;
    }
    else if(H[b].status==empty){
      return (number+1)*-1;
    }
    number=number+1;b=h_1(p,number);
  }while(b!=init_b);

  return 0;
}

int search(POINT p){
  int b,init_b;
  int count;
  count=0;
  b=h_1(p,count);
  init_b=b;
  do{
    if(H[b].status==occupied){
      if(H[b].data.x==p.x && H[b].data.y==p.y)return-1;
    }
    else return 1;
  }while(b!=init_b);
  return 0;
}

int delete_hash(POINT p){
  int count;
  int b,init_b;
  count=0;
  b=h_1(p,count);
  init_b=b;
  do{
    if(H[b].status==occupied){
      if(H[b].data.x==p.x && H[b].data.y==p.y){
	H[b].status=deleted;
	return 1;
      }
    }
    count=count+1;b=h_1(p,count);
  }while(b!=init_b);
  return -1;
}

int insert_hash(POINT p){
  int count;
  int b,init_b;
  b=h_1(p,count);
  init_b=b;
  if(search(p)==-1)return -1;
  do{
    if(H[b].status==empty || H[b].status==deleted){
      H[b].data.x=p.x;
      H[b].data.y=p.y;
      H[b].status=occupied; 
      return count;
    }else
      {
	count=count+1;b=h_1(p,count);
	printf("%d hash\n",b);
      }
  }while(b!=init_b);
  if(b>B)return -2;
  return 0;
}

int main(void){
  int i,N;
  POINT p;
  scanf("%d",&N);

  init_hash();

  srand((unsigned)time(NULL));

  for(i=0;i<N;i++){
    p.x=rand()%500;
    p.y=rand()%500;
    if(p.x+p.y<500){
      printf("%d\n",insert_hash(p));
    }
  }
  return 0;
}
  
  
  

[みけCAT]

コード:

int h_1(POINT p,int count){
  return p.x*p.y*count%B;
}

コード:

int insert_hash(POINT p){
  int count;
  int b,init_b;
  b=h_1(p,count);

未初期化の自動変数countの値が使用されていますが、この値は不定であり、未定義動作になるので、やってはいけません。

[kew]

ありがとうございます！
自分で考えてみて、ハッシュ関数h_1によって、衝突が必ず起こってしまうということがわかりました。改善前のハッシュ関数ではcountの値をあたえられた2次元平面座標のx座標y座標の値にかけてしまっていたがために、最初のデータを登録するとき以外は、必ず一度ハッシュ値が0になってしまい、そのことにより衝突が起こってしまっていることがわかりました。上記の部分を改善してみた結果、データを順に登録して行った際、最初の方に登録されるデータによる衝突回数は0となり、正しい結果が得られるようになったと思われます。
しかし、今度は比較的大きな数字をscanfによって入力した際 Bus Error:10というのが出るようになってしまいました。これは、データの個数が大きすぎる時に起こるものなのでしょうか？また、解決策を教えていただけると幸いです。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define B 30011
#define empty 0
#define occupied 1
#define deleted 2

typedef struct _point{
   int x;
   int y;
}POINT;

typedef struct h_array{
  POINT data;
  int status;
}HARRAY;

HARRAY H[B];

void init_hash(){
  int i;
  for(i=0;i<B;i++){
    H[i].status=empty;
  }
}

int h_1(POINT p,int count){
  return p.x*p.y+count%B;
}

int h_2(POINT p,int count){
  return p.x*(p.y+count)%B;
}

int search_hash(POINT p){
  int number;
  int b,init_b;
  number=0;
  b=h_1(p,number);
  init_b=b;
  do{
    if(H[b].status==occupied){
      if(H[b].data.x==p.x && H[b].data.y==p.y)return number+1;
    }
    else if(H[b].status==empty){
      return (number+1)*-1;
    }
    number=number+1;b=h_1(p,number);
  }while(b!=init_b);
  return 0;
}

int search(POINT p){
  int b,init_b;
  int count;
  count=0;
  b=h_1(p,count);
  init_b=b;
  do{
    if(H[b].status==occupied){
      if(H[b].data.x==p.x && H[b].data.y==p.y)return-1;
    }
  }while(b!=init_b);
  return 1; 
}

int delete_hash(POINT p){
  int count;
  int b,init_b;
  count=0;
  b=h_1(p,count);
  init_b=b;
  do{
    if(H[b].status==occupied){
      if(H[b].data.x==p.x && H[b].data.y==p.y){
	H[b].status=deleted;
	return 1;
      }
    }
    count=count+1;b=h_1(p,count);
  }while(b!=init_b);
  return -1;
}

int insert_hash(POINT p){
  int count;
  int b,init_b;
  b=h_1(p,count);
  init_b=b;
  if(search(p)==-1)return -1;
  if(search(p)==1){
    do{
    if(H[b].status==empty || H[b].status==deleted){
      H[b].data.x=p.x;
      H[b].data.y=p.y;
      H[b].status=occupied;
      return count;
    }
    count=count+1;b=h_1(p,count);
    if(b>B)return -2;
  }while(b!=init_b);
  }
  return 0;
}

int main(void){
  int i,N;
  POINT p;
  scanf("%d",&N);
  printf("\n");
  init_hash();


  srand((unsigned)time(NULL));

  for(i=0;i<N;i++){
    p.x=rand()%500;
    p.y=rand()%500;
    if(p.x+p.y<500){
      printf("crash=%d\n",insert_hash(p));
      printf("\n");
    }
  }
  return 0;
}
  
  
  

[kew]

lldbにてエラー箇所を探してみたところ62行目で起こっているようです...

[みけCAT]

例えばp.x=250、p.y=249だと、p.x+p.y<500は真なのでinsert_hashが呼び出され、そこからsearch関数が呼び出されます。
このときint型に格納できる範囲が十分大きいとするとh_1関数の戻り値は62250以上になりますが、
Hの要素数は30011しかないので、62行目で範囲外へのアクセスが発生し、未定義動作になります。
Nが大きくなると試行回数が増えるので、範囲外アクセスを発生させるパラメータが生成される確率も上がるでしょう。
改善するには、範囲外アクセスを発生させないようにチェックと分岐を入れるか、h_1関数の値域を制限するといいでしょう。