Cでハッシュテーブルを作ってみた - ＊「ふっかつのじゅもんがちがいます。」withぬこ

今日は引っ越し先の内見に行くはずだったけど、なんか先方の手違いで明日にリスケになった。
おとなしく部屋の掃除でもしてればよかったんだけど、ついつい id:amachangの「駄文 - C 言語の勉強」を見て、そういえば僕は物心ついたころからSTLのstd::mapとか使ってたから、Cでハッシュテーブルを自作したことないなーと思ったのを思い出してしまい、レクリエーションのためにCでハッシュテーブル作ろうとか思い立ったのが運のつきだった。

ハッシュアルゴリズムは、同じくid:amachangのところの「ruby のハッシュで使われている st_hash とは」から見た

出掛けにセジウィックのアルゴリズムCを見たら、「ハッシュ表のサイズは素数にして、文字列を超多倍長数としてみる」ような恐ろしげな方法が載っている。いやなのでその辺のソースに頼ってみよう。

これを使ってみた。
文字列を超多倍長整数と見るということはつまり、char str[30]くらいの文字列とかだったら256進29桁ほどになるわけだ*1。さーてそんなのどう計算しようかと思っていろいろ考えてたら、どうせ最終的に剰余にしちゃうのだから加算乗算のたびに剰余とっちゃえばオーバーフローは全く気にしないでよいことに気づいた。（これはちょうどSICP読書会でやった[＝p.28〜31のFermatテスト]あたりだ。）
そいから、超多倍長整数としての値を求めるのも、SICP p.69あたりのHornerの方法を使うのが早そうだ。
Hornerの方法とは、

$a_{n}x^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0}$
を計算するときに、
$(((...(a_{n}x + a_{n-1})x + a_{n-2})x + ... +a_{1})x + a_{0}$
のように計算する算法であり、SICPの脚注によればこれがもっとも計算回数が少ないらしい。

これは素敵な再帰アルゴリズムであり、めちゃ簡単に実装できる。(SICPではaccumulateを使ってこれを計算せよという問題だけど、Cで汎用的なaccumulateを書くのは大変だ)

charの配列であるところのC文字列が
$a_{n} a_{n-1} ... a_{1} a_{0}$
であり、charが8bitでUCHAR_MAX=255とかだとすれば、文字列を超多倍長整数として見るときの整数値とは、
$f(x)=a_{n}x^n + a_{n-1}x^{n-1} + ... + a_{1}x + a_{0}$
とおいたときに
$f(256)$
を求めることに他ならず、Hornerの方法がそのまま使える。

というわけで上記２つを使えばハッシュ関数はさくっと書ける。例えばこんな感じだ。

unsigned int horner_rule(const char* key, int mod){
	unsigned char val;
	if(!key){ return 0; }
	if(*key == '\0'){ return 0; }
	val = (unsigned char)(*key) % mod;
	return ( val + horner_rule(key+1, mod) * ((UCHAR_MAX+1) % mod)) % mod;
}

そこまではよかった、というかハッシュテーブル自体を実装するところまではよかったけど、一通り書き終わってテストしてみたらSegumentation faultやらBus Errorやらが出るわ出るわ。泣きながらデバッグするはめになった。やっぱCはしばらく書かないとすぐ書けなくなりますね。
そこそこ安定してきたと思って、テーブルのサイズを増やしたりいろいろ試してると今度はつい再帰で書いちゃった関数が再帰深すぎてSegmentation Faultとかw

とかそんな楽しい休日でした。

書いたハッシュテーブルのソースはこちら。識者の方の突っ込み大歓迎です。
main.c
hash.c
hash.h

*1:charが8bitの処理系では