• <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
            能寫一下注釋嗎?
            久久亚洲欧美国产精品| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久久久久精品免费看SSS| 97精品国产97久久久久久免费| 五月丁香综合激情六月久久| 国产精品久久久久久搜索| 国产精品伦理久久久久久| 国产精品久久久香蕉| 国内精品久久久久久野外| 亚洲精品乱码久久久久久蜜桃 | 久久精品水蜜桃av综合天堂| 国产99久久久国产精品~~牛| 亚洲欧美国产精品专区久久| 久久精品国产99国产精偷| 精品久久久无码21p发布| 久久这里只有精品久久| 久久亚洲av无码精品浪潮| 久久亚洲精品国产精品| 人妻丰满?V无码久久不卡| 亚洲成人精品久久| 无码精品久久久天天影视| 久久久99精品成人片中文字幕| 国产情侣久久久久aⅴ免费| 亚洲精品国产自在久久| 久久精品国产亚洲av瑜伽| AAA级久久久精品无码片| 99久久综合国产精品免费| 日韩精品国产自在久久现线拍| 日韩人妻无码精品久久免费一 | 色综合久久久久无码专区| 亚洲乱码日产精品a级毛片久久| 久久精品国产福利国产秒| 久久午夜夜伦鲁鲁片免费无码影视| 久久高潮一级毛片免费| 久久精品中文字幕有码| 久久精品www| 国产一区二区精品久久凹凸 | 久久大香香蕉国产| 精品国产乱码久久久久久郑州公司| 亚洲午夜久久久久妓女影院| 亚洲精品无码久久久久久|