Posted on 2012-04-18 20:18
C小加 阅读(2451)
评论(3) 编辑 收藏 引用 所属分类:
数据结构和算法 、
模板
hash_map，顾名思义，就是利用hash_set存储结构的写map映照容器，普通的map用的是红黑树存储结构写的。元素的检索时间对比，hash_set近似为O(1)，红黑树为O(logn)。Hash_map的空间开销要比map 的空间开销大，尤其是我用数组模拟指针写的hash_map。
所以，如果有必要采取映射结构的时候，能用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;
};