Perlのhash - mizuno_takaakiの日記

Perlのhashって相当使ってるけど、中身知らないなー、とふと思い、調べてみたら、こんなページがあった。
http://www.perl.com/lpt/a/679
2002年に書かれたもので、ちょっと古いけれど、読んでいったら、詳しく知りたかったらとりあえずPerl 1.0のhash.cから始めたらいいんじゃないかみたいなことから書いてあって、なるほどと思って読んでみた。短い。
与えられたキーからデータの入っている場所を探すハッシュ関数としては、以下みたいなループ。

for (s=key,i=0,hash = 0;
  /* while */ *s;
  s++,i++,hash *= 5) {
  hash += *s * coeff[i];
}
oentry = &(tb->tbl_array[hash & tb->tbl_max]);

こんな感じで、キーの文字１文字ずつを使ってcoeffという配列の要素と掛け合わせて足していき、それを、ハッシュテーブルの配列のデータサイズで~~割って~~論理積をとって、格納場所を特定する。値の取得、設定、削除それぞれの関数に同じ処理が書かれていてちょっと冗長。
coeffはこんな感じで定義されてる。

char coeff[] = {
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
		61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};

これって、キーがcoeffのサイズを超えたらだめな気がする。サイズチェックしてないぞ。で、同じ格納場所に別のキーが割り当てられたら、チェイン法でつながってる。
これは、取得の部分。

entry = tb->tbl_array[hash & tb->tbl_max];
for (; entry; entry = entry->hent_next) {
  if (entry->hent_hash != hash)		/* strings can't be equal */
    continue;
  if (strNE(entry->hent_key,key))	/* is this it? */
    continue;
  return entry->hent_val;
}
return Nullstr;

シンプルだった。要するに、同じ場所に来てしまったら、hent_nextというポインタでずらっとつなげていく。hentはHash Entryの略だな。
ところで、tbl_maxなんだけど、最初は7に設定されている。小さい。

HASH *
hnew()
{
    register HASH *tb = (HASH*)safemalloc(sizeof(HASH));

    tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
    tb->tbl_fill = 0;
    tb->tbl_max = 7;
    hiterinit(tb);	/* so each() will start off right */
    bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
    return tb;
}

だけど、データを登録した際に、tbl_fillという、配列がどれだけ埋まっているかという数を増やしていて、それが閾値を超えると、hsplitという、配列サイズを２倍にする関数が呼ばれるようになっていた。

if (i) {				/* initial entry? */
  tb->tbl_fill++;
  if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
    hsplit(tb);
}

なるほど。でもこれだと、ハッシュ関数の結果が同じ値のものばっかりになると、ずらーっとチェーンがつながって遅くなってしまう気がするぞう。
と、簡単に読めたけど、

Perl 5 took the giant leap of referring to associative arrays as hashes. (As far as I know, it is the first language to have referred to the data structure thus, rather than "hash table" or something similar.) Somewhat ironically, it also moved the relevant code from hash.c into hv.c.

ということなんで（今どうなってるか分からないけど）、次はPerl 5のhv.cをよむべ。