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

C言語はソース貼っても試すのめんどいよなあとか思ったんだけど、よく考えるとCodePad に貼れば記事を見た人がすぐ実行できるとか思ったので早速やってみた。

以下思ったこと。

ハッシュテーブルに入れるvalueをどういう型にするか迷う

これはCを使うときにはいつも迷う。
最初はvoid*にして、確保と開放はユーザの責任ということにした。でも単純にポインタ型にすると、文字列をvalueに入れたりするのは簡単になるけど、ハッシュテーブルを使ってワードカウンティングをするとか、そういうのがすごく面倒になる。
逆にintしか入らないハッシュテーブルとか寒い。
templateが欲しくなるけど、C++使うならそもそもハッシュテーブルなぞ作る必要はない。
結局、valueは型タグとintやらvoid*やらが入る共用体をくっつけた構造体として、適切な型の出し入れはユーザ側の責任ということにした。あとintやらポインタとしてset/getするようなメソッドを作って楽に出し入れできるように。

enum val_type { H_NIL, H_INT, H_CHAR, H_LONG, H_DOUBLE, H_PTR };
typedef struct val_t {
	enum val_type type;
	union {
		int n;
		char ch;
		long l;
		double d;
		void* pt;
	} val;
} val_t;

HASH hash_set(HASH me, const char* key, val_t val);
HASH hash_set_i(HASH me, const char* key, int val);
...
HASH hash_set_p(HASH me, const char* key, void* val);

val_t  hash_get(HASH me, const char* key);
int    hash_get_i(HASH me, const char* key);
...
void*  hash_get_p(HASH me, const char* key);

使うときはこう。

HASH h = hash_create();
hash_change_func(h, func);
for( i=0; i<NUM; i++ ){
	sprintf(key, "key%d", i);
	/* 直接 int値を入れることができる */
	hash_set_i(h, key, i);
	/* 直接 int値を取り出せる */
	assert(i == hash_get_i(h, key));
}
hash_delete(h);

ハッシュ関数により性能が大きく左右される

http://codepad.org/Bybm7P8I の実行結果を見ると分かるけど、

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

ハッシュ関数をこのようないい加減な実装にすると性能が著しく劣化する。とにかく衝突が多くなるので、今回のように衝突を連鎖法で回避している実装では連鎖の深さが大変深くなってひどいことになる。特にこの実装では、ハッシュ値が非常に小さい値になりやすいので、ハッシュテーブルを大きくしても衝突が減らなかったりする。

あと、ハッシュ関数とスロットサイズの相性によっては、めちゃめちゃ性能が悪化する。
最悪な例の一つが、char配列を256進数の多倍長整数と考えた上で、スロットサイズを2のベキ乗にしてしまった場合だ。よく考えればわかるけど、これは例えばスロットサイズが65536であるとき、キーの先頭2byte(実装によっては末尾2byte)以外を無視して2byte分しか使わないのと同じことであり、とてつもなく衝突が発生する。
char配列を256進数とした場合でもスロットサイズが素数であればそれなりに分散するし、また逆にchar配列を何らかのちょっと大きな素数基数(例えば977進数とか)と考えるとスロットサイズが2のベキ乗でもちゃんと性能がでる。

さらに細かいことを言うと、char配列を素数基数としてスロットサイズを2のベキ乗にする場合の基数は、例えば
$65537=2^{16}+1$
のような2のベキ乗+1になるような素数は具合が悪い(2のベキ乗で剰余を取ると1になりやすい)。
まあ実際にはスロット数は素数にしておいて、ハッシュ関数が多少間抜けでもマシにしておくのが実践的だろう。

このように、ハッシュテーブルって実装の質に依存して結構ピーキーなので(まあ僕の実装が悪いだけかもしれないけど)、実は現実的にはバイナリツリーのほうが性能のバランス/安定性がよかったりしないのかな。実際のところ、O(1)>>>>>>>O(logn) になるような極端に巨大な要素数 n を格納できるようなフラットなメモリを確保できるんだろうか。