ネタバレ注意！
member()があっさり 0 を返しすぎるのはすぐわかった。コメント欄の、ハッシュ表があふれることを否定しない表現「『要素の個数はハッシュ表のサイズBより小さいとする』という前提なので、『全部埋まっていたら』の意味にもよりますが」を読んでいて、前提条件に関わらず、同じ要素が複数回 insert()されるとハッシュ表があふれるのもわかった。さて 3つめは？ そして修正版は？
(member()相当の機能が欲しいだけなら)ソート済みの int配列にすれば…… < ハッシュテーブルじゃない！
意外にできる子とはいえ insert()と delete()でのメモリブロックの移動コストが気になる。一定サイズの配列(Chunk)をリストで管理したら……とかどうでもいい。
(元記事コメントから)> 削除済みマークを付ける
delete()で EMPTY(0)にせず DELETED(-1とか)にするのね。clear()するまで不良資産(DELETEDな要素)は貯まる一方、というわけでもなく、insert()するときに再利用できそうだ。
これ(削除済みマークを付ける)って FAじゃないのかなあ。
とりあえず、気付いた 2つの問題(delete()がからむと member()が不正確。重複要素であふれる)に対処した insert()はこう。EMPTYな要素より DELETEDな要素を優先して使用したくてフラグっぽい変数が増えてしまった。
/* 要素xをハッシュ表hに追加 */
void insert(int x) {
int i = hash(x);
int j = -1; /* i より優先して xを代入すべき位置 */
while (h[i] != EMPTY) {
if (h[i] == x) {
/* return; */
j = i;
break;
} else if (h[i] == DELETED) {
j = i;
}
i = (i + 1) % B;
}
h[j != -1 ? j : i] = x;
}
delete()の方も、EMPTYの代わりに DELETEDを代入するように変更する。
重複要素でハッシュ表があふれることがなくなったとはいっても、insert()と delete()を繰り返すうちに DELETEDな要素が増えていって EMPTY要素の数が 0になる可能性はないだろうか。EMPTY要素がなくなると、存在しない要素xを引数にした member()が無限ループに陥る。直観的にそういう可能性はない気がするけど……。
完全ハッシュ関数の状態からスタートしよう。ハッシュテーブルには最低でも一か所の穴(どの要素xも配置されない)がある。この位置を一時的にでもある要素で埋められればハッシュテーブルの全ての要素を DELETEDにできる。直接この穴に配置される要素xは存在しないからハッシュ値を衝突させて insert()で玉突き処理を行わせなければいけない。完全ハッシュ関数を二つの要素のハッシュ値だけが衝突するように変更してみよう。玉突きで穴を一つ塞ぐことができるが、完全ハッシュ関数ではなくなることで穴は二つ(以上)になっていた。以下略。
拍子抜け。要素を重複して格納せず、DELETEDな要素を再利用している限り、ハッシュ表が DELETEDであふれることはない。あっけなさすぎて自作自演臭がしてきた。
蛇足も蛇足の別バージョン。全然かわりばえしない。
/* 要素xをハッシュ表hに追加 */
void insert(int x) {
int i = hash(x);
int d = -1; /* hash(x)に一番近い DELETEDの位置 */
while (h[i] != EMPTY && h[i] != x) {
if (d == -1 && h[i] == DELETED) {
d = i;
h[d] = x;
}
i = (i + 1) % B;
}
if (d == -1) {
h[i] = x;
} else if (h[i] != EMPTY) {
h[i] = DELETED;
}
}
0 ≦ hash(x) ＜ B は暗黙の前提にしてるけど、3つ目のミスだったりして。
コメントも読めばわかるけど、ミスが 1。修正過程で陥りやすい落とし穴が 2つくらい、なんだってば。(でもわかりにくい)