C言語でハッシュテーブルを実装してみた

ちょっと理解できたかも記念ぱぴこ。リア充は市ね。
参考にならない程度のコードもつけときます。


ちょっと長くなるので以下からどうぞ。
http://codepad.org/QAtH9yr8


今回はオープンアドレス法で実装しました。
キーには文字列を使い、値は汎用にできるといいと思ったので、voidポインタを使いました。
問題がいろいろあり、領域は静的にしか取れない、キーの長さに制限、削除できない、ちょっと問題があったら即exitする等があります。
set/getのループあたりの条件が間違っていそうで怖い。
また、今回はキーの長さが0のとき(1文字目がヌル文字)は、データがないものとして登録します。
削除するときは、キーの長さを0にすればいいです。
また、キーの長さが0のキーを使うと、エラー扱いになります。仕様です。


各関数の説明

unsigned int calcHash(const unsigned char *key)

キーkeyからハッシュを算出し、返します。
この実装はperlgutsの説明にあるPERL_HASHと同様の実装です。

unsigned int rehash(unsigned int calc)

ハッシュの再計算を行います。ただ、次の領域を取るだけです。

initHash(struct Hash *hash)

hashを初期化します。必ず最初に呼び出します。

clearHash(struct Hash *hash)

該当する値を削除します。
今回はinitHashで使われるだけですが、削除の必要も出てきたとき、使えます

setHash(struct Hash *hash, const char *key, void *val)

hashのキーkeyへ値valをセットします。
MAX_HASH_SIZEを超える個数の値を登録した場合、exitします。
void *型の表現を超える型を値にすることはできません(コンパイラが許さないと思うけど。)

void * getHash(struct Hash *hash, const char *key)

hashのキーkeyに対応付けられている値を取り出します。
void *型で返すので、別の型にする場合、キャストを必要とします。
keyに該当するものがない場合、0を返します。

#define HV(V) ( (void *)(V) )

マクロ関数で、引数の値をvoid *型に変換します。
setHash時の警告メッセージを回避する目的で使います。

メモ

本当はC++で書くつもりだったんだけど、クラスの使い方がまだ慣れないのと、色々躓いたので、Cで手抜いて書く事にしました。
本来なら、不特定多数のデータを扱う事を考慮して、動的に拡張するなどの仕組みがあるべき。
JavaのHashMapではおそらくオープンアドレス法で実装されていて、
ある程度登録されると、動的に拡張します。また、初期サイズも指定できるし、拡張するタイミングも調整できます。
あと問題になるのが、動的に確保した値をハッシュの値として使った場合、いつ開放するのか。
ユーザの任意にしたほうが楽なんだけど、そうもいかない場面も多い。
C++にはガベージコレクションの仕組みがないので、スマートポインタを使う必要があるかも。
知らん事が多すぎるC++なめてたサーセン

追記

今思ったら、探索中に該当するキーがなかった場合、0を返すけど、
この探索、すべてに対して行ってるけど、途中でキーの長さが0のものが見つかったら、そこで探索を打ち切れる。
なぜなら、キーを格納した場合、必ず開いている場所まで線形探索を行うから、存在しているキーなら、キーの長さが0のものはヒットし得ない。
これで該当なしの場合に掛かる時間オーダO(n)を回避できる、と。