ハッシュテーブルの検索

超有名なデータ格納の方法の一つ。
諸事情により、自前でハッシュマップとハッシュセットを作る必要があったので、作ってみた。
理論上計算回数がΟ(1)でいけるはずなんだけど、どうもそんな感じがしない。

っで、STLのsetと自作ハッシュセットで比較してみた。
結論だけ言うと、
ハッシュセットは早いけど遅い。
なんのことだ？と思うかもしれないけどそんな感じ。
実装の都合上、衝突が起きた際に得られたハッシュ関数で得られたハッシュ値を増やして空きを探したり、
要素が存在しているか検索しているのだが、これがまずい。
無限の箱があってハッシュ値も衝突がおき得ないのならΟ(1)なんだろうけど、箱は有限。っで箱が50000とか超えた時に、存在しない値の検索をすると、ループが50000回走る。つまりΟ(n)になる。
う～ん、存在する値だとものすごく早くてそれこそΟ(1)に近い値が出るんだけど、う～ん。
衝突時にリストにしてもいいけど、メモリ管理が面倒な気がする・・・う～ん・・・

どうでもいいけど、
「Ο」これ「O(アルファベット)」じゃなくて「Ο(オミクロン)」だったのね。初めて知った^^;