ハッシュ表の削除ができません

Question

以下のコードはハッシュ表に線形走査法でデータを挿入した後に、全ての削除するということをしています
↓挿入し、削除するデータです

22
alpha
beta
delta
art
mean
tau
minimum
average
sqsum
gamma 
eps
alpha
median
max
tau
eps
min
quadratic
variance
rat
rho
sum

以下のコードを実行した結果、

A[36]:art
A[37]:delta
A[38]:eps
A[39]:tau
A[40]:median
A[41]:rat
A[42]:rho
A[50]:sum
A[52]:average
A[65]:variance
A[84]:sqsum
A[85]:minimum
A[86]:quadratic
after delete:
A[24]:-1
A[29]:-1
A[30]:-1
A[33]:-1
A[34]:min
A[35]:-1
A[36]:-1
A[37]:-1
A[38]:-1
A[39]:-1
A[40]:-1
A[41]:rat
A[42]:rho
A[50]:-1
A[52]:-1
A[65]:-1
A[84]:-1
A[85]:-1
A[86]:quadratic

このようになってしまいました、ところどころの削除が出来ていないようなのですが、原因がわかりません。どなたか教えてください

#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* 文字列関数を扱えるようにする */
#define W 10 /* W = 文字列の最大長さ，ここでは 10 に設定 */
#define m 97 /* m = ハッシュ表のサイズ，ここでは 97 に設定 */
#define maxN 50 /* maxN = 扱う文字列の最大数，ここでは 50 に設定 */

struct cell
{
  char key[W+1]; unsigned int state:2; /* 構造体 cell の定義 */
};
int hash_search(struct cell *A, char *a); /* 関数 hash_search の宣言 */
void hash_insert(struct cell *A, char *a);
void hash_delete(struct cell *A, char *a);
int length(struct cell *A);
/* （他の関数も宣言すること） */
int main(void)
{
  struct cell A[m]; /* ハッシュ表を表すの配列 */
  int N; /* 数値の数は N */
  char word[W+1]; /* ファイルから読み込んだ文字列を格納する変数 */
  int h,y,i;/* 必要な変数を宣言 */
  char fname[128];
  FILE *fp; /* 入力ファイル */

for (h=0; h<m; h++){ A[h].state = 0;} /* ハッシュ表の初期化 */

    printf("input filename: "); /* ファイル名の入力を要求 */
    fgets(fname, sizeof(fname), stdin); /* ファイル名取得 */
    fname[strlen(fname)-1] = '\0';
    fflush(stdin);
    fp = fopen(fname, "r"); /* ファイルを読み込みモードで開く */
    fscanf(fp, "%d", &N); /* N をファイルから読み込む */
    if (N > maxN){
      printf("N is too large, setting N = %d\n", maxN);
      N = maxN;
    }
    for (i=0; i<N; i++){
      fscanf(fp, "%s", word); /*文字列をファイルから読み込み,wordに格納*/
      y = hash_search(A, word);
      if(y == -1)
        {
          hash_insert(A,word);
        }
    }
    fclose(fp);
for (h=0; h<m; h++){
      if(A[h].state == 1)
        {
          printf("A[%d]:%s\n", h, A[h].key);
        }
    }

    fp = fopen(fname, "r"); /* ファイルを再度読み込みモードで開く */
    fscanf(fp, "%d", &N); /* N をファイルから読み込む */
    if (N > maxN){N = maxN;}
    for (i=0; i<N; i++){
      fscanf(fp, "%s", word); /* 文字列をファイルから読み込み，wordに格納 */
      hash_delete(A, word);
    }
    fclose(fp);

 printf("after delete:\n");
    for (i=0; i<m; i++){
      if(A[i].state == 2)
        {
          printf("A[%d]:%s\n", i, A[i].key);
        }
      if(A[i].state == 1)
        {
          printf("A[%d]:%s\n", i, A[i].key);
        }
    }
    return 0;
}

int hash_val(char *a) /* 文字列はポインタ渡し */
{
  int h, i;
  h = 0; i = 0;
  while (a[i] != 0 && i < W) /* 文字の整数コードの和を計算 */
    {
      h = h + (int)a[i];
      i = i + 1;
    }
  h = h % m; /* m で割った余りを取る */
  return h;
}

int hash_search(struct cell *A, char *a)
{
  int x,i=0;
  x = hash_val(a);
  for(i=0; i<m; i++)
    {
      if(A[x].state == 1 && strcmp(A[x].key, a) == 0)
        {
          return x;
        }
      else if(A[x].state == 0)
        {
          return -1;
        }
      else
        {
          i = i+1;
          x = (x+i)%m;
        }
    }
  return 0;
}

void hash_insert(struct cell *A, char *a)
{
  int h;
  int x = -1;
  int i = 0;

  h = hash_val(a);

  while(x == -1 && i < m)
    {
      if(A[(h+i)%m].state != 1)
        {
          x = (h+i)%m;
        }

      else
        {
          i = i+1;
        }
    }
if(x == -1)
    {
      printf("error: out of space");
    }
  else
    {
      strcpy(A[x].key,a);
      A[x].state = 1;
    }
}

void hash_delete(struct cell *A, char *a)
{
  int x,h;

  x = hash_search(A,a);
  h = hash_val(a);
  if(x != -1)
    {
      strcpy(A[h].key,"-1");
      A[h].state = 2;
    }
}

Answer 1

わかりやすいのが

art
rat

ですね

このハッシュ関数ですと、順序に関係なく格納する文字が一緒ならば同じハッシュ値になります。

まぁ衝突自体は悪いことではありませんが

void hash_delete(struct cell *A, char *a)
{
int x,h;

x = hash_search(A,a);
h = hash_val(a);
if(x != -1)
{
strcpy(A[h].key,"-1");
A[h].state = 2;
}
}

にてhash_val("art")とhash_val("rat")が同じ値を返すのは不都合にみえませんか？

---

追記

int hash_search(struct cell *A, char *a)
{
  int x,i=0;
  x = hash_val(a);
  for(i=0; i<m; i++)
    {
      if()
      else if()
      else
        {
          i = i+1;
          x = (x+i)%m;
        }
    }
}

iとxの動きに注目
xが
hash_val(a) → hash_val(a)+1 → hash_val(a)+1+3 → hash_val(a)+1+3+5
と動きます。

Comments

[退会済みユーザー]

delete関数の部分を
x = hash_search(A,a);
if(x != -1)
{
strcpy(A[x].key,"-1");
A[x].state = 2;
}
のようにしてみたのですが、ratが残ってしまいます。これはasmさんの言う通り"art"と"rat"のハッシュ値の関係だと思うのですが、search関数の部分を少し工夫しないといけないということでしょうか？

[asm]

それですと
A[36]:art
A[37]:delta
A[38]:eps
(このへんはart,ratが一緒なのと同様に衝突している)
を、delta→art→epsの順番に削除しようとするとepsおよびartが削除されているため
hash_search("eps")の段階で失敗します。

残っている衝突データの再割当てを行わなければなりません。

アイデアとしてはおそらく2種類存在し
削除対象以後の衝突しているデータをすべて動かす方法
衝突している一番最後のデータを持ってきて穴埋めする方法
が思いつきます

---

追記
hash_searchで削除データはスキップしていましたね。すいません。
ここで挙げたのは多分違うので細かくデバッグしてみないとちょっと分からないです。

[asm]

問題点が判明したので回答しておきました。

[退会済みユーザー]

ご丁寧にありがとうございます！