hash_mapの実装の仕方
http://www.hatena.ne.jp/1138956162
より。
これでも衝突が怖いのでしたら、ハッシュ関数のグレードを落として他の方法と併用した方がいいでしょう。
CRC32やchecksumのような速いがおよそハッシュ関数とは呼べないものを使った上で、B-Treeとか。
これならば衝突可能性はゼロになりますからね。
これってhash_mapみたい?と思った私であるのですが・・・
私の頭の中ではhash_mapの構造は簡単で高速なhash関数でRed Black Treeオブジェクトの配列上のインデックスを決めてRed Black Treeオブジェクトにキーとデータを格納するって感じだと思っています。*1
私がハッシュ系コンテナを作るとしたらそんな感じだなと2年程前から思っていた次第です。
ハッシュ系コンテナを作る場合皆さんはどのようなアプローチをとるのでしょうか?
さて、上記のURLでのDBってデータベースのことですよね。
hash_map的な構造をファイルに落とせるように特化させればいいのかな?と思っていたりします。B-Treeはファイル構造とかの管理に適しているらしいのでなるほどと・・・B-Treeって結構亜種が存在するらしいのでその中から一番パフォーマンスの良い亜種を探すのなんて面白そうです。*2
DB的な事を扱ったことが無いので良く分からないですが^^;