C++ 进阶：unordered_set 与 unordered_map 模拟实现

stl_hash_set

/*-------------------------- stl_hash_set --------------------------*/
// 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

/*-------------------------- stl_hash_map --------------------------*/
// 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, select1st<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;
};

代码结构设计

unordered_set/map 容器的结构

头文件实现

HashTable.h

这是底层哈希表的核心实现，采用了链地址法处理冲突，并包含了哈希函数特化、扩容逻辑以及迭代器设计。

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

/*------------------任务：定义哈希表函数的'通用类模板'------------------*/
template<class K>
struct HashFunc {
    // 重载 () 运算符 ---> 作用：将 K 类型转化为 size_t 类型，用于计算哈希值
    size_t operator()(const K& key) {
        return (size_t)key; // 注意：默认为直接转换，适用于 int、long 等整数类型
    }
};

/*------------------任务：定义哈希函数的'模板特化'------------------*/
template<>
struct HashFunc<string> {
    // 实现：'() 运算符的重载' ---> 作用：将 string 类型的变量转化为哈希值
    size_t operator()(const string& s) {
        // 定义 size_t 类型变量记录 string 类型的变量计算的哈希值
        size_t hash = 0;
        // 使用范围 for 循环遍历字符串并用 BKDR 算法计算其哈希值
        for (auto it : s) {
            // 先将字符的 ASCII 值累加到哈希值中
            hash += it;
            // 再让哈希值乘以质数 131（BKDR 哈希算法认为：131 可有效减少冲突）
            hash *= 131;
        }
        // 返回最终计算的哈希值
        return hash;
    }
};

/*------------------任务：实现'获取下一个 >=n 的质数的函数'---> '用于哈希表扩容'------------------*/
inline unsigned long _stl_next_prime(unsigned long n) {
    // 指定素数表的大小
    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
    };
    // 使用二分查找找到第一个 >=n 的素数
    // 使用一个指针指向素数表中的'第一个素数'
    const unsigned long* first = _stl_prime_list;
    // 使用一个指针指向素数表中的'最后一素数的下一位置'
    const unsigned long* last = _stl_prime_list + _stl_num_primes;
    // 使用 lower_bound() 接口函数求出第一个 >=n 的素数
    const unsigned long* pos = lower_bound(first, last, n);
    // 适合作为哈希表容量的质数
    return pos == last ? *(last - 1) : *pos;
}

/*------------------任务：使用'链地址法'实现哈希表------------------*/
namespace hash_bucket {
    /*------------------任务：定义'哈希表节点的结构体模板'------------------*/
    template<class T> // 为了封装 unordered_set/unordered_map 容器这里的模板参数已经从 <class K, class V> ---> <class T>
    struct HashNode {
        // 存储的数据
        T _data;
        // 指向下一个节点的指针
        HashNode<T>* _next;

        HashNode(const T& data) : _data(data), _next(nullptr) {}
    };

    // 前置声明，因为 HTIterator 中要用到 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 {
        // 指向当前节点的指针
        HashNode<T>* _node;
        // 指向哈希表的指针 ---> 用于遍历的桶
        const HashTable<K, T, KeyOfT, Hash>* _ht;

        // 重命名'哈希表节点'的类型：HashNode<T> ---> Node
        typedef HashNode<T> Node;
        // 重命名'哈希表的迭代器'的类型：HTIterator<K,T,Ref,Ptr,SetKeyOfT,Hash> ---> Self
        typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
        // 重命名'哈希表'的类型：HashTable<K,T,KeOfT,Hash> ---> HT
        typedef HashTable<K, T, KeyOfT, Hash> HT;

        // 迭代器的构造函数
        HTIterator(Node* node, const HT* ht) : _node(node), _ht(ht) {}

        // *运算符的重载 ---> 返回数据的引用（本身）
        Ref operator*() { return _node->_data; }

        // ->运算符的重载---> 返回数据的指针（地址）
        Ptr operator->() { return &_node->_data; }

        // !=运算符的重载 ---> 用于判断两个迭代器是否指向不同节点
        bool operator!=(const Self& ht) { return _node != ht._node; }

        // ==运算符的重载 ---> 用于判断两个迭代器是否指向相同节点
        bool operator==(const Self& ht) { return _node == ht._node; }

        // 前置++运算符的重载---> 用于遍历哈希表
        Self& operator++() {
            // 情况 1：当前链表中的还有后序节点 ---> 访问下个节点
            if (_node->_next) {
                _node = _node->_next;
            }
            // 情况 2：当前链表中的所有节点都已经遍历完了 ---> 寻找下一个非空桶
            else {
                // 定义提取当前节点的键的仿函数
                KeyOfT kot;
                // 定义将键转化为 size_t 类型的仿函数
                Hash hashFunc;

                // 计算当前键对应桶索引
                size_t hash_i = hashFunc(kot(_node->_data)) % _ht->_tables.size();
                // 从当前桶的下一个位置开始线性搜索空桶的位置
                ++hash_i;
                // 使用 while 循环遍历后序的桶 ---> 直到找到非空桶或结束
                while (hash_i < _ht->_tables.size()) {
                    // 获取当桶的头节点
                    _node = _ht->_tables[hash_i];
                    // 情况 1：当前桶是非空桶 ---> 停止搜索
                    if (_node) {
                        break;
                    }
                    // 情况 2：当前桶是空桶 ---> 继续检查下一桶
                    else {
                        ++hash_i;
                    }
                }
                // 处理未找到空桶的情况 ---> 将迭代器置为 end() 的状态
                if (hash_i == _ht->_tables.size()) {
                    _node = nullptr;
                }
            }
            return *this;
        }
    };

    /*------------------任务：定义'哈希表的类模板'------------------*/
    template<class K, class T, class KeyOfT, class Hash>
    class HashTable {
    private:
        // 存储 HashNode<T>*类型数据的数组，每个元素都是桶的头指针
        vector<HashNode<T>*> _tables;
        // 记录哈希表中有效元素的变量
        size_t _n;

        typedef HashNode<T> Node;

        // 将'哈希表迭代器的类模板'声明为'哈希表类模板'的友元类
        template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
        friend struct HTIterator;

    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++) {
                Node* current = _tables[i];
                if (current) {
                    return Iterator(current, this);
                }
            }
        }

        // 获取普通迭代器的终止位置---> 用 nullptr 表示
        Iterator End() {
            return Iterator(nullptr, this);
        }

        // 获取常量迭代器的起始位置---> 找到第一个非空桶的第一个节点（只读）
        ConstIterator Begin() const {
            if (_n == 0) {
                return End();
            }
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* current = _tables[i];
                if (current) {
                    return ConstIterator(current, this);
                }
            }
        }

        // 获取常量迭代器的终止位置---> 用 nullptr 表示
        ConstIterator End() const {
            return ConstIterator(nullptr, this);
        }

        // 哈希表的构造函数
        HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

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

        // 查找操作---> 根据键查找对应的节点，找到返回节点指针，未找到返回 nullptr
        Iterator Find(const K& key) {
            KeyOfT kot;
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            Node* current = _tables[hash_i];
            while (current) {
                if (kot(current->_data) == key) {
                    return Iterator(current, this);
                }
                current = current->_next;
            }
            return End();
        }

        // 删除操作---> 根据键删除哈希表中的节点，成功返回 true，失败返回 false
        bool Erase(const K& key) {
            KeyOfT kot;
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            Node* curr = _tables[hash_i];
            Node* prev = nullptr;

            while (curr) {
                if (kot(curr->_data) == key) {
                    if (prev == nullptr) {
                        _tables[hash_i] = curr->_next;
                    } else {
                        prev->_next = curr->_next;
                    }
                    delete curr;
                    --_n;
                    return true;
                }
                prev = curr;
                curr = curr->_next;
            }
            return false;
        }

        // 插入操作---> 插入键值对，成功返回 true，键已存在返回 false
        pair<Iterator, bool> Insert(const T& data) {
            KeyOfT kot;
            Iterator it = Find(kot(data));
            if (it != End()) {
                return {it, false};
            }

            // 进行扩容判断：负载因子（元素数/桶数）等于 1 时触发扩容
            if (_n == _tables.size()) {
                vector<Node*> newVector(_tables.size() * 2);
                for (size_t i = 0; i < _tables.size(); i++) {
                    Node* current = _tables[i];
                    while (current) {
                        Node* next = current->_next;
                        Hash hashFunc;
                        size_t hash_i = hashFunc(kot(current->_data)) % newVector.size();
                        current->_next = newVector[hash_i];
                        newVector[hash_i] = current;
                        current = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newVector);
            }

            Node* newNode = new Node(data);
            Hash hashFunc;
            size_t hash_i = hashFunc(kot(data)) % _tables.size();
            newNode->_next = _tables[hash_i];
            _tables[hash_i] = newNode;
            ++_n;

            return {Iterator(newNode, this), true};
        }
    };
}

Myunordered_set.h

#pragma once
#include "HashTable.h"
namespace Myunordered_set {
    enum State { EXIST, EMPTY, DELETE };

    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        State _state = EMPTY;
    };

    template<class K, class Hash = HashFunc<K>>
    class unordered_set {
    private:
        struct SetKeyOfT {
            const K& operator()(const K& key) { return key; }
        };
        hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
    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(); }
        iterator find(const K& key) { return _ht.Find(key); }
        bool erase(const K& key) { return _ht.Erase(key); }
        pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); }
    };
}

Myunordered_map.h

#pragma once
#include "HashTable.h"
namespace Myunordered_map {
    template<class K, class V, class Hash = HashFunc<K>>
    class unordered_map {
    private:
        struct MapKeyOfT {
            const K& operator()(const pair<K, V>& kv) { return kv.first; }
        };
        hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
    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(); }
        iterator find(const K& key) { return _ht.Find(key); }
        bool erase(const K& key) { return _ht.Erase(key); }
        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;
        }
    };
}

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include "Myunordered_set.h"
#include "Myunordered_map.h"
using namespace std;

void test01() {
    cout << "=== 测试 unordered_set 基本功能 ===" << endl;
    Myunordered_set::unordered_set<int> s;
    s.insert(3); s.insert(1); s.insert(4); s.insert(1);
    s.insert(2); s.insert(5);
    cout << "遍历元素：";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    int key = 3;
    auto find_ret = s.find(key);
    if (find_ret != s.end()) {
        cout << "找到元素：" << *find_ret << endl;
    }
    key = 4;
    bool erase_ret = s.erase(key);
    if (erase_ret) {
        cout << "删除元素 " << key << " 成功" << endl;
    }
    cout << "删除后遍历：";
    for (auto val : s) {
        cout << val << " ";
    }
    cout << endl << endl;
}

void test02() {
    cout << "=== 测试 unordered_set 字符串类型 ===" << endl;
    Myunordered_set::unordered_set<string> str_set;
    str_set.insert("apple"); str_set.insert("banana"); str_set.insert("cherry");
    cout << "字符串集合元素：";
    for (const auto& str : str_set) {
        cout << str << " ";
    }
    cout << endl;
    string target = "banana";
    auto it = str_set.find(target);
    if (it != str_set.end()) {
        cout << "找到字符串：" << *it << endl;
    }
    str_set.erase("cherry");
    cout << "删除 cherry 后：";
    for (const auto& str : str_set) {
        cout << str << " ";
    }
    cout << endl << endl;
}

void test03() {
    cout << "=== 测试 unordered_map 基本功能 ===" << endl;
    Myunordered_map::unordered_map<string, int> m;
    m.insert({"apple", 10}); m.insert({"banana", 20}); m.insert({"cherry", 30});
    m["date"] = 40; m["banana"] = 25;
    cout << "遍历键值对：" << endl;
    for (auto it = m.begin(); it != m.end(); ++it) {
        cout << it->first << ": " << it->second << endl;
    }
    string key = "cherry";
    auto it = m.find(key);
    if (it != m.end()) {
        cout << "找到 " << key << ": " << it->second << endl;
    }
    key = "banana";
    bool erase_ret = m.erase(key);
    if (erase_ret) {
        cout << "删除 " << key << " 成功" << endl;
    }
    cout << "删除后 " << key << " 是否存在：" << (m.find(key) != m.end() ? "是" : "否") << endl << endl;
}

void test04() {
    cout << "=== 测试 unordered_map [] 运算符 ===" << endl;
    Myunordered_map::unordered_map<int, string> m;
    m[1]; m[2] = "two"; m[2] = "second"; m[3] = "three";
    for (auto& kv : m) {
        cout << kv.first << ": " << kv.second << endl;
    }
    cout << endl;
}

void test05() {
    cout << "=== 测试边界情况 ===" << endl;
    Myunordered_set::unordered_set<int> s_empty;
    cout << "空 set 的 begin() == end(): " << (s_empty.begin() == s_empty.end() ? "true" : "false") << endl;
    cout << "删除空 set 中的元素：" << (s_empty.erase(100) ? "成功" : "失败") << endl << endl;
    Myunordered_map::unordered_map<int, int> mp_empty;
    cout << "空 map 的 begin() == end(): " << (mp_empty.begin() == mp_empty.end() ? "true" : "false") << endl;
    cout << "访问空 map 的 []: " << mp_empty[100] << endl;
}

int main() {
    test01();
    test02();
    test03();
    test04();
    test05();
    return 0;
}

运行结果

核心逻辑解析

仿函数与键值提取

unordered_set 和 unordered_map 的模拟实现类结构要更复杂一些，但整体大框架和思路是完全类似的。由于 HashTable 是泛型实现，无法确定模板参数 T 具体是 K（像 unordered_set 的元素类型），还是 pair<K, V>（像 unordered_map 的键值对类型）。在插入操作（insert）时，需要用 K 对象转换为整数取模，以及进行 K 的相等性比较。可 pair 的 value 本就不参与取模计算而且默认比较逻辑是对 key 和 value 一起比较是否相等，但我们实际只需要比较 K 对象。所以：在 unordered_set 和 unordered_map 这一层，我们分别实现 SetKeyOfT 和 MapKeyOfT 这两个仿函数，传递给 HashTable 的 KeyOfT。之后：HashTable 就能通过 KeyOfT 仿函数，从 T 类型对象里提取出 K 对象，再完成转换为整数取模以及 K 相等性比较的操作。

迭代器设计

unordered_set 和 unordered_map 的 iterator 的实现框架，和 list 的 iterator 思路一致：用一个类型封装'结点指针'，再通过重载运算符，让迭代器能像指针一样完成访问操作。需要注意的是，哈希表的迭代器是单向迭代器（只能向后遍历，无法反向）。此外，unordered_map 的迭代器不允许修改 key，但允许修改 value。只需把 unordered_map 的键值对中'第一个参数（key）'设为 const K 即可，对应哈希表声明为：HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;。unordered_set 的迭代器不支持修改 key，只需把 unordered_set 的第二个模板参数改为 const K 即可，对应哈希表声明为：HashTable<K, const K, SetKeyOfT, Hash> _ht;。

operator++ 的设计

迭代器内部会维护一个'指向结点的指针'，operator++ 实现时，要分两种情况：如果当前桶还有后续结点，直接让指针指向下一个结点即可；如果当前桶已经遍历完毕，就需要'寻找下一个桶'。这里的关键设计是：迭代器中除了存'结点指针'，还会存'哈希表对象的指针'。这样，当当前桶遍历完时：可通过哈希表对象，结合 key 值计算当前桶位置，然后往后找'第一个不为空的桶'，就能拿到下一批结点。

begin() 和 end() 的设计

begin()：返回'第一个非空桶的第一个结点指针'构造的迭代器。end()：返回一个代表'遍历结束'的空迭代器（可用空指针等方式表示）。

map 支持 [] 运算符的重载

要让 unordered_map 支持 [] 运算符，关键在于调整 insert 相关的返回值逻辑。具体来说，需要修改 HashTable 中的 Insert 函数，使其返回值类型变为 pair<Iterator, bool>，也就是把 Insert 函数定义改为 pair<Iterator, bool> Insert(const T& data)。这样的修改，能为 unordered_map 实现 [] 运算符提供必要的返回值支撑，让插入操作的结果可以被合理利用。