ハッシュ実装の話

次の内部ハッシュの実装（C言語のプログラムの一部）には誤りがある。誤っている部分を正しく修正せよ。ただし、Bはハッシュ表のサイズ、hashはハッシュ関数である。ハッシュ表の要素は正の整数とし、要素の個数はハッシュ表のサイズBより小さいとする。

本当はむずかしいハッシュテーブル - sumiiの日記

ということで勉強中の身なので何が間違っているかをコードレビューしてみました。

一つ目はハッシュ値が重なった値が追加された後に、その前の要素がdeleteで削除されると追加された値がmemberで検出できなくなります。

二つ目はinsertやmemberにおいて、ハッシュテーブルhに全て値が格納された状態で無限ループになってしまいます。またdeleteに対しても存在しない値を渡すと無限ループです。

三つ目がちょっとわからないですね。元記事の話では三つバグがあるらしいのですが・・・。

で、とりあえず分かる範囲でこれらを不具合を修正してみました。また、なるべく元のコードを大きく変更しないように修正しました。

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

// 空の要素を表す定数
#define EMPTY 0

// 削除済みを表す定数
#define DELETE -1

// 少なめに設定しておく
#define B 4
int h[B];

// とりあえず常に重なるように0を返しておく
unsigned int hash(int i) {
    // i使わないと警告出るので無理やりｗ
    return i-i;
}

/* ハッシュ表hを空にする */
void clear() {
  int i;
  for (i = 0; i < B; i ++) {
    h[i] = EMPTY;
  }
}

/* 要素xをハッシュ表hに追加 */
void insert(int x) {
  int i = hash(x);
  int j = i;
  while (h[i] != EMPTY && h[i] != DELETE) {
    i = (i + 1) % B;
    if ( i == j ) return;
  }
  h[i] = x;
}

/* 要素xをハッシュ表hから削除（xがhにない場合は考えなくて良い） */
void delete(int x) {
  int i = hash(x);
  int j = i;
  while (h[i] != x) {
    i = (i + 1) % B;
    if ( i == j ) return;
  }
  h[i] = DELETE;
}

/* 要素xがハッシュ表hにあれば1を、なければ0を返す */
int member(int x) {
  int i = hash(x);
  int j = i;
  while (h[i] != x) {
    if (h[i] == EMPTY) return 0;
    i = (i + 1) % B;
    if ( i == j ) return 0;
  }
  return 1;
}

int main (void) {
    insert(1); // 1を格納
    insert(2); // 2を格納
    insert(3); // 3を格納
    delete(2); // 2を削除
    delete(9); // 存在しない値を削除してみる
    insert(4); // 4を格納
    insert(5); // 5を格納
    insert(6); // 6はハッシュテーブル満杯なので格納されず
    
    printf("%d\n",member(1)); // 1
    printf("%d\n",member(2)); // 0
    printf("%d\n",member(3)); // 1
    printf("%d\n",member(4)); // 1
    printf("%d\n",member(5)); // 1
    printf("%d\n",member(6)); // 0
    
    {
        int i;
        for(i=0;i<B;i++) {
            printf("%d ",h[i]);
        }
    }
    
    return 0;
}

無限ループ回避の策としてはとりあえず最初の要素をjに保存しておいてj==iになったら先頭に戻ってきたとみなし、ループを抜けるようにしました。

削除でおかしくなるバグに関してはEMPTYとは別にDELETEを用意し、それを格納させるようにしています。これによってmemberでは正しく値を取得することができるようになりました。またinsertはDELETEも対象に入れることで、再利用されるようにもしてあります。

たぶんこれでうまくいってるような気はします。間違ってる可能性も十二分にありますが・・・。