• <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
            能寫一下注釋嗎?
            青春久久| AV狠狠色丁香婷婷综合久久| 88久久精品无码一区二区毛片| 精品国产乱码久久久久久郑州公司| 久久久久无码精品国产| 91久久精品视频| 久久这里只有精品首页| 久久婷婷综合中文字幕| 一本大道久久东京热无码AV| 中文字幕日本人妻久久久免费| 青青热久久综合网伊人| 久久精品青青草原伊人| Xx性欧美肥妇精品久久久久久| 欧美成a人片免费看久久| 国产成人精品综合久久久久| 亚洲乱亚洲乱淫久久| 伊人久久大香线蕉综合影院首页| 久久夜色精品国产亚洲| 无码精品久久久天天影视| 香蕉aa三级久久毛片| 韩国三级大全久久网站| 久久精品久久久久观看99水蜜桃| 97精品伊人久久久大香线蕉| 久久精品人人做人人爽电影蜜月| 人妻无码αv中文字幕久久琪琪布| 国产精品伊人久久伊人电影| 日日噜噜夜夜狠狠久久丁香五月| 久久国产V一级毛多内射| 久久午夜电影网| 2020久久精品国产免费| 久久99国产精品尤物| 色88久久久久高潮综合影院| 亚洲香蕉网久久综合影视| 四虎国产精品成人免费久久| 久久亚洲色一区二区三区| 久久久不卡国产精品一区二区| 久久精品一区二区| 99热成人精品免费久久| 99久久精品九九亚洲精品| 久久精品成人一区二区三区| 久久99精品久久久久久噜噜|