C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

hash_map哈希映照容器的实现

Posted on 2012-04-18 20:18 C小加 阅读(2433) 评论(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_maphash_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;
};

 

Feedback

# re: hash_map哈希映照容器的实现  回复  更多评论   

2012-04-19 16:15 by 嵌入式培训
很好的方法

# re: hash_map哈希映照容器的实现  回复  更多评论   

2012-04-19 17:06 by SunRise_at
写的不错。。。。

# re: hash_map哈希映照容器的实现  回复  更多评论   

2012-05-10 19:31 by fanxixian
能写一下注释吗?

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理