過去にオープンアドレス法で実装したこともあって、C++でサクっとかけるかな！と思って書いてみたら30分ぐらいで書き終わってﾄﾞﾔ顔しようとしたけど、
値を削除すると、他の値が読み出せなくなる欠点があり、その解決にうまい方法が思いつかなかったので、
チェイン法で実装しなおした。
http://codepad.org/PFsQMvhV
codepadだとエラー吐くけど、手元の環境じゃ-Wallでも何も起きないで無事実行できた。
特徴
値の追加、削除、キーの存在の有無が使えます。
ハッシュの持つ領域をnとした場合、
代入 O(1)
存在の確認 O(1)
削除 O(1)
ハッシュのコピー O(n)
と、ごく普通のハッシュです。
仕様
キーから値のオブジェクトを取得するにはoperator(key)=valを使います。
キーが存在するかはexists(key)を使います。
キーがさす値を削除するにはremove(key)を使います。
キーからハッシュ値を計算する時、Key型ごとにcalcHashを定義する必要があります。
キーの比較にはoperator==を使います。
この2つを満たせば、どんなものをキーにしてもいけるはず。
キーで参照した値は初期化されません。
また、operatorを呼び出した直後で、値を代入しなくてもexists==trueになります。
Hash<int,int> hash(10); // 10個の領域を持つハッシュ std::cout << (hash.exists(5) ? "true" : "false") << std::endl; // false std::cout << hash[5] << std::endl; // 未定義 std::cout << (hash.exists(5) ? "true" : "false") << std::endl; // true
課題
std::mapなりstd::tr1::unordered_mapなりと比べる。
値の代入でいちいちnewしているので遅そうだけど。
std::tr1::unordered_mapの実装が気になるのでそっちも調べたい。
