はじめての C
C programming note*1
ハッシュ関数を 使えば、1回の 照合で 探索 search が 可能のように 思われますが、実は データが たびたび 更新されると、照合の回数が 増えてしまいます。
その場合でも、ハッシュを 使うことで、平均すれば 2, 3回の 照合で 検索は 可能に なります。
ただし 経験則で、データを 入れる 配列の数が、総データ数の 2倍以上であれば、探索は ほぼ 2回以下で 収まることが わかっています。(注)
(注) ブルーバックス版 「パソコンなんでも小事典」(isbn:4062572427) p126-127)
ハッシュは アルゴリズムですから、目的に よって そのデータ構造が 少しずつ 違ってきます。
例えば K&R 2nd の 例では、構造体を 使って、リンクリストを つくっています。
struct nlist {
struct nlist *next;
char *name;
char *defn;
};また、データを 格納して そのハッシュ値を 決定する install 間数では、そのための リンクリスト つくっていきます。
install 関数の 中を 見ていくと、
1. lookup 関数で、データに name が 含まれているかを チェック。
2. なければ、malloc で nlist 分の メモリを 確保。
3. strdup 関数を 使って name の コピーを 作成し、nlist に 格納。
4. name から ハッシュ値を 求めて、配列ポインタ hashtab の 添字とし、nlist を つないでいく。
5. 1 へ 戻って、name が 含まれているときは、一応 前の defn 定義分を free で 消去。
6. (新しい) defn の コピーを つくって nlist に 格納。
7. リスト作成に 成功した 場合には、name と defn の 格納された nlist の ポインタを 返す。
(なお、ここで 使われている strdup は 標準ライブラリ関数では なく、K&R 2nd p173 に あるものです)
hashtable から name を 削除する undef 関数については、次の page に 載っています。
http://users.powernet.co.uk/eton/kandr2/krx605.html
最初の 回答例のほうが やさしいので、参考のため 写してみましょう。
int undef(char *name)
{
struct nlist *np1;
struct nlist *np2; if )((np1 = lookup(name))( == NULL) /* name not found */
return 1;
for (np1 = np2 = hashtab[hash(name)]; np1 != NULL; np2 = np1, np1 = np1->next) {
if (strcmp(name, np1->name) == 0) { /* name found */
/* remove name from list */
if (np1 == np2)
hashtab[hash(name)] = np1->next;
else
np2->next = np1->next;
/* free memory */
free(np1->name);
free(np1->defn);
free(np1);
return 0;
}
}
return 1;
}
(;_;)
*1:「作ってわかる Cプログラミング」
