快捷導(dǎo)航

C++中用哈希表封裝myunordered_set和myunordered_map方法詳解

更新時(shí)間：2026年05月05日 09:23:34 作者：進(jìn)擊的荊棘

這篇文章主要介紹了C++中用哈希表封裝myunordered_set和myunordered_map方法,封裝通用哈希表底層,快速實(shí)現(xiàn)myunordered_set和myunordered_map,掌握STL無(wú)序容器核心設(shè)計(jì),需要的朋友可以參考下

1.源碼及框架分析

SGI-STL30版本源代碼中沒(méi)有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，這兩個(gè)容器是C++11之后才更新的。但是SGI-STL30實(shí)現(xiàn)了哈希表，只是容器的名字是hash_map和hash_set，它是作為非標(biāo)準(zhǔn)容器出現(xiàn)的，非標(biāo)準(zhǔn)是指非C++標(biāo)準(zhǔn)規(guī)定必須實(shí)現(xiàn)的，源代碼在hash_map/hash_set/set_hash_map/stl_hash_set/stl_hashtable.h中

hash_map和hash_set的實(shí)現(xiàn)結(jié)構(gòu)框架核心部分截?。?/p>

//stl_hash_set
template<class Value,class HashFcn=hash<Value>,
            class EqualKey=equal_to<Value>,
            class Alloc=alloc>
class hash_set{
private:
    typedef hashtable<Value,Value,HashFcn,identity<Value>,
                                EqualKey,Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::const_iterator iterator;
    typedef typename ht::const_iterator const_iterator;
    hasher hash_funct() const {return rep.hash_funct();}
    key_equal key_eq() const {return rep.key_eq();}
};
//stl_hash_map
template<class Key,class T,class HashFcn=hash<Key>,
                    class EqualKey=equal_to<Key>,
                    class Alloc=alloc>
class hash_map{
private:
    typedef hashtable<pair<const Key,T>,Key,HashFcn,
                        selectlst<pair<const Key,T>>,EqualKey,Alloc> ht;
    ht rep;
public:
    typedef typename ht::key_type key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef typename ht::value_type value_type;
    typedef typename ht::hasher hasher;
    typedef typename ht::key_equal key_equal;
    typedef typename ht::iterator iterator;
    typedef typename ht::const_iterator const_iterator;
};
//stl_hashtable.h
template<class Value,class Key,class HashFcn,
            class ExtractKey,class EqualKey,
            class Alloc>
class hashtable{
public:
    typedef Key key_type;
    typedef Value value_type;
    typedef HashFcn hasher;
    typedef EqualKey key_equal;
private:
    hasher hash;
    key_equal equals;
    ExtractKey get_key;
    typedef __hashtable_node<Value> node;
    vector<node*,Alloc> buckets;
    size_type num_elements;
public:
    typedef __hashtable_iterator<Value,Key,HashFcn,ExtractKey,EqualKey,
                Alloc> itertor;
    pair<iterator,bool> insert_unique(const value_type& obj);
    const_iterator find(const key_type& key) const;
};
template<class Value>
struct __hashtable_node{
    __hahstable_node* next;
    Value val;
};

●通過(guò)源碼可以看到，結(jié)構(gòu)上hash_map和hash_set跟map和set的完全類似，復(fù)用同一個(gè)hashtable實(shí)現(xiàn)key和key/value結(jié)構(gòu)，hash_set傳給hash_ table的是兩個(gè)key，hash_map傳給hash_table的是pair<const key,value>

●需要注意源碼里面跟map/set源碼類似，命名風(fēng)格比較亂，這里比map和set還亂，hash_set模板參數(shù)居然用的Value命名，hash_map用的是Key和T命名。

2.模擬實(shí)現(xiàn)

2.1實(shí)現(xiàn)出復(fù)用哈希表的框架并支持insert

●unordered_map和unordered_set復(fù)用之前實(shí)現(xiàn)的哈希表。

●key參數(shù)用K，value參數(shù)用V，哈希表中數(shù)據(jù)類型，使用T。

●其次跟map和set相比而言u(píng)nordered_map和unordered_set的模擬實(shí)現(xiàn)類結(jié)構(gòu)更復(fù)雜一點(diǎn)，但是大框架和思路完全類似。一i那位HashTable實(shí)現(xiàn)了泛型不知道T參數(shù)到底是K，還是pair<K,V>，那么insert內(nèi)部進(jìn)行插入時(shí)要用K對(duì)象轉(zhuǎn)換成整型取模和K比較相等，因?yàn)閜air的value不參與計(jì)數(shù)取模，且默認(rèn)支持的key和value一起比較相等，需要時(shí)的任何時(shí)候只需要比較K對(duì)象，所以在unordered_map和unordered_set層分別實(shí)現(xiàn)一個(gè)MapKeyOfT和SetKeyOfT的仿函數(shù)傳給HashTable的KeyOfT，然后HashTable中通過(guò)KEyOfT仿函數(shù)取出T類型對(duì)象中的K對(duì)象，再轉(zhuǎn)換成整型取模和K比較相等。

namespace Achieve{
    template<class K,class Hash=HashFunc<K>>
    class unordered_set{
        struct SetKeyOfT{
            const K& operator()(const K& kv){
                return key;
            }
        };
    public:
        bool insert(const K& key){
            return _ht.Insert(key);
        }
    private:
        hash_buckte::HashTable<K,K,SetKeyOfT,Hash> _ht;
    };
}
namespace Achieve{
    template<class K,class V,class Hash=HashFunc<K>>
    class unordered_map{
        struct MapKeyOfT{
            const K& operator()(const pair<K,V>& kv){
                return kv.first;
            }
        };
    public:
        bool insert(const pair<K,V>& kv){
            return _ht.Insert(kv);
        }
    private:
        hash_buckte::HashTable<K,pair<K,V>,MapKeyOfT,Hash> _ht;
    };
}
inline unsigned long __stl_next_prime(unsigned long n){
    //Note:assumes long is at least 32 bits
    static const int __stl_num_primes=28;
    static const unsigned long __stl_prime_list[__stl_num_primes]={
        53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
    };
    const unsigned long* first=__stl_prime_list;
    const unsigned long* last=__stl_prime_list+__stl_num_primes;
    const unsigned long* pos=lower_bound(first,last,n);
    return pos==last?*(last-1):*pos;
}
namespace hash_buckte{
    template<class T>
    struct HashNode{
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data)
            :_data(data)
            ,_next(nullptr)
        {}
    };
    template<class K,class T,class KeyOfT,class Hash>
    class HashTable{
        typedef HashNode<T> Node;
    public:
        HashTable()
            :_tables(__stl_next_prime(0))
            ,_n(0)
        {}
        ~HashTable(){
            for(int i=0;i<_tables.size();i++){
                Node* cur=_tables[i];
                while(cur){
                    Node* next=cur->_next;
                    delete cur;
                    cur=next;
                }
                _tables[i]=nullptr;
            }
        }
        bool Insert(const T& data){
            KeyOfT kot;
            Hash hash;
            Iterator it=Find(kot(data));
            if(it!=End()) return false;
            //當(dāng)負(fù)載因子為1時(shí)，擴(kuò)容
            if(_n==_tables.size()){
                //直接復(fù)用Insert，不好
                /*HashTable<K,V> newht;
                newht._tables.resize(_tables.size()*2);
                for(int i=0;i<_tables.size();i++){
                    Node* cur=_tables[i];
                    while(cur){
                        newht.Insert(cur);
                        cur=cur->_next;
                    }
                }
                _tables.swap(newht);*/
                vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
                //newht._tables.resize(_tables.size()*2);
                //newht._tables.resize(__stl_next_prime(_tables.size()+1));
                for(int i=0;i<_tables.size();i++){
                    Node* cur=_tables[i];
                    while(cur){
                        Node* next=cur->_next;
                        size_t hash1=hash(kot(cur->_data))%newTable.size();
                        //頭插
                        cur->_next=newTable[hash1];
                        newTable[hash1]=cur;
                        cur=next;
                    }
                    _tables[i]=nullptr;
                }
                _tables.swap(newTable);
            }
            //頭插
            size_t hash1=hash(kot(data))%_tables.size();
            Node* newNode=new Node(data);
            newNode->_next=_tables[hash1];
            _tables[hash1]=newNode;
            ++_n;
            return true;
        }
    private:
        vector<Node*> _tables;
        size_t _n;
    };
}

2.2支持iterator的實(shí)現(xiàn)

iterator核心源代碼

template<class Value,class Key,class HashFcn,
            class ExtractKey,class EqualKey,class Alloc>
struct __hashtable_iterator{
    typedef hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>
            hashtable;
    typedef __hashtable_iterator<Value,Key,HashFcn,
                                ExtractKey,EqualKey,Alloc>
            iterator;
    typedef __hashtable_const_iterator<Value,Key,HashFcn,ExtraceKey,EqualKey,Alloc>
            const_iterator;
    typedef __hashtable_node<Value> node;
    typedef forward_iterator_tag iterator_vategory;
    typedef Value value_type;
    node* cur;
    hashtable* ht;
    __hashtable_iterator(node* n,hashtable* tab): cur(n),ht(tab) {}
    __hashtable_iterator() {}
    reference operator*() const { return cur->val;}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const {return &(operator*());}
#endif /*__SGI_STL_NO_ARROW_OPERATOR*/
    iterator& operator++();
    iterator operator++(int);
    bool operator==(const iterator& it) const {return cur==it.cur;}
    bool operator!=(const iterator& it) const {return cur!=it.cur;}
template<class V,class K,class HF,class ExK,class EqK,class A>
__hashtable_iterator<V,K,HF,ExK,EqK,A>&
__hashtable_iterator<V,K,HF,ExK,EqK,A>::operator++(){
    const node* old=cur;
    cur=cur->next;
    if(!cur){
        size_type bucket=ht->bkt_num(old->val);
        while(!curL&&++bucket<ht->buckets.size())
            cur=ht->buckets[bucket];
    }
    return *this;
}

iterator實(shí)現(xiàn)思路分析

●iterator實(shí)現(xiàn)的大框架跟list的iterator思路是一致的，用一個(gè)類型封裝節(jié)點(diǎn)的指針，再通過(guò)重載運(yùn)算符實(shí)現(xiàn)，迭代器像指針一樣訪問(wèn)的行為，要注意哈希表的迭代器是單向迭代器。

●難點(diǎn)是operator++的實(shí)現(xiàn)。iterator中有一個(gè)指向節(jié)點(diǎn)的指針，若當(dāng)前桶下面還有節(jié)點(diǎn)，則節(jié)點(diǎn)的指針指向下一個(gè)節(jié)點(diǎn)即可。若當(dāng)前桶走完了，則需要想辦法計(jì)算找到下一個(gè)桶。這里的難點(diǎn)反而是結(jié)構(gòu)設(shè)計(jì)的問(wèn)題，上面的源碼，我們可以看到iterator中除了有節(jié)點(diǎn)的指針，還有哈希桶對(duì)象的指針，這樣當(dāng)前桶走完了，要計(jì)算下一個(gè)桶就相對(duì)容易多了，用key值計(jì)算出當(dāng)前桶位置，依次往后找下一個(gè)不為空的桶即可。

●begin（）返回第一個(gè)桶中的第一個(gè)節(jié)點(diǎn)指針構(gòu)造的迭代器，這里end（）返回迭代器可以用空表示。

●unoedered_set的iterator也不支持修改，把unordered_set的第二個(gè)模板參數(shù)改成const K即可，HashTable<k,const K,SetKeyOfT,Hash> _ht;

●unordered_map的iterator不支持修改key但是可以修改value，把unordered_map的第二個(gè)模板參數(shù)pair的第一個(gè)參數(shù)改成const K即可，HashTable<K,pair<const K,V>,MapKeyOfT,Hash> _ht;

2.3map支持[]

●unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中的insert返回值為pair<Iterator,bool> Insert(const T& data)

2.4Achieve::unordered_map和Achieve::unordered_set代碼實(shí)現(xiàn)

namespace Achieve{
    template<class K,class Hash=HashFunc<K>>
    class unordered_set{
        struct KeyOfT{
            const K& operator()(const K& key){
                return key;
            }
        };
    public:
        typedef typename hash_buckte::HashTable<K,const K,KeyOfT,Hash>::Iterator iterator;
        typedef typename hash_buckte::HashTable<K,const K,KeyOfT,Hash>::ConstIterator const_iterator;
        iterator begin(){
            return _ht.Begin();
        }
        iterator end(){
            return _ht.End();
        }
        const_iterator begin() const{
            return _ht.Begin();
        }
        const_iterator end() const{
            return _ht.End();
        }
        pair<iterator,bool> insert(const K& key){
            return _ht.Insert(key);
        }
        iterator Find(const K& key){
            return _ht.Find(key);
        }
        bool erase(const K& key){
            return _ht.Erase(key);
        }
    private:
        hash_buckte::HashTable<K,const K,KeyOfT,Hash> _ht;
    };
            void print(const unordered_set<int>& s){
            unordered_set<int>::const_iterator it=s.begin();
            while(it!=s.end()){
                cout<<*it<<" ";
                ++it;
            }
            cout<<endl;
            for(auto e:s){
                cout<<e<<' ';
            }
            cout<<endl;
        }
        void test_set(){
            int a[]={3,11,86,88,1,881,5,6,7,6};
            unordered_set<int> s;
            for(auto e:a){
                s.insert(e);
            }
            unordered_set<int>::iterator it=s.begin();
            while(it!=s.end()){
                cout<<*it<<" ";
                ++it;
            }
            cout<<endl;
            for(auto e:s){
                cout<<e<<' ';
            }
            cout<<endl;
            print(s);
        }
}
namespace Achieve{
    template<class K,class V,class Hash=HashFunc<K>>
    class unordered_map{
        struct MapKeyOfT{
            const K& operator()(const pair<K,V>& kv){
                return kv.first;
            }
        };
    public:
        typedef typename hash_buckte::HashTable<K,pair<const K,V>,MapKeyOfT,Hash>::Iterator iterator;
        typedef typename hash_buckte::HashTable<K,pair<const K,V>,MapKeyOfT,Hash>::ConstIterator const_iterator;
        iterator begin(){
            return _ht.Begin();
        }
        iterator end(){
            return _ht.End();
        }
        const_iterator begin() const{
            return _ht.Begin();
        }
        const_iterator end() const{
            return _ht.End();
        }
        V& operator[](const K& key){
            pair<iterator,bool> ret=insert({key,V()});
            return ret.first->second;
        }
        pair<iterator,bool> insert(const pair<K,V>& kv){
            return _ht.Insert(kv);
        }
        iterator Find(const K& key){
            return _ht.Find(key);
        }
        bool erase(const K& key){
            return _ht.Erase(key);
        }
    private:
        hash_buckte::HashTable<K,pair<const K,V>,MapKeyOfT,Hash> _ht;
    };
    void test_map(){
        unordered_map<string,string> dict;
        dict.insert({"sort","排序"});
        dict.insert({"字符串","string"});
        dict.insert({"sort","排序"});
        dict.insert({"left","左邊"});
        dict.insert({"right","右邊"});
        dict["left"]="左邊、剩余";
        dict["insert"]="插入";
        dict["string"];
        for(auto& kv:dict){
            cout<<kv.first<<":"<<kv.second<<endl;
        }
        cout<<endl;
        unordered_map<string,string>::iterator it=dict.begin();
        while(it!=dict.end()){
            it->second+='x';
            cout<<it->first<<":"<<it->second<<endl;
            ++it;
        }
        cout<<endl;
    }
}
template<class K>
struct HashFunc{
    size_t operator()(const K& key){
        return (size_t)key;
    }
};
//特化
template<>
struct HashFunc<string>{
    size_t operator()(const string& s){
        //BKDR
        size_t hash=0;
        for(auto ch:s){
            hash+=ch;
            hash*=131;
        }
        return hash;
    }
};
inline unsigned long __stl_next_prime(unsigned long n){
    //Note:assumes long is at least 32 bits
    static const int __stl_num_primes=28;
    static const unsigned long __stl_prime_list[__stl_num_primes]={
        53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
    };
    const unsigned long* first=__stl_prime_list;
    const unsigned long* last=__stl_prime_list+__stl_num_primes;
    const unsigned long* pos=lower_bound(first,last,n);
    return pos==last?*(last-1):*pos;
}
namespace hash_buckte{
    template<class T>
    struct HashNode{
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data)
            :_data(data)
            ,_next(nullptr)
        {}
    };
    //前置聲明，防止HashIterator不認(rèn)識(shí)HashTable
    template<class K,class T,class KeyOfT,class Hash>
    class HashTable;
    template<class K,class T,class Ref,class Ptr,class KeyOfT,class Hash>
    struct HTIterator{
        typedef HashNode<T> Node;
        typedef HashTable<K,T,KeyOfT,Hash> HT;
        typedef HTIterator<K,T,Ref,Ptr,KeyOfT,Hash> Self;
        Node* _node;
        const HT* _ht;//取模時(shí)要用
        HTIterator(Node* node,const HT* ht)
            :_node(node)
            ,_ht(ht)
        {}
        Ref operator*(){
            return _node->_data;
        }
        Ptr operator->(){
            return &_node->_data;
        }
        bool operator!=(const Self& s){
            return _node!=s._node;
        }
        Self& operator++(){
            if(_node->_next){
                _node=_node->_next;
            }
            else{
                //找下一個(gè)不為空的桶
                Hash hash;
                KeyOfT kot;
                size_t hash0=hash(kot(_node->_data))%_ht->_tables.size();
                ++hash0;
                while(hash0<_ht->_tables.size()){
                    _node=_ht->_tables[hash0];                    
                    if(_node){
                        break;
                    }
                    else ++hash0;
                }
                //所有桶都走完了，end（）給的空的標(biāo)識(shí)的_node
                if(hash0==_ht->_tables.size()){
                    _node=nullptr;
                }                
            }
            return *this;
        }
    };
    template<class K,class T,class KeyOfT,class Hash>
    class HashTable{
        //友元聲明,為防止模板參數(shù)沖突，將參數(shù)改名
        template<class K1,class T1,class Ref,class Ptr,class KeyOfT1,class Hash1>
        friend struct HTIterator;
        typedef HashNode<T> Node;
    public:
        typedef HTIterator<K,T,T&,T*,KeyOfT,Hash> Iterator;
        typedef HTIterator<K,T,const T&,const T*,KeyOfT,Hash> ConstIterator;
        HashTable()
            :_tables(__stl_next_prime(0))
            ,_n(0)
        {}
        ~HashTable(){
            for(int i=0;i<_tables.size();i++){
                Node* cur=_tables[i];
                while(cur){
                    Node* next=cur->_next;
                    delete cur;
                    cur=next;
                }
                _tables[i]=nullptr;
            }
        }
        Iterator Begin(){
            if(_n==0){
                return End();
            }
            for(int i=0;i<_tables.size();i++){
                Node* cur=_tables[i];
                if(cur) return Iterator(cur,this);;
            }
            return End();
        }
        Iterator End(){
            return Iterator(nullptr,this);
        }
        ConstIterator Begin() const{
            if(_n==0){
                return End();
            }
            for(int i=0;i<_tables.size();i++){
                Node* cur=_tables[i];
                if(cur) return ConstIterator(cur,this);;
            }
            return End();
        }
        ConstIterator End() const{
            return ConstIterator(nullptr,this);
        }
        pair<Iterator,bool> Insert(const T& data){
            KeyOfT kot;
            Hash hash;
            Iterator it=Find(kot(data));
            if(it!=End()) return {it,false};
            //當(dāng)負(fù)載因子為1時(shí)，擴(kuò)容
            if(_n==_tables.size()){
                //直接復(fù)用Insert，不好
                /*HashTable<K,V> newht;
                newht._tables.resize(_tables.size()*2);
                for(int i=0;i<_tables.size();i++){
                    Node* cur=_tables[i];
                    while(cur){
                        newht.Insert(cur);
                        cur=cur->_next;
                    }
                }
                _tables.swap(newht);*/
                vector<Node*> newTable(__stl_next_prime(_tables.size()+1));
                //newht._tables.resize(_tables.size()*2);
                //newht._tables.resize(__stl_next_prime(_tables.size()+1));
                for(int i=0;i<_tables.size();i++){
                    Node* cur=_tables[i];
                    while(cur){
                        Node* next=cur->_next;
                        size_t hash1=hash(kot(cur->_data))%newTable.size();
                        //頭插
                        cur->_next=newTable[hash1];
                        newTable[hash1]=cur;
                        cur=next;
                    }
                    _tables[i]=nullptr;
                }
                _tables.swap(newTable);
            }
            //頭插
            size_t hash1=hash(kot(data))%_tables.size();
            Node* newNode=new Node(data);
            newNode->_next=_tables[hash1];
            _tables[hash1]=newNode;
            ++_n;
            return {Iterator(newNode,this),true};
        }
        Iterator Find(const K& key){
            KeyOfT kot;
            Hash hash;
            size_t hash0=hash(key)%_tables.size();
            Node* cur=_tables[hash0];
            while(cur){
                if(kot(cur->_data)==key)
                    return Iterator(cur,this);
                cur=cur->_next;
            }
            return End();
        }
        bool Erase(const K& key){
            KeyOfT kot;
            Hash hash;
            //沒(méi)有這個(gè)值
            if(!Find(key)) return false;
            size_t hash0=hash(key)%_tables.size();
            Node* cur=_tables[hash0];
            Node* prev=nullptr;
            while(cur){
                if(kot(cur->_data)==key){
                    //刪除的節(jié)點(diǎn)是鏈表的頭
                    if(!prev){
                        _tables[hash0]=cur->_next;
                    }
                    else{
                        prev->_next=cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                else{
                    prev=cur;
                    cur=cur->_next;
                }
            }
            return false;
        }
    private:
        vector<Node*> _tables;
        size_t _n;
    };
}

以上就是C++中用哈希表封裝myunordered_set和myunordered_map方法詳解的詳細(xì)內(nèi)容，更多關(guān)于C++封裝myunordered_set和myunordered_map的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: