Cでハッシュテーブルを作ってみた

2008-04-06

今日は引っ越し先の内見に行くはずだったけど、なんか先方の手違いで明日にリスケになった。

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

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

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

■[study

これを使ってみた。

文字列を超多倍長整数と見るということはつまり、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;
}