図1: 配列
st_table
メソッドテーブルやインスタンス変数テーブルとしてst_tableは既に何度か登
場してきた。本章ではまずこのst_tableについて詳しい作りを見ていくことに
しよう。
st_tableはハッシュテーブルだということはもう言った。ではハッシュ
テーブルは何かと言うと一対一対応を記録するデータ構造である。一対一の対
応とは例えば変数名とその値、関数名とその実体、などだ。
ただしもちろんハッシュテーブル以外でも一対一対応は表せる。 例えば次のような構造体のリストを使ってもいい。
struct entry {
ID key;
VALUE val;
struct entry *next; /* 次のエントリを指す */
};
しかしこの方法は「遅い」。もしリストが1000個あったら最悪1000回リンクを たぐって探さなければならない。つまり要素の個数に比例して検索時間が長く なってしまう。これはまずい、ということで古来からいろいろな高速化手法が 考えられてきた。ハッシュテーブルはそのような手法の一つである。つまりハッ シュテーブルは「それでないとダメ」というよりは高速化できるというところ に意義がある。
さて、それでst_tableを見ていくわけだが、このライブラリは
まつもとさんのオリジナルではなく、
▼st.cのクレジット
1 /* This is a public domain general purpose hash table package
written by Peter Moore @ UCB. */
(st.c)
……だ、そうである。
ちなみにGoogleで見付けた他のバージョンのコメントからすると
st_tableはSTring TABLEの略らしい。しかしgeneral purposeという文面と
stringではまるきり矛盾していると思うのだが……。
ハッシュテーブルの考えかたはこうだ。まず n 個の長さを持つ配列 を用意しておく。例えば n=64 としよう（図1）。
図1: 配列
そしてキーから0〜 n-1 （0〜63）の範囲の整数 i を得る関数 f を用意す る。この f をハッシュ関数と言う。 f は同じキーに対しては常に同じ i を返さなくてはいけない。例えば キーが正の整数だけと仮定できるなら、キーを64で割れば余りは必ず0〜63に なるはずだ。だからこの計算式は関数 f になりうる。
対応関係を記録するときは、キーに対して f を呼んで i を求め、用意した配列の インデックス i に値を入れればよい（図2）。 ようするに、配列へのインデックスアクセスなら超高速なのだから、キーをな んとかして整数に変換してしまおうというのがアイデアの根幹だ。
図2: 配列にセット
しかし世の中そうそううまい話はないわけで、このアイデアには致命的
な問題がある。 n は今64しかないから、64個以上の対応関係を記録しようと
したら絶対に i が重複してしまう。64個未満だとしても別々のキーに対して同
じインデックスが割り振られてしまうかもしれない。例えば先程のハッシュ関数
「key % 64」の場合だと、キーが65でも129でもハッシュ値は1である。これを
「ハッシュ値の衝突（collision）」と言う。衝突を解決する方法は何種類か
存在する。
例えば衝突が起こったらその次の要素に入れる方法がある。 これは開番地法と言う（図3）。
図3: 開番地法
他に、配列をそのまま使うのではなくて、配列の要素一つ一つをリンクリ
ストへのポインタにする方法もある。そして衝突が起こったらどんどん
リストをつなげていく。こちらは連鎖法と言う（図4）。
st_tableはこの連鎖法を採用している。
図4: 連鎖法
ところで、もし使う可能性のあるキーの集合が事前にわかっていたとしたら
「絶対に衝突の起こらないハッシュ関数」を考えることもできるかもしれない。
そのような関数を「完全ハッシュ関数」と言う。そして実は任意の文字列の集
合に対してこの完全ハッシュ関数を作ってくれるツールがある。
GNU gperfがソレだ。rubyのパーサの実装でも実際にこれを使っているの
だが……まだその話をする時期ではない。これについては第二部で続きを話す
ことにしよう。
ここからは実際のソースコードに入る。序章で書いたとおり、
データとコードがあるならまずデータから読んだほうがいい。
以下にst_tableが使うデータ型を示す。
▼st_table
9 typedef struct st_table st_table;
16 struct st_table {
17 struct st_hash_type *type;
18 int num_bins; /* スロットの数 */
19 int num_entries; /* 格納している要素の総数*/
20 struct st_table_entry **bins; /* スロット */
21 };
(st.h)
▼struct st_table_entry
16 struct st_table_entry {
17 unsigned int hash;
18 char *key;
19 char *record;
20 st_table_entry *next;
21 };
(st.c)
st_tableがメインのテーブルの構造で、st_table_entryが値一つを格納する
ホルダである。st_table_entryにはnextという名前のメンバがあるのでこれは
当然リンクリストだ。連鎖法の連鎖の部分である。st_hash_typeという型が使
われているが、これはこの後で説明するのでまずはその他の部分について
図5と見比べつつ役割を確認していただきたい。
図5: st_tableのデータ構造
ではst_hash_typeについて註釈する。
▼struct st_hash_type
11 struct st_hash_type {
12 int (*compare)(); /* 比較関数 */
13 int (*hash)(); /* ハッシュ関数 */
14 };
(st.h)
なにぶんまだ第3章なのでやや丁寧に見ていこう。
int (*compare)()
の部分はもちろん「intを返す関数へのポインタ」型のメンバcompare、
を表している。hashも同様だ。こういう変数には次のように代入し、
int
great_function(int n)
{
/* ToDo: なにかすごいことをする */
return n;
}
{
int (*f)();
f = great_function;
次のように呼び出す。
(*f)(7);
}
ここでst_hash_typeの解説に戻ろう。hash compareと二つあるメンバの
うち、hashが前述のハッシュ関数 f を表している。
一方のcompareはキーが同じであるかどうかを判定する関数である。連鎖法
では同じハッシュ値 n のところに複数の要素が入ることがあるのだった。そ
の要素のどれが本当に求めるものかを知るためには、今度は完全に信用できる
比較関数が必要になる。そのための関数がcompareだ。
このst_hash_typeはなかなかうまい汎用化技法である。ハッシュテーブル自
体は格納するキーがどんな型なのか特定できない。例えばrubyでは
st_tableのキーとしてID・char*・VALUEを使っているのだが、それぞ
れに全く同じ仕組みのハッシュを書いてやるのはいくらなんでもバカらしい。
キーの型が違ったところで変化するのはハッシュ関数などごく一部だけで、メ
モリ割り当てや衝突検出など大部分のコードは同じだからだ。そこで型によっ
て実装が違う部分「だけ」を関数としてくくりだし、それへのポインタを受け
取って使うことにするのである。これによってコードの大部分を占めるハッシュ
テーブル自体の実装を使いまわすことができる。
オブジェクト指向言語だとそもそもオブジェクトに手続きをくっつけて持ち運 ぶことができるのでこういう仕組みは必要ない。あるいは、こういう仕組みを 言語の機能として組み込んでいる、というほうが正しいか。
st_hash_typeの例
st_hash_typeのような構造体を使う方法は確かに汎用化としてはうまいのだ
が、実際にどんなコードを通るのかということは逆にわかりにくくなる。
hashやcompareにどういう関数が使われるのか見てみないとどうも実感が
つかめない。それには前章でも登場していたst_init_numtable()を見てみる
といいだろう。これは整数型キーのためのテーブルを作る関数だ。
▼st_init_numtable()
182 st_table*
183 st_init_numtable()
184 {
185 return st_init_table(&type_numhash);
186 }
(st.c)
st_init_table()がテーブルのメモリを割り当ててたりする関数で、
type_numhashがst_hash_type（メンバ名で言うとtype）になる。
そのtype_numhashはと言うと……
▼type_numhash
37 static struct st_hash_type type_numhash = {
38 numcmp,
39 numhash,
40 };
552 static int
553 numcmp(x, y)
554 long x, y;
555 {
556 return x != y;
557 }
559 static int
560 numhash(n)
561 long n;
562 {
563 return n;
564 }
(st.c)
とても単純だ。rubyのインタプリタで使うテーブルは
だいたいこのtype_numhashを使っている。
st_lookup()
では今度はこの構造を使う関数を見ていこう。最初は検索用の関数から見てい
くのがいい。ハッシュテーブルを検索する関数st_lookup()を以下に示す。
▼st_lookup()
247 int
248 st_lookup(table, key, value)
249 st_table *table;
250 register char *key;
251 char **value;
252 {
253 unsigned int hash_val, bin_pos;
254 register st_table_entry *ptr;
255
256 hash_val = do_hash(key, table);
257 FIND_ENTRY(table, ptr, hash_val, bin_pos);
258
259 if (ptr == 0) {
260 return 0;
261 }
262 else {
263 if (value != 0) *value = ptr->record;
264 return 1;
265 }
266 }
(st.c)
重要なところはほとんどdo_hash()とFIND_ENTRY()で行われているようだ。
順番に見る。
▼do_hash()
68 #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key)) (st.c)
念のため書くと、マクロ本体のややこしい部分は
(table)->type->hash
という関数ポインタから、keyを引数にして関数を起動する記法である。
*はtableにはかからない。つまり型ごとに用意されたハッシュ関数
type->hashでもってkeyに対するハッシュ値を求めるのがこのマクロだ。
続いてFIND_ENTRY()を見る。
▼FIND_ENTRY()
235 #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
236 bin_pos = hash_val%(table)->num_bins;\
237 ptr = (table)->bins[bin_pos];\
238 if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
239 COLLISION;\
240 while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
241 ptr = ptr->next;\
242 }\
243 ptr = ptr->next;\
244 }\
245 } while (0)
227 #define PTR_NOT_EQUAL(table, ptr, hash_val, key) ((ptr) != 0 && \
(ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))
66 #define EQUAL(table,x,y) \
((x)==(y) || (*table->type->compare)((x),(y)) == 0)
(st.c)
COLLISIONはデバッグ用のマクロなので無視していい（すべきだ）。
FIND_ENTRY()の引数は前から
st_table
である。また二番目の引数には見付かったst_table_entry*が保存される。
それと一番外側には複数の式からなるマクロを安全にくくるためのdo〜
while(0)が使ってある。これはrubyの、と言うよりC言語のプリプロセッ
サのイディオムだ。if(1)だとelseが付いてしまう恐れがある。
while(1)だと最後にbreakが必要になる。
while(0)のあとにセミコロンを置かないのもポイントだ。なぜなら、
FIND_ENTRY();
と普通に書いたときに文末のセミコロンが無駄にならないからである。
st_add_direct()
続いてハッシュテーブルに新しい関連付けを登録する関数st_add_direct()を
見よう。この関数はキーが既に登録されているかどうかを検査せず、無条件
に新しいエントリを追加する。それがつまり関数名の「direct」の意味だ。
▼st_add_direct()
308 void
309 st_add_direct(table, key, value)
310 st_table *table;
311 char *key;
312 char *value;
313 {
314 unsigned int hash_val, bin_pos;
315
316 hash_val = do_hash(key, table);
317 bin_pos = hash_val % table->num_bins;
318 ADD_DIRECT(table, key, value, hash_val, bin_pos);
319 }
(st.c)
先程と同じくハッシュ値を求めるマクロdo_hash()の呼び出しがある。その
次の計算もFIND_ENTRY()の最初にあったもので、ハッシュ値を実際のインデッ
クスに変換する。
そして挿入操作自体はADD_DIRECT()で実行されているようだ。これも、名前
が大文字であることから想像できるように、マクロである。
▼ADD_DIRECT()
268 #define ADD_DIRECT(table, key, value, hash_val, bin_pos) \
269 do { \
270 st_table_entry *entry; \
271 if (table->num_entries / (table->num_bins) \
> ST_DEFAULT_MAX_DENSITY) { \
272 rehash(table); \
273 bin_pos = hash_val % table->num_bins; \
274 } \
275 \
/*（A）*/ \
276 entry = alloc(st_table_entry); \
277 \
278 entry->hash = hash_val; \
279 entry->key = key; \
280 entry->record = value; \
/*（B）*/ \
281 entry->next = table->bins[bin_pos]; \
282 table->bins[bin_pos] = entry; \
283 table->num_entries++; \
284 } while (0)
(st.c)
最初のifは例外的な場合を扱っているので後にして、その次から。
（A）st_table_entryを割り当て、初期化して、
（B）entryをリストの先頭に追加する。
こちらはリストを扱うときのイディオムだ。つまり
entry->next = list_beg; list_beg = entry;
でリストの先頭にエントリを追加することができる。Lispの用語を使って
「cons（コンス）する」と言うこともある。もしlist_begがNULLでも
このコードは通用することを確認しよう。
最後に、棚上げにしておいたコードを説明する。
▼ADD_DIRECT()−rehash
271 if (table->num_entries / (table->num_bins) \
> ST_DEFAULT_MAX_DENSITY) { \
272 rehash(table); \
273 bin_pos = hash_val % table->num_bins; \
274 } \
(st.c)
DENSITYとは「濃度」。つまりこの条件式ではハッシュテーブルが「混んで
いないか」確かめている。
st_tableでは同じbin_posを使っている値が増えるほどリンクリストが
長くなる、つまり検索が遅くなる。だからbinの数に対
して要素数が多くなりすぎたら、binを増やして混雑を緩和するわけだ。
現在ST_DEFAULT_MAX_DENSITYは
▼ST_DEFAULT_MAX_DENSITY
23 #define ST_DEFAULT_MAX_DENSITY 5 (st.c)
と設定されているから、全てのbin_posに五つのst_table_entryが連なって
いるような状況になったらサイズを増やす、ということになる。
st_insert()
st_insert()はst_add_direct()とst_lookup()の組み合わせにすぎないので
この二つが分かれば簡単である。
▼st_insert()
286 int
287 st_insert(table, key, value)
288 register st_table *table;
289 register char *key;
290 char *value;
291 {
292 unsigned int hash_val, bin_pos;
293 register st_table_entry *ptr;
294
295 hash_val = do_hash(key, table);
296 FIND_ENTRY(table, ptr, hash_val, bin_pos);
297
298 if (ptr == 0) {
299 ADD_DIRECT(table, key, value, hash_val, bin_pos);
300 return 0;
301 }
302 else {
303 ptr->record = value;
304 return 1;
305 }
306 }
(st.c)
既に要素がテーブルに登録されているかどうか調べ、 登録されていないときにだけ追加する。 実際に追加したら真を返す。追加しなかったら偽を返す。
IDとシンボル
IDというものが何であるかということは既に述べた。任意の文字列と一対一
に対応する数値のことで、いろいろな名前を表すために使われる。実際の型は
unsigned intだ。
char*からID
文字列からIDへの変換はrb_intern()で行っている。
この関数はやや長いので途中を省略して掲載しよう。
▼rb_intern()（簡約版）
5451 static st_table *sym_tbl; /* char* → ID */
5452 static st_table *sym_rev_tbl; /* ID → char* */
5469 ID
5470 rb_intern(name)
5471 const char *name;
5472 {
5473 const char *m = name;
5474 ID id;
5475 int last;
5476
/* 既にnameに対応するIDが登録されていたらそれを返す */
5477 if (st_lookup(sym_tbl, name, &id))
5478 return id;
/* 省略……新しいIDを作る */
/* nameとIDの関連を登録する */
5538 id_regist:
5539 name = strdup(name);
5540 st_add_direct(sym_tbl, name, id);
5541 st_add_direct(sym_rev_tbl, id, name);
5542 return id;
5543 }
(parse.y)
文字列とIDの一対一対応はst_tableを使って実現できる。
特に難しいところはないだろう。
省略しているところでは何をしているかと言うと、グローバル変数名や
インスタンス変数名を特別扱いしてフラグを立てているのである。
パーサで、IDから変数
の種類を知る必要があるからだ。だがIDの原理自体にはあまり関りがないこと
なので、ここには載せない。
IDからchar*
rb_intern()の逆、IDからchar*を得るために使うのがrb_id2name()である。
御存知と思うが、id2nameの2はtoのことだ。toとtwoの発音が同じだから
代わりに使っているのだ。この記法はプログラムではわりとよく見かける。
この関数もIDの種別フラグをいろいろしているために長いので、思い切り
簡単にしてものを見ておくことにする。
▼rb_id2name()（簡約版）
char *
rb_id2name(id)
ID id;
{
char *name;
if (st_lookup(sym_rev_tbl, id, &name))
return name;
return 0;
}
ちょっと簡単にしすぎたような気もするが、 実際に小細工を削ればこんなものなのだ。
ここで注目したいのは、検索したnameをコピーしていないことである。rubyの
APIでは返り値は常に、free()する必要はない（してはならない）。また引数
を渡した場合は常にコピーして使ってくれる。つまり生成と解放が常にユーザか
rubyか、片方で完結するようになっているのだ。
では生成と解放を対応させることができない（渡したら渡しっぱなしになる） 値の場合はどうするかというと、その時はRubyオブジェクトを使うようにする。 まだ話していないが、Rubyのオブジェクトは我々が面倒を見なくとも必要が なくなったときに自動的に解放されるからだ。
VALUEとIDの変換
IDはRubyレベルではSymbolクラスのインスタンスとして表され、"string".internの
ようにして得ることができる。そのString#internの実体がrb_str_intern()だ。
▼rb_str_intern()
2996 static VALUE
2997 rb_str_intern(str)
2998 VALUE str;
2999 {
3000 ID id;
3001
3002 if (!RSTRING(str)->ptr || RSTRING(str)->len == 0) {
3003 rb_raise(rb_eArgError, "interning empty string");
3004 }
3005 if (strlen(RSTRING(str)->ptr) != RSTRING(str)->len)
3006 rb_raise(rb_eArgError, "string contains `\\0'");
3007 id = rb_intern(RSTRING(str)->ptr);
3008 return ID2SYM(id);
3009 }
(string.c)
この関数はrubyのクラスライブラリのコード例としてもなかなか手頃だ。
RSTRING()を使ってキャストし、構造体メンバにアクセスしているところに
注目してほしい。
コードを読もう。まずrb_raise()は単なるエラー処理なのでとりあえず無視。
先程見たばかりのrb_intern()があり、ID2SYM()がある。ID2SYM()はIDを
Symbolに変換するマクロだった。
またこの逆の操作はSymbol#to_sなどで行える。
その実体はsym_to_sである。
▼sym_to_s()
522 static VALUE
523 sym_to_s(sym)
524 VALUE sym;
525 {
526 return rb_str_new2(rb_id2name(SYM2ID(sym)));
527 }
(object.c)
SYM2ID()はSymbol（VALUE）をIDに変換するマクロである。
なんてことはない関数に見えるが、メモリ処理まわりには注意すべきだろう。
rb_id2name()はfree()してはならないchar*を返し、rb_str_new2()は引数の
char*をコピーして使う（また引数を変更したりはしない）。このように
方針が一貫しているからこそ関数の連鎖だけで書けるのである。
御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。
『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。
Copyright (c) 2002-2004 Minero Aoki, All rights reserved.