C++ 哈希表封装实战：unordered_map/set 底层原理与完整实现

这里我们就不再画图分析了，通过源码可以看到，结构上 hash_map 和 hash_set 跟 map 和 set 的完全类似，复用同一个 hashtable 实现 key 和 key/value 结构，hash_set 传给 hash_table 的是两个 key，hash_map 传给 hash_table 的是 pair<const key,value}。

需要注意的是源码里面跟 map/set 源码类似，命名风格比较乱，这里比 map 和 set 还乱，hash_set 模板参数居然用的 Value 命名，hash_map 用的是 Key 和 T 命名。

二。核心设计思路：哈希表的泛型复用

myunordered_map 和 myunordered_set 复用同一哈希表底层，核心通过模板参数抽象和仿函数提取 key，实现'一颗哈希表适配两种存储场景'：

• myunordered_set：存储单个 key（去重 + 无序），需提取 key 本身进行哈希和比较；
• myunordered_map：存储 key-value 对（key 去重 + 无序），需提取 pair 中的 first 作为 key 进行哈希和比较。

2.1 哈希表模板参数设计

哈希表需支持三种核心抽象，通过模板参数暴露接口，适配不同容器需求：

template<class K,class T,class KeyofT,class Hash>
class HashTable{
    // K：哈希和查找时的 key 类型（myunordered_set 为 K，myunordered_map 为 K）
    // T：哈希表节点存储的实际数据类型（myunordered_set 为 K，myunordered_map 为 pair<const K, V>）
    // Hash：哈希函数仿函数（将 K 转为整形用于计算桶位置）
    // KeyOfT：从 T 中提取 K 的仿函数（适配 T 的不同类型）
};

三。实现出复用哈希表的框架，并支持 insert

参考源码框架，unordered_set 和 unordered_map 复用之前我们实现的哈希表。

我们这里相比源码调整一下，key 参数就用 K，value 参数就用 V，哈希表中的数据类型，我们使用 T。

其次跟 map 和 set 相比而言 unordered_map 和 unordered_set 的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为 HashTable 实现了泛型不知道 T 参数导致是 K，还是 pair<K, V>，那么 insert 内部进行插入时要 K 对象转换成整形取模和 K 比较相等，因为 pair 的 value 不参与计算取模，且默认支持的是 key 和 value 一起比较相等，我们需要的时候只需要比较 K 对象，所以我们在 unordered_map 和 unordered_set 层分别实现一个 MapKeyOfT 和 SetKeyOfT 的仿函数传给 HashTable 的 KeyOfT，然后 HashTable 中通过 KeyOfT 仿函数取出 T 类型对象中的 K 对象，再转换成整形取模和 K 比较相等，具体细节参考如下代码实现。

// MyUnorderedSet.h
namespace Lotso {
template<class K,class Hash= HashFunc<K>>
class unordered_set{
    struct SetKeyofT{
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const K& key){return key;}
    };
public:
    bool insert(const K& key){return _ht.Insert(key);}
private:
    hash_bucket::HashTable<K,const K, SetKeyofT, Hash> _ht;
};
}

// MyUnorderedMap.h
namespace Lotso {
template<class K,class V,class Hash= HashFunc<K>>
class unordered_map{
    struct MapKeyofT{
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const pair<const K, V>& kv){return kv.first;}
    };
public:
    bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}
private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash> _ht;
};
}

// HashTable.h
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 质数表 (SGI STL 同款，用于扩容)
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
};

inline unsigned long __stl_next_prime(unsigned long n){
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    // >= n
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

// 哈希函数仿函数
template<class K>
struct HashFunc{
    size_t operator()(const K& key){
        return (size_t)key; // 默认直接转换
    }
};

// 特化 string 类型的哈希函数
template<>
struct HashFunc<string>{
    // BKDR 字符串哈希算法
    size_t operator()(const string& key){
        size_t hash = 0;
        for(auto ch : key){
            hash += ch; // 累加字符 ASCII 码
            hash *= 131; // 乘质数 131，减少冲突
        }
        return hash;
    }
};

namespace hash_bucket {
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= HashFunc<K>>
class HashTable{
    typedef HashNode<T> Node;
    HashTable():_tables(__stl_next_prime(1),nullptr),_n(0){}
    ~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;
        }
        _n = 0;
    }
    bool Insert(const T& data){
        KeyofT kot; Hash hs;
        // 先查找，避免重复插入
        if(Find(kot(data))) return false;
        // 负载因子 == 1 就开始扩容
        if(_n == _tables.size()){
            std::vector<Node*> newtables(__stl_next_prime(_tables.size()+1),nullptr);
            for(size_t i = 0; i < _tables.size(); i++){
                // 遍历旧表，旧表节点重新映射，挪动到新表
                Node* cur = _tables[i];
                while(cur){
                    Node* next = cur->_next;
                    // 头插
                    size_t hashi = hs(kot(cur->_data)) % newtables.size();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i]=nullptr;
            }
            _tables.swap(newtables);
        }
        size_t hashi = hs(kot(data)) % _tables.size();
        // 头插
        Node* newnode = new Node(data);
        newnode->_next = _tables[hashi];
        _tables[hashi] = newnode;
        ++_n;
        return true;
    }
private:
    std::vector<Node*> _tables;
    size_t _n;
};
}

四。实现 iterator 和 map 支持 [] 的功能

4.1 迭代器实现：支持哈希桶遍历

iterator 实现思路分析：

• iterator 实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
• 这里的难点是 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点反而是结构设计的问题，参考上面的源码，我们可以看到 iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶即可。
• begin() 返回第一个桶中第一个节点指针构造的迭代器，这里 end() 返回迭代器可以用空表示。
• unordered_set 的 iterator 也不支持修改，我们把 unordered_set 的第二个模板参数改成 const K 即可，HashTable<K, const K, SetKeyOfT, Hash> _ht;
• unordered_map 的 iterator 不支持修改 key 但是可以修改 value，我们把 unordered_map 的第二个模板参数 pair 的第一个参数改成 const K 即可，HashTable<K, pair<const K, V>,MapKeyOfT, Hash> _ht;
• 支持完整的迭代器还有很多细节需要修改，具体参考最后的代码。

// 哈希表迭代器
template<class K,class T,class Hash,class KeyOfT,class Equal>
struct HashTableIterator{
    typedef HashNode<T> Node;
    typedef HashTable<K, T, Hash, KeyOfT, Equal> HashTable;
    typedef HashTableIterator Self;
    Node* _node; // 当前指向的节点
    HashTable* _ht; // 指向哈希表，用于桶切换

    // 构造函数
    HashTableIterator(Node* node, HashTable* ht):_node(node),_ht(ht){}

    // 解引用运算符（返回节点数据引用）
    T& operator*(){return _node->_data;}

    // 箭头运算符（支持->访问成员，如 map 的 first/second）
    T* operator->(){return &_node->_data;}

    // 前置++（核心：遍历当前桶所有节点后，切换到下一个非空桶）
    Self& operator++(){
        if(_node->_next){
            // 当前桶还有下一个节点，直接移动
            _node = _node->_next;
        }else{
            // 当前桶遍历完毕，找下一个非空桶
            K key = _ht->_kot(_node->_data);
            size_t hashi = _ht->_hash(key) % _ht->_tables.size();
            // 从当前桶的下一个桶开始查找
            ++hashi;
            while(hashi < _ht->_tables.size()){
                if(_ht->_tables[hashi]){
                    _node = _ht->_tables[hashi];
                    return *this;
                }
                ++hashi;
            }
            // 所有桶遍历完毕，迭代器失效（指向 nullptr）
            _node = nullptr;
        }
        return *this;
    }

    // 相等判断
    bool operator==(const Self& s)const{return _node == s._node;}

    // 不相等判断
    bool operator!=(const Self& s)const{return _node != s._node;}
};

4.2 map 支持 []

• unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为 pair<Iterator, bool> Insert(const T& data)
• 有了 insert 支持 [] 实现就很简单了，具体参考下面代码实现

五。完整代码实现

5.1 HashTable.h

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 质数表 (SGI STL 同款，用于扩容)
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
};

inline unsigned long __stl_next_prime(unsigned long n){
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    // >= n
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

// 哈希函数仿函数
template<class K>
struct HashFunc{
    size_t operator()(const K& key){
        return (size_t)key; // 默认直接转换
    }
};

// 特化 string 类型的哈希函数
template<>
struct HashFunc<string>{
    // BKDR 字符串哈希算法
    size_t operator()(const string& key){
        size_t hash = 0;
        for(auto ch : key){
            hash += ch; // 累加字符 ASCII 码
            hash *= 131; // 乘质数 131，减少冲突
        }
        return hash;
    }
};

namespace hash_bucket {
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;
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* _pht;
    HTIterator(Node* node,const HT* pht):_node(node),_pht(pht){}
    Ref operator*(){return _node->_data;}
    Ptr operator->(){return&_node->_data;}
    Self& operator++(){
        if(_node->_next)//当前桶没走完
        {
            _node = _node->_next;
        }else//当前桶走完了，找到下一个桶的第一个结点
        {
            KeyofT kot; Hash hs;
            // 算出当前位置
            size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
            // ++到下一个位置
            ++hashi;
            while(hashi < _pht->_tables.size()){
                if(_pht->_tables[hashi])// 找到下一个不为空的桶
                {
                    _node = _pht->_tables[hashi];
                    break;
                }else{
                    ++hashi;
                }
            }
            if(hashi == _pht->_tables.size())// 最后一个桶走完了，要++到 end() 位置
            {// end() 中_node 是空
                _node = nullptr;
            }
        }
        return *this;
    }
    bool operator!=(const Self& s)const{return _node != s._node;}
    bool operator==(const Self& s)const{return _node == s._node;}
};

template<class K,class T,class KeyofT,class Hash= HashFunc<K>>
class HashTable{
    // 友元声明
    template<class K,class T,class Ref,class Ptr,class KeyofT,class Hash>
    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;
    
    Iterator Begin(){
        if(_n == 0){return End();}
        for(size_t i = 0; i < _tables.size(); i++){
            if(_tables[i]){
                return Iterator(_tables[i],this);
            }
        }
        return End();
    }
    Iterator End(){return Iterator(nullptr,this);}
    ConstIterator Begin()const{
        if(_n == 0){return End();}
        for(size_t i = 0; i < _tables.size(); i++){
            if(_tables[i]){
                return ConstIterator(_tables[i],this);
            }
        }
        return End();
    }
    ConstIterator End()const{return ConstIterator(nullptr,this);}

    HashTable():_tables(__stl_next_prime(1),nullptr),_n(0){}
    ~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;
        }
        _n = 0;
    }
    pair<Iterator,bool>Insert(const T& data){
        KeyofT kot; Hash hs;
        // 先查找，避免重复插入
        if(auto it = Find(kot(data));it!=End())return{it,false};
        // 负载因子 == 1 就开始扩容
        if(_n == _tables.size()){
            std::vector<Node*> newtables(__stl_next_prime(_tables.size()+1),nullptr);
            for(size_t i = 0; i < _tables.size(); i++){
                // 遍历旧表，旧表节点重新映射，挪动到新表
                Node* cur = _tables[i];
                while(cur){
                    Node* next = cur->_next;
                    // 头插
                    size_t hashi = hs(kot(cur->_data)) % newtables.size();
                    cur->_next = newtables[hashi];
                    newtables[hashi] = cur;
                    cur = next;
                }
                _tables[i]=nullptr;
            }
            _tables.swap(newtables);
        }
        size_t hashi = hs(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 hs;
        size_t hashi = hs(key) % _tables.size();
        Node* cur = _tables[hashi];
        while(cur){
            if(kot(cur->_data)== key){return{ cur ,this};}
            cur = cur->_next;
        }
        return{nullptr,this};
    }
    bool Erase(const K& key){
        KeyofT kot; Hash hs;
        size_t hashi = hs(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;
                }
                --_n;
                delete cur;
                return true;
            }
            prev = cur; cur = cur->_next;
        }
        return false;
    }
private:
    std::vector<Node*> _tables;
    size_t _n;
};
}

5.2 unordered_set.h

#pragma once
#include"HashTable.h"
namespace Lotso {
template<class K,class Hash= HashFunc<K>>
class unordered_set{
    struct SetKeyofT{
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const K& key){return key;}
    };
public:
    typedef typename hash_bucket:: HashTable<K,const K, SetKeyofT, Hash>::Iterator iterator;
    typedef typename hash_bucket::HashTable<K,const K, SetKeyofT, 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_bucket::HashTable<K,const K, SetKeyofT, Hash> _ht;
};
}

5.3 unordered_map.h

#pragma once
#include"HashTable.h"
namespace Lotso {
template<class K,class V,class Hash= HashFunc<K>>
class unordered_map{
    struct MapKeyofT{
        // 仿函数：从 T（pair<const K, V>）中提取 key
        const K& operator()(const pair<const K, V>& kv){return kv.first;}
    };
public:
    typedef typename hash_bucket::HashTable<K, pair<const K,V>, MapKeyofT, Hash>::Iterator iterator;
    typedef typename hash_bucket::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();}
    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:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyofT, Hash> _ht;
};
}

5.4 测试代码 (test.cpp)

#define_CRT_SECURE_NO_WARNINGS 1
#include"HashTable.h"
#include"unordered_set.h"
#include"unordered_map.h"

void Print(const Lotso::unordered_set<int>& s){
    Lotso::unordered_set<int>::const_iterator it = s.begin();
    while(it != s.end()){
        //*it = 1;
        cout <<*it <<" ";
        ++it;
    }
    cout << endl;
}

int main(){
    Lotso::unordered_set<int> us;
    us.insert(3);
    us.insert(1000);
    us.insert(2);
    us.insert(102);
    us.insert(2111);
    us.insert(22);
    Lotso::unordered_set<int>::iterator it = us.begin();
    while(it != us.end()){
        //*it = 1;
        cout <<*it <<" ";
        ++it;
    }
    cout << endl;
    Print(us);
    
    Lotso::unordered_map<string, string> dict;
    dict.insert({"string","字符串"});
    dict.insert({"string","字符串"});
    dict.insert({"left","左边"});
    dict.insert({"right","右边"});
    // 修改
    dict["left"]="左边，剩余";
    // 插入
    dict["insert"];
    // 插入 + 修改
    dict["map"]="地图";
    for(auto&[k, v]: dict){
        //k += 'x';//v += 'x';
        cout << k <<":"<< v << endl;
    }
    return 0;
}

结语

myunordered_map 和 myunordered_set 的封装核心是'哈希表泛型复用 + 仿函数解耦'—— 通过模板参数抽象不同容器的存储需求，用仿函数屏蔽 key 提取、哈希计算、相等比较的差异，最终实现'一套底层哈希表，支撑两种容器功能'。掌握这套封装逻辑，不仅能理解 STL unordered 系列容器的底层实现，更能学会'泛型编程 + 接口抽象'的设计思想，在实际开发中灵活适配不同存储场景。如果需要扩展功能（如支持自定义哈希函数、解决极端哈希冲突），可基于本文代码进一步优化。