汎用型ハッシュを書きました。
今なら糞コード付。
長いのでcodepadへ。
http://codepad.org/elk6geVc
使い方
createHashでハッシュのモトを作って、
setHash, getHashとかして、
freeHashで後始末。
特徴
オープンアドレス法で実装。
初期領域をcreateHash時に指定できます。
足りなくなってきたら自動的に領域を増やしてくれます。
（領域の75%にデータを登録された時に、領域を1.5倍に拡張）
キーや値はどんな型でも対応できます。（そのサイズを教える必要があります）
登録/取得/削除が可能です。
エラー処理は自己責任で。だいたい0を返してきたら問題が起こってます。
使い勝手は最悪です。
えー
まず、ハッシュの肝となるハッシュ関数から。
ハッシュ関数はうまい実装を考えられなかったので、Perlでの実装をそのまま写したレベルです。
オープンアドレス法では衝突で再計算が必要になるので、1加算してずらしていきます。
汎用型を扱えるようにするために使い勝手を捨ててます。
値をsetするにもgetするにも、変数を1個かませる必要があります。
最初はnodeで返そうかな、と思ったんですが、keyがconstでないので、
間違えてでも変更されるとハッシュが機能しなくなるので、それを恐れたため。
この辺はキャストとかでどうにかなるかもしれないけど、めんどくさくｒｙ
キーを指定するにも、値を渡すにも、その型のサイズもしくは領域の大きさも渡す必要があります。
キーに限っては、文字列で扱えたほうが何かと良いと思うので、
マクロなりで、strlenを渡すようにすればキーの長さを渡す必要がなくなります。
この使いにくいフォーマットに従えば、キーも値も様々な型に対応できます。
しかし欠点があり、キーが意図しないうちにかぶる可能性があります。
例えばキーとしての、int型整数0x34333231と、char文字列"1234"は、同じになる環境があるかもしれません。
上の文字列では、char s[4]={0x31,0x32,0x33,0x34}; になり、
上の整数をリトルエンディアンで扱う場合に、かぶることになります。
速度としても早くないです。
無駄な部分がまだまだありそうですが、ちょっといじるのがめんどくさくｒｙ
8文字のよくある文字を扱ったランダムなキーで100万のデータを、
十分な領域（再確保しない程度の領域）へset/getするのに2秒ぐらいかかります。
調べると、同条件で0.8秒台の実行速度をもつハッシュもあるようなので、3倍近く遅いことになります。
以下そのベンチマークのコードです。（上のコードのmain関数部分を入れ替えれば動きます）
そんなこんなで使いにくいことこの上ないんです。僕もこんなハッシュ使いたくないです。
ただC++にすると、引数やoperatorのオーバーロード、テンプレートにより上の問題は全部解決できます。
速度も多分テンプレートになればマシになるはず。
int main(){ char randchar[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; int randchar_num = sizeof(randchar)-1; clock_t start, end; int i; // double sum=0; srand(time(NULL)); getchar(); for(i=1; i<=10; ++i){ int size = i * 100000; int j; int recv; HashNode *node = (HashNode *)malloc(sizeof(HashNode) * size); Hash *hash; // create randkey=>val pare for(j=0; j<size; ++j){ int randkey_size = 8; int k; char *randkey = (char *)malloc(randkey_size + 1); int *randval = (int *)malloc(sizeof(int)); *randval = j; for(k=0; k<randkey_size; ++k) randkey[k] = randchar[rand()%randchar_num]; randkey[randkey_size] = '\0'; node[j].key = randkey; node[j].keysize = randkey_size; node[j].val = randval; node[j].valsize = sizeof(int); } // benchmark!! start=clock(); hash = createHash(3000000); for(j=0; j<size; ++j){ setHash(hash, node[j].key, node[j].keysize, node[j].val, node[j].valsize); getHash(hash, node[j].key, node[j].keysize, &recv); // sum += recv; } freeHash(hash); end=clock(); printf("MyHash => %5d clock [n=%d]\n", end-start, size); // free randkey=>val for(j=0; j<size; ++j){ freeHashNode(node+j); } free(node); } // printf("sum: %f\n", sum); return 0; }
