hash_map哈希映照容器的实现

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;
};

补充：综合编程 , 安全编程 ,