Posted on 2012-04-18 20:18
C小加 閱讀(2465)
評論(3) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法 、
模板
hash_map，顧名思義，就是利用hash_set存儲結(jié)構(gòu)的寫map映照容器，普通的map用的是紅黑樹存儲結(jié)構(gòu)寫的。元素的檢索時(shí)間對比，hash_set近似為O(1)，紅黑樹為O(logn)。Hash_map的空間開銷要比map 的空間開銷大，尤其是我用數(shù)組模擬指針寫的hash_map。
所以，如果有必要采取映射結(jié)構(gòu)的時(shí)候，能用hash_map就別用map。
需要注意的是，hash_map遍歷出來的元素不是有序的。
Hash_map和普通hash_set相比的話，hash_map比hash_set多了一張value表，也就是映射表。
下面是hash_map的模板，和hash_set的模板差不多。
template<class KeyType,int MaxHash>
struct HashFunction
{
int operator()(const KeyType& key)
{
int h=key%MaxHash;
if (h<0) h+=MaxHash;
return h;
}
};
template<class KeyType,class ValueType,int KeyContain,int MaxHash,class HashFun=HashFunction<KeyType,MaxHash> >
class HashMap
{
public:
HashMap():hashfun(){Clear();}
ValueType& operator[](const KeyType& key)
{
int h=hashfun(key);
int pos=head[h];
for(;pos!=0;pos=next[pos])
{
if(keys[pos]==key)
return values[pos];
}
next[++top]=head[h];
head[h]=top;
keys[top]=key;
values[top]=ValueType();//初始化
++sz;
return values[top];
}
void Clear()
{
memset(head,0,sizeof(head));
memset(next,0,(top+1)*sizeof(int));
top=0;
sz=0;
}
unsigned int size() const {return sz;}
private:
unsigned int sz;
HashFun hashfun;
int head[MaxHash];
int next[KeyContain];
KeyType keys[KeyContain];
ValueType values[KeyContain];
int top;
};