如何使用boost :: unordered_map
-
10-10-2019 - |
题
对于我的应用程序,我需要使用哈希地图,因此我编写了一个测试程序,其中我将Baseclass的一些实例存储在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大,这意味着有多个实例具有相同的参数和哈希码。
解决我的问题的方法是什么?请帮忙。
谢谢
解决方案
这是一些设计问题:
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);
}
这使地图存储了一个带有悬空指针的剧本对象。另外,您还返回对function local对象的XX in findClass的函数本地对象的参考。此参考的使用调用不确定的行为。
考虑重命名地图的密钥类型。哈希代码本身不应该是关键。正如您的操作员== Hashkey建议的那样,您不希望实际键是哈希代码,而是可变长度的整数序列。另外,请考虑将序列存储在密钥类型的内部而不是指针中,例如作为向量。另外,避免返回对函数本地对象的引用。
其他提示
使用unordered_map不能保证您不会得到碰撞,这就是您在此处描述的。
有一个以上的实例具有相同的参数和哈希码
您可以调整哈希算法以最大程度地减少此算法,但是在(不可避免的)碰撞案例中,哈希容器扩展了与该哈希码相对应的对象中的对象列表。然后,使用平等比较来解决碰撞到特定匹配对象。这可能是您的问题所在 - 也许您 operator==
没有适当地消除相似的歧义,但没有相同的对象。
您不能指望每个桶一个对象,否则容器将在大型收藏尺寸的情况下生长无限。
顺便说一句,如果您使用的是较新的编译器,则可能会发现它支持 std::unordered_map
, ,因此您可以使用(官方的STL版本)代替Boost版本。