• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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小加 閱讀(2472) 評論(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
            能寫一下注釋嗎?
            亚洲欧美日韩中文久久| 久久精品99无色码中文字幕| 亚洲精品无码久久一线| 久久久久久九九99精品| 国产69精品久久久久9999| 亚洲午夜福利精品久久| 国产精品美女久久久久| 日韩精品久久久久久| 国产成人综合久久精品红| 久久天天躁狠狠躁夜夜不卡| 亚洲综合久久久| 久久精品国产亚洲网站| 久久毛片一区二区| 国产精品99精品久久免费| 一本色道久久综合狠狠躁篇 | 99热精品久久只有精品| 久久久久久亚洲精品影院| 久久久久免费看成人影片| 久久久噜噜噜久久中文字幕色伊伊| 久久精品国产精品亚洲精品| 久久这里只精品国产99热| 亚洲色婷婷综合久久| 久久99这里只有精品国产| 久久综合久久综合久久综合| 一本久久知道综合久久| 热综合一本伊人久久精品| 国产精品九九久久免费视频 | 7777久久亚洲中文字幕| 久久精品国产乱子伦| 欧美伊人久久大香线蕉综合69| 狠狠色丁香久久婷婷综合五月 | 97久久精品人人做人人爽| 久久国产精品无码HDAV| 久久99精品国产麻豆宅宅| 一本色综合久久| 久久无码AV一区二区三区| 亚洲日本va午夜中文字幕久久| 久久久久中文字幕| 99久久综合国产精品二区| 国产精品欧美久久久久无广告 | 97精品伊人久久大香线蕉app|