C++ 哈希表封装实战：模拟实现 unordered_map 与 unordered_set

C++ 标准库参考文档

在深入源码之前，建议先查阅以下官方或社区维护的参考文档，以便快速定位接口：

• 非官方文档：cplusplus
• 官方同步文档：cppreference
• 容器参考：set、map、unordered_set、unordered_map 等均有详细 API 说明。

源码框架解析

历史背景

SGI-STL30 版本（C++11 之前）中并没有 unordered_map 和 unordered_set。这两个容器是 C++11 引入的标准特性。在此之前，STL 提供了非标准的 hash_map 和 hash_set，它们基于哈希表实现，但命名和接口并不统一。

核心结构

通过查看 SGI 源码，可以发现 hash_map 和 hash_set 的核心实现都复用了同一个 hashtable 类。其基本框架如下：

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:
    // ... 类型定义及接口 ...
};

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:
    // ... 类型定义及接口 ...
};

可以看到，hash_set 传给 hashtable 的是两个 key（Value 作为 Key），而 hash_map 传入的是 pair<const Key, Value>。这种复用机制大大减少了代码冗余。

需要注意的是，早期 STL 源码的命名风格较为混乱，例如 hash_set 使用 Value 作为模板参数名，而 hash_map 使用 Key 和 T。我们在模拟实现时，会采用更规范的命名风格。

模拟实现思路

1. 复用哈希表框架

我们基于之前实现的通用哈希表 HashTable 进行封装。为了适配不同的容器需求，我们需要调整模板参数：

• unordered_set：存储单一值，Key 即 Value。
• unordered_map：存储键值对，Key 为 K，Value 为 V。

由于 HashTable 内部泛型未知具体是 K 还是 pair<K,V>，在插入时需要提取 Key 进行哈希计算和比较。为此，我们引入仿函数 KeyOfT：

• SetKeyOfT：直接返回传入的对象本身。
• MapKeyOfT：从 pair<K,V> 中提取 first 成员。

这样，HashTable 只需调用 KeyOfT::operator() 即可获取用于哈希计算的 Key。

2. 迭代器实现

哈希表的迭代器属于单向迭代器。难点在于 operator++ 的实现：

• 如果当前桶内还有节点，直接指向下一个节点。
• 如果当前桶已遍历完，需要找到下一个不为空的桶。这要求迭代器持有哈希表对象的指针，以便访问桶数组并计算下一个位置。

此外，begin() 应返回第一个非空桶的第一个节点，end() 则用空指针表示结束。

对于 unordered_set，迭代器不应支持修改元素，因此模板参数中的 Value 类型设为 const K。 对于 unordered_map，Key 不可修改但 Value 可修改，因此传入 HashTable 的类型为 pair<const K, V>。

3. operator[] 的支持

unordered_map 的 operator[] 需要支持查找和插入。底层依赖 insert 方法，若 Key 不存在则插入默认构造的 Value 并返回引用。因此，insert 需返回 pair<Iterator, bool> 以指示插入是否成功。

完整代码示例

以下是完整的实现代码，包含哈希表基类、unordered_set 封装及 unordered_map 封装。

HashTable.h

#pragma once
#include<vector>
#include<algorithm>
#include<string>

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;
    const unsigned long* pos = std::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;
    }
};

template<>
struct HashFunc<std::string> {
    size_t operator()(const std::string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash += ch;
            hash *= 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 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()) {
                    _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>
    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;
            if (auto it = Find(kot(data)); it != End()) return { it, false };

            Hash hs;
            // 负载因子 == 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;
    };
}

unordered_set.h

#pragma once
#include"HashTable.h"

namespace jqj {
    template<class K, class Hash = HashFunc<K>>
    class unordered_set {
        struct SetKeyOfT {
            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;
    };
}

unordered_map.h

#pragma once
#include"HashTable.h"

namespace jqj {
    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_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 = _ht.Insert(make_pair(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;
    };
}

Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
using namespace std;
#include"unordered_map.h"
#include"unordered_set.h"

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

int main() {
    jqj::unordered_set<int> us;
    us.insert(3);
    us.insert(1000);
    us.insert(2);
    us.insert(102);
    us.insert(2111);
    us.insert(22);

    auto it = us.begin();
    while (it != us.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    Print(us);

    jqj::unordered_map<string, string> dict;
    dict.insert({ "string","" });
    dict.insert({ "left","左边" });
    dict.insert({ "right","右边" });

    dict["left"] = "左边";
    dict["map"] = "地图";

    for (auto& [k, v] : dict) {
        cout << k << ":" << v << endl;
    }
    return 0;
}

总结

通过复用通用的哈希表结构，我们可以高效地实现 unordered_map 和 unordered_set。关键在于设计好 KeyOfT 仿函数来处理不同类型的 Key 提取，以及正确实现迭代器的 operator++ 逻辑以支持跨桶遍历。这种封装方式既保持了代码的复用性，又符合 C++ 标准库的设计哲学。