C++ 哈希表核心改造与 unordered_set、unordered_map 封装实现 | 极客日志

C++算法

C++ 哈希表核心改造与 unordered_set、unordered_map 封装实现

基于链地址法实现哈希表，通过改造模板参数和迭代器支持 Key 或 Key-Value 存储。详细阐述了哈希表的扩容、插入、查找、删除操作及迭代器重载逻辑，并在此基础上封装实现了标准库风格的 unordered_set 和 unordered_map 容器，包含完整的测试代码展示。

SparkGeek发布于 2026/3/15更新于 2026/4/183 浏览

C++ 哈希表核心改造与 unordered_set、unordered_map 封装实现

修改哈希表

我们基于链地址法实现的哈希表来封装实现 unordered_set 和 unordered_map ，但是由于实现的哈希表是 Key-Value 结构的并且我们的实现的哈希表缺少了迭代器，所以我们需要对之前实现的哈希表进行改造。

模板参数

HashNode
节点里不再存储确定的 pair<K, V> ，而是类型 T ，代表存储的数据可能是 key 或者 key-Value 。

template<class T>
struct HashNode {
    T _data;
    HashNode<T>* _next;
    HashNode(const T& data):_data(data),_next(nullptr){}
};

HashTable

template<class K,class T,class KeyOfT,class hash= HashFunc<K>>
class HashTable

K ：代表的是 key
T ：代表是存的可能是 key 或者 key-value
KeyOfT ：仿函数，目的是拿到 T 里面的 key

迭代器

哈希表的迭代器其实就是对节点指针进行封装，而且是单向迭代器，只需实现 ++ 即可。

//哈希表与迭代器相互依赖，需要前置声明
template<class K,class T,class KeyOfT,class hash>
class HashTable;
template< , , , , , >
  {
     HashNode<T> Node;
     HashTable<K, T, KeyOfT, Hash> HT;
     HTIterator<K, T, KeyOfT, Hash, Ref, Ptr> Self;
    Node* _node; 
     HT* _pht;
    (Node* node, HT* pht):_node(node),_pht(pht){}
    Ref *(){ _node->_data;}
    Ptr ->(){&_node->_data;}
     !=( Self& s){ _node != s._node;}
    Self& ++(){
};

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

Self& operator++(){
    //当前哈希桶还有数据，直接到下一个节点
    if(_node->_next){ 
        _node = _node->_next; 
    }
    //当前哈希桶走完了，寻找下一个不为空的哈希桶
    else if(_node->_next == nullptr){ 
        KeyOfT kot; 
        Hash hashfunc; 
        size_t hashi = hashfunc(kot(_node->_data)) % _pht->_tables.size();
        ++hashi;
        while(hashi < _pht->_tables.size()){ 
            _node = _pht->_tables[hashi]; //找到了下一个桶
            if(_node) break;
            else ++hashi; 
        }
        //处理迭代器在最后一个不为空的哈希桶的最后一个节点的情况
        if(hashi == _pht->_tables.size()){ 
            _node = nullptr; 
        }
    }
    return *this; 
}
Self& operator++(int){ 
    Self tmp = *this; 
    ++(*this); 
    return tmp; 
}

//构造函数
HashTable():_tables(__stl_next_prime(0)),_n(0){}

//拷贝构造函数
HashTable(const HashTable<K, T, KeyOfT, hash>& ht){ 
    _tables.resize(ht._tables.size());
    for(auto& data : ht){Insert(data);}
}

//赋值重载
HashTable<K, T, KeyOfT, hash>& operator=(const HashTable<K, T, KeyOfT, hash>& ht){ 
    vector<Node*>newtables(ht._tables.size());
    for(size_t i = 0; i < ht._tables.size();++i){ 
        Node* cur = ht._tables[i];
        while(cur){ 
            Node* newnode = new Node(cur->_data); 
            newnode->_next = newtables[i]; 
            newtables[i]= newnode; 
            cur = cur->_next; 
        }
    } 
    _tables.swap(newtables);
    return *this; 
}

//析构函数
~HashTable(){
    for(size_t i = 0; i < _tables.size();++i){ 
        Node* cur = _tables[i];
        while(cur){ 
            Node* next = cur->_next;
            delete cur; 
            cur = next; 
        } 
        _tables[i]=nullptr; 
    }
}

typedef HTIterator<K, T, KeyOfT, hash, T&, T*> Iterator;
typedef HTIterator<K, T, KeyOfT, hash,const T&,const T*> Const_Iterator;

Iterator begin(){
    if(_n == 0)return end();
    for(size_t i = 0; i < _tables.size();++i){ 
        Node* cur = _tables[i];
        if(cur){return Iterator(cur,this);}
    }
    return end();
}
Iterator end(){return Iterator(nullptr,this);}

Const_Iterator begin()const{
    if(_n == 0)return end();
    for(size_t i = 0; i < _tables.size();++i){ 
        Node* cur = _tables[i];
        if(cur){return Const_Iterator(cur,this);}
    }
}
Const_Iterator end()const{return Const_Iterator(nullptr,this);}

void CheckCapacity(){
    if(_n == _tables.size()){
        //把哈希桶里的链表每个节点拆下来插入 newht 效率太低了
        /*HashTable<K, V> newht; 
         newht._tables.resize(__stl_next_prime(_tables.size() + 1)); 
         for (size_t i = 0; i < _tables.size(); ++i) { 
             Node* cur = _tables[i]; 
             while (cur) { 
                 newht.Insert(cur->_kv); 
                 cur = cur->_next; 
             } 
         } 
         _tables.swap(newht._tables);*/ 
         KeyOfT kot; 
         hash hashfunc; 
         vector<Node*>newtables(__stl_next_prime(_tables.size()+1));
         for(size_t i = 0; i < _tables.size();++i){ 
             Node* cur = _tables[i];
             while(cur){ 
                 Node* next = cur->_next; 
                 size_t hashi = hashfunc(kot(cur->_data)) % newtables.size();
                 //头插 
                 cur->_next = newtables[hashi]; 
                 newtables[hashi]= cur; 
                 cur = next; 
             }
             _tables[i]=nullptr; 
         } 
         _tables.swap(newtables); 
    }
}

pair<Iterator,bool> Insert(const T& data){ 
    KeyOfT kot; 
    Iterator it = Find(kot(data));
    //不等于 end() 说明哈希表里有重复元素
    if(it != end())return{ it,false};
    
    //检查是否需要扩容
    CheckCapacity(); 
    
    hash hashfunc; 
    size_t hashi = hashfunc(kot(data)) % _tables.size(); 
    Node* newnode = new Node(data); 
    newnode->_next = _tables[hashi]; 
    _tables[hashi]= newnode;
    ++_n;
    return{Iterator(newnode,this),true};
}

Iterator Find(const K& key){ 
    KeyOfT kot; 
    hash hashfunc; 
    size_t hashi = hashfunc(key) % _tables.size(); 
    Node* cur = _tables[hashi];
    while(cur){
        if(kot(cur->_data)== key){return Iterator(cur,this);} 
        cur = cur->_next; 
    }
    //没找到就返回
    return end();
}

bool Erase(const K& key){ 
    KeyOfT kot; 
    hash hashfunc; 
    size_t hashi = hashfunc(key) % _tables.size(); 
    Node* prev = nullptr; 
    Node* cur = _tables[hashi];
    while(cur){
        if(kot(cur->_data)== key){
            //删除头节点的情况
            if(prev == nullptr){ 
                _tables[hashi]= cur->_next; 
            }
            //非头节点的情况
            else{ 
                prev->_next = cur->_next; 
            }
            delete cur;
            --_n;
            return true;
        }else{ 
            prev = cur; 
            cur = cur->_next; 
        }
    }
    return false;
}

template<class K,class hash= HashFunc<K>>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key){return key;}
    };
public:
    typedef typename HashTable<K,const K, SetKeyOfT, hash>::Iterator iterator;
    typedef typename HashTable<K,const K, SetKeyOfT, hash>::Const_Iterator 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:
    HashTable<K,const K, SetKeyOfT, hash> _ht;
};

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 HashTable<K, pair<const K, V>, MapKeyOfT, hash>::Iterator iterator;
    typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, hash>::Const_Iterator 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 pair<K, V>& kv){return _ht.Insert(kv);}
    V& operator[](const K& key){ 
        pair<iterator,bool> ret = Insert({ key,V()});
        return ret.first->second; 
    }
    iterator Find(const K& key){return _ht.Find(key);}
    bool Erase(const K& key){return _ht.Erase(key);}
private:
    HashTable<K, pair<const K, V>, MapKeyOfT, hash> _ht;
};