Stlでキーを検索するHash_map

Question

私は初心者であり、ハッシュテーブルに問題があります。私のプログラムにはハッシュテーブル構造が必要です。まず、boost unordered_mapを使用します。私に必要なすべてのものがありますが、私のプログラムはとても遅くなります。 stl hash_mapをテストしたいのですが、私が必要とするすべてのことを行うことはできません。これは私の最初のコード（これはサンプルです）

#include <hash_map> 
using namespace std; 

struct eqstr 
{ 
    bool operator()(int s1, int s2) const 
    { 
    return s1==s2; 
    } 
}; 
typedef stdext::hash_map< int, int, stdext::hash_compare< int, eqstr > > HashTable; 

int main() 
{ 
    HashTable a; 
    a.insert(std::pair<int,int>(1, 1)); 
    a.insert(std::pair<int,int>(2, 2)); 
    a.insert(std::pair<int,int>(4, 4)); 
//next i want to change value of key 2 to 20 
    a[2] = 20; 
//this code only insert pair<2,20> into a, buy when I use boost unordered_map this code       modify previous key of 2 
//next I try this code for delete 2 and insert new one 
    a.erase(2);//this code does work nothing !!! 
//next I try to find 2 and delete it 
    HashTable::iterator i; 
    i = a.find(2);//this code return end, and does not work!!! 
    a.erase(i);//cause error 
//but when I write this code, it works!!! 
    i=a.begin(); 
    a.erase(i); 
//and finally i write this code 
    for (i = a.begin(); i!=a.end(); ++i) 
    { 
    if (i->first == 2) 
     break; 
    } 
    if (i!= a.end()) 
    a.erase(i); 
//and this code work 

ですが、私は私のデータを検索したい場合は、私は、配列を使用する理由私はアクセスすることはできません、modityをhash_mapし、（1）Oでhash_mapから削除しません 私の間違いは何ですか、そして、初期化段階で多くの値変更を伴う私のプログラムのためには、どのハッシュ構造が速いのですか？それは私にそれにいくつかのチュートリアルを与えることができる場合、私に適したGoogleのsparse_hashです。任意のヘルプ

Answer 1

ため おかげであなたが見てもよい：http://msdn.microsoft.com/en-us/library/525kffzd(VS.71).aspx

私はstdext::hash_compare< int, eqstr >がここでの問題を引き起こしていると思います。それを消してみてください。

ハッシュマップの別の実装はstd::tr1::unordered_mapです。しかし、私は、さまざまなハッシュマップ実装のパフォーマンスが似ていると思います。 boost :: unordered_mapがどれほど遅いかについてもっと詳しく説明できますか？どのように使ったのですか？何のために？

Answer 2

ハッシュマップは非常に多くの種類があり、多くの開発者は独自のものを書いています。自分のものでより高いパフォーマンスを得ることができます。 、人々は本当に高いパフォーマンスが必要なときにハッシュを使用する傾向があります。

最初に考慮する必要があることは、本当に必要なものと、本当に必要なパフォーマンスがどれだけあるのか、既成のものがそれを満たすことができるのか、自分で何かを書く必要があるのか​​どうかを判断することです。

たとえば、要素を決して削除しないで、一度書いてから常にルックアップすれば、取得した実際のセットの衝突を減らすことができます。

エントリを「null」にするだけでは不十分であるため、要素を削除すると、別のものが衝突コースの一部としてあなたの上を歩いている可能性があります。それはあなたのnullに当たるとすぐに "見つからない"と断念します。