1

私のアプリケーションでは、ハッシュマップを使用する必要があるため、基本クラスのいくつかのインスタンスをboost::unordered_mapに格納するテストプログラムを作成しました。しかし、ベースの派生クラスを返す特殊関数を呼び出してインスタンスに到達したいので、それらの関数のパラメーターを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を持つインスタンスが複数存在することを意味します。

私の問題の解決策は何ですか？助けてください。
ありがとう

4

2 に答える 2

3

以下に、いくつかの設計上の問題を示します。

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 の operator== が示唆するように、実際のキーをハッシュ コードにするのではなく、可変長の整数のシーケンスにする必要があります。また、ポインターの代わりにキーの型の内部にシーケンスを格納することを検討してください。たとえば、ベクトルとして。さらに、関数ローカル オブジェクトへの参照を返さないようにします。

于 2010-10-21T11:27:28.187 に答える
1

unordered_mapを使用しても、衝突が発生しないことは保証されません。これについては、ここで説明します。

同じパラメータとHASHCODEを持つインスタンスが複数あります

これを最小限に抑えるためにハッシュアルゴリズムを調整できますが、（避けられない）衝突の場合、ハッシュコンテナはそのハッシュコードに対応するバケット内のオブジェクトのリストを拡張します。次に、等式比較を使用して、特定の一致するオブジェクトへの衝突を解決します。これはあなたの問題が存在する場所かもしれません-おそらくあなたoperator==は類似しているが同一ではないオブジェクトを適切に明確にしないでしょう。

バケットごとに1つのオブジェクトを期待することはできません。そうしないと、コレクションサイズが大きい場合にコンテナが無制限に大きくなります。

ところで、新しいコンパイラを使用している場合はstd::unordered_map、それがサポートしていることがわかるかもしれません。そのため、Boostバージョンの代わりにそれ（公式のSTLバージョン）を使用できます。

于 2010-10-21T11:09:55.960 に答える