使用stdext :: hash_set/hash_map與對象指針進行衝突

Question

我目前使用MS VC++ 2008及其提供的帶有擴展的標準庫。 我想使用散列容器來快速插入/刪除/查找對象。所以，我想這應該工作剛剛好：

stdext::hash_set<MyOjbectClass*> 

我發現那是什麼衝突是非常高的默認散列函數（我假設只是使用指針值）。

當我在調試器中運行下面的代碼：

stdext::hash_set<void*> hs; 
for (int i=0; i<30; i++) 
{ 
    hs.insert(new std::string()); 
} 

我看到所有項目都放在同一個桶！ （facepalm） 雖然所有的指針都是唯一的。所以我可以忘記O（1）。

那麼，使其有效工作的正確方法是什麼？

提供自定義哈希函數？這樣的指針是好的嗎？

注意：我需要使用hash_map/hash_set。請不要提供使用unordered_map/set或boost等。

Answer 1

經過一番搜索，我發現了很少的哈希值。下面的資源是有幫助的：這裏找到

兩個功能：What is the best hash function for uint64_t keys ranging from 0 to its max value?

和1功能在這裏：http://naml.us/blog/2012/03

經過一番測試MurmurHash3表現出最好的結果對我來說。它有最好的表現。所有3個散列函數的桶分佈的標準偏差幾乎相同，並且比使用標準散列函數的情況要好得多。