如何使用boost :: unordered_map

我的應用程序，我需要使用哈希映射，所以我寫了一個測試程序，其中我將一些基類的實例存儲在boost :: unordered_map中。但我想通過調用返回基類的派生類的特殊函數來到達實例，並且我使用這些函數的參數作爲unordered_map的哈希鍵。如果沒有找到具有某些參數的類，那麼將生成一個類並將其存儲在地圖中。程序的目的可能不明確，但這裏是代碼。如何使用boost :: unordered_map

#include <boost/unordered_map.hpp> 
#include <iostream> 

using namespace std; 
using namespace boost; 
typedef unsigned char BYT; 
typedef unsigned long long ULL; 

class BaseClass 
{ 
public: 
    int sign; 
    size_t HASHCODE; 
    BaseClass(){} 
}; 

class ClassA : public BaseClass 
{ 
public: 
    int AParam1; 
    int AParam2; 
    ClassA(int s1, int s2) : AParam1(s1), AParam2(s2) 
    { 
     sign = AParam1; 
    } 
}; 


struct HashKey 
{ 
    ULL * hasharray; 
    size_t hashNum; 
    size_t HASHCODE; 
    HashKey(ULL * ULLarray, size_t Hashnum) : hasharray(ULLarray), hashNum(Hashnum), HASHCODE(0) 
    { } 
    bool operator == (const HashKey & hk) const 
    { 
     bool deg = (hashNum == hk.hashNum); 
     if (deg) 
     { 
      for (int i = 0; i< hashNum;i++) 
       if(hasharray[i] != hk.hasharray[i]) return false; 
     } 
     return deg; 
    } 
}; 

struct ihash : std::unary_function<HashKey, std::size_t> 
{ 
    std::size_t operator()(HashKey const & x) const 
    { 
     std::size_t seed = 0; 
     if (x.hashNum == 1) 
      seed = x.hasharray[0]; 
     else 
     { 
      int amount = x.hashNum * 8; 
      const std::size_t fnv_prime = 16777619u; 
      BYT * byt = (BYT*)x.hasharray; 
      for (int i = 0; i< amount;i++) 
      { 
       seed ^= byt[0]; 
       seed *= fnv_prime; 
      } 
     } 
     return seed; 
    } 
}; 

typedef std::pair<HashKey,BaseClass*> HashPair; 
unordered_map<HashKey,BaseClass*,ihash> UMAP; 
typedef unordered_map<HashKey,BaseClass*,ihash>::iterator iter; 


BaseClass * & FindClass(ULL* byt, int Num, size_t & HCode) 
{ 
    HashKey hk(byt,Num); 
    HashPair hp(hk,0); 
    std::pair<iter,bool> xx = UMAP.insert(hp); 
// if (xx.second) UMAP.rehash((UMAP.size() + 1)/UMAP.max_load_factor() + 1); 
    if (!xx.first->second) HCode = UMAP.hash_function()(hk); 
    return xx.first->second; 
} 


template <typename T, class A,class B> 
T* GetClass(size_t& hashcode ,A a, B b) 
{ 
    ULL byt[3] = {a,b,hashcode}; 
    BaseClass *& cls = FindClass(byt, 3, hashcode); 
    if(! cls){ cls = new T(a,b); cls->HASHCODE = hashcode;} 
    return static_cast<T*>(cls); 
} 



ClassA * findA(int Period1, int Period2) 
{ 
    size_t classID = 100; 
    return GetClass<ClassA>(classID,Period1,Period2); 
} 

int main(int argc, char* argv[]) 
{ 
    int limit = 1000; 
    int modnum = 40; 
    int result = 0; 

    for(int i = 0 ; i < limit; i++) 
    { 
     result += findA(rand() % modnum ,4)->sign ; 
    } 

    cout << UMAP.size() << "," << UMAP.bucket_count() << "," << result << endl; 

    int x = 0; 

    for(iter it = UMAP.begin(); it != UMAP.end(); it++) 
    { 
     cout << ++x << "," << it->second->HASHCODE << "," << it->second->sign << endl ; 
     delete it->second; 

    } 

    return 0; 
}

問題是，我期望UMAP的大小等於然而modnum它是比永諾modnum這意味着有具有相同的參數和hashcode多個實例更大。

我的問題的解決方案是什麼？請幫忙。
謝謝

來源

2010-10-21 ali_bahoo

任何人都會調試你的程序的機會真的很低。嘗試將問題隔離到*更短的程序。另外，儘量避免使用編譯器特定的東西，如編譯指示，__int64等。 – sellibitze 2010-10-21 09:38:13

現在可以嗎？ – 2010-10-21 10:16:45

不，你包括，做系統（「暫停」），使用LARGE_INTEGER和QueryPerformanceCounter（無論這些是什麼）。 – 2010-10-21 11:04:28

這裏有幾個設計問題：

struct HashKey 
{ 
    ULL * hasharray; 
    ...

密鑰類型存儲指針數組一些。但這個指針被初始化爲本地對象的地址：

BaseClass * & FindClass(ULL* byt, int Num, size_t & HCode) 
{ 
    HashKey hk(byt,Num); // <-- !!! 
    HashPair hp(hk,0); 
    std::pair<iter,bool> xx = UMAP.insert(hp); 
    if (!xx.first->second) HCode = UMAP.hash_function()(hk); 
    return xx.first->second; 
} 

template <typename T, class A,class B> 
T* GetClass(size_t& hashcode ,A a, B b) 
{ 
    ULL byt[3] = {a,b,hashcode}; // <-- !!! 
    BaseClass *& cls = FindClass(byt, 3, hashcode); 
    if(! cls){ cls = new T(a,b); cls->HASHCODE = hashcode;} 
    return static_cast<T*>(cls); 
}

這使得地圖存儲與懸掛指針HashKey對象。另外，您還要返回對FindClass中名爲xx的函數本地對象的成員的引用。這個引用的使用調用未定義的行爲。

考慮重命名地圖的密鑰類型。散列碼本身不應該是關鍵。正如你的運營商== HashKey所建議的那樣，你不希望實際的密鑰是散列碼，而是可變長度的整數序列。另外，考慮將序列存儲在鍵類型中而不是指針，例如作爲矢量。另外，避免返回對函數本地對象的引用。

來源

2010-10-21 11:27:28 sellibitze

哇。我擺脫了ULL * hasharray，並使用 typedef ULL ULLArrayof4 [4]; struct HashKey { \t // ULL * hasharray; \t ULLArrayof4 hasharray;改爲。問題是懸着的指針。現在都很好。謝啦。 :) – 2010-10-21 11:57:44

使用unordered_map並不能保證你沒有碰撞，這就是你在這裏描述的。

有多個實例具有相同的參數和hashCode

你可以調整你的哈希算法，以儘量減少這一點，但在（必然）發生碰撞的情況下，散列容器擴展與該哈希碼對應的桶中的對象列表。然後使用相等比較來解決碰撞到特定的匹配對象。這可能是你的問題所在 - 也許你的operator==不能正確地消除類似但不相同的對象的歧義。

您不能指望每個存儲桶有一個對象，或者容器在大型集合大小的情況下將無限增長。

btw如果您使用的是較新的編譯器，您可能會發現它支持std::unordered_map，因此您可以使用該（官方STL版本）而不是Boost版本。

來源

2010-10-21 11:09:55

如何使用boost :: unordered_map

回答

相關問題